تقسيم ثنائي

في الرياضيات ، يُعدّ التقسيم الثنائي أسلوبًا لتسريع التقييم العددي لأنواع عديدة من المتسلسلات ذات الحدود النسبية. وعلى وجه الخصوص، يمكن استخدامه لتقييم المتسلسلات فوق الهندسية عند النقاط النسبية.

بالنظر إلى سلسلة

${\displaystyle S(a,b)=\sum _{n=a}^{b}{\frac {p_{n}}{q_{n}}}}$

حيث أن p و _n عددان صحيحان _، فإن الهدف من تقسيم النظام الثنائي هو حساب العددين الصحيحين P ( a , b ) و Q ( a , b ) بحيث

${\displaystyle S(a,b)={\frac {P(a,b)}{Q(a,b)}}.}$

تتضمن عملية التقسيم تحديد m = [( a  + b )/2] وحساب P ( a , b ) و Q ( a , b ) بشكل متكرر من P ( a , m ) و P ( m , b ) و Q ( a , m ) و Q ( m , b ). عندما تكون قيمتا a و b متقاربتين بدرجة كافية، يمكن حساب P ( a , b ) و Q ( a , b ) مباشرةً من p _{_a} ...p_{_b} و q_{_a} ...q _{_b} . 

يتطلب تقسيم الأعداد الثنائية ذاكرة أكبر من الجمع المباشر لكل حد على حدة، ولكنه أسرع تقاربياً لأن أحجام جميع نواتج الضرب الفرعية الناتجة تقل. إضافةً إلى ذلك، بينما تستخدم أبسط طريقة لتقييم المتسلسلة الكسرية قسمة كاملة الدقة لكل حد في المتسلسلة، فإن تقسيم الأعداد الثنائية لا يتطلب سوى قسمة نهائية واحدة بالدقة المستهدفة؛ وهذا ليس أسرع فحسب، بل يُزيل أخطاء التقريب بشكل ملائم. للاستفادة الكاملة من هذه الطريقة، يجب استخدام تقنيات ضرب سريعة مثل ضرب توم-كوك وخوارزمية شونهاج -ستراسن ؛ أما مع الضرب العادي من ^رتبة O ( n² )، فقد لا يُحقق تقسيم الأعداد الثنائية أي تسريع على الإطلاق أو قد يكون أبطأ.

بما أن جميع التقسيمات الفرعية للسلسلة يمكن حسابها بشكل مستقل عن بعضها البعض، فإن التقسيم الثنائي مناسب تمامًا للتوازي ونقاط التفتيش .

بمعنى أقل تحديدًا، قد يشير التقسيم الثنائي أيضًا إلى أي خوارزمية فرق تسد التي تقسم المشكلة دائمًا إلى نصفين.

• كزافييه غوردون وباسكال سيباه. طريقة التقسيم الثنائي
• ديفيد ف. تشودنوفسكي وغريغوري ف. تشودنوفسكي. الجبر الحاسوبي في خدمة الفيزياء الرياضية ونظرية الأعداد . في كتاب الحوسبة والرياضيات (ستانفورد، كاليفورنيا، 1986) ، الصفحات  9-232، ديكر، نيويورك، 1990.
• برونو هايبل، توماس بابانيكولاو. التقييم السريع متعدد الدقة لسلاسل الأعداد النسبية . ورقة بحثية موزعة مع شفرة المصدر لمكتبة CLN .
• لوزير، دي دبليو وأولفر، إف دبليو جيه التقييم العددي للدوال الخاصة. رياضيات الحساب 1943-1993: نصف قرن من الرياضيات الحسابية، دبليو. جاوتشي، محرر، وقائع ندوة الرياضيات التطبيقية، الجمعية الأمريكية للرياضيات، المجلد 48، الصفحات  79-125 (1994).
• باخ، إي. تعقيد الثوابت النظرية العددية. رسائل معالجة المعلومات، العدد 62، ص  145-152 (1997).
• Borwein, JM, Bradley, DM and Crandall, RE استراتيجيات حسابية لدالة زيتا لريمان. مجلة الحوسبة والرياضيات التطبيقية، المجلد 121، العدد 1-2، الصفحات  247-296 (2000).
• كاراتسوبا، إي إيه. التقييم السريع للدوال المتسامية. (الإنجليزية. الأصل الروسي) مشاكل نقل المعلومات 27، العدد 4، 339-360 (1991)؛ ترجمة من مشاكل نقل المعلومات 27، العدد 4، 76-99 (1991).
• ايكاترينا كاراتسوبا. الخوارزميات السريعة وطريقة الرسوم