3

宿題プロジェクト用の小さなbignumライブラリを書いています。カラツバ掛け算を実装するのですが、その前に単純な掛け算ルーチンを書きたいと思います。

オンラインで無料で入手できる「Modern Computer Arithmetic」というタイトルの Paul Zimmerman によって書かれたガイドに従っています。

4 ページに、小学校の乗算を実行する BasecaseMultiply というタイトルのアルゴリズムの説明があります。

B^j が 1, j 回の桁シフトであるステップ 2、3 を理解しています。しかし、A*b_j があるステップ 1 と 3 がわかりません。bignum の乗算がまだ定義されていない場合、この乗算はどのように実行されるのでしょうか?

このアルゴリズムの操作「*」は、単に繰り返し加算法ですか?

ここまで書いてきた部分です。私はそれらをユニットテストしたので、ほとんどの場合正しいようです：

bignum に使用する構造は次のとおりです。

#define BIGNUM_DIGITS 2048
typedef uint32_t u_hw; // halfword
typedef uint64_t u_w; // word

typedef struct {
    unsigned int sign; // 0 or 1
    unsigned int n_digits;
    u_hw digits[BIGNUM_DIGITS];
} bn;

現在利用可能なルーチン:

bn *bn_add(bn *a, bn *b); // returns a+b as a newly allocated bn
void bn_lshift(bn *b, int d); // shifts d digits to the left, retains sign
int bn_cmp(bn *a, bn *b); // returns 1 if a>b, 0 if a=b, -1 if a<b
4

2 に答える 2

2

少し前に乗算アルゴリズムを書きましたが、このコメントが一番上にあります。同じサイズ (同じ n_digits) の 2 つの数値 x と y がある場合、このように乗算して n を取得すると、桁数が 2 倍になります。アルゴリズムの複雑さの一部は、n_digits が両方の入力で同じでない場合に、どのビットを乗算しないかを計算することに起因します。

右から n0 は x0*y0 で、オーバーフローを節約します。ここで、n1 は x1*y0 と y1*x0 の合計であり、前のオーバーフローが桁サイズだけシフトされます。64 ビット演算で 32 ビットの数字を使用している場合、それは n0 = low32(x0*y0) を意味し、high32(x0*y0) をオーバーフローとして運びます。実際に 32 ビットの数字を使用した場合、64 ビットを超えないと中央の列を追加できないことがわかります。したがって、おそらく 30 または 31 ビットの数字を使用します。

1 桁あたり 30 ビットの場合、2 つの 8 桁の数字を掛け合わせることができます。最初に、最大 8 桁の n_digits を持つ 2 つの小さなバッファーを受け入れ、算術演算にネイティブの数学を使用するようにこのアルゴリズムを作成します。次に、任意のサイズの n_digits を取り、最初のバージョンを shift および add メソッドと共に使用して、一度に 8x8 の数字のチャンクを乗算して、再度実装します。

/*
    X*Y = N

                          x0     y3
                            \   /  
                             \ /   
                              X    
                      x1     /|\     y2
                        \   / | \   /  
                         \ /  |  \ /   
                          X   |   X    
                  x2     /|\  |  /|\     y1
                    \   / | \ | / | \   /  
                     \ /  |  \|/  |  \ /   
                      X   |   X   |   X    
              x3     /|\  |  /|\  |  /|\     y0
                \   / | \ | / | \ | / | \   /
                 \ /  |  \|/  |  \|/  |  \ /
                  V   |   X   |   X   |   V
                  |\  |  /|\  |  /|\  |  /|
                  | \ | / | \ | / | \ | / |
                  |  \|/  |  \|/  |  \|/  |
                  |   V   |   X   |   V   |
                  |   |\  |  /|\  |  /|   |
                  |   | \ | / | \ | / |   |
                  |   |  \|/  |  \|/  |   |
                  |   |   V   |   V   |   |
                  |   |   |\  |  /|   |   |
                  |   |   | \ | / |   |   |
                  |   |   |  \|/  |   |   |
                  |   |   |   V   |   |   |
                  |   |   |   |   |   |   |
              n7  n6  n5  n4  n3  n2  n1  n0
*/
于 2010-05-02T21:51:34.433 に答える
1

A*b_j を実行するには、bignum と 1 桁の小学校の乗算を実行する必要があります。最終的には、2 桁の製品をまとめて追加する必要があります。

bn *R = ZERO;
for(int i = 0; i < n; i++) {
  bn S = {0, 2};
  S.digits[0] = a[i] * b_j;
  S.digits[1] = (((u_w)a[i]) * b_j) >> 32;  // order depends on endianness
  bn_lshift(S, i);
  R = bn_add(R, S);
}

もちろん、これは非常に非効率的です。

于 2010-05-02T21:58:37.233 に答える