设万维读者为首页 广告服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:诤友
万维读者网 > 教育学术 > 帖子
一种没有溢出的算法来解决乘法计算
送交者: 茶树油之家 2011年07月01日10:18:02 于 [教育学术] 发送悄悄话
我前一段写了一篇博文分享过一纽约长岛女孩(非常可爱聪明的大女孩)用视觉方式计算两位数的乘法。但是我很快发现,如果最后一位数和中间的和数都大于9的话,就会有一个进位的问题。而且如果视图中间的交叉点太多,计算起来也十分繁琐。

但我很快发现这种视觉的方式实际上是将传统的竖式计算方法用图像的方式来表达出来,这的确是十分有想象力的。我仔细研究传统的竖式算法,我发现计算的过程实际上两个单数不断相乘的过程,个位数留下,如果有十位数,则十位数进位,然后不断重复的过程。这用编程的方式来说,实际上可以用两个循环来模拟进行。因为是两个单数的相乘,这不会有溢出的问题,在计算过程中,将最左边的各位数不断留下来,存放在一个字符的串变量之中,整个循环完成之后,就可以得到结果。这样就不会有整数溢出的问题(电脑计算过程中,整数是有一定上限的,超过这个上限就会出现溢出)。


根据这个推理逻辑,我用网页的HTML+Javascript编写了这个算法的程序。经过调试之后,嘿!还真工作,任何两位整数的乘法不会出现溢出。


计算程序


下面是我编写的计算程序:

function v1timesv2(v1, v2) {
  var x = ''// result
  var i = 0;
  var j = 0;
  var r;
  var r1;
  var r2;
  var k;
  var tempVal;
  var preTempVal = '';
  debug ('v1: ' + v1);
  debug ('v2: ' + v2);
  for (i= v2.length-1; i >= 0; i--) // v2
  {
    r2 = 0;
    tempVal = '';
    k = preTempVal.length;
    for (j=v1.length-1;j >=0; j--)  // v1
    {
      if ((k--) > 0)
      {
        r2 += Number(preTempVal[k]);
      }
      r = v1[j] * v2[i] + r2;
      r1 = r % 10;
      r2 = 0;
      if ( r > 9 )
      {
        r2 = (r - r1) / 10;
      }
      tempVal = r1 + tempVal;
    }
    if ( r > 9 )
    {
       tempVal = r2 + tempVal;
    }
    debug('intermediate calculated result: ' + tempVal);
    // Get the last char as result
    x = tempVal[tempVal.length - 1] + x;
    debug('intermediate result: ' + x);
    // Get the remaining as previous val
    if ( tempVal.length > 1 ) 
    {
      preTempVal = tempVal.substr(0, tempVal.length - 1);
    }
    else
    {
      preTempVal= '';
    }
    debug('== carry forward result: ' + preTempVal + ' ==' );
  }
  x = preTempVal + x;
  debug('>>final result:    ' + x);
  debug('>>verified result: ' + Number(v1) * Number(v2) + ' (' + v1 + ' x ' + v2 + ')');
  return x ;
}


我的算法肯定不是最优化的方式,如有高手,请多多纠正指导。


原程序和计算网页


为了方便进行调试,我采用了Javascript方式写计算的程序,然后利用网页HTML的方式将程序隐藏在文件的header部分,网页的body部分为用户界面,你可以输入两个整数,点击计算button就可以得到没有溢出的计算结果。


请从后面的参考中试试我的乘法计算网页或下载原码用你的网页浏览器试试。

注意:该HTML网页没有检测你的输入数据是否是整数,如果输入其它无效字符则不会得到计算结果。

如果你是用Safari,Chrome,Firefox网络浏览器,右点鼠标键打开监视网页元素(inspect elements),然后点击Console,这样你还会看到计算过程中我加入的debug计算详细信息:



随后感


英特网的出现使得信息出现空前的膨胀,我记得一次在听《吴东相对论》播客中,他们提到现在许多多人因为网络信息太多而不愿读书,而且对许多信息也没有真正的分析的兴趣,什么都是一览而过,大脑越来越迟钝。对于年轻来说,大量的信息反而造成他们的学习能力降低。

我每天也快速浏览许多网络中的许多东西,但是我有一个习惯,如果发现特别有兴趣的东西,我特别喜欢品味和琢磨,有机会和同事或朋友们分享。别小看分享过程,这是一个将吸收的东西再加工和表述的过程。我经常发现在表述的过程中突然卡住,无法将我的想法流畅的表述出来。在这种情况下,我再回去认真读览,查询其它的资料,直到我感到能够完全理解和备有丰富的支持资料之后,我就会感到我能够再次有信心地表述一次。

这次我是通过视觉计算的启发,迅速联想到我编程过程中经常遇到的溢出问题,在仔细研究之后,开始对自己的新想法加以验证,结果得到这种算法的答案。这是一个绞尽脑汁的过程,需要知识和全神贯注的投入,我们的大脑不正是需要这样的锻炼过程吗?

参考资料



我的RSS
0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制