係数の計算方法についてさらに説明します。
実数のアイデアとケース
たとえば、コードがdouble x = a / 2.5の場合、これはx = a *（1.0 / 2.5）またはx = a * 0.4に置き換えることができます。 コードは高速になりますが、精度が低下する場合があります。 整数の場合、額にこのようなトリックは機能しません。 係数は1（ゼロ）より小さくなります。 固定小数点数（仮数N ）を使用できます： int x = a / b = a * B >> N、ここでB =（1 << N）/ b 問題は、計算されたxが正解とは1異なることがあり、整数では受け入れられないことです。
アルゴリズム
単純化するために、非負の数のみを使用します。 数学的定式化：
既知の整数bについて、すべての整数a に対して0≤a <（1 << N ） 、 x = [a / b] = [a * B >> M]である整数のペアM、Bを見つけます。ここで[]は整数ですそして、>> Mは、 aを2のM乗で割る（および<<乗算する）ことです。
1.0 / bをバイナリ形式（場合によっては無限に長い数）で記述します。最初のMビットは整数Cとして示され、残りのビット（尾部余り）はDとして、 1.0 / b = C >> M + D、D <（1> > M） 。
B = Cかつa * D≤1 （ N≤M ）の場合に何が起こるか見てみましょう：
x = [a / b] = [a *（C >> M + D）] = [a * C >> M + a * D]≥[a * C >> M] + [a * D] = [ a * C >> M]
Bが数値1 / bの最初のMビットであり、残りのビットが破棄される（ゼロに置き換えられる）場合、正しい値が得られることがあり、 xよりも1少ないことがあります。 これは、* Dが破棄されるために発生します。これは、 1未満ではありますが、全体を変更する可能性があります。
Bを1増やしてみて（ B = C + 1 ）、それから：
[a *（C + 1）>> M] = [a * C >> M + a *（1 >> M）]≥[a * C >> M + a * D] = [a *（C> > M + D）] = [a / b] = x
ここで、正しい答えxが得られる場合と、さらに1が得られる場合があります。
乗算によってxを正確に計算することは不可能に思われるかもしれません。なぜなら、ある近似では、数値が必要な数よりも1少なくなり、さらに1になるためです。 しかし、これはそうではありません。 実際、 aは整数であり、最大小数部a / bは正確に（b-1）/ bであり、 xの計算ではa *（（1 >> M）-D）増加します。 ええ、それはa *（（1 >> M）-D）<1 / bの場合、不平等が平等に変わることを意味します!!! 数Lを 、 （1 << L）≥b 、次に（1 >> M）≤（1 >>（L + N））またはM≥L + Nで同等になるようにします。
Javaの例
この例では、除数は127（ L = 7）です。 JVMによる乗算の結果は32ビットに収まるはずです。N =（32-7）/ 2 = 12を選択します。例：
final static int N = 12; private static int divideBy127(int a) { final int b = 127; final int L = 7; final int B = ((1 << (N + L)) / b) + 1; return (a * B) >>> (N + L); } public static void main(String[] args) { final int size = 20000; final int times = 10001; final int[] data = new int[size]; for (int i = 0; i < size; ++i) data[i] = (i * i) & ((1 << N) - 1); // fill by any random data for (int iteration = 0; iteration < 10; ++iteration) { long time0 = System.currentTimeMillis(); // Test 1: Using div int v0 = 0; for (int j = 0; j < times; ++j) for (int i = 0; i < size; ++i) v0 ^= data[i] / 127; // keep result long time1 = System.currentTimeMillis(); // Test 2: Using mul int v1 = 0; for (int j = 0; j < times; ++j) for (int i = 0; i < size; ++i) v1 ^= divideBy127(data[i]); // keep result long time2 = System.currentTimeMillis(); System.out.println((time1 - time0) + " vs " + (time2 - time1) + " " + (v0 - v1)); } }
Intel Core-i5 2500、JITおよびオプション-XX：+ AggressiveOptsを使用したJVM 1.7.0u5では、除算テストは乗算の2倍遅くなります 。
追加
この記事で取り上げていないトピックの残りの部分：
- 配当はマイナスになる場合があります。
- 乗算中のオーバーフローを回避する方法。
- 整数にx86を乗算した結果は64ビットを必要とし、特定の条件下では、右へのシフトを削除できます。
- 数値が割り切れる整数であることがわかっている場合は、別のアルゴリズムを使用できます。
- 場合によっては、乗算を左シフトと加算で置き換えることができます。
- 実行速度がさらに速い一部の仕切りの特殊なケース。
文学
「乗算を使用した不変整数による除算」、Torbjorn Granlund、Peter L. Montgomery-正式な証明およびトピックに関するその他のアルゴリズム。