項目歐拉＃101 - 如何解決numpy多項式溢出？

Project Euler #101 項目歐拉＃101 - 如何解決numpy多項式溢出？

我剛開始學習Numpy，到目前爲止，它看起來非常簡單。

我碰到的一件事是，當我評估多項式時，結果是一個int32，所以會發生溢出。

u = numpy.poly1d([1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1]) 
for i in xrange(1, 11): 
    print(i, u(i))

的結果是：

(1, 1) 
(2, 683) 
(3, 44287) 
(4, 838861) 
(5, 8138021) 
(6, 51828151) 
(7, 247165843) 
(8, 954437177) 
(9, -1156861335) 
(10, 500974499)

最後兩個項目顯然是不正確。

圍繞我能想到的是由100

u = numpy.poly1d([0.01, -0.01, 0.01, -0.01, 0.01, -0.01, 0.01, -0.01, 0.01, -0.01, 0.01]) 
for i in xrange(1, 11): 
    print(i, int(u(i) * 100))

融通係數這一次的結果是正確的

(1, 1) 
(2, 682) 
(3, 44286) 
(4, 838860) 
(5, 8138020) 
(6, 51828151) 
(7, 247165843) 
(8, 954437177) 
(9, 3138105961L) 
(10, 9090909091L)

有沒有更好的辦法的工作？ Numpy是否允許我更改數據類型？謝謝。

來源

2010-01-08 grokus

我張貼的項目3-後發現5即使我的工作也不正確。 – grokus 2010-01-08 20:29:45

這不是縮小了100的幫助，而是給出的數字是浮點數而不是整數，因此具有更高的範圍。由於浮點計算，如您所見，計算中會引入一些不準確的地方。

你可以手動指定類型是這樣的：

u = numpy.poly1d(numpy.array([1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1], dtype=numpy.int64))

對於這個問題適合在64位整數的計算，所以這會奏效。

支持的類型列於here。

來源

2010-01-08 20:24:51 interjay

謝謝，我GOOGLE了一下，發現該數組可能有另一種數據類型，但沒有意識到poly1d可以接收一個numpy數組作爲參數。 – grokus 2010-01-08 20:31:02

Interjay在寫這篇文章的時候發佈了一個更好的答案，但我想你可能想要一個替代方案。

這裏有一個簡單的實現爲例子，你表明：

class Poly(object): 
    def __init__(self, coefficients): 
     assert len(coefficients) > 0 
     self.coefficients = coefficients 
    def __call__(self, value): 
     total = self.coefficients[0] 
     for c in self.coefficients[1:]: 
      total = total * value + c 
     return total

一些測試

assert Poly([5])(1) == 5 
assert Poly([7])(1) == 7 
assert Poly([2,3])(5) == 13 
assert Poly([1,0,0,0,0])(-2) == 16 
u = Poly([1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1]) 
for i in range(1, 11): 
    print (i, u(i))

和相當無用沿

assert Poly([2,"!"])("Hello ") == "Hello Hello !"

來源

2010-01-08 20:51:09

項目歐拉＃101 - 如何解決numpy多項式溢出？

回答

相關問題