python - 整数のn乗根を見つける方法は?

Question

n の k 乗根以下の最大の整数を見つけたい。私は試した

int(n**(1/k))

しかし、n=125、k=3 の場合、これは間違った答えになります! 5 の 3 乗は 125 であることをたまたま知っています。

>>> int(125**(1/3))
4

より良いアルゴリズムは何ですか?

背景: 2011 年、この失敗により、Google Code Jam の問題Expensive Dinnerを打ち負かすことができませんでした。

Answer 1

ひどい火傷を負った後の私の慎重な解決策：

def nth_root(N,k):
    """Return greatest integer x such that x**k <= N"""
    x = int(N**(1/k))      
    while (x+1)**k <= N:
        x += 1
    while x**k > N:
        x -= 1
    return x

Answer 2

これを試してみませんか：

125 ** (1 / float(3)) 

また

pow(125, 1 / float(3))

5.0 を返すので、int() を使用して int に変換できます。

Answer 3

対数に基づく方法から始めると、丸め誤差の原因を突き止めるのに役立つのではないかと思います。例えば：

import math
def power_floor(n, k):
    return int(math.exp(1.0 / k * math.log(n)))

def nth_root(val, n):
    ret = int(val**(1./n))
    return ret + 1 if (ret + 1) ** n == val else ret

cases = [
    (124, 3),
    (125, 3),
    (126, 3),
    (1, 100),
    ]


for n, k in cases:
    print "{0:d} vs {1:d}".format(nth_root(n, k), power_floor(n, k))

プリントアウト

4 vs 4
5 vs 5
5 vs 5
1 vs 1

Answer 4

ここでは、Lua で Newton-Raphson 法を使用しています。

> function nthroot (x, n) local r = 1; for i = 1, 16 do r = (((n - 1) * r) + x / (r ^ (n -   1))) / n end return r end
> return nthroot(125,3)
5
> 

Python バージョン

>>> def nthroot (x, n):
...     r = 1
...     for i in range(16):
...             r = (((n - 1) * r) + x / (r ** (n - 1))) / n
...     return r
... 
>>> nthroot(125,3)
5
>>> 

Answer 5

すべての前にこれを行います：

from __future__ import division

次に、上記の指定された手法のいずれかを実行して結果を取得します。

Answer 6

/ をゼロに切り下げる代わりに、最も近い整数に丸めることができます (Python が何を指定しているのかわかりません)。

def rtn (x):
    return int (x + 0.5)

>>> rtn (125 ** (1/3))
5