C++ BigInt乘法概念問題

我正在C++中構建一個用於我的編程語言的小型BigInt庫。C++ BigInt乘法概念問題

的結構是這樣的：

short digits[ 1000 ]; 
int len;

我有一個通過拆分其分成單個字符並將其付諸digits一個字符串轉換爲BIGINT的功能。

中位數的數字都是顛倒的，所以數字123看起來像下面這樣：

digits[0]=3 digits[1]=3 digits[2]=1

我已經成功地編寫了加入功能，它完美的作品。

它的工作原理有點像這樣：

overflow = 0 
for i ++ until length of both numbers exceeded: 
    add numberA[ i ] to numberB[ i ] 
    add overflow to the result 
    set overflow to 0 
    if the result is bigger than 10: 
    substract 10 from the result 
    overflow = 1 
    put the result into numberReturn[ i ]

（溢出是在這種情況下，當我添加1〜9個究竟：10。減去10，加1到溢出，溢出被添加到下一個數字）

所以認爲的兩個數是如何存儲的，像那些：

0 | 1 | 2 
    --------- 
A 2 - - 
B 0 0 1

上面表示bigints 2（A）和100（B）的digits。 -表示未初始化的數字，它們不被訪問。

因此將上述號碼正常工作：從0開始，加2 + 0，到1，加0，進入2，加1

但是：

當我想做乘法與上述的結構，我的計劃最後也做了以下內容：

從0開始，乘2 0（伊克），去1，...

所以很明顯，對於乘法，我必須得到這樣的訂單：

0 | 1 | 2 
    --------- 
A - - 2 
B 0 0 1

然後，一切都將是明確的：從0開始，0乘以0，到1，0乘以0，進入2，乘以1與2

哪有我設法讓digits進入乘法的正確形式？
我不想做任何陣列移動/翻轉 - 我需要性能！

來源

2010-04-22 Kapo

你所謂的「溢出」是大多數人稱之爲「攜帶」的東西。 – 2010-04-22 12:50:16

[0..9]

char

short

你在想關於不正確的乘法
。在乘法的情況下，您需要一個double for循環，將B與A中的每個數字相乘，然後將它們以正確的十冪進行移位。

編輯：由於一些匿名downvoted這個沒有評論這基本上是乘算法：

bigint prod = 0 
for i in A 
    prod += B * A[i] * (10^i)

的B與A[i]乘法是通過一個額外的for循環，你還跟蹤完成的進位。 (10^i)是通過避免目標指數實現的，因爲bigint位於第10位。

來源

2010-04-22 12:41:57

謝謝，這真的很簡單，很容易實現！ – Zpalmtree 2017-11-24 23:16:53

Andreas是對的，您必須將一個數字乘以另一個數字並相應地求和結果。我認爲最好將較長的數字乘以較短數字的數字。如果你在你的數組中存儲了十進制數字，char就足夠了，但是如果你想要性能，也許你應該考慮更大的類型。我不知道你的平臺是什麼，但是以x86爲例，你可以使用32位整數和硬件支持來給出32位乘法的64位結果。

來源

2010-04-22 13:06:07

+1你是對的。如果你想要性能，你應該使用int的整個範圍。 – 2010-04-22 13:21:11

我正在C++中構建一個小的BigInt庫，以用於我的編程語言。

爲什麼？有一些優秀的現有bigint庫（例如，gmp,tommath），你可以使用而不必從頭開始編寫自己的。製作你自己的作品很多，結果在性能上不太可能好。（特別是，寫快代碼執行乘法和除法比乍看起來要複雜得多）。

來源

2010-04-22 13:12:33

爲了學習體驗？那裏有很多事情沒有被其他人改善。 – 2010-04-22 13:36:05

但這很荒謬。他說他正在做一個編程語言的實現（大概是用C++編寫的），他需要性能。在那個時候，寫你自己的東西肯定是浪費時間。 – 2010-04-22 14:00:54

@Donal Fellows有人可能會爭辯說，編寫自己的編程語言的整個想法是浪費時間。（順便說一句，-1不是我） – 2010-04-22 16:44:02

你的問題中的例子是我認爲最好的過度工程。由於涉及的乘法和加法的剪切數量，你的方法最終會比正常的長乘法更慢。不要限制自己一次只能在一個基數上工作，一次可以乘以大約9！！將base10字符串轉換爲hugeval，然後然後對其執行操作。不要直接對字符串進行操作。你會發瘋。以下是一些演示加法和乘法的代碼。更改M以使用更大的類型。你也可以使用std :: vector，但是你錯過了一些優化。

#include <iostream> 
#include <string> 
#include <algorithm> 
#include <sstream> 
#include <cstdlib> 
#include <cstdio> 
#include <iomanip> 

#ifdef _DEBUG 
#include <assert.h> 
#define ASSERT(x) assert(x) 
#else 
#define ASSERT(x) 
#endif 

namespace Arithmetic 
{ 
    const int M = 64; 
    const int B = (M-1)*32; 

    struct Flags 
    { 
     Flags() : C(false),Z(false),V(false),N(false){} 
     void Clear() 
     { 
      C = false; 
      Z = false; 
      V = false; 
      N = false; 
     } 
     bool C,Z,V,N; 
    }; 

    static unsigned int hvAdd(unsigned int a, unsigned int b, Flags& f) 
    { 
     unsigned int c; 
     f.Clear(); 
     //b = -(signed)b; 
     c = a + b; 

     f.N = (c >> 31UL) & 0x1; 
     f.C = (c < a) && (c < b); 
     f.Z = !c; 
     f.V = (((signed)a < (signed)b) != f.N); 

     return c; 
    } 

