Деление больших чисел в Python

Question

Я пытаюсь разделить несколько больших чисел в Python, но получаю странные результаты

NStr = "7D5E9B01D4DCF9A4B31D61E62F0B679C79695ACA70BACF184518" \
       "8BDF94B0B58FAF4A3E1C744C5F9BAB699ABD47BA842464EE93F4" \
       "9B151CC354B21D53DC0C7FADAC44E8F4BDF078F935D9D07A2C07" \
       "631D0DFB0B869713A9A83393CEC42D898516A28DDCDBEA13E87B" \
       "1F874BC8DC06AF03F219CE2EA4050FA996D30CE351257287" 

N = long(NStr, 16)
f2 = 476

fmin = N / float(f2)

print N - (fmin * float(f2))

Это выводит как 0.0 как и ожидалось. Однако, если я, например, изменить код на

fmin = N / float(f2)
fmin += 1

Я все еще получаю вывод 0.0

Я также попытался использовать десятичный пакет

fmin = Decimal(N) / Decimal(f2)
print Decimal(N) - (fmin * Decimal(f2))

Но это дает мне вывод -1.481136900397802034028076389E+280

Я предполагаю, что я не говорю Python, как правильно обрабатывать большие числа, но я не знаю, куда идти дальше.

Я также должен добавить, что конечной целью является расчет

fmin = ceil(N / float(f2))

максимально длинный и точный

Answer 1

Расширяю свой комментарий, если N а также f2 являются longстрого больше 0, то

 fmin = (N - 1) // f2 + 1

это точно ceil(N / float(f2)) (но даже более точно, чем использование поплавков).

(Использование // скорее, чем / для целочисленного деления - для совместимости с Python 3.x без лишних усилий.)

Это потому что N // f2 дает вам (в основном) floor(N / float(f2)) так что N // f2 + 1 почти всегда так же, как ceil, Однако когда N это кратное f2, N // f2 + 1 слишком большой (+1 не должно быть там), но с помощью N - 1 исправляет это и не нарушает другой случай.

(Это не работает ни для N, f2 меньше или равно 0, но это может быть обработано отдельно)

Answer 2

fmin это float после того, как вы разделите длинное целое число на число с плавающей точкой. Его ценность 1.84952718165824e+305, Добавление 1 к этому ничего не меняет, точность просто не так высока.

Если вы вместо этого сделаете целочисленное деление, fmin остается long:

>>> fmin = N / f2
>>> fmin
18495271816582402193321106509793602189617847415669131056768139225220221855498293
49983070478076000952025038039460539798061570960870927236986153971731443029057201
52035339202255934728764897424408896865977423536890485615063959262845076766281553
766072964756078264853041334880929452289298495368916583660903481130L
>>> N - (fmin * f2)
111L

Конечно, вы не получаете 0 из-за целочисленного деления, где отбрасывается десятичная часть результата. Но теперь добавление 1 будет иметь значение:

>>> N - ((fmin+1) * f2)
-365L

С использованием Decimal модуль не меняет проблему:

>>> from decimal import Decimal, getcontext
>>> fmin = Decimal(N) / Decimal(f2)
>>> fmin
Decimal('1.849527181658240219332110651E+305')

Там все еще нет безграничной точности, и даже если вы установите Decimal.getcontext().prec = 2000, вы все равно не получите точно 0.

Answer 3

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

fmin = (N + f2 - 1) / f2

На Python 3.x используйте // оператор вместо / получить целочисленное деление.

Answer 4

Fraction от fractions модуль может быть полезен:

>  : N = Fraction(N)   
>  : f2 = Fraction(f2)
>  : fmin = N / f2
>  : print N-f2*fmin
0
>  : fmin += 1
>  : print N-f2*fmin
-476

Но если ваша единственная цель состоит в том, чтобы рассчитать ceil(N / float(f2)) ты можешь использовать:

>  : fmin = N/f2 + int(ceil((N % f2) / float(f2)))
>  : print fmin
184952718165824021933211065097936021896178474156691310567681392252202218554982934998307047807600095202503803946053979806157096087092723698615397173144302905720152035339202255934728764897424408896865977423536890485615063959262845076766281553766072964756078264853041334880929452289298495368916583660903481131

Answer 5

Поплавкам просто не хватает точности для такого рода операций.

Вы можете улучшить точность decimal модуль с getcontext(), Например, чтобы использовать 65536 десятичных знаков:

from decimal import Decimal, getcontext
getcontext().prec = 2**16

Затем:

>>> print Decimal(N) - (fmin * Decimal(f2))
-2E-65228

Все еще не 0, но ближе:)

Смотрите этот ответ, чтобы сделать ceil() на Decimal объект.

Answer 6

Я также обнаружил подобное поведение в Python 2.7.2:

In [17]: N
Out[17]: 8803749384693223444020846698661754642258095369858506383021634271204825603217187705919415475641764531639181067832169438773077773745613648054092905441668
8183122792368821460273824930892091174018634908205253603559871152770444609114256540750019592650731223893254070047675403322419289706083795604293822590057017991L

In [18]:

In [18]: (fmin * float(f2))
Out[18]: 8.803749384693223e+307
In [19]: N - (fmin * float(f2))
Out[19]: 0.0

In [20]: (fmin * float(f2))
Out[20]: 8.803749384693223e+307

In [21]: N == (fmin * float(f2))
Out[21]: False

In [22]: N < (fmin * float(f2))
Out[22]: False

In [23]: N > (fmin * float(f2))
Out[23]: True

По причинам, которые я не понимаю, кажется, что вычитание float из long дает 0.

Казалось бы, решение состоит в том, чтобы преобразовать оба в decimal.Decimal:

In [32]: decimal.Decimal(N) - decimal.Decimal(fmin * float(f2))
Out[32]: Decimal('4.099850360284731589507226352E+291')