神奇的乘法(四)

第十一种乘法:卷积

最最平常的乘法,也是一种卷积。

例如,计算 123×456,可以这样做:
制作如图的两个滑块,123竖着往下写,456倒着往上写。
然后,让456从123的旁边滑下来。

模拟卷积

每滑动一格,都把两个数重叠的部分进行点积运算,结果记录下来。每次结果的个位向后移动一位。

当滑动结束以后,把那些结果加起来,即可。

这种运算就是卷积的直观展示。

无处不在的卷积

类比乘法的卷积方法,可以定义两个序列的乘积。让一个序列从另一个序列旁边滑过,形成很多的点积,把这些点积加起来,得到序列积。

序列可以是有限的,也可以是无限的。

无限的序列可以有生成函数,生成函数,就是类似对等比数列求和的结果。用那结果,就可以生成等比数列。

序列乘积的时候,一个序列可以转化成向量,另外一个转化为矩阵。用矩阵,意味着乘法不可交换。

卷积常用在傅立叶分析。

第十二种乘法:印度乘法

印度乘法,是指普通的数字乘法,特别的地方有两处。

其一是:格子乘法。

格子乘法

格子乘法最早记载在1150年印度数学家婆什迦罗的《丽罗娃提》一书,后来传到阿拉伯,再后来传到欧洲,由意大利人传到中国,中国数学家程大位给起了个好听的名字,叫“铺地锦”。

但中国人还是习惯用珠算,用“一口清”来计算乘法。

其二是:大九九。

中国传统的大九九乘法口诀,只是把普通的小九九扩充一倍,例如“三九二十七”成为两句口诀“三九二七”与“九三二七”。而印度的大九九则更大,要求背诵所有的两位数乘以两位数,背诵以后,计算速度无疑会大大提升。

当然,背诵是有技巧的。不是单纯的死记硬背。例如十几乘以十几,方法就是,把乙的个位数加在甲的末尾,添零,再加上两数个位与个位相乘,得结果。

例如:18×13,(18+3)=21,添零以后是210,个位乘积是8×3=24,结果就是210+24=234。

第十三种乘法:俄罗斯农民乘法

俄罗斯农民的乘法,直观思想十分朴素,举个特殊例子来看:

16×17=8×34=4×68=2×136=1×272=272

指导思想就是,不断的把被乘数减半,把乘数加倍,直到被乘数变为1,结果就出来了。

上面的例子,碰巧被乘数减半的过程中,一直是偶数,如果是奇数,怎么办呢?如果是奇数,就单独记录下那一步的乘数,把被乘数减一,继续运算,在最后,把记录的结果加上去即可。

例如:

35×37
=34×37+37
=17×74+37
=16×74+74+37
=8×148+111
=4×296+111
=2×592+111
=1×1184+111
=1295

这种运算,表面上看,步骤很多,很笨拙。但正应了中国的古训“大巧若拙”,其实这种算法,是极其迅速的。尤其到了计算机的时代,到了二进制的时代。

俄罗斯农民的算法,可以用极快的速度完成大数的乘法。所谓大数,就是几百位或者几千位的数字相乘。

用普通的乘法是很慢的,要做多次的乘法和加法,复杂程度一般是N的平方;而俄罗斯农民算法的复杂度是N×(log N)。因此,是及其迅速的。并且,计算机中,除以2或者乘以2,很多时候是不需要计算的,只需要移动一位,因为计算机经常使用2进制。

俄罗斯农民算法可以扩展为使用4进制,16进制都可以,64进制等都可。

在大数乘法中,能比俄罗斯农民的乘法更快的算法并不多。

第十四种乘法:用快速傅立叶变换作乘法

离散傅立叶变换,可以用来计算乘法。

但如果不是快速傅立叶变换,复杂度仍然是N的平方。

如果用快速傅立叶变换,就可以超越俄罗斯农民算法。

仅仅因为,傅立叶变换应用太广泛,人们针对傅立叶变换,研究了各种快速算法,使得快速傅立叶变换可以达到N(log N)的复杂度。

本质上讲,快速傅立叶变换的速度并没有超过俄罗斯农民的算法。仅仅因为,它已经有了各种成熟的库,各种优化的算法,因此,应用更广泛,就得到更多的优化,速度更快了。

