作者 主題: 有關陣列作極大整數的乘法  (閱讀 7169 次)

0 會員 與 1 訪客 正在閱讀本文。

Forwell

  • 可愛的小學生
  • *
  • 文章數: 16
    • 檢視個人資料
有關陣列作極大整數的乘法
« 於: 2005-11-01 21:16 »
Big Number應該算很常見的問題...也就是整數大到無法用int進行運算,必需用陣列來實作
我已經作出加法減法...但對於乘法依然沒啥頭緒..
我想請問一下有寫過以上程式的先進...
乘法是怎樣來達成的...
我目前想到的好像都會搞的很複雜....

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

先謝過囉~~~\

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #1 於: 2005-11-07 23:24 »
我沒仔細想過, 不過應該跟ASM的乘、除法類似吧...

dean

  • 管理員
  • 俺是博士!
  • *****
  • 文章數: 1279
  • 性別: 男
  • 有些人,有些事,值得.
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #2 於: 2005-11-08 03:50 »
呵呵,中國人的智慧..算盤...
想像一下算盤的乘法..
再看看算盤像不像一個陣列..

Forwell

  • 可愛的小學生
  • *
  • 文章數: 16
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #3 於: 2005-11-08 21:18 »
我用了最笨的方法寫~~~累加...唉...碰到天文數字就葛屁
另外一個就是像我們平常寫的那種形式...
不過陣列的值要位移...

 :lol:

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #4 於: 2005-11-09 17:39 »
你所謂的天文數字是大到哪裏??

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料

nirvanaphoenix

  • 活潑的大學生
  • ***
  • 文章數: 227
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #6 於: 2005-11-09 20:14 »
其實這題我也找了好多天..發現好多1.25" 的磁片都長霉了 ^^|||
..因為以前用BASIC寫出來過(經過學長提示)....可是現在卻寫不出來 @@

15年前這個題目,
可是高中程式(BASIC)競賽的題目 : n! 運算喔~
我有個學長,就靠這題拿了第二名...... (根據不才模糊的記憶)
記得那時用了四位數來給程式算階乘...
Run 了四小時左右才把答案弄出來 .....
386 XT 的時代  好懷念啊... I am old .. Orz
^^^打錯了...286才對
img]http://pics14.webs-tv.net/2/userfile/n/nirvanaphoenix/album/143bab414303c2.gif[/img]不知何時涅盤掉了的鳳凰.. >_<

Forwell

  • 可愛的小學生
  • *
  • 文章數: 16
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #7 於: 2005-11-09 21:27 »
引述: "學飛的小鳥"
你所謂的天文數字是大到哪裏??

就是可以到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值
}

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #8 於: 2005-11-09 21:38 »
引述: "nirvanaphoenix"
其實這題我也找了好多天..發現好多1.25" 的磁片都長霉了 ^^|||
..因為以前用BASIC寫出來過(經過學長提示)....可是現在卻寫不出來 @@

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


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

nirvanaphoenix

  • 活潑的大學生
  • ***
  • 文章數: 227
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #9 於: 2005-11-09 21:47 »
引述: "學飛的小鳥"

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

怎麼感覺兩個 oldman在回憶從前...
再懷念下去,我們就... 離題了  :P
img]http://pics14.webs-tv.net/2/userfile/n/nirvanaphoenix/album/143bab414303c2.gif[/img]不知何時涅盤掉了的鳳凰.. >_<

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #10 於: 2005-11-09 23:34 »
引述: "nirvanaphoenix"
引述: "學飛的小鳥"

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

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


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

對否??

nirvanaphoenix

  • 活潑的大學生
  • ***
  • 文章數: 227
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #11 於: 2005-11-09 23:50 »
回樓上大大....我不知道耶..
G神好像有答案 :P
img]http://pics14.webs-tv.net/2/userfile/n/nirvanaphoenix/album/143bab414303c2.gif[/img]不知何時涅盤掉了的鳳凰.. >_<

學飛的小鳥

  • 活潑的大學生
  • ***
  • 文章數: 349
    • 檢視個人資料
有關陣列作極大整數的乘法
« 回覆 #12 於: 2005-11-10 09:36 »
引述: "Forwell"
引述: "學飛的小鳥"
你所謂的天文數字是大到哪裏??

就是可以到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