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乘法概念问题

回答

相关问题