如果对俄罗斯农民算法进行适当的优化,也可以达到快速傅立叶变换的速度。

日常如果要做大数乘法,用俄罗斯农民算法足矣。如果有更高的要求,可以用GNU的库函数,其中各种算法的实现都有,尤其是用快速傅立叶变换来计算乘法。

大数的乘法有什么用处呢?一般的,还真没什么用处。无聊的时候,可以把圆周率计算个几万位,就只有这种用处。

而几万位的圆周率,本身就没有什么用处。50位以内的小数,足够地球上的天文学家和物理学家用了。

大数乘法的其它用处包括:彰显科技,比拼电脑的计算速度,RSA加密,破解RSA加密等。

傅立叶变换怎样做乘法,以及为什么能做乘法,需要专门来讨论。

第十五种乘法:利用三角函数计算乘法

在没有计算器的年代里,三角函数专门有一个表,叫做三角函数表。已知角度,可以查询三角函数值。已知三角函数值,如正弦值,也可以查到角度。

利用这个表,可以进行乘法运算。把需要相乘的两个数字,通过适当的移位,变成三角函数可以表示的范围。然后查到对应的两个角度,用积化和差公式来计算。最后,对结果重新移位恢复。

例如,计算 4766×8848
先变成 0.4766×0.8848,
然后假设这是两个角度的正弦,查表的到两个角度:
28.463575度
62.22692度

根据公式
sinA × sin B = [cos (A-B) - cos(A+B)]/2

需要查计算:

两个角度的差是33.763344度,差表得余弦为 0.83134;
两个角度的和是90.6905度,差表得余弦为 -0.01205;
两者做差,平均以后,为0.421695。

按照这个结果,移位,原来乘积就是 42169500。
实际上,前面的部分都很精确,只有最后两位不同。

真实的结果是42169568。

在精确程度允许的情况下,足够了。
关键是,这种方法,只用加减法来计算乘法。

第十六种乘法:利用对数计算乘法

对数非常神奇,甚至可以说吊诡:

(1)对数,先于指数被发明;

(2)自然对数(接近),先于常用对数被发明

对数最自然的底,竟然就是自然对数底。一开始,人们各种尝试,就使得底非常接近自然对数底。

自然对数底,无疑是神秘的,欧拉对此剖析的最透彻,关于e的故事,三天三夜也说不完。

后来,有了常用对数,对数用来做乘法就更方便了。

外国人,有一种精神,是我们所没有的:在没有对数表格的情况下,他们可以经过几代人的努力,来编制长长的表格,做这样的苦功,枯燥且乏味。然后印刷下来,供大家使用,世界人民共享劳动成果。在有了表格的情况下,他们又尝试发明各种仪器,来简化运算,终于把计算尺,计算器和计算机搞出来了,还是大家都能用。这里,既有厚德载物的精神,又有自强不息的精神。

我们,却还在培养珠心算,用“一口清”这些高端乘法技术。尽量的,连笔和纸都不使用,来完成计算。这些技术,只能适用于少数有天赋的儿童,而且要经过辛苦的训练才能掌握。并且,这种技能的传承非常困难。并且,如果不经常使用,很快就会退化。

有工具,为什么不用呢?人类最高超的技能,不就是制造和使用工具吗?其实,根本不用担心加减乘除的技能退化。

现在,没有多少人会手动开平方。加减乘除并不比开平方重要。所以,就算大多数人不懂口算,也没什么关系。

能机械运算的,就用机械运算。能查表的,就查表。这样,才是真正的解放生产力,发展生产力。

数学需要运算。但运算不是数学的本质。

我们常常嘲笑外国人太笨,但他们才是真正的大智若愚啊!他在菜市场或者超市不会口算,是因为他们不需要计算,所以不需要会算。

中国古人,鄙视会算术的人,认为这些是属于底层人民的东西。属于“奇挤淫巧”一类。上层社会的人完全不懂得算术。这样的做法似乎也不妥。

理想的状态应该是:不同职业的人都得到应有的尊重,有体面的收入。职业平等,不分高低贵贱。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,837评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,551评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,417评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,448评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,524评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,554评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,569评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,316评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,766评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,077评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,240评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,912评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,560评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,176评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,425评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,114评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,114评论 2 352

推荐阅读更多精彩内容