Вы можете заставить его работать немного быстрее, избегая циклов 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
Доп. 0,566340923309