关于开高次方的算法《天才与锻炼》-华罗庚 (转载)# Joke - 肚皮舞运动L*S2014-01-21 08:011 楼想在amazon买几本书,运费都快赶上书的价格了。如果我同时买好几本书,是不是可以考虑从同一个seller那里买,然后只用付一个运费?大家有什么别的办法节省运费吗?谢谢
d*f2014-01-21 08:012 楼【 以下文字转载自 Mathematics 讨论区 】发信人: luckysnake (lucky), 信区: Mathematics标 题: 关于开高次方的算法《天才与锻炼》-华罗庚发信站: BBS 未名空间站 (Tue Jan 21 08:45:35 2014, 美东)国人数学家里比计算功力,还是华老最牛。大家看看当年华老怎么评价那个印度计算神人的。天才与锻炼——从沙昆塔拉快速计算所想到的轰动听闻的消息提问者写下一个201位的 数:916,748,679,200,391,580,986,609,275,853,801,624,831,066,801,443,086,224,071,265,164,279,346,570,408,670,965,932,792,057,674,808,067,900,227,830,163,549,248,523,803,357,453,169,351,119,035,965,775,473,400,756,816,883,056,208,210,161,291,328,455,648,057,801,588,067,711解答者马上回答:这数的23次方根等于9位数546,372,891.《环球》杂志的一篇文章中是这样说的(请参阅《环球》1982年第3期《胜过电子计算机的人》一文):印度有一位37岁的妇女沙昆塔拉在计算这道题时速度超过了一台最先进的电子计算机.这台在美国得过奖的最现代化、最尖端的产品Univac 1180型电子计算机在算这道题时,要先馈入近2万个指令和数字单元,然后才能开始计算.它整整用了一分钟时间才算出结果.而沙昆塔拉在教授在黑板上用了 4分钟写出这个201位数后,仅用50秒钟就算出了以上的答案.美国报纸称她为数学魔术师,轰动一时!文章末尾还神秘地说,在她快生孩子的一个星期,她的计算能力出了问题.面对这样的问题怎么办?看到上述消息,可能有以下几种态度:一是惊叹,望尘莫及,钦佩之至,钦佩之余也就罢了.二是不屑一顾,我是高等数学专家,岂能为这些区 区计算而浪费精力.三是我掌握着快速电子计算机,软件有千千万,她一次胜了我算个啥!老实说,有上述这些思想是会妨碍进步的.第一种态度是没出息,不想和高手较量较量. 第二种态度是自命不凡.实际上连计算也怕的人,能在高等数学上成为权威吗?即使能成,也是“下笔虽有千言,胸中实无一策”,瞧不起应用,又对应用一无所能 的人.第三种是固步自封,不想做机器的主人.动脑筋是推进科学发展的动力之一,而勤奋、有机会就锻炼是增长我们能耐的好方法.人寿几何!我并不是说碰到所有的问题都想,而是说要经常动脑筋,来考验自己.在我们见到这问题的时候,首先发现文章中答数的倒数第二位错了,其次我们用普通的计算器(Sharp 506)可以在20秒内给出答数.那位教授在黑板上写下那个201位数用了4分钟,实际上在他写出8个数字后,我们就可算出答数了.所以说,沙昆塔拉以 50″对1′胜了Univac 1180,而我们用Sharp 506小计算器以-3′40″胜了沙昆塔拉的50″.但我们所靠的不是天才,而是普通人都能学会的方法.让我从头说起吧!从开立方说起文章中提到,沙昆塔拉在计算开方时,经常能纠正人们提出的问题,指出题目出错了,可见他们是共同约定开方是开得尽的.现在我们也做这样的约定,即开方的答数都是整数.我国有一位少年,能在一分钟内开6位数的立方.少年能想得出这个方法是值得称道的,但美中不足之处在于他没有把方法讲出来,因而搞得神秘化了.当然也考试了人们,为什么少年能想得出的方法,一些成年人就想不出来,反而推波助澜造成过分的宣扬?这问题对我是一个偶遇:在飞机上我的一位助手借了邻座一位香港同胞的杂志看,我从旁看到一个数59,319,希望求这数的立方根.我脱口而出答数是 39.他问为什么,我说,前二位不是说明答数的首位是3吗?尾数是9不是说明答数的末位应当是9吗?因此答数不该是39吗?然后,我告诉他,我的完整想法是:把六位数开立方,从前三位决定答数的第一位,答数的第二位根据原数的末位而定:2、 8互换,3、7互换,其它照旧(这是因为1、2、3、4、5、6、7、8、9立方的末位分别为1、8、7、4、5、6、3、2、9).例如314,432的立方根是68,前三位决定6,末位是2,它决定答数的末位是8.沙昆塔拉可以脱口而出地回答188,132,517的立方根是573.当然188决定了首位5,末位7决定了3,但读者试想一下,中间的7怎样算?归纳起来可以看出有两个方法:一个由头到尾,一个由尾到头.习题:求90,224,199的五次方根.我们怎样看出答数倒数第二位是错的这一点比较难些,要运用一个结果:即a23的最后两位数和a3的最后两位数是完全相同的.913的最后两位数是71而不是11,而713的最后两位数才是11,因此答数中的9应当改为7.先不管出现这个差错的原因是什么,我们这里已经做了一个很好的习题.想不到竟是Univac1180把题目出错了,这事我们后面再讲它.附记 我们来证明a23的最后两位数和a3的最后两位数相同.当a=2或5时,容易直接验算.今假定a不能被2和5除尽,我们只要证明a20的末两位是01就够了.首先因a是奇数,a2-1总能被8除尽,所以a20-1当然也能被8除尽.其次,因a4-1=(a-1)(a+1)[(a-2)(a+2)+5],a不是5的倍数,所以a-2,a-1,a+1,a+2中肯定有一个是5的倍数.即b=a4-1是5的倍数,而a20-1=(b+1)5-1=b5+5b4+10b3+10b2+5b. 因而a20-1是25的倍数.从而a20-1是100的倍数.具备些数论知识的人也可从费尔马定理推出来.我们怎样算我们用的原则是:如果解答是L位整数,我们只要用前L位(有时只要L-1位)或后L位就够了.用后L位的方法见附录二,先说前一方法.以前当那位教授说要开201位数的23方时,以23除201余17,就能预测答数是9位数.当教授写到第六、七位时,我们就在Sharp 506上按这六位和七位数,乘以1016,然后按开方钮算出(9.16748×1016)1/23=5.46372873,(9.167486×1016)1/23=5.46372892,这样我们定出了答数的前七位:5,463,728,后二位已由上节的方法决定了,因此答数应该是546,372,871.其实,更进一步考虑,只需利用这个201位数的前八位数字就能在计算器上得到它的23次方根(证明见下面的附记):但不幸的是,把这个数乘23次方,结果与原来给的数不相符(见附录一).与原题比较,发现原题不但尾巴错了,而且在第八和第九位之间少 了一个6.竟想不到Univac1180把题目出错了,也许是出题的人故意这样做的.为什么沙昆塔拉这次没能发现这个错误?看来她可能也是根据前八位算出了结果,而没对解答进行验算.我们的习题没有白做,答数错了我们发现了,连题目出错了我们也纠正了.结论是:在教授写到91,674,867时,我们在计算器上按上这八个数字。再乘1016,然后按钮开23方就可算出答案,总共约用20″就够了,也就是比那个教授写完这个数还要快3分40秒,比沙昆塔拉快了4分半钟.既然已经知道答数是九位数,或者说在要求答数有九位有效数字时,我们就只需把前八位或九位数字输入计算机就够了,而无需把201位数全部输入机器,进行一些多余的计算.附记 以a表示那个201位数,b也表示一个201位数,它的前L位与a相同,后面各位都是零.由中值公式,可知存在一个ξ(b<ξ<a)使当取L=8时,上式小于1/2,由b1/23的前九位(第十位四舍五入)就可给出a1/23.虚构下面讲一个虚构的故事,在沙昆塔拉计算表演后,有一天教授要给学生们出一道计算题.一位助手取来了题目.是一个871位数开97方,要求答案有 9位有效数字.教授开始在黑板上抄这个 数:456,378,192,765,431,892,634,578,932,246,653,811,594,667,891,992,354,467,768,892,…… 当抄到二百多位后,教授的手已经发酸了.“唉!”他叹了一口气,把举着的手放下甩了一下.这时一位学生噗嗤一声笑了起来,对教授说,当您写出八位数字后, 我已把答案算出来了,它是588,415,036.那位助手也跟着笑了.他说,本来后面这些数字是随便写的,它们并不影响答数.这时教授恍然大悟,“哈 哈,我常给你们讲有效数字,现在我却把这个概念忘了.”多余的话我不否认沙昆塔拉这样的计算才能.对我来说,不要说运算了,就是记忆一个六、七位数都记不住.但我总觉得多讲科学化比多讲神秘化好些, 科学化的东西学得会,神秘化的东西学不会,故意神秘化就更不好了.有时传播神秘化的东西比传播科学更容易些.在科学落后的地方,一些简单的问题就能迷惑 人.在科学进步的地方,一些较复杂的问题也能迷惑人.看看沙昆塔拉能在一个科学发达的国家引起轰动,就知道我们该多么警惕了,该多么珍视在实践中考验过的 科学成果了,该多么慎重地对待一些未到实践中去过而夸夸其谈的科学能人了.同时也可以看到,手中拿了最先进的科学工具,由于疏忽或漫不经心而造成的教训.现代计算工具能计算得很快很准,但也有一个缺点,一旦算 错了,不容易检查出来.对于计算象201位数字开23次方这类的问题——多少属于数学游戏性质的问题,算错了无所谓,而对在实际运用中的问题算错了就不是玩的.“二万条指令”出错的可能性多了,而在演算过程中想法少用或不用计算机演算,检查起来就不那么难了.这说明人应该是机器的主人,而不是机器的奴隶. 至于大算一阵吓唬人的情况就更不值一提了.这里我们还可以看到基本功训练的重要性.如果基本功较差,那么就是使用大型计算机来演算201 位数开23次方也要1分多钟才能算完.而有了很好的基本功,就是用小计算器也能花比1分钟少的时间算出来.这是一篇可写可不写的文章,我之所以写出的原因,在于我从沙昆塔拉这件事中得到了启发,受到教育,我想,这些也许对旁人也会是有用的.
d*f2014-01-21 08:014 楼我终于找到这篇文章了【在 d********f 的大作中提到】: 【 以下文字转载自 Mathematics 讨论区 】: 发信人: luckysnake (lucky), 信区: Mathematics: 标 题: 关于开高次方的算法《天才与锻炼》-华罗庚: 发信站: BBS 未名空间站 (Tue Jan 21 08:45:35 2014, 美东): 国人数学家里比计算功力,还是华老最牛。大家看看当年华老怎么评价那个印度计算神: 人的。: 天才与锻炼: ——从沙昆塔拉快速计算所想到的轰动听闻的消息: 提问者写下一个201位的 数:916,748,679,200,391,580,986,609,275,: 853,801,624,831,066,801,443,086,224,071,265,164,279,346,570,
l*o2014-01-21 08:0112 楼真搞科研的喜欢琢磨,遇到问题都尽量想通。这个靠训练很难,属于先天性格。【在 H******7 的大作中提到】: 这才是真正科学家,科普委委道来。现在的院士不神秘也要给你摆成神秘
T*e2014-01-21 08:0115 楼以后神算子一律不得算开方,全算高位数相乘。另,据说周同学算加法不大灵,四位数的加法用时一分三十秒。【在 d********f 的大作中提到】: 我要怎么跟dr. 魏证明这和大脑有关?
z*n2014-01-21 08:0116 楼我原来看Lord Kelvin生平,里面说他6岁就可以算7位数之内任意数的乘除,觉得这是真功夫。【在 T******e 的大作中提到】: 以后神算子一律不得算开方,全算高位数相乘。: 另,据说周同学算加法不大灵,四位数的加法用时一分三十秒。
d*f2014-01-21 08:0117 楼上期那个5岁小孩算20个随即3位数加减我看就是真功夫,我老现在这个年纪真心算不下来了【在 z*****n 的大作中提到】: 我原来看Lord Kelvin生平,里面说他6岁就可以算7位数之内任意数的乘除,觉得: 这是真功夫。
g*e2014-01-21 08:0118 楼博导的形象高大了起来。14寸简直是对你的玷污。【在 d********f 的大作中提到】: 上期那个5岁小孩算20个随即3位数加减我看就是真功夫,我老现在这个年纪真心算不下: 来了
l*o2014-01-21 08:0119 楼这两个不对啊?!(9.16748×1016)1/23=5.46372873,计算机结果 (9.16748×1016)1/23=1.4878921(9.167486×1016)1/23=5.46372892,=1.4878922哪里错了?
y*r2014-01-21 08:0120 楼14寸贴的时候格式丢了,应该是(powershell):PS C:> [math]::pow(9.16748*1e16, 1./23.)5.46372873459235【在 l*****o 的大作中提到】: 这两个不对啊?!: (9.16748×1016)1/23=5.46372873,: 计算机结果 (9.16748×1016)1/23=1.4878921: (9.167486×1016)1/23=5.46372892,: =1.4878922: 哪里错了?
n*t2014-01-21 08:0121 楼不明觉厉,深思极恐其实俺小时候也华罗庚,长大就吴孟达了 。。。。。【在 d********f 的大作中提到】: 上期那个5岁小孩算20个随即3位数加减我看就是真功夫,我老现在这个年纪真心算不下: 来了
x*g2014-01-21 08:0125 楼看来你是文科生。。。【在 l*****o 的大作中提到】: 这两个不对啊?!: (9.16748×1016)1/23=5.46372873,: 计算机结果 (9.16748×1016)1/23=1.4878921: (9.167486×1016)1/23=5.46372892,: =1.4878922: 哪里错了?
h*n2014-01-21 08:0131 楼华老的这篇文章虽然精彩,但还是没有完全解答我的疑问。201位数开23次方,得546,372,891,用华老的方法估算前两位和后两位大概没问题,但是别人可是算出了所有九位,虽然十位数错了。中间的63728这五位怎么心算出来?华老没有解释,只是说用计算器也能很快算出来。有数学高手可以解释一下吗?【在 d********f 的大作中提到】: 上期那个5岁小孩算20个随即3位数加减我看就是真功夫,我老现在这个年纪真心算不下: 来了
a*e2014-01-21 08:0132 楼en, 我看电视的时候就说这种题,就给他个平方根算算。开方越多越好算。【在 d********f 的大作中提到】: 上期那个5岁小孩算20个随即3位数加减我看就是真功夫,我老现在这个年纪真心算不下: 来了
d*f2014-01-21 08:0133 楼传说印度大妈其实有计算器【在 h*****n 的大作中提到】: 华老的这篇文章虽然精彩,但还是没有完全解答我的疑问。: 201位数开23次方,得546,372,891,用华老的方法估算前两位和后两位大概没问题,: 但是别人可是算出了所有九位,虽然十位数错了。: 中间的63728这五位怎么心算出来?华老没有解释,只是说用计算器也能很快算出来。: 有数学高手可以解释一下吗?
l*o2014-01-21 08:0134 楼"我不否认沙昆塔拉这样的计算才能".还是承认6位数的23次开方是心算的【在 h*****n 的大作中提到】: 华老的这篇文章虽然精彩,但还是没有完全解答我的疑问。: 201位数开23次方,得546,372,891,用华老的方法估算前两位和后两位大概没问题,: 但是别人可是算出了所有九位,虽然十位数错了。: 中间的63728这五位怎么心算出来?华老没有解释,只是说用计算器也能很快算出来。: 有数学高手可以解释一下吗?
a*e2014-01-21 08:0136 楼原帖的意思就是只要计算器按前8位就行了我估计华老还是暗示烙印可能作弊了,不过他不是方舟子,没必要跳出来打假【在 z*****n 的大作中提到】: 计算器也按不出200多位吧?
d*f2014-01-21 08:0137 楼你要搞清楚这个test的关键,就是那时候计算机慢,大妈作的就是比你输入计算机然后给出结果还快就可以了。我不知道她是不是有计算器,或者打草稿了。其实用手算也是可能的,因为设定是整数,这个range不是很大其实【在 z*****n 的大作中提到】: 计算器也按不出200多位吧?
d*f2014-01-21 08:0138 楼http://en.wikipedia.org/wiki/Horner's_method这个就是传说中的杨辉三角【在 d********f 的大作中提到】: 你要搞清楚这个test的关键,就是那时候计算机慢,大妈作的就是比你输入计算机然后: 给出结果还快就可以了。我不知道她是不是有计算器,或者打草稿了。其实用手算也是: 可能的,因为设定是整数,这个range不是很大其实
m*y2014-01-21 08:0139 楼我记得以前看过本教心算的书,用的是算盘的原理,加减乘除大数不在话下,让我对中国古老的计算工具崇拜不已。我也觉得这种算数本来都是有技巧的,有专家慢慢研究然后传授方法给别人就行,说不上大脑特异,电影雨人那种能力其实是1 记忆力(过目不忘) 2 估算能力(就是直觉,扫一眼地上的牙签就知道大概多少根,这种我记得有个科学家传记里也有过描述,说扫一眼饭店里的椅子就知道够不够来宾用的),这是大脑最基本的功能,如果这两样能异于常人才说的上是天才。
m*y2014-01-21 08:0140 楼还有这种复杂的计算可以类比为计算机处理复杂运算,速度取决于两个方面:1 硬件:CPU和内存,对应人脑就是大脑反应的速度和记忆力2 软件:算法,对应人脑就是特殊的运算技巧,如华老的文章所述软件厉害算不得天才,因为可以别人给你灌进去,硬件厉害才算天才。直接考考他的反应和记忆力,算这么大的数脑子里的缓存不仅大而且快,那就现场随便记一个无理数好了,能记50位就算异于常人了。
R*a2014-01-21 08:0141 楼其实人类云计算最慢步骤的就是查询寄存器,算盘,算筹,纸等工具的主要目的就是使用了更有效率的外置寄存器【在 m****y 的大作中提到】: 我记得以前看过本教心算的书,用的是算盘的原理,加减乘除大数不在话下,让我对中: 国古老的计算工具崇拜不已。: 我也觉得这种算数本来都是有技巧的,有专家慢慢研究然后传授方法给别人就行,说不: 上大脑特异,电影雨人那种能力其实是1 记忆力(过目不忘) 2 估算能力(就是直觉: ,扫一眼地上的牙签就知道大概多少根,这种我记得有个科学家传记里也有过描述,说: 扫一眼饭店里的椅子就知道够不够来宾用的),这是大脑最基本的功能,如果这两样能: 异于常人才说的上是天才。
G*Y2014-01-21 08:0142 楼华老还是很注重教育的当年小学课本不是还有他普及优选法的文章吗大学时还为他可惜呀。如果不搞优选法之类的,说不定可以证明什么大定理了。【在 d********f 的大作中提到】: http://en.wikipedia.org/wiki/Horner's_method: 这个就是传说中的杨辉三角
p*n2014-01-21 08:0143 楼原文有附录的:http://mkd.lyge.cn/a85/y1-1/116.htm【在 h*****n 的大作中提到】: 华老的这篇文章虽然精彩,但还是没有完全解答我的疑问。: 201位数开23次方,得546,372,891,用华老的方法估算前两位和后两位大概没问题,: 但是别人可是算出了所有九位,虽然十位数错了。: 中间的63728这五位怎么心算出来?华老没有解释,只是说用计算器也能很快算出来。: 有数学高手可以解释一下吗?
h*n2014-01-21 08:0144 楼这倒是个解释。不过问题在于,文章里面只详细描叙了较简单的前两步,对于最困难的最后一步就用“重复上面类似的计算可得到”直接跳过了。说明这一步如果写出来的话,看上去也就不象漂亮的速算了。(最后一步比前两步貌似难一个数量级,因为不止数变大了,还出现了平方项)老实说,如果有人能用这个算法在50秒内心算出答案,那也是不可否认的超强了。【在 p*****n 的大作中提到】: 原文有附录的:: http://mkd.lyge.cn/a85/y1-1/116.htm
a*w2014-01-21 08:0145 楼人家已经智障了, 你至少也得是无脑吧? 扮相不好做, 可用PS过的脑CT和平直脑电波图证明【在 d********f 的大作中提到】: 我准备报名参加最强大脑了,恩,你们说我包装成什么比较好
e*e2014-01-21 08:0146 楼昨天看了半天也是同问。估计这篇文章讲的是批驳有人自诩比计算机还快。其实计算器都能比她快。没看出怎么徒手开8位数23次方的诀窍。还是认为,最后结果是4位数或者以上的话基本都无法“心算”出来。2位,3位的而且是整数的基本都容易算出来。谁能在这类表演里最后算出结果是一个多位数才叫本事。另外准备好的数或者人(托儿)都不能算,要现场转轮盘或者掷骰子才能保证随机。这个大师估计是利用了数字技巧+点魔术:)【在 h*****n 的大作中提到】: 华老的这篇文章虽然精彩,但还是没有完全解答我的疑问。: 201位数开23次方,得546,372,891,用华老的方法估算前两位和后两位大概没问题,: 但是别人可是算出了所有九位,虽然十位数错了。: 中间的63728这五位怎么心算出来?华老没有解释,只是说用计算器也能很快算出来。: 有数学高手可以解释一下吗?