مطلوب دقة العمل لخوارزمية BBP؟

Question

أنا أتطلع لحساب نرقم T من PI في بيئة ذاكرة منخفضة. بما أنني لا أملك العشرية المتاحة لي ، فهذا خوارزمية BBP عدد صحيح فقط في بيثون لقد كانت نقطة انطلاق رائعة. أنا فقط بحاجة إلى حساب رقم واحد من PI في وقت واحد. كيف يمكنني تحديد أقل ما يمكنني تعيينه ، "عدد أرقام دقة العمل"؟

D = 4 يعطيني العديد من الأرقام الصحيحة ، ولكن سيتم إيقاف عدد قليل من الأرقام. على سبيل المثال ، يعطيني رقم الحوسبة 393 بدقة 4 0xafda ، والتي أقوم بها استخراج الرقم 0xA. ومع ذلك ، فإن الرقم الصحيح هو 0xB.

بغض النظر عن مدى ارتفاع D ، يبدو أن اختبار عدد كاف من الأرقام يجد واحدة حيث تقوم الصيغة بإرجاع قيمة غير صحيحة.

لقد حاولت زيادة الدقة عندما يكون الرقم "قريب" من آخر ، على سبيل المثال 0x3FFF أو 0x1000 ، ولكن لا يمكن العثور على أي تعريف جيد لـ "Close" ؛ على سبيل المثال ، الحساب في الرقم 9798 يعطيني 0xجDE6 ، وهو ليس قريبًا جدًا من 0xD000 ، ولكن الرقم الصحيح هو 0xD.

هل يمكن لأي شخص مساعدتي في معرفة مقدار دقة العمل اللازمة لحساب رقم معين باستخدام هذه الخوارزمية؟

شكرًا لك،

تعديل
كمرجع:

precision (D)   first wrong digit
-------------   ------------------
3               27
4               161
5               733
6               4329
7               21139
8+              ???

لاحظ أنني أحسب رقمًا واحدًا في وقت واحد ، على سبيل المثال:

for i in range(1,n):
    D = 3 # or whatever precision I'm testing
    digit = pi(i) # extracts most significant digit from integer-only BBP result
    if( digit != HARDCODED_PI[i] ):
        print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i]) )

Answer 1

بغض النظر عن مدى ارتفاع D ، يبدو أن اختبار عدد كاف من الأرقام يجد واحدة حيث تقوم الصيغة بإرجاع قيمة غير صحيحة.

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

من الصعب تحديد التكرار غير المحدود مع الاستراحة عندما لا يتغير الرقم الحد الأدنى الدقة المطلوبة لعدد معين من الأرقام.

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

تحرير: لكي تكون أكثر دقة ، تتضمن الخوارزمية حلقة - من 0..N ، حيث N هو الرقم الذي يجب حسابه. كل تكرار من الحلقة سوف يقدم كمية معينة من الخطأ. بعد حلق عدد كافٍ من المرات ، سوف يتعدى الخطأ إلى أهم أرقام تقوم بحسابه ، وبالتالي ستكون النتيجة خاطئة.

تستخدم مقالة ويكيبيديا 14 رقمًا من الدقة ، وهذا يكفي لحساب 10 ** 8 أرقام بشكل صحيح. كما أظهرت ، يؤدي عدد أقل من الأرقام الدقيقة إلى حدوث أخطاء في وقت سابق ، حيث أن هناك دقة أقل ويصبح الخطأ مرئيًا مع عدد أقل من التكرارات. النتيجة الصافية هي أن قيمة N التي يمكننا حساب رقم بشكل صحيح تصبح أقل مع عدد أقل من الأرقام من الدقة.

إذا كان لديك D Hex Sigits من الدقة ، فهذا D*4 بت. مع كل تكرار ، يتم تقديم خطأ قدره 0.5bits في البت الأقل أهمية ، لذلك مع تكرارين هناك فرصة لخطأ LSB. أثناء التجميع ، تتم إضافة هذه الأخطاء ، وبالتالي تتراكم. إذا وصل عدد الأخطاء المجمعة إلى LSB في أهم أرقام ، فإن الرقم الواحد الذي تستخرجه سيكون خاطئًا. تقريبا ، هذا هو عندما n> 2 ** (d-0.75). (صحيح لبعض قاعدة لوغاريتمية.)

استخلاص بياناتك تجريبياً ، يبدو أن الملاءمة التقريبية هي n = ~ (2 ** (2.05*d)) ، على الرغم من وجود عدد قليل من نقاط البيانات ، لذا قد لا يكون هذا تنبؤًا دقيقًا.

خوارزمية BBP التي اخترتها هي تكرارية ، وبالتالي فإنها تستغرق وقتًا أطول تدريجياً لحساب الأرقام في التسلسل. لحساب الأرقام 0..n ، سوف تأخذ O(n^2) خطوات.

تعطي مقالة ويكيبيديا صيغة لحساب الرقم n'th الذي لا يتطلب التكرار ، فقط الأسعار والأرقام العقلانية. لن يعاني هذا من نفس فقدان الدقة مثل الخوارزمية التكرارية ويمكنك حساب أي رقم من PI حسب الحاجة في الوقت المستمر (أو في أسوأ الأحوال لوغاريتمي ، اعتمادًا على تنفيذ الأسس مع المعامل) ، وبالتالي الحوسبة n سوف تأخذ الأرقام O(n) الوقت ربما o (n log n).