ما هي أسرع طريقة لتقسيم عدد صحيح بنسبة 3?

Question

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Answer 1

هذا هو الأسرع حيث سيقوم برنامج التحويل البرمجي بتحسينه إذا كان بإمكانه اعتمادًا على معالج الإخراج.

int a;
int b;

a = some value;
b = a / 3;

Answer 2

كان الرجل الذي قال "اترك الأمر إلى المترجم" على حق ، لكن ليس لدي "السمعة" لتعديله أو التعليق. طلبت من GCC تجميع اختبار int (int a) {return a / 3 ؛ } لـ IX86 ثم تفكيك الإخراج. فقط من أجل الاهتمام الأكاديمي ، ما تفعله بقسوة اضرب على 0x55555556 ثم أخذ أعلى 32 بت من النتيجة 64 بت من ذلك. يمكنك إظهار هذا لنفسك على سبيل المثال:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$ 

صفحة ويكيبيديا على قسم مونتغمري من الصعب القراءة ، لكن لحسن الحظ ، قام اللاعبون المترجمون بذلك حتى لا يضطرون إلى ذلك.

Answer 3

هناك أسرع طريقة للقيام بذلك إذا كنت تعرف نطاقات القيم ، على سبيل المثال ، إذا كنت تقسيم صحيح وقعت قبل 3 و تعرف على مجموعة من القيمة تقسم 0 إلى 768, ثم يمكنك مضاعفة من قبل عامل التحول إلى اليسار من قبل قوة من 2 إلى أن عامل مقسوما على 3.

على سبيل المثال.

مجموعة 0 -> 768

هل يمكن استخدام تحويل 10 بت التي ضرب 1024 ، تريد القسمة على 3 إذا مضاعف الخاص بك ينبغي أن تكون 1024 / 3 = 341,

بحيث يمكنك الآن استخدام (x * 341) >> 10
(تأكد من التحول هو وقع التحول في حالة استخدام وقعت الصحيحه), أيضا تأكد من التحول هو تغيير الواقع وليس قليلا لفة

هذا سيكون فعالا في تقسيم القيمة 3 ، سيتم تشغيل حوالي 1.6 مرات من السرعة الطبيعية القسمة على 3 على مستوى x86 / x64 CPU.

بالطبع السبب الوحيد الذي يمكن أن يجعل هذا التحسين عند المترجم غير قادر لأن المترجم لا يعرف أقصى مدى من X و بالتالي لا يمكن اتخاذ هذا القرار ، ولكن أنت كما يمكن للمبرمج.

في وقت ما حتى أنه قد يكون أكثر فائدة الانتقال من قيمة إلى قيمة أكبر ثم تفعل نفس الشيء ، أي.إذا كان لديك الباحث من مجموعة كاملة يمكن أن تجعل من قيمة 64 بت ومن ثم القيام التكاثر والتحول بدلا من القسمة على 3.

كان علي أن أفعل هذا في الآونة الأخيرة إلى تسريع معالجة الصور, كنت بحاجة إلى العثور على متوسط من 3 لون قنوات كل قناة لون مع بايت المدى (0 - 255).الأحمر والأخضر والأزرق.

في البداية أنا فقط ببساطة المستخدمة:

avg = (r + g + b) / 3;

(لذلك r + g + b لديه الحد الأقصى من 768 والحد الأدنى من 0 ، لأن كل قناة هو بايت 0 - 255)

بعد الملايين من تكرار العملية برمتها أخذت 36 ميلي ثانية.

لقد غيرت الخط:

avg = (r + g + b) * 341 >> 10;

و التي أخذت عليه إلى 22 ميلي ثانية, مدهش ما يمكن القيام به مع القليل من الإبداع.

هذه السرعة حتى وقعت في C# حتى ولو كان أمثلية تشغيل و تم تشغيل البرنامج أصلا دون التصحيح معلومات و ليس IDE.

Answer 4

نرى كيف تقسم على 3 للاطلاع على مناقشة ممتدة حول تقسيمها بشكل أكثر كفاءة على 3 ، ركز على القيام بعمليات الحساب FPGA.

ذات صلة أيضا:

• تحسين أقسام عدد صحيح مع تحول مضاعف في C#

Answer 5

