設萬維讀者為首頁 廣告服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:諍友
萬維讀者網 > 教育學術 > 帖子
一種沒有溢出的算法來解決乘法計算
送交者: 茶樹油之家 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 | 全球最佳航空公司出爐:海航獲五星
海外華人福利!在線看陳建斌《三叉戟》熱血歸回 豪情築夢 高清免費看 無地區限制