C++で2つの64桁の数字を掛ける

Question

私はkaratsubaの乗算アルゴリズムを実装しました。私はこの方法で2桁の64桁の数字を掛けることができるように改善したいと思いますが、どうやってこれを行うのか分かりません。私は両方の数字に2のべき乗である数字の桁数が含まれていることを示唆しましたが、それは何も示唆していません。他のヒントを教えてください。数学ヒントやアルゴリズム改善のヒント。ここで

#include <iostream> 
#include <math.h> 
using namespace std; 

int getLength(long long value); 
long long multiply(long long x, long long y); 

int getLength(long long value) 
{ 
    int counter = 0; 
    while (value != 0) 
    { 
     counter++; 
     value /= 10; 
    } 
    return counter; 
} 

long long multiply(long long x, long long y) 
{ 
    int xLength = getLength(x); 
    int yLength = getLength(y); 

    // the bigger of the two lengths 
    int N = (int)(fmax(xLength, yLength)); 

    // if the max length is small it's faster to just flat out multiply the two nums 
    if (N < 10) 
     return x * y; 

    //max length divided and rounded up 
    N = (N/2) + (N % 2); 

    long long multiplier = pow(10, N); 

    long long b = x/multiplier; 
    long long a = x - (b * multiplier); 
    long long d = y/multiplier; 
    long long c = y - (d * N); 

    long long z0 = multiply(a, c); 
    long long z1 = multiply(a + b, c + d); 
    long long z2 = multiply(b, d); 


    return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N))); 

} 

int main() 
{ 
    long long a; 
    long long b; 
    cin >> a; 
    cout << '\n'; 
    cin >> b; 
    cout << '\n' << multiply(a, b) << endl; 
    return 0; 
} 

Answer 1

がヒントです：

(A + kB) * (C + kD) = AC + k(BC + AD) + k^2(BD) 

kはあなたがあなたの数字を維持しているベースのパワーである場合、これは役立ちますたとえば、kは1'000'000'000とあなたの場合。数字が10進数の場合、kの乗算は単純に数値をシフトして（ゼロを加算することによって）行われます。

とにかく、64桁の数字を2桁で区切り、上記。 AC、BC、AD、およびBDを計算するには、同様に実行できる32桁の数字のペアを掛けます。

桁のあなたの数が2のべき乗であるので、あなたが管理している数の大きさに到達するまで、あなたが半分にあなたの番号を壊す保つことができる（例えば、1桁の数字。）

ところで、それはよりはっきりしていませんあなたが64ビットか64桁の数字を話しているかどうかあなたの質問。あなたが探しているのは、64ビットの数値を掛け合わせるだけの場合です。

// I haven't actually run this code, so... 

typedef unsigned long long u64; 

u64 high32 (u64 x) {return x >> 32;} 
u64 low32 (u64 x) {return x & 0xFFFFFFFF;} 

u64 add_with_carry (u64 a, u64 b, u64 * carry) 
{ 
    u64 result = a + b; 
    if (result < a) // and/or b? 
     *carry = 1; 
    return result; 
} 