اعتمادًا على النظام الأساسي الخاص بك واعتمادًا على برنامج التحويل البرمجي C ، وهو حل أصلي مثل الاستخدام فقط

y = x / 3

يمكن أن تكون سريعة أو يمكن أن تكون بطيئة للغاية (حتى لو تم الانقسام بالكامل في الأجهزة ، إذا تم القيام به باستخدام تعليمات DIV ، فإن هذه التعليمات أبطأ حوالي 3 إلى 4 مرات من الضرب على وحدات المعالجة المركزية الحديثة). قد تعمل هذه العملية على تحسين هذه العملية ، ولكن إذا كنت تريد أن تكون متأكدًا ، فمن الأفضل تحسينها بنفسك.

من أجل التحسين ، من المهم أن يكون لديك عدد صحيح من الحجم المعروف. في C int لا يوجد حجم معروف (يمكن أن يختلف حسب النظام الأساسي والمترجم!) ، لذلك من الأفضل استخدام أعداد صحيحة بحجم C99. يفترض الرمز أدناه أنك تريد تقسيم عدد صحيح 32 بت غير موقّع على ثلاثة وأنك برنامج التحويل البرمجي C يعرف حوالي 64 بت عدد صحيح (ملاحظة: حتى في بنية وحدة المعالجة المركزية 32 بت ، يمكن لمعظم المترجمين C التعامل مع 64 بت الأعداد الصحيحة على ما يرام):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

على الرغم من أن هذا قد يبدو مجنونًا ، لكن الطريقة المذكورة أعلاه تنقسم بالفعل على 3. كل ما تحتاجه للقيام بذلك هو تكاثر 64 بت واحد (كما قلت ، قد تكون الضربات أسرع من 3 إلى 4 مرات من الأقسام في وحدة المعالجة المركزية الخاصة بك ). في تطبيق 64 بت ، سيكون هذا الرمز أسرع بكثير مما كان عليه في تطبيق 32 بت (في تطبيق 32 بت مضاعفة رقم 64 بت تأخذ 3 مضاعفات و 3 إضافات على قيم 32 بت) - ومع ذلك ، قد لا يزال أسرع من أ تقسيم على آلة 32 بت.

من ناحية أخرى ، إذا كان المترجم الخاص بك جيدًا جدًا ويعرف الخدعة كيفية تحسين قسم عدد صحيح من خلال ثابت (آخر GCC ، لقد راجعت للتو) ، فسيقوم بإنشاء الرمز أعلاه على أي حال (ستقوم GCC بإنشاء هذا الرمز بالضبط لـ "/3" إذا قمت بتمكين مستوى التحسين على الأقل). بالنسبة للمجموعات المترجمين الآخرين ... لا يمكنك الاعتماد أو توقع استخدام الحيل من هذا القبيل ، على الرغم من أن هذه الطريقة موثقة جيدًا وذكرها في كل مكان على الإنترنت.

المشكلة هي أنها تعمل فقط للأرقام الثابتة ، وليس للأرقام المتغيرة. تحتاج دائمًا إلى معرفة الرقم السحري (هنا 0xaaaaaaab) والعمليات الصحيحة بعد الضرب (التحولات و/أو الإضافات في معظم الحالات) وكلاهما مختلف اعتمادًا على الرقم الذي تريد تقسيمه ويأخذ كلاهما وقتًا كبيرًا في وحدة المعالجة المركزية احسبها على الطيران (سيكون ذلك أبطأ من قسم الأجهزة). ومع ذلك ، من السهل على المترجم حسابها خلال وقت الترجمة (حيث يلعب وقت ترجمة أكثر أو أقل في دور لا يكاد دور).

Answer 6

ماذا لو أنك حقًا لا تريد الضرب أو الانقسام؟ هنا هو تقريب أنا اخترعته للتو. إنه يعمل لأن (x/3) = (x/4) + (x/12). ولكن نظرًا لأن (x/12) = (x/4)/3 ، علينا فقط أن نكرر العملية حتى تكون جيدة بما يكفي.

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

والنتيجة هي 330. يمكن جعلها أكثر دقة باستخدام B = ((B+2) >> 2) ؛ لحساب التقريب.

