целое число n-й корень

Question

x '- это n-й корень y, если x' - наибольшее целое число, такое что x ^ n <= y.х, х 'и у все целые числа.Есть ли эффективный способ вычисления такого n-го корня?Я знаю, что это обычно делается с помощью <a href="http://en.wikipedia.org/wiki/Nth_root_algorithm" rel="nofollow"> n-го корневого алгоритма , но сложность здесь в том, что все целое, потому что я работаю со встроенной системой.

Кстати, я даже пытался бинарноищите от 1 до y, чтобы определить наибольшее значение x, такое, что x ^ n <= y, но это не работает, поскольку x ^ n легко переполняется, особенно когда n большое. </p>

Answer 1

Сохранить таблицу для заданного y максимального значения x, чтобы x ^ y не переполнялся.Используйте эти значения для бинарного поиска;таким образом, больше нет переполнения и аккуратный алгоритм, который будет работать до тех пор, пока x и n имеют одинаковый (целочисленный) тип.Правильно?

Примечание: для y> 32 максимальное значение для x равно 2 для 32-разрядных целых чисел ... другими словами, ваша таблица будет иметь тот же размер, что и число бит в целых числах вашей системыпонимает, примерно.

Answer 2

Вы ищете только целочисленные корни?Или вы хотите знать, что 5-й корень из 34 равен 2,024 ...?Или «2» является достаточным ответом?Если вам нужны десятичные разряды, вам нужно будет выполнить какую-то математическую операцию с плавающей запятой или с фиксированной запятой.

Вы должны прочитать Вычисление главных корней и заметить, что он говорит о первомНьютон приблизительный.Если ошибка около 0,03% достаточно близка, я бы посоветовал вам воспользоваться этим.Возможно, вы захотите построить таблицу, которую вы можете использовать для начальных приближений.Эта таблица не такая большая, как кажется.Кубический корень 2 ^ 32 составляет всего около 1626.Вы можете легко вычислить квадраты и сгенерировать x ^ n, если вы можете сгенерировать x ^ 2 и x ^ 3.Таким образом, выполнить аппроксимации довольно просто.

Другая возможность состоит в том, чтобы создать себе таблицу корней и использовать некоторую интерполяцию.Опять же, эта таблица не должна быть очень большой, если вы рассматриваете квадратный корень как особый случай.5-й корень 2 ^ 32 меньше 100, поэтому вы говорите о довольно маленькой таблице, чтобы получить довольно большой диапазон корней.

Answer 3

Я думаю, что лучший способ - это использовать метод Ньютона-Рафсона из статьи в Википедии.

Хорошее начальное значение может быть вычислено из длины в битах ввода, деленной на n.В каждой итерации вы используете целочисленное деление, которое округляется.Повторяйте, пока не найдете значение x, такое, что x^n <= y < (x+1)^n.

. Будьте осторожны, чтобы избежать переполнения.Как говорится в другом ответе, вы можете использовать таблицу максимального корня для n < bit size, чтобы сделать это (для больших n ответ всегда 1, за исключением y = 0).