Project Euler #101 - 如何解决numpy多项式溢出？

Question

Project Euler #101

我刚开始学习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能让我改变数据类型吗？谢谢。

Answer 1

在我写这个的时候，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 !"

Answer 2

其实，问题不是因为把数字放大了100倍，而是因为给出的数字是浮点数（小数），而不是整数（整数字），所以它们的范围更大。由于浮点数计算的原因，计算中会出现一些不准确的情况，正如你所看到的那样。

你可以手动指定数据类型，像这样：

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

这个问题的计算可以用64位的整数来处理，所以这样做是没问题的。

支持的数据类型可以在这里找到。