اذا أنت نكون المسموح له بالضرب ، ما عليك سوى اختيار تقريب مناسب لـ (1/3) ، مع مقسوم قوة 2. على سبيل المثال ، n * (1/3) ~ = n * 43 /128 = (n * 43) >> 7.

هذه التقنية مفيدة للغاية في إنديانا.

Answer 7

لا أعرف ما إذا كان الأمر أسرع ولكن إذا كنت ترغب في استخدام مشغل bitwise لأداء القسم الثنائي ، يمكنك استخدام طريقة التحول والطرح الموصوفة في هذه الصفحة:

• اضبط الحاصل على 0
• محاذاة أقصى اليسار في توزيعات الأرباح والقسمة
• يكرر:
  • إذا كان هذا الجزء من الأرباح فوق المقسوم أكبر من أو يساوي المقسوم:
    • ثم طرح المقسوم من هذا الجزء من الأرباح و
    • متسلسل 1 إلى نهاية اليد اليمنى من الحاصل
    • آخر متسلسل 0 إلى نهاية اليد اليمنى من الحاصل
  • قم بتحويل المقسوم مكانًا واحدًا صحيحًا
• حتى يكون توزيعات الأرباح أقل من المقسوم:
• الحاصل صحيح ، توزيعات الأرباح الباقية
• قف

Answer 8

لأرقام 64 بت:

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

ومع ذلك ، فإن هذا ليس تقسيم عدد صحيح مقطوع قد تتوقعه. إنه يعمل بشكل صحيح إذا كان الرقم قابلاً للقسمة بالفعل على 3 ، لكنه يعيد رقمًا كبيرًا إذا لم يكن كذلك.

على سبيل المثال ، إذا قمت بتشغيله على سبيل المثال 11 ، فإنه يعيد 6148914691236517209. هذا يبدو وكأنه قمامة ولكن في الواقع الإجابة الصحيحة: اضربها بمقدار 3 وستعود إلى 11!

إذا كنت تبحث عن التقسيم المقتطع ، فما عليك سوى استخدام / المشغل. أشك بشدة في أنه يمكنك الحصول على أسرع من ذلك بكثير.

نظرية:

64 بت الحساب غير موقّع هو modulo 2^64 الحساب. هذا يعني بالنسبة لكل عدد صحيح وهو coprime مع معامل 2^64 (جميع الأرقام الفردية بشكل أساسي) يوجد معكوس مضاعف يمكنك استخدامه للضرب بدلاً من التقسيم. يمكن الحصول على هذا الرقم السحري عن طريق حل 3*x + 2^64*y = 1 المعادلة باستخدام خوارزمية إقليدية ممتدة.

Answer 9

إذا كنت تريد حقًا رؤية هذه المقالة تقسيم صحيح, ، ولكن لديها فقط ميزة أكاديمية ... سيكون تطبيقًا مثيرًا للاهتمام يحتاج فعليًا إلى أداء يستفيد من هذا النوع من الخدعة.

Answer 10

بالنسبة لقسم عدد صحيح كبير حقًا (على سبيل المثال ، أرقام أكبر من 64 بت) يمكنك تمثيل رقمك كقسم int [] وأداء التقسيم بسرعة كبيرة عن طريق أخذ رقمين في وقت واحد وتقسيمهما على 3. سيكون الباقي جزءًا من الرقمين التاليين وهكذا دواليك.

على سبيل المثال. 11004 /3 تقول

11/3 = 3 ، بقي = 2 (من 11-3*3)

20/3 = 6 ، الباقي = 2 (من 20-6*3)

20/3 = 6 ، الباقي = 2 (من 20-6*3)

24/3 = 8 ، الباقي = 0

وبالتالي النتيجة 3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  for (int i = 0; i < a.Length; i++)
  {
    var val = remainder + a[i];
    var div = val/3;

    remainder = 10*(val%3);
    if (div > 9)
    {
      res.Add(div/10);
      res.Add(div%10);
    }
    else
      res.Add(div);
  }
  if (res[0] == 0) res.RemoveAt(0);
  return res;
}

Answer 11

حساب سهل ... في معظم التكرارات n هو عدد البتات الخاصة بك:

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}

Answer 12

سيكون نهج جدول البحث أسرع أيضًا في بعض البنى.

uint8_t DivBy3LU(uint8_t u8Operand)
{
   uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];

   return ai8Div3[u8Operand];
}