3

我正在用 C++ 构建一个小型 BigInt 库，用于我的编程语言。

结构如下：

short digits[ 1000 ];
int   len;

我有一个函数，通过将字符串拆分为单个字符并将它们放入digits.

数字中的数字都是相反的，所以数字 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

以上代表了digitsbigints 2 (A) 和 100 (B) 的。 -表示未初始化的数字，它们不被访问。

所以添加上面的数字可以正常工作：从 0 开始，加 2 + 0，到 1，加 0，到 2，加 1

但：

当我想用上述结构进行乘法运算时，我的程序最终会执行以下操作：

从 0 开始，将 2 与 0 (eek) 相乘，然后到 1，...

所以很明显，对于乘法，我必须得到这样的顺序：

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

然后，一切都清楚了：从 0 开始，将 0 与 0 相乘，到 1，将 0 与 0 相乘，再到 2，将 1 与 2 相乘

  • 我怎样才能设法digits进入正确的乘法形式？
  • 我不想做任何阵列移动/翻转 - 我需要性能！
4

5 回答 5

4
  1. 你为什么用在ashort中存储数字就足够了[0..9]char
  2. 您对乘法的思考不正确。在乘法的情况下，您需要一个 double for 循环，该循环B与每个数字相乘，A并将它们相加，并以正确的 10 次幂移位。

编辑：由于一些匿名者在没有评论的情况下对此进行了投票，这基本上是乘法算法：

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

Bwith的乘法A[i]是通过一个额外的 for 循环完成的，您还可以在其中跟踪进位。这(10 ^ i)是通过偏移目标索引来实现的，因为 bigint 以 10 为底。

于 2010-04-22T12:41:57.687 回答
4

在我看来，你在问题中的例子是过度设计。由于涉及的乘法和加法的剪切数量，您的方法最终会比正常的长乘法更慢。当您一次可以乘以大约 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-23T08:47:50.580 回答
1

安德烈亚斯是对的，你必须将一个数字乘以另一个数字并相应地求和结果。我认为最好将较长的数字乘以较短的数字。如果您将十进制数字存储在您的数组 char 中确实就足够了，但是如果您想要性能，也许您应该考虑更大的类型。我不知道您的平台是什么，但在 x86 的情况下，您可以使用 32 位整数和硬件支持来提供 32 位乘法的 64 位结果。

于 2010-04-22T13:06:07.160 回答
1

好吧，看到这个问题在 11 年前就得到了回答，我想我会为正在编写自己的 BigInt 库的人提供一些指导。

首先，如果您想要纯粹的性能而不是学习如何实际编写高性能代码，请学习如何使用 GMP 或 OpenSSL。要达到 GMP 的性能水平，有一条非常陡峭的学习曲线。

好的，让我们开始吧。

  1. 当您可以使用更大的基数时，不要使用基数 10。 CPU在加减乘除方面都是神级的，好好利用吧。

假设你有两个 BigInt

a = {9,7,4,2,6,1,6,8} // length 8
b = {3,6,7,2,4,6,7,8} // length 8
// Frustrating writing for-loops to calculate a*b

当他们可以进行 1 次以 2^32 为底的计算时，不要让他们以 10 为底进行 50 次计算：

a = {97426168}
b = {36724678}
// Literally only need to type a*b

如果您的计算机可以表示的最大数是 2^64-1，请使用 2^32-1 作为 BigInt 的基数，因为它可以解决乘法时实际溢出的问题。

  1. 使用支持动态内存的结构。缩放您的程序以处理两个 100 万位数字的乘法可能会破坏您的程序，因为它在堆栈上没有足够的内存。在 C 中使用 std::vector 而不是 std::array 或 raw int[] 来利用您的内存。

  2. 了解SIMD以提高您的计算性能。菜鸟代码中的典型循环不能同时处理多个数据。学习这一点应该可以将速度从 3 倍提高到 12 倍。

  3. 了解如何编写自己的内存分配器。如果您使用 std::vector 来存储无符号整数，那么稍后您可能会遇到性能问题，因为 std::vector 仅用于一般目的。尝试根据自己的需要定制分配器，以避免每次执行计算时都进行分配和重新分配。

  4. 了解您的计算机架构和内存布局。编写您自己的汇编代码以适应特定的 CPU 架构肯定会提高您的性能。这也有助于编写您自己的内存分配器和 SIMD。

  5. 算法。对于小型 BigInt，您可以依靠您的小学乘法，但随着输入的增长，一定要好好看看 Karatsuba、Toom-Cook，最后是在您的库中实施的 FFT。

如果您遇到困难，请访问我的BigInt库。它没有自定义分配器、SIMD 代码或自定义汇编代码，但对于 BigInteger 的初学者来说应该足够了。

于 2021-04-11T01:22:01.330 回答
0

我正在用 C++ 构建一个小型 BigInt 库，用于我的编程语言。

为什么？那里有一些优秀的现有 bigint 库（例如gmp、tommath），您可以直接使用它们，而无需从头开始编写自己的库。制作自己的作品需要大量工作，而且在性能方面不太可能有那么好。（特别是，编写快速代码来执行乘法和除法比乍看之下要复杂得多。）

于 2010-04-22T13:12:33.287 回答