خوارزمية الصنبور

خوارزمية الصنبور هي خوارزمية لحساب قيمة عدد متسامٍ (مثل π أو e ) تُولّد أرقام العدد بالتسلسل من اليسار إلى اليمين، مما يوفر دقة متزايدة مع تقدم الخوارزمية. تهدف خوارزميات الصنبور أيضًا إلى تقليل حجم التخزين الوسيط المطلوب. يُشتق الاسم من معنى كلمة "صنبور" التي تُشير إلى صنبور أو صمام يتحكم في تدفق السائل. يمكن مقارنة خوارزميات الصنبور بالخوارزميات التي تخزن وتعالج الأعداد الكاملة لإنتاج تقريبات أكثر دقة تدريجيًا للعدد المتسامي المطلوب.

ازداد الاهتمام بخوارزميات الصنبور في بدايات الرياضيات الحاسوبية نتيجةً للقيود الشديدة على الذاكرة، وقد ظهرت خوارزمية لحساب أرقام العدد e في ورقة بحثية لسيل عام 1968. ^{[ 1 ]} وفي عام 1970، قدم عبدلي خوارزمية أكثر عمومية لحساب مجاميع المتسلسلات التي يمكن فيها التعبير عن نسب الحدود المتتالية كناتج قسمة دوال صحيحة لمواقع الحدود. هذه الخوارزمية قابلة للتطبيق على العديد من المتسلسلات المألوفة للدوال المثلثية واللوغاريتمات والأعداد المتسامية لأن هذه المتسلسلات تحقق الشرط المذكور أعلاه. ^{[ 2 ]} ويبدو أن مصطلح "خوارزمية الصنبور" قد صاغه ستانلي رابينوفيتز وستان واجن ، حيث تُعرف خوارزميتهما لحساب أرقام π أحيانًا باسم " خوارزمية الصنبور لـ π ". ^{[ 3 ]}

خوارزمية رابينوفيتز وواغون المحدودة هي خوارزمية ذات حدّ ، بمعنى أنه يجب تحديد عدد حدود المتسلسلة اللانهائية التي ستُعالَج مسبقًا. يشير مصطلح " خوارزمية التدفق " ^{[ 4 ]} إلى منهج لا يفرض هذا القيد. يسمح هذا بتشغيل الحساب بشكل مستمر مع تغيير مقدار التخزين الوسيط أثناء تقدم الحساب.

يستخدم أحد أشكال أسلوب الصنبور خوارزميةً لحساب رقم واحد عشوائي من العدد المتسامي دون حساب الأرقام السابقة: ومن الأمثلة على ذلك صيغة بيلي-بورواين-بلوف ، وهي خوارزمية لاستخراج الأرقام من π تُنتج أرقامًا بالأساس 16. ويعني الاقتطاع الحتمي للمتسلسلة اللانهائية الأساسية للخوارزمية أن دقة النتيجة قد تكون محدودة بعدد الحدود المحسوبة.

يوضح هذا المثال آلية عمل خوارزمية الصنبور من خلال حساب الأرقام الثنائية للوغاريتم الطبيعي للعدد 2 (التسلسل A068426 في OEIS ) باستخدام المتطابقة

${\displaystyle \ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

للبدء في حساب الأرقام الثنائية من، على سبيل المثال، الخانة الثامنة، نضرب هذه الوحدة في 2 ⁷ (لأن 7 =  8  −  1):

${\displaystyle 2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

ثم نقسم المجموع اللانهائي إلى "رأس"، حيث تكون أسس العدد 2 أكبر من أو تساوي الصفر، و"ذيل"، حيث تكون أسس العدد 2 سالبة:

${\displaystyle 2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.}$

نحن مهتمون فقط بالجزء الكسري من هذه القيمة، لذلك يمكننا استبدال كل حد من الحدود في "الرأس" بـ

${\displaystyle {\frac {2^{7-k}}{k}}{\bmod {1}}={\frac {2^{7-k}{\bmod {k}}}{k}}\,.}$

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

ك	أ = 2 7− ك	ب = أ mod ك	ج = ب / ك​​	مجموع C mod 1
1	64	0	0	0
2	32	0	0	0
3	16	1	١/٣​​​​	١/٣​​​​
4	8	0	0	١/٣​​​​
5	4	4	٤ / ٥​​	2 / 15​​
6	2	2	١/٣​​​​	7 / 15​​
7	1	1	1 / 7​​	64 / 105​​

نضيف بعض الحدود في "الذيل"، مع ملاحظة أن الخطأ الناتج عن اقتطاع المجموع أقل من الحد الأخير:

ك	D = 1 / k 2 k −7​​	مجموع D	أقصى خطأ
8	1 / 16​​	1 / 16​​	1 / 16​​
9	1 / 36​​	13 / 144​​	1 / 36​​
10	1 / 80​​	37 / 360​​	1 / 80​​

بجمع "الرأس" والحدود القليلة الأولى من "الذيل" معًا نحصل على:

${\displaystyle 2^{7}\ln(2){\bmod {1}}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}\,,}$

إذن، الأرقام الثنائية من الثامن إلى الحادي عشر في التمثيل الثنائي لـ ln(2) هي 1، 0، 1، 1. لاحظ أننا لم نحسب قيم الأرقام الثنائية السبعة الأولى - في الواقع، تم تجاهل جميع المعلومات المتعلقة بها عمدًا باستخدام الحساب النمطي في مجموع "الرأس".

يمكن استخدام نفس الأسلوب لحساب أرقام التمثيل الثنائي للوغاريتم الطبيعي للعدد 2 (ln(2)) بدءًا من أي موضع n . يزداد عدد الحدود في مجموع "الرأس" خطيًا مع n ، لكن تعقيد كل حد لا يزداد إلا مع لوغاريتم n إذا استُخدمت طريقة فعالة للأس المعياري . دقة الحسابات والنتائج الوسيطة وعدد الحدود المأخوذة من مجموع "الذيل" مستقلة عن n ، وتعتمد فقط على عدد الأرقام الثنائية التي يتم حسابها - يمكن استخدام الحساب أحادي الدقة لحساب حوالي 12 رقمًا ثنائيًا، بغض النظر عن موضع البداية.

• أرندت، يورج. هينيل، كريستوف، π العنان ، سبرينغر فيرلاج، 2000.
• وايسستين، إريك دبليو. “خوارزمية الحنفية” . عالم الرياضيات .