Блог

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

 def isGrafting(a):
  for i in xrange(1, int(ceil(log10(a)))   2):
    if a == floor((sqrt(a) * 10**(i-1)) % 10**int(ceil(log10(a)))):
      return 1

a = 0
while(1):
  if (isGrafting(a)):
    print "%d %.15f" % (a, sqrt(a))
  a  = 1
 

В этом коде отсутствует по крайней мере один известный номер прививки. 9999999998 => 99999.99998999999999949999999994999999999374999999912... Кажется, что после умножения он теряет дополнительную точность 10**5 .

 >>> a = 9999999998
>>> sqrt(a)
99999.99999
>>> a == floor((sqrt(a) * 10**(5)) % 10**int(ceil(log10(a))))
False
>>> floor((sqrt(a) * 10**(5)) % 10**int(ceil(log10(a))))
9999999999.0
>>> print "%.15f" % sqrt(a)
99999.999989999996615
>>> print "%.15f" % (sqrt(a) * 10**5)
9999999999.000000000000000
 

Поэтому я написал короткую программу на C , чтобы посмотреть, был ли это мой процессор, усекающий число с плавающей запятой, или каким-то образом python.

 #include <cstdio>
#include <cmath>
#include <stdint.h>

int main()
{
  uint64_t a = 9999999998;
  printf("%ld %.15f %.15f %.15f %.15fn", a, sqrt((double)a), sqrt((double)a)*1e4, sqrt((double)a)*1e5, sqrt((double)a)*1e6);
  a = 999999999998;
  printf("%ld %.15f %.15f %.15f %.15fn", a, sqrt((double)a), sqrt((double)a)*1e5, sqrt((double)a)*1e6, sqrt((double)a)*1e7);
  a = 99999999999998;
  printf("%ld %.15f %.15f %.15f %.15fn", a, sqrt((double)a), sqrt((double)a)*1e6, sqrt((double)a)*1e7, sqrt((double)a)*1e8);
  return 0;
}
 

Какие результаты:

 9999999998 99999.999989999996615 999999999.899999976158142 9999999999.000000000000000 99999999990.000000000000000
999999999998 999999.999998999992386 99999999999.899993896484375 999999999999.000000000000000 9999999999990.000000000000000
99999999999998 9999999.999999899417162 9999999999999.900390625000000 99999999999999.000000000000000 999999999999990.000000000000000
 

Таким образом, похоже, что я сильно превышаю пределы точности с плавающей запятой, и процессор отсекает оставшиеся биты, потому что он думает, что оставшаяся разница-ошибка с плавающей запятой. Есть ли способ обойти это в Python? Или мне нужно перейти на C и использовать GMP или что-то в этом роде?

В стандартной библиотеке decimal модуль может быть тем, что вы ищете. Кроме того, я обнаружил, что mpmath весьма полезен. В документации также есть много замечательных примеров (к сожалению, мой офисный компьютер не mpmath установлен; в противном случае я бы проверил несколько примеров и опубликовал их).

Однако есть одно предостережение по поводу decimal модуля. Модуль содержит несколько встроенных функций для простых математических операций (например sqrt ), но результаты этих функций не всегда могут соответствовать соответствующей функции в math или других модулях с более высокой точностью (хотя они могут быть более точными). Например,

 from decimal import *
import math

getcontext().prec = 30
num = Decimal(1) / Decimal(7)

print("   math.sqrt: {0}".format(Decimal(math.sqrt(num))))
print("decimal.sqrt: {0}".format(num.sqrt()))
 

В Python 3.2.3 это выводит первые две строки

    math.sqrt: 0.37796447300922719758631274089566431939601898193359375
decimal.sqrt: 0.377964473009227227214516536234
actual value: 0.3779644730092272272145165362341800608157513118689214
 

что, как уже говорилось, не совсем то, что вы ожидали бы, и вы можете видеть, что чем выше точность, тем меньше совпадают результаты. Обратите внимание, что decimal в этом примере модуль имеет большую точность, так как он более точно соответствует фактическому значению.

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

Для этой конкретной проблемы decimal это отличный способ, потому что он хранит десятичные цифры в виде кортежей!

 >>> a = decimal.Decimal(9999999998)
>>> a.as_tuple()
DecimalTuple(sign=0, digits=(9, 9, 9, 9, 9, 9, 9, 9, 9, 8), exponent=0)
 

Поскольку вы ищете свойство, которое наиболее естественно выражается в десятичной нотации, немного глупо использовать двоичное представление. На странице википедии, на которую вы ссылались, не указано, сколько «цифр без прививки» может появиться до начала «цифр для прививки», поэтому это позволяет вам указать:

 >>> def isGrafting(dec, max_offset=5):
...     dec_digits = dec.as_tuple().digits
...     sqrt_digits = dec.sqrt().as_tuple().digits
...     windows = [sqrt_digits[o:o   len(dec_digits)] for o in range(max_offset)]
...     return dec_digits in windows
... 
>>> isGrafting(decimal.Decimal(9999999998))
True
>>> isGrafting(decimal.Decimal(77))
True
 

Я думаю, что есть большая вероятность того, что результат Decimal.sqrt() будет более точным, по крайней мере для этого, чем результат из math.sqrt() -за преобразования между двоичным представлением и десятичным представлением. Рассмотрим, например, следующее:

 >>> num = decimal.Decimal(1) / decimal.Decimal(7)
>>> decimal.Decimal(math.sqrt(num) ** 2) * 7
Decimal('0.9999999999999997501998194593')
>>> decimal.Decimal(num.sqrt() ** 2) * 7
Decimal('1.000000000000000000000000000')
 

Python не имеет встроенных поплавков произвольной точности, но существуют сторонние пакеты Python, которые используют GMP: gmpy и PyGMP.

используйте decimal , (вот более четкий пример):

 >>> 2.3-2.2
0.09999999999999964
>>> from decimal import Decimal
>>> Decimal('2.3')-Decimal('2.2')
Decimal('0.1')
>>> float(Decimal('2.3')-Decimal('2.2'))
0.1
>>>