Как вычислить n-й корень из очень большого целого числа

Мне нужен способ для вычисления n-го корня длинного целого числа в Python.

Я пытался pow(m, 1.0/n), но это не работает:

OverflowError: long int слишком велико для преобразования в float

Любые идеи?

Под длинным целым я подразумеваю ДЕЙСТВИТЕЛЬНО длинные целые числа, такие как:

11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 485046262847265769280883237649461122479734279424416861834396522 819159219215308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108430809620626 059287437887495827369474189818588006905358793385574832590121472 680866521970802708379837148646191567765584039175249171110593159 305029014037881475265618958103073425958633163441030267478942720 703134493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 940683350937992500211758727939459249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224 613682478900505821893815926193600121890632

10.12.2008 13:49:19
Как предполагает Давид, pow (n, 1/3) даст вам кубический (т.е. 3-й) корень n.
Brian 10.12.2008 13:59:02
Нет, не будет, так как 1/3 == 0 в
Matthew Schinckel 10.12.2008 14:05:57
(Но это не будет тем, чего хотел ОП).
Matthew Schinckel 10.12.2008 14:06:37
Py3 не имеет целочисленных ограничений ... они могут расти вечно, пока не закончится память. Я проверил на моей установке. Это решение.
user3917838 9.11.2015 04:08:10
10 ОТВЕТОВ
РЕШЕНИЕ

Вы можете заставить его работать немного быстрее, избегая циклов while в пользу установки низкого значения на 10 ** (len (str (x)) / n) и высокого на низкое значение * 10. Вероятно, лучше заменить len (str (x) )) с битовой длиной и использованием сдвига битов. Основываясь на моих тестах, я оцениваю ускорение на 5% от первого и ускорение на 25% со второго. Если целые числа достаточно большие, это может иметь значение (и ускорения могут отличаться). Не доверяйте моему коду без тщательного тестирования. Я провел некоторое базовое тестирование, но, возможно, пропустил крайний случай. Кроме того, эти ускорения зависят от выбранного количества.

Если фактические данные, которые вы используете, намного больше, чем вы разместили здесь, это изменение может стоить.

from timeit import Timer

