Karatsubaアルゴリズムのオーバーフロー

Question

私は勉強してきましたKaratsuba's algorithm on Wikipedia 私はこのセクションで停止しました。なぜこのアルゴリズムにオーバーフローがありますか？この問題を解決するために彼が行った手順はわかりません。私の問題のスクリーンショット

Answer 1

LESTのみスターターのために正の数を考慮してください。 8ビットの数字/数字をx0,x1,y0,y1にすることができます。

x0*y0 -> 8bit * 8bit -> 16 bit 

これは、16ビットの結果までを生成します。

は、我々は8ビットの乗算を適用します。トップ値は次のとおりです。

FFh*FFh = FE01h 
255*255 = 65025 

今、私たちはカラツバに戻る場合

X = x0 + x1<<8 
Y = y0 + y1<<8 
Z = X*Y = z0 + z1<<8 + z2<<16 

今すぐz1は、17ビットのトップとしてあることをzi

z2 = x1*y1   -> 16 bit 
z1 = x1*y0 + x0*y1 -> 17 bit 
z0 = x0*y0   -> 16 bit 

注意のビット幅を見てみましょうみましょう値は

65025+65025 = 130050 

したがって、ziのそれぞれが8ビットをオーバーフローします。これを処理するには、最低位の8ビットのみを取り、残りの部分を上位桁に追加します（キャリーの伝播など）。したがって、通常は乗算の​​HW実装はこれを単独で処理し、1つではなく2つの単語として結果を返します。

したがって、16ビット乗算の結果は32ビットです。 8ビットのサブ結果を追加するには、3つの数値を加算するか、9ビット（または8ビット+ 1のキャリー）を1つずつ追加して伝播する必要があるため、少なくとも10ビットが必要です。

これに符号付きの値を追加する場合は、もう1ビットの符号が必要です。これを回避するには、オペランドの兆候を覚えて、abs値を使用して...元の兆候に応じて結果の符号を設定します。詳細については

は、これらを参照してください。私はまだZ1は、17ビットのトップvalue..whereはないです理由を理解いけないmuch..except

• C++ 32bit * 32bit multiplication without asm
• Fast bignum square computation