主題: 有關陣列作極大整數的乘法

[Forwell]

Big Number應該算很常見的問題...也就是整數大到無法用int進行運算，必需用陣列來實作
我已經作出加法減法...但對於乘法依然沒啥頭緒..
我想請問一下有寫過以上程式的先進...
乘法是怎樣來達成的...
我目前想到的好像都會搞的很複雜....

或者先前有文章討論過的也煩請告知一下...我試著用一些keyword搜尋過..沒有相關文章 :lol:

先謝過囉~~~\

[學飛的小鳥]

我沒仔細想過, 不過應該跟ASM的乘、除法類似吧...

[dean]

呵呵,中國人的智慧..算盤...
想像一下算盤的乘法..
再看看算盤像不像一個陣列..

[Forwell]

我用了最笨的方法寫～～～累加．．．唉．．．碰到天文數字就葛屁
另外一個就是像我們平常寫的那種形式．．．
不過陣列的值要位移．．．

 :lol:

[學飛的小鳥]

你所謂的天文數字是大到哪裏??

[學飛的小鳥]

看看這頁 http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/BigNumber.htm

[nirvanaphoenix]

其實這題我也找了好多天..發現好多1.25" 的磁片都長霉了 ^^|||
..因為以前用BASIC寫出來過（經過學長提示）....可是現在卻寫不出來 @@

15年前這個題目，
可是高中程式(BASIC)競賽的題目 : n! 運算喔~
我有個學長，就靠這題拿了第二名...... （根據不才模糊的記憶)
記得那時用了四位數來給程式算階乘...
Run 了四小時左右才把答案弄出來 .....
386 XT 的時代  好懷念啊... I am old .. Orz
^^^打錯了...286才對

[Forwell]

你所謂的天文數字是大到哪裏??

就是可以到4~50位啦~~~但會跑到翻掉～～～




程式白痴用的累加法....
有人會用到的話...嗯~~加減看...
混用cout和printf是不好的用法~~~但我有我的苦衷...
void multiplication()
{
   int n=1;
   int i,j;
   int digit=0;
   bool result=false;
                b_temp[1]=1;
   while(!result)
   {
     b_temp[1]++;//b_temp[]開始累加
      for(i=1;i<=asize;i++)
     {
          a+=a_temp;//a陣列進行不斷的加總
          if(a>9)
          {
              a[i+1]+=a/10;
              a=a%10;
          }

     }
     for(i=1;i<=bsize;i++)//b_temp[]累加其間進行進位的動作
     {
        if(b_temp>9)
           b_temp[i+1]+=b_temp/10;
            b_temp=b_temp%10;
     }
     /*for(i=1;i<=bsize;i++)//測試用，觀察b_temp的加總狀況
     {
        cout<<b_temp;
     }*/
     result=diag_equal(b,b_temp);//比較b_temp的陣列內容是否已已經和b陣列相等...若為真的話則結束加總(也就是完成乘法)

   
   }
    for(j=(asize+bsize);j>0;j--)//這裡列印的位數大小是以a b二陣列大小的和
   {
      printf("%d",a[j]);//列印運算結果
   }
}

bool diag_equal(int *b,int *b_temp)//比較陣列是否相同的Function
{
   bool diagnose;//宣告布林變數
   vector<int> v1(b,b+(bsize+1)),v2(b_temp,b_temp+(bsize+1));//把b及b_temp陣列建立成向量v1,v2
    diagnose=equal(v1.begin(),v1.end(),v2.begin());//比較二者是否相同
   //cout<<endl;
   //cout<<"the result(0 or 1) is "<<result<<endl;觀察用程式碼
    return diagnose;//回傳result值
}

[學飛的小鳥]

其實這題我也找了好多天..發現好多1.25" 的磁片都長霉了 ^^|||
..因為以前用BASIC寫出來過（經過學長提示）....可是現在卻寫不出來 @@

15年前這個題目，
可是高中程式(BASIC)競賽的題目 : n! 運算喔~
我有個學長，就靠這題拿了第二名...... （根據不才模糊的記憶)
記得那時用了四位數來給程式算階乘...
Run 了四小時左右才把答案弄出來 .....
386 XT 的時代  好懷念啊... I am old .. Orz

嗯...以前的電腦在效能上雖然跟現在差好多..
以前是用 APPLE][ 或 8088 跑數值分析、物理模擬..
雖然很累, 不過很感覺很充實, 很懷念當年寫程式的生活...

[nirvanaphoenix]

....
 很懷念當年寫程式的生活...

怎麼感覺兩個 oldman在回憶從前...
再懷念下去，我們就... 離題了  

[學飛的小鳥]

....
 很懷念當年寫程式的生活...

怎麼感覺兩個 oldman在回憶從前...
再懷念下去，我們就... 離題了  

嗯嗯.....ok
我想問一下...
50! = 30414093201713378043612608166064768844377641568960512000000000000

對否??

[nirvanaphoenix]

回樓上大大....我不知道耶..
G神好像有答案

[學飛的小鳥]

你所謂的天文數字是大到哪裏??

就是可以到4~50位啦~~~但會跑到翻掉～～～

參考這裏  http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/BigNumber.htm
改寫後執行的結果如下...

12804747411456573 * 6765432123456789 = 86629649470218464959026315524097
用 windows 的小算盤驗算過, 無誤

86629649470218464959026315524097 * 86629649470218464959026315524097 = 7504696167332922366543902979654607266277966521740854499787665409
windows 小算盤驗算 = 7.5046961673329223665439029796546e+63
P4 3.0G 大概花費 100 ms