標準の反復アルゴリズムを使用して n 乗根を計算しようとしました。
たとえば、(111^123)^(1/123) です。
標準アルゴリズムは、基数の高べき乗(この場合は 111^123)を計算しますが、これには多くの時間がかかります。アルゴリズムはここにありますhttp://en.wikipedia.org/wiki/Nth_root_algorithm
しかし、double を使用した同じ処理に 1 ミリ秒もかからないことに気付きました。明らかに、彼らはいくつかの賢いアイデアを使用しています。これに関するヒントはありますか？
しかし、double を使用した同じ処理に 1 ミリ秒もかからないことに気付きました。明らかに、彼らはいくつかの賢いアイデアを使用しています。
あまり。double単純に精度が限られているため、基本的に結果の最上位 52 ビットのみを計算する必要があり、残りの計算をスキップできます。もちろん、これをハードウェアに実装することも役立ちます。
バイナリ累乗を使用してみてください。つまり、次のことを行います。
111 * 111 = 111^2、これで 111^2 が何であるかがわかったので、(111^2) * (111^2) を実行して 111^4 を計算できます。これがシーケンス全体です (これはおそらく最も効率的な方法ではないことに注意してください)。
111 * 111 = 111^2
111^2 * 111^2 = 111^4
111^4 * 111^4 = 111^8
111^8 * 111^8 = 111^16
111^16 * 111^16 = 111^32
111^32 * 111^32 = 111^64
111^64 * 111^32 = 111^96
111^96 * 111^16 = 111^112
111^112 * 111^8 = 111^120
111^120 * 111^2 * 111^1 = 111^123.