вычисление больших корней: bigdecimal / java

Question

Я пытался использовать стандартный итерационный алгоритм для вычисления n-х корней.

Например (111 ^ 123) ^ (1/123).

Стандартный алгоритм вычисляет большие мощности базы (в данном случае 111 ^ 123) , что занимает много времени. Алгоритм приведен здесь http://en.wikipedia.org/wiki/Nth_root_algorithm

Тем не менее, я заметил, что то же самое с использованием double занимает менее миллисекунды. Очевидно, они используют некоторые умные идеи. Есть намеки на это?

Answer 1

Однако я заметил, что то же самое использование двойного занимает меньше миллисекунды. Так очевидно, что они используют некоторые умные идеи.

Не совсем. double просто имеет ограниченную точность, поэтому он в основном должен вычислять только самые важные 52 бита результата и может пропускать оставшиеся вычисления. И, конечно, помогает реализовать это на аппаратном уровне.

Answer 2

Попробуйте использовать двоичное возведение в степень. Что я имею в виду сделать:

111 * 111 = 111 ^ 2, теперь вы знаете, что такое 111 ^ 2, теперь вы можете вычислить 111 ^ 4, выполнив (111 ^ 2) * (111 ^ 2). Вот вся последовательность (обратите внимание, что это, вероятно, не самый эффективный способ).

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.