الضرب السريع

Question

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

لقد قمت بإنشاء مصفوفة عائمة تحتوي على أعضاء مثل 0، 1، 0.5، 0.3333 وما إلى ذلك.لكنني أعتقد أن هناك ثوابت MAGIC (مثل 0x55555556) للأرقام باستثناء (1/3).

ما هي هذه الأرقام؟

Answer 1

إذا التعليمات تقسيم على متحكم الخاص بك هو سريع بما فيه الكفاية، واستخدام ذلك. إذا كنت في حاجة إلى الجزء الكسري من النتيجة، قد تكون قادرا على استخدام ما تبقى. في معظم أبنية، تعليمات تقسيم يضع حاصل في سجل واحد والباقي في بلد آخر.

إذا تعليمات تقسيم ليست سريعة بما يكفي ولكن تعليمات الضرب هو، يمكنك استخدام تقنية التالية (وهذا يبدو كما لو كان هذا هو أسلوب كنت بعد). في معظم أبنية، بضرب عدد 32 بت من النتائج عدد 32 بت آخر في نتيجة 64-بت؛ يتم تخزين نصف أكثر أهمية في سجل واحد ويتم تخزين نصف أقل أهمية في الآخر. يمكنك استغلال ذلك من خلال إدراك أن القسمة على عدد من ن هو نفسه ضرب من قبل (2 ^ 32) / ن، ثم أخذ 32 بت أكثر أهمية من النتيجة. وبعبارة أخرى، إذا كنت ترغب في القسمة على 3، يمكنك مضاعفة بدلا من 0x100000000 / 3 = 0x55555555، ثم يأخذ 32 بت أكثر أهمية من النتيجة.

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

Answer 2

ويمكن استبدال تقسيم عدد صحيح بواسطة ثابت عدد صحيح مع مجموعة من تحول والضرب. انظر هذا التحسين دليل للحصول على مزيد من التفاصيل. من cource هذا مفيد إذا كان actully أسرع على رقاقة من الفائدة.

Answer 3

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

البداية الجيدة هي القسمة على 2 و4 و8.يمكن القيام بذلك من خلال التحولات الصحيحة بمقدار 1 و 2 و 3 بت على التوالي، على افتراض أن وحدة المعالجة المركزية الخاصة بك لديها تعليمات منطقية للتحول إلى اليمين.

ثانيًا، القسمة على 1 هي مجرد إبقاء الرقم كما هو.هذا يترك فقط 3 و5 و6 و7 و9.

الشيء الصعب يبدأ هنا:

بالنسبة للأرقام الأخرى، يمكنك استخدام حقيقة أنه يمكن استبدال القسمة بالضرب والتحويل.

لنفترض أن لديك معالج 16 بت.للقسمة على N، عليك الضرب بـ 256/N والتحويل إلى اليمين 8 بتات:

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

خذ المثال العشوائي 72 / 5.اضرب 72 في 51 لتحصل على 3672 ثم انقله لليمين 8 بت لتحصل على 14.

لكي ينجح هذا الأمر، يجب ألا تتجاوز أرقامك التي تستخدمها الـ 16 بت.نظرًا لأن أسوأ حالة لديك هي الضرب في 85، فيمكنك التعامل مع الأرقام حتى 771.

السبب وراء نجاح ذلك هو أن التحول إلى اليمين بمقدار 8 بتات هو نفس القسمة على 256، و:

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

إذا كان لديك معالج 32 بت، فإن القيم والنطاقات تتغير إلى حد ما، نظرًا لأنه 65536/N:

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

مرة أخرى، لنختار الرقم العشوائي 20,000/7:20,000 مضروبًا في 9,363 يساوي 187,260,000، وعندما تقوم بإزاحة 16 بت إلى اليمين، تحصل على 2,857 - النتيجة الحقيقية هي 2,857.

يُظهر برنامج الاختبار التالي في لغة C أرقام الدقة للقيم المعطاة.إنه يستخدم قيمًا موقعة، لذا فهو جيد فقط حتى حوالي 98000 ولكن يمكنك أن ترى أن أكبر خطأ هو 1 وأنه يحدث عند النقطة المنخفضة البالغة 13110 (خطأ 0.008٪ فقط).

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

هذه المخرجات:

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1