首页

欢迎

 

Welcome

欢迎来到这里, 这是一个学习数学、讨论数学的网站.

转到问题

请输入问题号, 例如: 2512

IMAGINE, THINK, and DO
How to be a scientist, mathematician and an engineer, all in one?
--- S. Muthu Muthukrishnan

Local Notes

Local Notes 是一款 Windows 下的笔记系统.

Local Notes 下载

Calculator

Calculator 是一款运行于 Windows 下的计算软件.

详情

Calculator 下载

Calculator(GUI)下载






注册

欢迎注册, 您的参与将会促进数学交流. 注册

在注册之前, 或许您想先试用一下. 测试帐号: usertest 密码: usertest. 请不要更改密码.


我制作的 slides

Problem

随机显示问题

Problèmes d'affichage aléatoires

计算数学 >> 算法
Questions in category: 算法 (Algorithm).

正整数乘法的 Karatsuba 算法

Posted by haifeng on 2019-04-28 08:41:57 last update 2019-04-28 09:15:17 | Answers (0)


我们以十位数乘以十位数为例. 这里 $ab$ 是十位数, 即 $10a+b$, $a,b\in\{0,1,2,\ldots,9\}$.

\[
ab\times cd=(10a+b)(10c+d)=100ac+10(ad+bc)+bd.
\]

这是通常的算法, 需要 4 次乘法.

 

 

注意到

\[
(a+b)(c+d)=(ac+bd)+(ad+bc),
\]

因此,

\[
ad+bc=(a+b)(c+d)-(ac+bd)
\]

于是

\[
ab\times cd=100ac+10(ad+bc)+bd=100ac+10[(a+b)(c+d)-(ac+bd)]+bd.
\]

这里, 我们只需 $ac$, $bd$, $(a+b)(c+d)$ 三次乘法.

 

对于大的整数, 采用分治策略, 归结为小整数的乘法和加法运算.