4

私はコンピュータ サイエンスを専攻しており、アセンブリ言語が整数除算関数を処理する方法に興味があります。除算と mod の両方を与えながら、単純に分子に加算するのは非現実的であるように思われるので、ビット シフト、減算、および 2 つのルックアップ テーブルを使用して除算する別の方法を考え出しました。

基本的に、関数は分母を取り、2 の最大乗数に基づいて「ブロック」を作成します。したがって、15 で割ると 4 のバイナリ ブロックが作成され、5 で割ると 3 のバイナリ ブロックが作成されます。次に、最初の 2^block- を生成します。サイズは分母の倍数。倍数ごとに、最初のブロックの値をキーにして、最初のブロックの後に値をルックアップ テーブルに書き込みます。

例: 2 進数の 5 の倍数 - ブロック サイズ 3 (8 進数)

000 000 **101** - 5 maps to 0    
000 001 **010** - 2 maps to 1  
000 001 **111** - 7 maps to 1  
000 010 **100** - 4 maps to 2  
000 011 **001** - 1 maps to 3  
000 011 **110** - 6 maps to 3  
000 100 **011** - 3 maps to 4  
000 101 **000** - 0 maps to 5

したがって、実際の手順には、最初のブロックを取得し、最初のブロックを左にビットシフトし、ブロックがマップする値を減算することが含まれます。結果の数値が 0 になる場合は完全に割り切れ、値が負になる場合はそうではありません。

別の列挙ルックアップ テーブルを追加すると、値が入ったときにカウンターにマップされ、除算の結果を計算できます。

例: 再び 5 の倍数

5 maps to 1  
2 maps to 2  
7 maps to 3  
4 maps to 4  
1 maps to 5  
6 maps to 6  
3 maps to 7  
0 maps to 8

あとは、すべてのブロックをカウンター テーブルにマッピングするだけで、答えが得られます。
この方法にはいくつかの問題があります。

  1. 答えが完全に割り切れない場合、関数はジャンクを返します。
  2. 整数値が大きい場合、これは機能しません。これは、32 ビットまたは 64 ビット整数の最後で 5 ブロック サイズが切り捨てられるためです。
  3. C の標準除算よりも約 100 倍遅いです。
  4. 分母が除数の因数である場合、ブロックは複数の値にマップする必要があり、さらに多くのテーブルが必要になります。これは素因数分解で解決できますが、簡単/迅速な素因数分解について私が読んだすべての方法には、除算が含まれており、この目的を無効にしています。

質問が 2 つあります。まず、これに似たアルゴリズムは既に存在しますか? 辺りを見回しましたが、似たようなものは見当たらないようです。第二に、実際のアセンブリ言語は整数除算をどのように処理しますか?

スタック オーバーフローに投稿するのはこれが初めてです。

4

1 に答える 1

1

申し訳ありませんが、返信が遅くなりました。わかりました、最初にあなたの質問のコメント者に関して:彼らは、アセンブリメモニック DIV または IDIV がassembly で異なる命令を使用して達成しようとしていると考えています。私には、DIV および IDIV によって選択されたオペコードがハードウェアでどのように除算を達成するかを知りたいようです。私の知る限り、Intel は SRT アルゴリズム (ルックアップ テーブルを使用) を使用し、AMD は Goldschmidt アルゴリズムを使用します。あなたがしていることはSRTに似ていると思います。ここでそれらの両方を見ることができます：

http://en.wikipedia.org/wiki/Division_%28digital%29

于 2011-02-21T11:02:47.127 に答える