Project Euler # 101 - как справиться с полнотелым переполнением?

Question

Проект Эйлера # 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

Помогло не масштабирование на 100, а тот факт, что приведенные числа были числами с плавающей точкой, а не целыми, и, следовательно, имели больший диапазон. Из-за вычислений с плавающей точкой, как вы видели, в вычислениях внесены некоторые неточности.

Вы можете указать тип вручную следующим образом:

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

Расчеты для этой задачи соответствуют 64-битным целым, поэтому это будет работать.

Поддерживаемые типы перечислены здесь .

Answer 2

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 !"