yangxintie1的个人博客分享 http://blog.sciencenet.cn/u/yangxintie1

博文

再谈速算法创立人史丰收的提前进位拟并行算法可改进CPU设计

已有 7350 次阅读 2014-7-3 23:48 |个人分类:非线性数理方法|系统分类:人物纪事| 科学院, 计算机, 史丰收, 速算法, 可惜了

       

 

  在科学网突然看到报道史丰收英年早逝的消息,十分震惊,史丰收去世这么早,可惜了,当年认识他的时候他还是个孩子,和他交往一幕幕不禁又重新呈现眼前。

      当年他还是孩子的时候,为了猜出他的运算方法,我曾一次次的考过他,根据猜测它使用的方法给科学院和数学所提供了一篇报告,次年春,最后一次问他,你的方法就是十字交乘法推广加上提前进位,他最后也同意了,于是劝他赶快总结,尽早出版。

 

   现在史丰收在海内外享有很高的赞誉,可是在三十多年前,还无人知晓,是到陕西省大荔县下乡的西北大学的学生发现了他的特殊能力,据说是一个生产队的账目计算要靠一个小孩子报出,这些下乡的师生们回来就向教育厅领导小组的负责人吴江声等同志作了汇报,于是省教育局就把此孩子作为特殊培养对象接到西北大学附中学习。

   吴江声老人是个刚刚解放出来的老干部,他38年参加抗大前就是才子,所以爱才,因此对史丰收很爱护,我是从吴江声老人来串门时听他说起这个事情的,知道了生于陕西省大荔县两宜镇这个普通农家的孩子,能够对任何多位进行迅速心算,但是如何算的,这个孩子自己就是说不出来.