def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def find_invpowAlt(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    low = 10 ** (len(str(x)) / n)
    high = low * 10

    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

x = 237734537465873465
n = 5
tests = 10000

print "Norm", Timer('find_invpow(x,n)', 'from __main__ import find_invpow, x,n').timeit(number=tests)
print "Alt", Timer('find_invpowAlt(x,n)', 'from __main__ import find_invpowAlt, x,n').timeit(number=tests)

Норма 0.626754999161

Alt 0.566340923309

6
11.12.2008 00:44:34
Ваша вторая функция, find_invpowAlt, дает дико неправильный ответ для й = 118997879821732370764604711647724283139870175351576755860556891902958645241483485254092600557474860904935286687480039428945219115513349647465379580432922136155355040992635166676363150438436216219094913514982415747153956476970303302126880391024128871557664284712411567099374094385902892603751471822837746770111, п = 3
tzs 15.05.2012 11:51:59
Строка low = high/2должна быть low = high // 2таковой, если вы хотите получить целое число в конце.
drhagen 8.05.2018 10:29:22
Я написал его, используя low = high/2намеренно, поскольку я непосредственно скопировал этот ответ из Кодекса Маркуса, чтобы сравнить его с моим предложенным улучшением. Отмечу, что с тех пор Маркус обновил свой код, чтобы исправить ошибку, и tzs ответил на мой код, что он также содержит ошибку. Однако на самом деле я не помню ни деталей проблемы, ни своего решения, поэтому я больше не чувствую себя компетентным, чтобы устранить эти недостатки.
Brian 9.05.2018 13:21:24

Попробуйте преобразовать экспоненту в плавающее число, так как в Python поведение по умолчанию - целочисленное деление

п ** (1 / поплавок (3))

-1
10.12.2008 13:54:39
n ** (1.0 / 3) тоже выполнит эту работу
Mapad 10.12.2008 13:57:46
OverflowError: long int слишком велико для преобразования в число с плавающей точкой, оно просто не будет работать, потому что огромное число не может быть преобразовано
Visgean Skeloru 6.12.2012 21:48:39
Насколько я могу судить, не было никаких признаков того, что он использовал Python 2.
Solomon Ucko 15.01.2019 01:54:15

В более старых версиях Python 1/3равен 0. В Python 3.0 1/3равен 0.33333333333 (и 1//3равен 0).

Итак, либо измените свой код для использования, 1/3.0либо переключитесь на Python 3.0.

1
10.12.2008 13:57:42
Насколько я могу судить, не было никаких признаков того, что он использовал Python 2.
Solomon Ucko 15.01.2019 01:54:00

Gmpy - это C-кодированный модуль расширения Python, который оборачивает библиотеку GMP, чтобы обеспечить коду Python быструю арифметику с множественными точностями (целочисленные, рациональные и с плавающей точкой), генерацию случайных чисел, расширенные теоретические функции и многое другое.

Включает rootфункцию:

x.root (n): возвращает 2-элементный кортеж (y, m), такой что y является (возможно, усеченным) n-м корнем x; m, обычный Python int, равен 1, если корень точный (x == y ** n), иначе 0. n должен быть обычным Python int,> = 0.

Например, 20-й корень:

>>> import gmpy
>>> i0=11968003966030964356885611480383408833172346450467339251 
>>> m0=gmpy.mpz(i0)
>>> m0
mpz(11968003966030964356885611480383408833172346450467339251L)
>>> m0.root(20)
(mpz(567), 0)
16
10.12.2008 14:28:43
С gmpy2это приводит: 'mpz' object has no attribute 'root'.
Zelphir Kaltstahl 11.12.2015 11:42:40
gmpy2 использует новый тип mpfr, основанный на библиотеке MPFR. gmpy2.root (x, n) -> mpfr Возвращает n-й корень из x. Результат всегда 'mpfr'.
gimel 12.12.2015 08:12:15
@Zelphir gmpy2 должен gmpy2.irootвычислять целочисленные корни.
jiakai 4.12.2016 12:54:43

Если это действительно большое число. Вы можете использовать бинарный поиск.

def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n <= x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

Например:

>>> x = 237734537465873465
>>> n = 5
>>> y = find_invpow(x,n)
>>> y
2986
>>> y**n <= x <= (y+1)**n
True
>>>
>>> x = 119680039660309643568856114803834088331723464504673392511960931441>
>>> n = 45
>>> y = find_invpow(x,n)
>>> y
227661383982863143360L
>>> y**n <= x < (y+1)**n
True
>>> find_invpow(y**n,n) == y
True
>>>
28
12.05.2016 07:30:50
Это все равно не удастся для чисел> ~ 10 ** 1000. Изменение mid = (low + high) // 2к mid = int((low + high) // 2) + 1исправит это.
Attila O. 18.05.2011 22:03:27
Проголосовал, потому что в нем есть ошибки. Я попытался find_invpow(64, 3)и получил 3, хотя результат должен был быть 4.
Elias Zamaria 11.05.2016 17:45:14
Строка low = high/2должна быть low = high // 2таковой, если вы хотите получить целое число в конце.
drhagen 8.05.2018 10:41:34

Что ж, если вас не особо беспокоит точность, вы можете преобразовать ее в строчку, отрубить несколько цифр, использовать функцию экспоненты, а затем умножить результат на корень того, сколько вы отрубили.

Например, 32123 примерно равно 32 * 1000, кубический корень примерно эквивалентен кубическому корню из 32 * кубического корня из 1000. Последний может быть рассчитан путем деления числа 0 на 3.

Это исключает необходимость использования модулей расширения.

-3
10.12.2008 14:23:20
Я беспокоюсь о точности, потому что я знаю это число, например, третья степень другого целого числа. (И, конечно, мне нужно знать это целое число) :)
PiX 10.12.2008 14:28:07
Кроме того, преобразование в строку может стать проблемой с огромными числами.
Attila O. 18.05.2011 22:02:57
@ Аттила: Не в определении огромного он дал в посте. Кроме того, не уверен точно, в каком формате он принимает ввод, но основная идея усечения будет работать в большинстве форматов.
Brian 19.05.2011 00:58:20
У него есть рабочий код, проблема только в точности
Solomon Ucko 19.04.2016 22:28:38

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

нс: ваш номер в виде строки

ns = "11968003966030964356885611480383408833172346450467339251196093144141045683463085291115677488411620264826942334897996389485046262847265769280883237649461122479734279424416861834396522819159219215308460065265520143082728303864638821979329804885526557893649662037092457130509980883789368448042961108430809620626059287437887495827369474189818588006905358793385574832590121472680866521970802708379837148646191567765584039175249171110593159305029014037881475265618958103073425958633163441030267478942720703134493880117805010891574606323700178176718412858948243785754898788359757528163558061136758276299059029113119763557411729353915848889261125855717014320045292143759177464380434854573300054940683350937992500211758727939459249163046465047204851616590276724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224613682478900505821893815926193600121890632"
from decimal import Decimal
d = Decimal(ns)
one_third = Decimal("0.3333333333333333")
print d ** one_third

и ответ: 2.287391878618402702753613056E + 305

Т.З. указал, что это не точно ... и он прав. Вот мой тест.

from decimal import Decimal

def nth_root(num_decimal, n_integer):
    exponent = Decimal("1.0") / Decimal(n_integer)
    return num_decimal ** exponent

def test():
    ns = "11968003966030964356885611480383408833172346450467339251196093144141045683463085291115677488411620264826942334897996389485046262847265769280883237649461122479734279424416861834396522819159219215308460065265520143082728303864638821979329804885526557893649662037092457130509980883789368448042961108430809620626059287437887495827369474189818588006905358793385574832590121472680866521970802708379837148646191567765584039175249171110593159305029014037881475265618958103073425958633163441030267478942720703134493880117805010891574606323700178176718412858948243785754898788359757528163558061136758276299059029113119763557411729353915848889261125855717014320045292143759177464380434854573300054940683350937992500211758727939459249163046465047204851616590276724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224613682478900505821893815926193600121890632"
    nd = Decimal(ns)
    cube_root = nth_root(nd, 3)
    print (cube_root ** Decimal("3.0")) - nd

if __name__ == "__main__":
    test()

Это примерно на 10 ** 891

3
10.12.2008 17:24:34
Um. Это может сработать, но это не точно. Используя ваши термины, и если ответ равен d one_third, то сколько (ответ 3 - d) должно быть?
tzot 10.12.2008 15:27:07
Десятичная дробь примерно настолько точна, насколько вам нужно ... моя строка 0,333 предназначена только для краткости.
Jim Carroll 10.12.2008 15:42:20
тз ... ты прав. Это далеко ... ну хорошо. Метод Ньютона выше действительно качает все же!
Jim Carroll 10.12.2008 16:38:50

Возможно, для вашего любопытства:

http://en.wikipedia.org/wiki/Hensel_Lifting

Это может быть техника, которую Maple будет использовать, чтобы найти n-й корень больших чисел.

Представьте тот факт x^n - 11968003.... = 0 mod p, и идти оттуда ...

2
10.12.2008 23:42:49

Если вы ищете что-то стандартное, пишите быстро с высокой точностью. Я хотел бы использовать десятичную и настроить точность (getcontext (). Prec) по крайней мере до длины х.

Код (Python 3.0)

from decimal import *

x =   '11968003966030964356885611480383408833172346450467339251\
196093144141045683463085291115677488411620264826942334897996389\
485046262847265769280883237649461122479734279424416861834396522\
819159219215308460065265520143082728303864638821979329804885526\
557893649662037092457130509980883789368448042961108430809620626\
059287437887495827369474189818588006905358793385574832590121472\
680866521970802708379837148646191567765584039175249171110593159\
305029014037881475265618958103073425958633163441030267478942720\
703134493880117805010891574606323700178176718412858948243785754\
898788359757528163558061136758276299059029113119763557411729353\
915848889261125855717014320045292143759177464380434854573300054\
940683350937992500211758727939459249163046465047204851616590276\
724564411037216844005877918224201569391107769029955591465502737\
961776799311859881060956465198859727495735498887960494256488224\
613682478900505821893815926193600121890632'

minprec = 27
if len(x) > minprec: getcontext().prec = len(x)
else:                getcontext().prec = minprec

x = Decimal(x)
power = Decimal(1)/Decimal(3)

answer = x**power
ranswer = answer.quantize(Decimal('1.'), rounding=ROUND_UP)

diff = x - ranswer**Decimal(3)
if diff == Decimal(0):
    print("x is the cubic number of", ranswer)
else:
    print("x has a cubic root of ", answer)

Ответ

х представляет собой кубическое количество 22873918786185635329056863961725521583023133411 451452349318109627653540670761962215971994403670045614485973722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 704433723567548799463129652706705873694274209728785041817619032774248488 2965377218610139128882473918261696612098418

7
12.03.2009 04:04:59

Я придумал свой собственный ответ, который берет идею @Mahmoud Kassem, упрощает код и делает его более пригодным для повторного использования:

def cube_root(x):
    return decimal.Decimal(x) ** (decimal.Decimal(1) / decimal.Decimal(3))

Я протестировал его в Python 3.5.1 и Python 2.7.8, и, похоже, он работал нормально.

Результат будет иметь столько цифр, сколько указано в десятичном контексте, в котором выполняется функция, которая по умолчанию составляет 28 десятичных знаков. Согласно документации для powerфункции в decimalмодуле, « результат четко определен, но только« почти всегда правильно округлен ». ». Если вам нужен более точный результат, это можно сделать следующим образом:

with decimal.localcontext() as context:
    context.prec = 50
    print(cube_root(42))
1
11.05.2016 18:55:54