非常に大きな整数のn乗根を計算する方法
https://stackoverflow.com/questions/356090
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はPythonでの長整数のn乗根を計算する方法が必要です。
私はpow(m, 1.0/n)を試してみましたが、それは動作しません。
はOverflowErrorます：
float型に変換するlong int型が大きすぎます
任意のアイデア？
長整数では私のような本当に長い整数を意味します
11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 485046262847265769280883237649461122479734279424416861834396522 819159219215308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108430809620626 059287437887495827369474189818588006905358793385574832590121472 680866521970802708379837148646191567765584039175249171110593159 305029014037881475265618958103073425958633163441030267478942720 703134493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 940683350937992500211758727939459249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737 961776799311859881060956465198859727495735498887960494256488224 613682478900505821893815926193600121890632
解決
あなたはそれが（LEN（文字列（X））/ n）の** 10までの低設定の賛成でwhileループを回避することにより、わずかに速く走らせると、おそらく低* 10、より良いに高いことができます（LENを交換することですSTR（x））をビット単位の長さとビットシフトを使用して。私のテストに基づいて、私は、第一及び第二から25％の高速化から5％のスピードアップを見積もります。 int型は十分な大きさであれば、これは問題かもしれません（とスピードアップは異なる場合があります）。慎重にそれをテストすることなく、自分のコードを信用してはいけません。私はいくつかの基本的なテストをしましたが、エッジケースを逃している可能性があります。また、これらの高速化は、選択された番号と異なります。
あなたが使用している実際のデータは、この変化は価値があるかもしれません、あなたはここに掲載するものよりもはるかに大きい場合ます。
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
他のヒント
それは本当に大きな数だ場合。あなたは、バイナリ検索を使用することができます。
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
>>>
Gmpy にはに提供するために、GMPライブラリをラップするCコード化されたPythonの拡張モジュールでありますPythonコード高速多倍精度演算（整数、有理数、フロート）、乱数生成、高度な数の理論的機能、およびよります。
root機能が含まれています：
x.root（N）：Yであるように、2要素のタプル（Y、M）を返します xの（おそらくは切り捨て）のn乗根。メートル、通常のPythonのint型、 ルートが正確である場合は0、nは、通常でなければならない他、（x == yの** n）が1であります Pythonの整数、> = 0。
たとえば、20ルート
>>> import gmpy
>>> i0=11968003966030964356885611480383408833172346450467339251
>>> m0=gmpy.mpz(i0)
>>> m0
mpz(11968003966030964356885611480383408833172346450467339251L)
>>> m0.root(20)
(mpz(567), 0)
あなたが何かの標準を探している場合は、高速で高精度に書き込むことができます。 Iは小数点を使用して、Xの少なくとも長さに精度（に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)
回答
xは22873918786185635329056863961725521583023133411の立方数であります 451452349318109627653540670761962215971994403670045614485973722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 704433723567548799463129652706705873694274209728785041817619032774248488 2965377218610139128882473918261696612098418
ああ、数値ののことの大きな、あなたがdecimalモジュールを使用することになります。
NS：文字列としてあなたの番号
ns = "11968003966030964356885611480383408833172346450467339251196093144141045683463085291115677488411620264826942334897996389485046262847265769280883237649461122479734279424416861834396522819159219215308460065265520143082728303864638821979329804885526557893649662037092457130509980883789368448042961108430809620626059287437887495827369474189818588006905358793385574832590121472680866521970802708379837148646191567765584039175249171110593159305029014037881475265618958103073425958633163441030267478942720703134493880117805010891574606323700178176718412858948243785754898788359757528163558061136758276299059029113119763557411729353915848889261125855717014320045292143759177464380434854573300054940683350937992500211758727939459249163046465047204851616590276724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224613682478900505821893815926193600121890632"
from decimal import Decimal
d = Decimal(ns)
one_third = Decimal("0.3333333333333333")
print d ** one_third
との答えは次のとおりです。2.287391878618402702753613056E + 305
TZが、これは正確ではないことを指摘した...そして彼は正しいです。ここに私のテストです。
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でオフです。
おそらく、あなたの好奇心のために：
http://en.wikipedia.org/wiki/Hensel_Liftingする
このメープルは、実際に多数のn番目の根を見つけるために使用する技術である可能性があります。
という事実x^n - 11968003.... = 0 mod pポーズ、そしてそこから行く...
のPythonの古いバージョンでは、1/3は、Python 3.0では0に等しい、1/3は（及び1//3は0に等しい）0.33333333333に等しくなります。
だから、どちらかのPython 3.0に1/3.0またはスイッチを使用するようにコードを変更します。
私は@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))
Pythonで/のデフォルトの動作として、フローティング数に指数を変換してみてくださいする整数除算である
N **（1 /フロート（3））
さて、あなたは、いくつかの数字を切り落とす指数関数を使用して、あなたが切り落とさどのくらいのルートで結果を掛け、スティングに変換することができます。
例えば。 32123は、32×1000にほぼ等しい、立方根は後者が3で0の数を割ることによって計算することができる1000の32 *立方根の立方根にequak程度である。
これは、拡張モジュールを使用する必要性を回避します。
