تقسيم أعداد كبيرة

Question

وانا بحاجة الى بعض خوارزمية التقسيم التي يمكن التعامل مع الأعداد الصحيحة الكبيرة (128 بت). لقد طلبت بالفعل كيفية القيام بذلك عن طريق مشغلي قليلا التحول. ومع ذلك، يبدو أن تنفيذ بلدي الحالي لطلب النهج الأفضل

والأساس، وأنا تخزين أرقام عن اثنين من long long unsigned int في شكل

وA * 2 ^ 64 + B مع B < 2 ^ 64.

وهذا العدد يقبل القسمة على 24 وأريد أن نقسمه 24.

ونهج بلدي الحالي هو تحويلها مثل

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

ولكن، وهذا هو عربات التي تجرها الدواب.

و(لاحظ أن الكلمة هي A / 24 وأن mod هو A % 24. يتم تخزين الانقسامات الطبيعية في long double، يتم تخزين الأعداد الصحيحة في long long unsigned int.

ومنذ 24 تساوي 11000 في ثنائي، ينبغي أن summand الثاني لم يتغير شيء في نطاق summand الرابعة منذ يتم إزاحة أنه 64 بت إلى اليسار.

وهكذا، إذا كان A * 2 ^ 64 + B هو القسمة على 24، وB ليس، فإنه يظهر بسهولة أن البق لأنه يعود بعض رقم غير متكاملة.

ما هو الخطأ في تنفيذ بلدي؟

Answer 1

وأسهل طريقة يمكنني أن أفكر للقيام بذلك هي لعلاج الأرقام 128 بت إلى أربعة أرقام 32 بت:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

وبعد ذلك القيام القسمة المطولة التي كتبها 24:

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

وأين X_Y يعني X*2^32 + Y. ثم يتم E_F_G_H الجواب مع T الباقي. في أي لحظة ما عليك سوى تقسيم أرقام 64 بت، لذلك ينبغي أن يكون هذا قابل للتحقيق مع عمليات صحيحا فقط.

Answer 2

وهذا يمكن ربما يمكن حلها مع الضرب معكوس؟ أول شيء هو أن نلاحظ أن 24 == 8 * 3 ذلك نتيجة

a / 24 == (a >> 3) / 3

واسمحوا x = (a >> 3) ثم نتيجة للتقسيم هي 8 * (x / 3). الآن يبقى للعثور على قيمة x / 3.

وينص الحساب وحدات أنه يوجد عدد من n بحيث n * 3 == 1 (mod 2^128). وهذا يعطي:

x / 3 = (x * n) / (n * 3) = x * n

ويبقى للعثور على n ثابت. هناك شرحا عن كيفية القيام بذلك على ويكيبيديا . سيكون لديك أيضا لتنفيذ وظائف لمضاعفة الأرقام إلى 128 بت.

وآمل أن يساعد هذا.

و/A.B.

Answer 3

ويجب أن لا يكون باستخدام long double لبك "الانقسامات طبيعية" ولكن الأعداد الصحيحة هناك أيضا. long double ليس لديها ما يكفي من الشخصيات الهامة للحصول على الجواب الحق (وعلى أي حال بيت القصيد هو أن تفعل هذا مع عمليات صحيح، صحيح؟).

Answer 4

<اقتباس فقرة>   

ومنذ 24 يساوي 11000 في ثنائي، ينبغي أن summand الثاني لم يتغير شيء في نطاق summand الرابعة منذ يتم إزاحة أنه 64 بت إلى اليسار.

وهو مكتوب صيغة الخاص بك في الأعداد الحقيقية. (A وزارة الدفاع 24) / 24 يمكن أن يكون لها عدد التعسفي من الكسور العشرية (24/1 هو على سبيل المثال 0.041666666 ...)، وبالتالي يمكن أن تتداخل مع فترة رابعة في التحلل، حتى تضاعفت مرة واحدة 2 ^ 64.

والخاصية التي Y * 2 ^ 64 لا تتداخل مع الأرقام الثنائية انخفاض الوزن في إضافة يعمل فقط عندما Y هو عدد صحيح.

Answer 5

لا.

والذهاب الاستيلاء على مكتبة للقيام بذلك الاشياء - عليك أن تكون شاكرا بشكل لا يصدق اخترت عند تصحيح أخطاء غريبة

وSnippets.org كان C / C ++ مكتبة BIGINT في الموقع انها منذ فترة من الوقت، تحولت جوجل أيضا ما يلي: http://mattmccutchen.net/bigint/