ضرب توم-كوك

في Toom- k ، نريد تقسيم العوامل إلى k أجزاء.

تتمثل الخطوة الأولى في اختيار الأساس B  = b ⁱ ، بحيث يكون عدد أرقام كل من m و n في الأساس B على الأكثر k (مثلاً، 3 في العدد 3). ويُعطى اختيار نموذجي لـ i بالصيغة التالية: 

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}$

^{في مثالنا ،} سنقوم بحساب العدد 3، لذا نختار B = b² = 10⁸ ^. ثم نفصل m و n إلى أرقامهما الأساسية B : mᵢ _و nᵢ _.

${\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}$

ثم نستخدم هذه الأرقام كمعاملات في كثيرات الحدود من الدرجة ( k - 1) p و q ، مع الخاصية التي تكون فيها p ( B )  = m و q ( B ) = n :   

${\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,}$

${\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,}$

إن الغرض من تعريف هذه كثيرات الحدود هو أنه إذا استطعنا حساب حاصل ضربها r ( x ) = p ( x ) q ( x ) ، فإن إجابتنا ستكون r ( B ) = m × n .

في حالة كون الأعداد المراد ضربها ذات أحجام مختلفة، من المفيد استخدام قيم مختلفة لـ k لكل من m و n ، والتي سنرمز لها بـ k_{_m} و k_{_n} . على سبيل المثال، تشير الخوارزمية "Toom-2.5" إلى خوارزمية Toom-Cook حيث k_{_m}  =  3 و k _{_n}  =  2. في هذه الحالة، يتم اختيار i في B  = b _ⁱ عادةً كما يلي: 

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}$

نهج توم-كوك لحساب حاصل ضرب كثير الحدود${\displaystyle p(x)q(x)}$وهي من الأنواع الشائعة الاستخدام. لاحظ أن كثيرة الحدود من الدرجة${\displaystyle d}$يتم تحديده بشكل فريد بواسطة${\displaystyle d+1}$النقاط (على سبيل المثال، خط مستقيم - يتم تحديد متعددة الحدود من الدرجة الأولى بنقطتين). الفكرة هي التقييم${\displaystyle p(\cdot )}$و${\displaystyle q(\cdot )}$عند نقاط مختلفة. ثم اضرب قيمها عند هذه النقاط للحصول على نقاط على متعددة الحدود الناتجة. وأخيرًا، قم بالاستيفاء لإيجاد معاملاتها.

منذ${\displaystyle \deg(pq)=\deg(p)+\deg(q)}$سنحتاج${\displaystyle \deg(p)+\deg(q)+1=k_{m}+k_{n}-1}$نقاط لتحديد النتيجة النهائية. لنسمي هذا${\displaystyle d}$في حالة توم-3،${\displaystyle d=5}$ستعمل الخوارزمية بغض النظر عن النقاط المختارة (مع بعض الاستثناءات الصغيرة، انظر شرط قابلية عكس المصفوفة في الاستيفاء )، ولكن من أجل تبسيط الخوارزمية، من الأفضل اختيار قيم عددية صغيرة مثل 0 و1 و-1 و-2.

إحدى القيم النقطية غير المألوفة التي تُستخدم بكثرة هي اللانهاية، وتُكتب${\displaystyle \infty }$أو${\displaystyle 1/0}$لتقييم متعدد الحدود${\displaystyle p}$في الواقع، تعني كلمة "عند اللانهاية" أخذ نهاية${\displaystyle p(x)/x^{\deg p}}$مثل${\displaystyle x}$يؤول إلى ما لا نهاية. وبالتالي،${\displaystyle p(\infty )}$دائمًا ما تكون قيمة معاملها ذي الدرجة الأعلى (في المثال أعلاه المعامل${\displaystyle m_{2}}$).

في مثالنا Toom-3، سنستخدم النقاط${\displaystyle 0}$،${\displaystyle 1}$،${\displaystyle -1}$،${\displaystyle -2}$، و${\displaystyle \infty }$تُسهّل هذه الخيارات عملية التقييم، مما ينتج عنه الصيغ التالية:

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}$