    static unsigned int hvSub(unsigned int a, unsigned int b, Flags& f) 
    { 
     unsigned int c; 
     f.Clear(); 
     c = a - b; 

     //f.N = ((signed)c < 0); 
     f.N = (c >> 31UL) & 0x1; 
     f.C = (c < a) && (c < b); 
     f.Z = !c; 
     f.V = (((signed)a < (signed)b) != f.N); 

     return c; 
    } 


    struct HugeVal 
    { 
     HugeVal() 
     { 
      std::fill(part, part + M, 0); 
     } 
     HugeVal(const HugeVal& h) 
     { 
      std::copy(h.part, h.part + M, part); 
     } 
     HugeVal(const std::string& str) 
     { 
      Flags f; 
      unsigned int tmp = 0; 

      std::fill(part, part + M, 0); 

      for(unsigned int i=0; i < str.length(); ++i){ 
       unsigned int digit = (unsigned int)str[i] - 48UL; 
       unsigned int carry_last = 0; 
       unsigned int carry_next = 0; 
       for(int i=0; i<M; ++i){ 
        tmp = part[i]; //the value *before* the carry add 
        part[i] = hvAdd(part[i], carry_last, f); 
        carry_last = 0; 
        if(f.C) 
         ++carry_last; 
        for(int j=1; j<10; ++j){ 
         part[i] = hvAdd(part[i], tmp, f); 
         if(f.C) 
          ++carry_last; 
        } 
       } 
       part[0] = hvAdd(part[0], digit, f); 
       int index = 1; 
       while(f.C && index < M){ 
        part[index] = hvAdd(part[index], 1, f); 
        ++index; 
       } 
      } 
     } 
     /* 
     HugeVal operator= (const HugeVal& h) 
     { 
      *this = HugeVal(h); 
     } 
     */ 
     HugeVal operator+ (const HugeVal& h) const 
     { 
      HugeVal tmp; 
      Flags f; 
      int index = 0; 
      unsigned int carry_last = 0; 
      for(int j=0; j<M; ++j){ 
       if(carry_last){ 
        tmp.part[j] = hvAdd(tmp.part[j], carry_last, f); 
        carry_last = 0; 
       } 
       tmp.part[j] = hvAdd(tmp.part[j], part[j], f); 
       if(f.C) 
        ++carry_last; 
       tmp.part[j] = hvAdd(tmp.part[j], h.part[j], f); 
       if(f.C) 
        ++carry_last; 
      } 
      return tmp; 
     } 
     HugeVal operator* (const HugeVal& h) const 
     { 
      HugeVal tmp; 

      for(int j=0; j<M; ++j){ 
       unsigned int carry_next = 0; 
       for(int i=0;i<M; ++i){ 

        Flags f; 

        unsigned int accum1 = 0; 
        unsigned int accum2 = 0; 
        unsigned int accum3 = 0; 
        unsigned int accum4 = 0; 

        /* Split into 16-bit values */ 
        unsigned int j_LO = part[j]&0xFFFF; 
        unsigned int j_HI = part[j]>>16; 
        unsigned int i_LO = h.part[i]&0xFFFF; 
        unsigned int i_HI = h.part[i]>>16; 

        size_t index = i+j; 
        size_t index2 = index+1; 

        /* These multiplications are safe now. Can't overflow */ 
        accum1 = j_LO * i_LO; 
        accum2 = j_LO * i_HI; 
        accum3 = j_HI * i_LO; 
        accum4 = j_HI * i_HI; 


        if(carry_next){ //carry from last iteration 
         accum1 = hvAdd(accum1, carry_next, f); //add to LSB 
         carry_next = 0; 
         if(f.C) //LSB produced carry 
          ++carry_next; 
        } 

        /* Add the lower 16-bit parts of accum2 and accum3 to accum1 */ 
        accum1 = hvAdd(accum1, (accum2 << 16), f); 
        if(f.C) 
         ++carry_next; 
        accum1 = hvAdd(accum1, (accum3 << 16), f); 
        if(f.C) 
         ++carry_next; 



        if(carry_next){ //carry from LSB 
         accum4 = hvAdd(accum4, carry_next, f); //add to MSB 
         carry_next = 0; 
         ASSERT(f.C == false); 
        } 

        /* Add the higher 16-bit parts of accum2 and accum3 to accum4 */ 
        /* Can't overflow */ 
        accum4 = hvAdd(accum4, (accum2 >> 16), f); 
        ASSERT(f.C == false); 
        accum4 = hvAdd(accum4, (accum3 >> 16), f); 
        ASSERT(f.C == false); 
        if(index < M){ 
         tmp.part[index] = hvAdd(tmp.part[index], accum1, f); 
         if(f.C) 
          ++carry_next; 
        } 
        carry_next += accum4; 
       } 
      } 
      return tmp; 
     } 
     void Print() const 
     { 
      for(int i=(M-1); i>=0; --i){ 

       printf("%.8X", part[i]); 
      } 
      printf("\n"); 
     } 
     unsigned int part[M]; 
    }; 

} 


int main(int argc, char* argv[]) 
{ 

    std::string a1("273847238974823947823941"); 
    std::string a2("324230432432895745949"); 

    Arithmetic::HugeVal a = a1; 
    Arithmetic::HugeVal b = a2; 

    Arithmetic::HugeVal d = a + b; 
    Arithmetic::HugeVal e = a * b; 

    a.Print(); 
    b.Print(); 
    d.Print(); 
    e.Print(); 
    system("pause"); 
}

來源

2010-04-23 08:47:50

C++ BigInt乘法概念問題

回答

相關問題