这件事引起了我们几个从到西工大进修的技术人员的极大兴趣,我们几个人,一个来自西工大,一个来自清华,一个来自北工,当时的鱼雷课程也不重,业余时间就一起商量着把史丰收请到西工大来,于是我就走访了西北大学数学系,除了数学系革委会以外,还访问了赵端榕教授,他们介绍我认识了附中史丰收班主任,联系了史丰收到西工大来交流的事宜。

   听他班主任讲,上世纪七十年代,史丰收曾与中国著名数学教授华罗庚“竞技”,一个用算盘,一个用速算法,结果史丰收获胜史丰收前后来了好几次,算的确实很快,但是他就是不说他是怎么算的,到华罗庚那里表演,也没有说出所以然,结果华罗庚语重心长地鼓励了他一些话,希望他加紧努力学习.

  我们问史丰收具体怎么算的时候,他也不说,只告诉我们这个算法很复杂,给你们说也说不清楚。我们都认为显然我们的理解能力似乎没有问题,也许这个当时的孩子对说出真实的计算方法还有顾虑,这就反而让我们大家更加感兴趣,更想把它“替史丰收总结出来!”。

      我们首先探讨一个常人的大脑如何进行多位数的乘法和除法计算,我们也翻阅了很多书籍,包括陕西省图书馆,西工大图书馆,还请教了西北大学赵端榕教授,这才知道中国很早就有九章算术的文献资料,最后眼光落到了古代一种"失传了的算法"掐头算上面,因为计算遇到的进位问题使得大脑运算只能从前往后才能进行,于是我们首先测试了史丰收的脑子到底能存几位的进位,为此编制了一大批考题,起先考他4位5位的乘法,除法,他做得很快,我们逐渐增加考题的位数,从六位数加到九位数计算,史丰收都很从容,后来为了增加进位的难度,特别在多位数里面增加9,8,7一类数字,来考史丰收。

      史丰收很配合,当我们测量到12位相乘的时候,史丰收就算得慢了,算了10分钟以上,并且容易出错了,尤其是当这些数都是7,8,9一类特别容易增加进位的数字的时候,报出的答案竟错了两次,我们说给他提醒的答案,史丰收倔强的说不要,还烦躁地说“你们不要干扰我”,又过了十来分钟,最后一次史丰收坚定认为我们答案错了,他还有一套检验的办法,它的判定法我也知道,肯定是我的“答案”错了,史丰收算得结果是对的。我的问题是花了一小时时间琢磨出来的,在一小时听课中间用手工计算出来的,确实也校核过,但是这个“答案”还是错了,不得不佩服从初中来的这个农家孩子。

  根据这些测试,大约可以判断史丰收的大脑在当时来说,和常人的大脑区别不大,也不能够存储两位以上的进位,但是他是如何把进位处理了的呢?谜团一时很难解开,在没有揭开谜团之前,我们研究加紧进行,然后就是在宿舍就这个话题进行讨论。这个问题的解决要分两步走,首先解决不考虑进位情况下的掐头算计算公式,然后才集中精力考虑进位问题,思路是先考虑了多位数乘法运算,乘法要从高位算到低位当然和初中学的十字交乘法不会有多大区别,除法,乘方,开方等运算应当在乘法"掐头算"的基础上得到,这个思路很快打通,所有的运算公式都推出来了,同时还不断的请史丰收从中学来“测试”。


  进位如何提前获取的呢?思考问题长了,把思考的方向转移一下,就会有一个一闪念的灵感出现;这个机遇让我们也抓住了,原来我们把精力放到乘法上面,回过头来看一看除法,1除以2,得到0.5,1除以3得到0.3333....;那么就是说,如果比0.3332还小的数字乘以3,就没有进位,而比0.333334大的数字乘以3,就会进位1;这样一来对于一排数字,乘以2至9的进位来说就非常容易得到一个判断准则了!

   这样就猜想除了史丰收从左向右,从高位到低位的速算规律,同时把根据猜想总结的结果和算法汇总成一篇详细的文章,记得当时把加、减、乘、除、开方、平方的算法都写成了迭代运算的公式,第二年春天,又把史丰收请来谈了一次,问他,你的算法就是“十字交乘法推广加提前进位”吧,史丰收还是不太愿意承认,最后憋出一句话,“你要这样说也可以吧”。我们建议史丰收赶快总结算法并发表。后来还配上了441B算计的代码,向数学所,北大,科学院等单位通过邮寄呈交。以后杨凌云等搞珠心算到北京看到的估计就是此文。

     记得给科学院和数学所那篇文字特别长,几十页,油印的,题目好像是“史丰收速算法在计算机中间的应用”最后还用汇编做了一段在我国最早的441B计算机上面运行的程序。当时为什么这样做,主要是对史丰收“算前位,看后位,提前进位”的速算方法非常看好。当时给科学院数学所和有关大学的报告用的是宁夏青铜峡中学一个教师的名字,后来杭州的杨凌云,西华县的口笔算的同志,一直设法通讯和青铜峡联系,不知道那位教师已经调走了。我因为在云南,后面也一直很忙,无暇顾及。

   时隔多年以后,才知道,实际上史丰使用的速算法在口算方面更成熟,已经通过许多人的努力,总结出来了口诀,但是基本的核心还是是算本位,看后位,提前加上后进位,进位的26句口诀是:

乘數爲2時,口訣爲:滿五進1;

乘數爲3時,口訣爲:超3進1,超6進2;

乘數爲4時,口訣爲:滿25進1,滿50進2,滿75進3;

乘數爲5時,口訣爲:滿2進1,滿4進2,滿6進3,滿8進4;

乘數爲6時,口訣爲:超16進1,超3進2,滿5進3,超6進4,超83進5;

乘數爲7時,口訣爲:超142857進1,超285714進2,超428571進3,超571428進4,超714285進5,超857142進6;

乘數爲8時,口訣爲:滿125進1,滿25進2,滿375進3,滿5進4,滿625進5,滿75進6,滿875進7;