void mul (u64 a, u64 b, u64 * result_low, u64 * result_high) 
{ 
    u64 a0 = low32(a), a1 = high32(a); 
    u64 b0 = low32(b), b1 = high32(b); 

    u64 a0b0 = a0 * b0; 
    u64 a0b1 = a0 * b1; 
    u64 a1b0 = a1 * b0; 
    u64 a1b1 = a1 * b1; 

    u64 c0 = 0, c1 = 0; 
    u64 mid_part = add_with_carry(a0b1, a1b0, &c1); 

    *result_low = add_with_carry(a0b0, (low32(mid_part) << 32, &c0); 
    *result_high = high32(mid_part) + a1b1 + (c1 << 32) + c0; // this won't overflow 
} 

この実装は、上記で概説したものと同じです。標準的なC/C++では、乗算の結果得られる意味のあるビットの最大数は64であるため、一度に2つの32ビットの数値を掛けることしかできません。これは私たちがここでやっていることです。

最終結果は128ビットになります。これは、符号なし64ビットの2つの数値で返します。 4つの32ビット乗算といくつかの加算を行うことで、64ビット×64ビットの乗算を行います。サイドノートとして

、これはこのアセンブリで書き込みが例えば通常C.よりwaaaaay容易であり、それらのいくつかのケースの一つである、x64のアセンブリでは、これは文字通り2 mov S 4 mul S 4 add sです、

Answer 2

Karatsubaまたはその他の乗算を低いビット幅の算術演算に適用するには、数値をより小さい「数字」に分割する必要があります。何かする前に、あなたはので、ここではこれらの「数字」にアクセスする必要がそれを行う方法です：あなたはこのような数字を得ることができ

1234 = 1*1000 + 2*100 + 3*10 + 4 

よう

あなたは数1234を持って、10^1桁にそれを分割したいです：

x=1234; 
a0=x%10; x/=10; // 4 
a1=x%10; x/=10; // 3 
a2=x%10; x/=10; // 2 
a3=x%10; x/=10; // 1 

あなたが10^2桁たい場合：

x=1234; 
a0=x%100; x/=100; // 34 
a1=x%100; x/=100; // 12 

ここで問題になるのは、これを行うには、完全でない数字を除算する必要があるということです。数字を文字列として取得した場合、それは簡単に実行できますが、そうでないと仮定します。とても「数字」のためのベースとして2の電源を使用するのは良いアイデアですので、コンピュータは、バイナリ計算に基づいています：

x = 1234 = 0100 1101 0010 bin 

今、私たちは、その後2^4=16ベースの数字を例えばしたい場合：

a0=x%16; x/=16; // 0010 
a1=x%16; x/=16; // 1101 
a2=x%16; x/=16; // 0100 

今

あなたは2のべき乗で除算するだけビット右シフトされ、残りは、次にように表現することができることを理解場合：

a0=x&15; x>>=4; // 0010 
a1=x&15; x>>=4; // 1101 
a2=x&15; x>>=4; // 0100 

ビットシフトは、任意のビット幅に積層することができますあなたはあなたが必要なものすべてを手に入れました。

DWORD x=0x12345678; // 32 bit number 
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x 

a0=db[0]; // 0x78 
a1=db[1]; // 0x56 
a2=db[2]; // 0x34 
a3=db[3]; // 0x12 

ので、あなたは直接数字にアクセスしたり、数字からXを再構築することができます：

あなたが​​、あなたが例えば代わり​​にポインタを使用することができる場合の例 2^8ための「数字」として選択した場合しかし、それはすべてではありません

DWORD x; // 32 bit number 
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x 
db[0]=0x78; 
db[1]=0x56; 
db[2]=0x34; 
db[3]=0x12; 
// here x should be 0x12345678 

順序はプラットフォームのMSBまたはLSBの最初の順序に依存することに注意してください。これで乗算を適用できます。例えば、32×32 = 64ビット、16ビット乗算で行わは、ナイーブO(n^2)アプローチで、このように行われる：A0、A1、B0、B1は、オペランドの桁である

x(a0+a1<<16) * y(b0+b1<<16) = a0*b0 + a0*b1<<16 + a1*b0<<16 + a1*b1<<32 

。それぞれのai*bjの結果は2桁の幅ですので、それを数字に分割し、ビットシフトによってアドレス指定された結果桁に格納する必要があります。追加すると上位桁にオーバーフローが発生する可能性があることに注意してください。それを処理するには、加算のために算術幅の少なくとも2倍（16 * 16ビット - > 32ビット加算）を使用するか、キャリーフラグを使用する必要があります。残念ながら、C++のアセンブリを使用すると、Carryフラグにアクセスすることはできません。幸いにもそれがシミュレートすることができます参照してください：

そして今、あなたはより多くの情報のためにあなたのカラツバや、より高度な乗算を構築することができますが、以下を参照してください

ここ
• Fast bignum square computation