| 一種沒有溢出的算法來解決乘法計算 |
| 送交者: 茶樹油之家 2011年07月01日10:18:02 於 [教育學術] 發送悄悄話 |
我前一段寫了一篇博文分享過一紐約長島女孩(非常可愛聰明的大女孩)用視覺方式計算兩位數的乘法。但是我很快發現,如果最後一位數和中間的和數都大於9的話,就會有一個進位的問題。而且如果視圖中間的交叉點太多,計算起來也十分繁瑣。 但我很快發現這種視覺的方式實際上是將傳統的豎式計算方法用圖像的方式來表達出來,這的確是十分有想象力的。我仔細研究傳統的豎式算法,我發現計算的過程實際上兩個單數不斷相乘的過程,個位數留下,如果有十位數,則十位數進位,然後不斷重複的過程。這用編程的方式來說,實際上可以用兩個循環來模擬進行。因為是兩個單數的相乘,這不會有溢出的問題,在計算過程中,將最左邊的各位數不斷留下來,存放在一個字符的串變量之中,整個循環完成之後,就可以得到結果。這樣就不會有整數溢出的問題(電腦計算過程中,整數是有一定上限的,超過這個上限就會出現溢出)。 計算程序下面是我編寫的計算程序: 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 ; } 我的算法肯定不是最優化的方式,如有高手,請多多糾正指導。 原程序和計算網頁注意:該HTML網頁沒有檢測你的輸入數據是否是整數,如果輸入其它無效字符則不會得到計算結果。 如果你是用Safari,Chrome,Firefox網絡瀏覽器,右點鼠標鍵打開監視網頁元素(inspect elements),然後點擊Console,這樣你還會看到計算過程中我加入的debug計算詳細信息: ![]() 隨後感 英特網的出現使得信息出現空前的膨脹,我記得一次在聽《吳東相對論》播客中,他們提到現在許多多人因為網絡信息太多而不願讀書,而且對許多信息也沒有真正的分析的興趣,什麼都是一覽而過,大腦越來越遲鈍。對於年輕來說,大量的信息反而造成他們的學習能力降低。 我每天也快速瀏覽許多網絡中的許多東西,但是我有一個習慣,如果發現特別有興趣的東西,我特別喜歡品味和琢磨,有機會和同事或朋友們分享。別小看分享過程,這是一個將吸收的東西再加工和表述的過程。我經常發現在表述的過程中突然卡住,無法將我的想法流暢的表述出來。在這種情況下,我再回去認真讀覽,查詢其它的資料,直到我感到能夠完全理解和備有豐富的支持資料之後,我就會感到我能夠再次有信心地表述一次。 這次我是通過視覺計算的啟發,迅速聯想到我編程過程中經常遇到的溢出問題,在仔細研究之後,開始對自己的新想法加以驗證,結果得到這種算法的答案。這是一個絞盡腦汁的過程,需要知識和全神貫注的投入,我們的大腦不正是需要這樣的鍛煉過程嗎? 參考資料
![]() |
|
![]() |
![]() |
| 實用資訊 | |
|
|
| 一周點擊熱帖 | 更多>> |
| 一周回復熱帖 |
| 歷史上的今天:回復熱帖 |
| 2010: | 曾廣泛分布在東亞的棕色人種的消退 and | |
| 2010: | 回遊的海歸: 我們是否應該回國? | |
| 2009: | 從漢語罵人豬談漢語的局限性 | |
| 2009: | 歐陽先生差矣 | |
| 2008: | 談我帖子“被罵的狗血噴頭” | |
| 2008: | 與李銀河商榷-誰是當代中國的真英雄? | |
| 2007: | 科學的三種人 | |
| 2006: | 香港大學超清華北大?談大學排名三大誤 | |



我前一段寫了一篇博文分享過一紐約長島女孩(非常可愛聰明的大女孩)用視覺方式計算兩位數的乘法。但是我很快發現,如果最後一位數和中間的和數都大於9的話,就會有一個進位的問題。而且如果視圖中間的交叉點太多,計算起來也十分繁瑣。