وبالمثل بالنسبة لـ${\displaystyle q}$في مثالنا، القيم التي نحصل عليها هي:

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}&=&56789012&=&56789012\\p(1)&=&m_{0}+m_{1}+m_{2}&=&56789012+78901234+123456&=&135813702\\p(-1)&=&m_{0}-m_{1}+m_{2}&=&56789012-78901234+123456&=&-21988766\\p(-2)&=&m_{0}-2m_{1}+4m_{2}&=&56789012-2\times 78901234+4\times 123456&=&-100519632\\p(\infty )&=&m_{2}&=&123456&=&123456\\[4pt]q(0)&=&n_{0}&=&54321098&=&54321098\\q(1)&=&n_{0}+n_{1}+n_{2}&=&54321098+43219876+98765&=&97639739\\q(-1)&=&n_{0}-n_{1}+n_{2}&=&54321098-43219876+98765&=&11199987\\q(-2)&=&n_{0}-2n_{1}+4n_{2}&=&54321098-2\times 43219876+4\times 98765&=&-31723594\\q(\infty )&=&n_{2}&=&98765&=&98765\end{array}}}$

كما هو موضح، قد تكون هذه القيم سالبة.

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

${\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}$

أبعاد المصفوفة هي d × k × _m لـ p و d × k _{× n} لـ q . صف اللانهاية يكون دائمًا أصفارًا باستثناء 1 في العمود الأخير.

بخلاف ضرب كثيرات الحدود${\displaystyle p(\cdot )}$و${\displaystyle q(\cdot )}$، بضرب القيم المقدرة${\displaystyle p(a)}$و${\displaystyle q(a)}$تتضمن هذه العملية ضرب الأعداد الصحيحة فقط ، وهي حالة مصغرة من المسألة الأصلية. نستدعي إجراء الضرب بشكل متكرر لضرب كل زوج من النقاط المحسوبة. في التطبيقات العملية، عندما تصبح المعاملات أصغر، ستتحول الخوارزمية إلى الضرب الطويل التقليدي . إذا كان r هو متعدد الحدود الناتج، ففي مثالنا لدينا:

${\displaystyle {\begin{array}{l c l c l c r}r(0)&=&p(0)\,q(0)&=&56789012\times 54321098&=&3084841486175176\\r(1)&=&p(1)\,q(1)&=&135813702\times 97639739&=&13260814415903778\\r(-1)&=&p(-1)\,q(-1)&=&-21988766\times 11199987&=&-246273893346042\\r(-2)&=&p(-2)\,q(-2)&=&-100519632\times -31723594&=&3188843994597408\\r(\infty )&=&p(\infty )\,q(\infty )&=&123456\times 98765&=&12193131840.\end{array}}}$

كما هو موضح، يمكن أن تكون هذه القيم سالبة أيضًا. بالنسبة للأعداد الكبيرة بما يكفي، تُعد هذه الخطوة الأكثر تكلفة، وهي الخطوة الوحيدة التي لا تتناسب خطيًا مع أحجام${\displaystyle m}$و${\displaystyle n}$.

هذه هي الخطوة الأكثر تعقيدًا، وهي عكس خطوة التقييم: بالنظر إلى${\displaystyle d}$نقاط على متعددة الحدود المنتجة${\displaystyle r(\cdot )}$، نحتاج إلى تحديد معاملاتها. بعبارة أخرى، نريد حل معادلة المصفوفة هذه لإيجاد المتجه الموجود على الجانب الأيمن:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}$

يتم إنشاء هذه المصفوفة بنفس طريقة إنشاء المصفوفة في خطوة التقييم، باستثناء أنها${\displaystyle d\times d}$يمكننا حل هذه المعادلة باستخدام تقنية مثل طريقة الحذف الغاوسي ، لكنها مكلفة للغاية. بدلاً من ذلك، نستفيد من حقيقة أن هذه المصفوفة قابلة للعكس، شريطة اختيار نقاط التقييم بشكل مناسب (انظر أيضًا مصفوفة فاندرموند )، وبالتالي:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}$

كل ما تبقى هو حساب حاصل ضرب المصفوفة في المتجه. على الرغم من أن المصفوفة تحتوي على كسور، فإن المعاملات الناتجة ستكون أعدادًا صحيحة ، لذا يمكن إجراء كل ذلك باستخدام العمليات الحسابية للأعداد الصحيحة، أي الجمع والطرح والضرب/القسمة على ثوابت صغيرة. يتمثل أحد تحديات التصميم الصعبة في Toom-Cook في إيجاد تسلسل فعال للعمليات لحساب هذا الناتج؛ أحد التسلسلات التي قدمها بودراتو ^{[ 6 ]} لـ Toom-3 هو التالي، والذي تم تنفيذه هنا على المثال قيد التشغيل:

${\displaystyle {\begin{array}{l c l c r}r_{0}&\leftarrow &r(0)&=&3084841486175176\\r_{4}&\leftarrow &r(\infty )&=&12193131840\\r_{3}&\leftarrow &(r(-2)-r(1))/3&=&(3188843994597408-13260814415903778)/3\\&&&=&-3357323473768790\\r_{1}&\leftarrow &(r(1)-r(-1))/2&=&(13260814415903778-(-246273893346042))/2\\&&&=&6753544154624910\\r_{2}&\leftarrow &r(-1)-r(0)&=&-246273893346042-3084841486175176\\&&&=&-3331115379521218\\r_{3}&\leftarrow &(r_{2}-r_{3})/2+2r(\infty )&=&(-3331115379521218-(-3357323473768790))/2+2\times 12193131840\\&&&=&13128433387466\\r_{2}&\leftarrow &r_{2}+r_{1}-r_{4}&=&-3331115379521218+6753544154624910-12193131840\\&&&=&3422416581971852\\r_{1}&\leftarrow &r_{1}-r_{3}&=&6753544154624910-13128433387466\\&&&=&6740415721237444\end{array}}}$

نعرف الآن متعددة الحدود الخاصة بالمنتج${\displaystyle r}$:

${\displaystyle {\begin{array}{rrrl}r(x)=&&3084841486175176&\\&+&6740415721237444&\!\!\!\!x\\&+&3422416581971852&\!\!\!\!x^{2}\\&+&13128433387466&\!\!\!\!x^{3}\\&+&12193131840&\!\!\!\!x^{4}\end{array}}}$

لو كنا نستخدم مختلفًا${\displaystyle k_{m},k_{n}}$، أو نقاط التقييم، ستتغير المصفوفة وبالتالي استراتيجية الاستيفاء لدينا؛ لكنها لا تعتمد على المدخلات وبالتالي يمكن ترميزها بشكل ثابت لأي مجموعة معينة من المعلمات.

أخيرًا، نقوم بحساب قيمة r(B) للحصول على الإجابة النهائية. هذا أمرٌ بسيط لأن B هي قوة من قوى b، وبالتالي فإن عمليات الضرب في قوى B هي جميعها إزاحات بعدد صحيح من الأرقام في النظام العددي ذي الأساس b . في المثال المذكور، b = 10⁴ ^و B = ^b² = ^10⁸ .

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840
	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

وهذا في الواقع ناتج ضرب 1234567890123456789012 و 987654321987654321098.

بتطبيق التعريف رسميًا، يمكننا اعتبار Toom-1 ( k_{_m} = k _{_n} = 1). لا ينتج عن هذا خوارزمية ضرب، بل خوارزمية تكرارية لا تتوقف أبدًا، إذ تُختزل كل حالة إدخال إلى استدعاء تكراري لنفس الحالة. تتطلب الخوارزمية نقطة تقييم واحدة، قيمتها غير مهمة، لأنها تُستخدم فقط لتقييم كثيرات الحدود الثابتة. بالتالي، فإن مصفوفة الاستيفاء هي مصفوفة الوحدة.

${\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}$

لا تزال خوارزمية Toom-1.5 ( حيث k _{_m} = 2 و k _{_n} = 1) خوارزميةً مُنحلة: فهي تُقلل أحد المدخلات بشكل متكرر عن طريق خفض حجمه إلى النصف، بينما تُبقي المدخل الآخر دون تغيير، وبالتالي لا يُمكننا تحويلها إلى خوارزمية ضرب إلا إذا وفرنا خوارزمية ضرب 1 × n كحالة أساسية (بينما تُختزل خوارزمية Toom-Cook الحقيقية إلى حالات أساسية ذات حجم ثابت). تتطلب هذه الخوارزمية نقطتي تقييم، تم اختيارهما هنا 0 و ∞. مصفوفة الاستيفاء الخاصة بها هي مصفوفة الوحدة.

${\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}$

تُعتبر الخوارزمية مكافئة بشكل أساسي لشكل من أشكال الضرب الطويل: حيث يتم ضرب كلا معاملي أحد العوامل في المعامل الوحيد للعامل الآخر.

تتطلب عملية Toom-2 ( حيث k _{_m} = 2 و k_{_n} = 2) ثلاث نقاط تقييم، تم اختيارها هنا لتكون 0 و 1 و ∞. وهي مماثلة لعملية ضرب كاراتسوبا ، مع مصفوفة استيفاء كالتالي:

${\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}$

تتطلب المعادلة Toom-2.5 ( حيث k_{_m} = 3 و k_{_n} = 2) أربع نقاط تقييم، تم اختيارها هنا لتكون 0 و 1 و -1 و ∞. وبالتالي، فإن مصفوفة الاستيفاء الخاصة بها هي:

${\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}$