1

からつばアルゴリズムの実装に問題があります。私のプロジェクトでは、次のライブラリに制限されています: iostream、iomanip、cctype、cstring。また、整数の組み込み型と配列/動的配列のみを使用して数値を処理するように制限されています (符号なし整数のみが入力されます)。動的配列を使用して任意のサイズの整数を処理するクラスを作成しました。大きな整数を乗算する関数を実装する必要があり、可能であればからつばを使用したいと考えています。私が直面している問題は、大きな整数を分解し、アルゴリズムで必要な乗算を行う方法です。これは再帰的に行うべきだと思います。誰かがこれを行う方法の例を教えてくれることを望んでいました。

例えば：

動的配列に格納されている 2 つの数値があります。それらが次のとおりであるとしましょう:

X = 123456789123456789123456789 Y = 987654321987654321987654321987654321

unsigned int 型のストレージ制限を考えると、カラツバはこれをどのように処理する必要がありますか? どんな助けでも大歓迎です！

4

2 に答える 2

3

ここの疑似コードを見ると、次のように配列で使用するように少し変更できます。

procedure karatsuba(num1, num2)

    if (num1.Length < 2) or (num2.Length < 2) //Length < 2 means number < 10    
        return num1 * num2 //Might require another mult routine that multiplies the arrays by single digits

    /* calculates the size of the numbers */
    m = max(ceiling(num1.Length / 2), ceiling(num2.Length / 2))
    low1, low2 = lower half of num1, num2
    high1, high2 = higher half of num1, num2

    /* 3 calls made to numbers approximately half the size */
    z0 = karatsuba(low1,low2)
    z1 = karatsuba((low1+high1),(low2+high2))
    z2 = karatsuba(high1,high2)

    //Note: In general x * 10 ^ y in this case is simply a left-shift
    //      of the digits in the 'x' array y-places. i.e. 4 * 10 ^ 3
    //      results in the array x[4] = { 4, 0, 0, 0 }
    return (z2.shiftLeft(m*2)) + ((z1-z2-z0).shiftLeft(m)) + (z0)

数値配列に対して定義された加算、減算、および追加の 1 桁乗算ルーチンがある場合、このアルゴリズムは非常に簡単に実装できます (もちろん、桁シフトや配列分割などの他の必要なルーチンと共に)。

そのため、これらの他のルーチンの準備作業は他にもありますが、それがカラツバ ルーチンの実装方法です。

于 2013-11-07T17:21:56.803 に答える
1

疑似コードにエラーがあります。つまり、代わりに

return (z2.shiftLeft(m)) + ((z1-z2-z0).shiftLeft(m/2)) + (z0)

そのはず

return (z2.shiftLeft(m*2)) + ((z1-z2-z0).shiftLeft(m)) + (z0)
于 2016-08-09T02:35:07.663 に答える