乘數為9時,口訣爲:超1進1,超2進2,超3進3,……超8進8        

   这样配合上 加减用手指算,手指伸屈动一下,结果一下出来,最快者一秒钟可以算四五个数,同时左手的不断摆动来刺激右脑,从而起到开发右脑的潜能。多位上是从个位上分化出来,与学校教的方法一样,无论多少位都可以算出来。比起来其它的方法,一般能算三、四位、最多也不过六位就很了不起了,但对史丰收速算法来讲,算个五六位相乘一点问题也没有,经过练习,二三四五十位都是一笔算到底。算开方,算乘方,利用泰勒公式还可以算三角,对数函数!     要说的是,我虽然研究算法,但自己始终没有性子练熟这套算法,在云南马过河卖鸡蛋的时候,17个鸡蛋每个一毛四分钱,一共多少?竟然算了半天还没算出来,旁边一个和我一起讨论过速算法的同伴就笑话我说,就你这样子,连十几个鸡蛋的钱都算不过来,还研究速算法呢?!

    这套算法在科学上有没有意义?我们在科学殿堂里面还会碰到一些这样的牛人,信誓旦旦的说这就不是科学!但是我们看到,美国最新的CPU设计方案里面已经加进去了依靠判断提前进位,解决进位延迟问题。相信有一天,我们会看到这种思路会在计算机设计上开花结果。

   因为这种算法实际解决了串行运算一个难题,实际上把它弄成了拟并行运算。到现在美国最新的芯片设计才摆脱旧的模式开始考虑提前进位的芯片设计,史丰收的算法是最形象,最直观,最生动的一种解决串行运算进位的方法,他不仅在提高大脑运算速度和能力方面有用,在计算机设计方面也是很有启发意义的,尤其现在并行计算已经到了瓶颈的情况下,也需要改变思维,考虑新的算法带来串行计算的意义。

  他这种方法把从低位高位的串行运算变成了从高位到低位的拟并行运算,还不止这样的内部并行,由于计算结果是从高位输出的,那么输出的结果马上就可以接着和下面数据的高位进行下一部的处理。如果把计算芯片成组成一群像史丰收大脑这样的计算单元联合起来,前面算过的高位马上报给第二名接着算,这样,在处理密码的极长数据运算问题上,就可以把那个长数据砍成一段一段来算,先算头,后算尾,如同一个联合生产线,每个工序只算一位,就立刻传到下一道工序,一条线上面摆的机器越多,就加工哦那个越快。越是长的数据(一万位吧),越有优势。想象一千个处理器联合起来蚂蚁啃骨头,处理一个原来一个处理器计算的大数据,这种速度的提升是可怕的!一亿位的数据处理呢?这种算法得到的结果越奇异!

  说道运算,就离不开进位,史丰收的通过判读提前进位是这种拟并行方法的保证,这一点也可以改进,因为计算机不像史丰收的脑子只能记三、四进位,计算机把进位也可以像矩阵一样的处理,就是说:研究史丰收算法必然得到第二条把串行运算变成拟并行的好处,这就可是以使得进位也变成拟并行,依靠判断提前得到的进位其实也是可以和主要数字的运算脱离的,就像本位数字一样进行从前高位向后面低位运算,而且进位也可以独立起来,就像中国老算盘那样,一个数字不一定只用一排数表示,可以用一排数字和他的几排不同节拍下的进位合起来表示,我过去对算盘上面两排珠子一直不得其解,现在考虑一下拟并行问题,几个手同时打算盘,显然算盘比日本一排珠子的设计要好!

      这样的数就写出来不是一排,而是多排,一位数字的肩膀上还可以写上它的进位,进位的肩膀上还可以戴上进位,可以把这种数字的描述体系叫做肩膀数,或者叫算盘数系,这是一种在计算机里面容易应用的数系,在不同的节拍里面,基本排面的数字和他携带的进位包袱一同进行不断整理和运算,实际上构成了一套从前往后计算,计算机如同多个流水线处理信息的新算法,这套算法必然大大加快了CPU或者GPU的运算速度。

  冯.诺依曼计算机出世70年了,不论用补码原码,CPU改动不是很大,而主要发展是在速度及多核并行上面。急需CPU的根本性设计变化。

   可以毫不夸大说:史丰收速算法是直接凭大脑进行运算的方法,又称为快速心算、快速脑算。它打破人类传统一般情况下从低位算起的方法,运用进位规律,由高位算起,加快计算速度,把数字运算从串行发展到拟并行,也给当代应用数学提供了加速计算机串行运算速度的新路子。冰山只漏尖尖角,水下面还有大头,还有待开发,“这孩子”走的太早了。

  我写这篇文章,其实30年前就写好了,但是被弄丢了,今天拿出来,一来纪念史丰收,二来希望这种算法在计算机上面的应用首先在中国开花结果。



https://blog.sciencenet.cn/blog-1354893-808836.html

上一篇:电子加速器加速电子能不能超过光速?寻找加速器研究者的帮助
下一篇:数学家们、数理学界的高手快来!救命!
收藏 IP: 123.138.79.*| 热度|

8 白图格吉扎布 赵建民 刘钢 武夷山 蒋迅 linhongye zjhs111 Vetaren11

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-5-8 22:23

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部