質問: C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか?? 桁を減らし、回数を増やした方がはやくなるかな?と思いました。 1/(x-2)(x-5) → 1/3(1/x-5 - 1/x-2) みたいに? 面白いサイトを見つけましたので、載せておきます。 プログラムによる数値演算のベンチマーク 教えてください。
回答: 乗算に関しては、Karatsuba法では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます(n桁×n桁の掛け算ででO(n^1.59)程度)し、3つの乗算のうち2つは並列実行できます。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。 これに対して、除算の場合、「分けて計算する」という方法が使えないので、O(n^2)のオーダーから減らすことができません(「割る数の桁数に比例した処理」を「割られる数の桁数に比例した回数」だけ繰り返すことになります)。上の桁が決まらないと下の桁の計算に入れないので、並列実行にも向きません。 結論:除算が遅い、というより、**乗算が高速化できる**から相対的に遅くなってしまう なお、「素因数分解で割る数を小さくする」というアイデアは、**素因数分解の手間自体が莫大となる**ため、一般の数に対する割り算の高速化にはほぼ使えません(「素因数分解がおいそれとできない」ことそのものがRSA暗号の安全性の鍵となっている、というように、本質的に困難な問題です)。