كاراتسوبا الضرب

ومن الممكن أن تؤدي الضرب من أعداد كبيرة في (العديد) عمليات أقل من أسلوب القوة الغاشمة المعتادة "الضرب الطويل." كما اكتشف Karatsuba (Karatsuba وOfman 1962)، الضرب اثنين - أرقامأرقام يمكن القيام به مع تعقيد قليلا أقل من استخدام الهويات من النموذج

(1)

فالإجراء المتكرر يعطي تعقيدًا قليلاً  ، حيث (Borwein et al. 1989). أفضل تجليد معروف هو خطوات (Schönhage and Strassen 1971، Knuth 1998). ومع ذلك ، من الصعب تنفيذ هذه الخوارزمية ، ولكن إجراءً يعتمد على التحويل السريع لـ Fourier سهل التنفيذ ويعطي تعقيدًا قليلاً  (Brigham 1974، Borodin and Munro 1975، Borwein et al. 1989، Knuth 1998).

كمثال ملموس ، ضع في اعتبارك الضرب من رقمين كل اثنين فقط "أرقام" طويلة في الأساس ،

			(2)
			(3)

ثم منتجهم هو

			(4)
			(5)
			(6)

بدلاً من تقييم منتجات الأرقام الفردية ، اكتب الآن

			(7)
			(8)
			(9)

المصطلح الرئيسي هو ، والتي يمكن توسيعها تجمع لاعبو، ومكتوب في شروط كما

(10)

ومع ذلك ، منذ ذلك ، وعلى الفور يتبع ذلك

			(11)
			(12)
			(13)

لذلك تم تقييم "الأرقام" الثلاثة باستخدام ثلاث مضاعفات بدلاً من أربعة. يمكن تعميم هذه التقنية على الأرقام متعددة الأرقام ، مع المقايضة كونها تتطلب المزيد من الإضافات والطرح.

الآن النظر في أربعة أرقام "أرقام"

(14)

والتي يمكن كتابتها كرقم "رقمين" ممثلة في القاعدة ،

(15)

"الأرقام" في القاعدة الجديدة هي الآن

			(16)
			(17)

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

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