Karatsuba's Algorithm Karatsuba 算法

1 复数乘法

假如现在有两个复数:
a*i + b 和 c*i + d
则，两个复数相乘，则是：
(a*i + b) * (c*i + d)
= (ac - bd) + (cb + ad)i
也就是说，共需要计算
4次乘法，3次加法

2 一个更好的方法：

  1. 计算a*c
  2. 计算b*d
  3. 计算(a+b)*(c+d)
  4. 结合1和2，得到 ac - bd
  5. 结合1,2,3，得到ad + bc

共需要：
3次乘法，5次加法

3 用于计算整数相乘：

如计算5822*4104:
5822 = 5 * 1000 + 822
4104 = 4 * 1000 + 104

  1. computea*c = 5*4 = 20;
  2. compute b*d = 822*104 = 85488;
  3. compute (a+b)*(c+d) = (5+822)*(4+104) = 89316;
  4. ac+bd = 20 + 85488 = 85508;
  5. ad + bc = (a+b)*(c+d)-a*c-b*d = 89316 - 85488 - 20 = 3808;
  6. (ac)*(i*i) + bd + (ad+bc)i = 20*1000*1000 + 85488 + 3808*1000 = 23893488；
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • #算法学习录#Strassen矩阵乘法
    今天我们谈谈一个“土豪”算法——Strasen矩阵算法之说以说它“土豪”就是因为其带来了巨大的空间开销。先来考察一...
    LRC_cheng阅读 1,594评论 0赞 1
  • 大数相乘之Karatsuba算法
    问题大数相乘 计算123×456，其实12345和6789就是大数。 思路 这是分治算法思想的典型体现。计算机只会...
    Stroman阅读 2,749评论 0赞 2
  • 算法概论笔记 - 分治法
    将原问题分解为一组子问题，每个子问题都与原问题类型相同，但是比原问题的规模小 递归求解这些子问题 将子问题的求解结...
    芥丶未央阅读 1,451评论 2赞 1
  • 大数乘法
    普通大数乘法 普通大数乘法模拟两个数字竖式相乘,为了方便操作,数字的个位在数组的第0位,时间复杂度为O ( n² ...
    Gitfan阅读 970评论 0赞 0
  • 算法考试复习
    引论 算法与数据结构与程序的区别算法是求解问题的过程描述：从蛮力到策略数据结构是数据的组织与存储：从杂乱无章到井然...
    FakeCSer爱去网吧阅读 1,965评论 0赞 3