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 を足し、オーバーフローは次の桁に足されます)

次のように、2 つの数値がどのように格納されるかを考えてみましょう。

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

上記digitsは、bigint 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

質問のあなたの例は、私の意見では最高の状態で過剰設計です。乗算と加算のせん断数が関係するため、アプローチは通常の長い乗算よりもさらに遅くなります。一度に約9を掛けることができる場合は、一度に1桁の数字で作業することに制限しないでください。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 に答える
4
  1. ashortに数字を格納するために使用するのはなぜですか?[0..9]char
  2. あなたは掛け算について間違った考えをしています。乗算の場合、B各桁で乗算しA、正しい 10 の累乗でシフトして合計する double for ループが必要です。

編集:一部の匿名がコメントなしでこれに反対票を投じたため、これは基本的に乗算アルゴリズムです:

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 に答える
1

アンドレアスは正しいです。一方の数値にもう一方の桁の各桁を掛けて、それに応じて結果を合計する必要があります。長い数字に短い数字の桁を掛けたほうがいいと思います。配列に10進数を格納する場合は、charで十分ですが、パフォーマンスが必要な場合は、より大きな型を検討する必要があります。プラットフォームが何であるかはわかりませんが、たとえばx86の場合、32ビット整数とハードウェアサポートを使用して、32ビット乗算の64ビット結果を得ることができます。

于 2010-04-22T13:06:07.160 に答える
0

私のプログラミング言語で使用するために、C++ で小さな BigInt ライブラリを構築しています。

なんで？いくつかの優れた既存の bigint ライブラリ ( gmp、tommath など) があり、独自にゼロから作成する必要はありません。独自のものを作成するのは大変な作業であり、結果としてパフォーマンスの面でそれほど優れたものになる可能性は低くなります。(特に、乗算と除算を実行するための高速なコードを作成することは、一見したよりもかなりトリッキーです。)

于 2010-04-22T13:12:33.287 に答える