Вычисление больших фракций в Python? - PullRequest
0 голосов
/ 02 мая 2018

Я пытаюсь вычислить дроби в Python 2.7. Метод limit_denominator отлично работает для первых 15 итераций этого кода. Однако затем код застревает в цикле, выводя знаменатели менее 1 000 000

Fraction = 1217471/860882

Когда я не использую limit_denominator, я получаю повторяющиеся результаты, например:

Fraction = 141421356237/100000000000

В конце концов я хочу перебрать i до 1000, поэтому мои дроби будут очень большими. Любая помощь?

from fractions import *
i = 0
x = 1/2.0
x1 = 0
count = 0
while i < 20:
    (y) = (1.0 + (x))
    (x) = (1 / (2.0 + (x)))
    y1 = Fraction(str(y)).limit_denominator()
    print("\nFraction = " + str(y1))
    i += 1

Ответы [ 3 ]

0 голосов
/ 02 мая 2018

Как говорит Чернослив, лучше избегать поплавков при работе с Fraction. И если вы хотите преобразовать свою дробь в десятичную без потери точности, вам нужно использовать числовой тип, например, десятичный, который имеет достаточную точность. Другой вариант - просто работать с целыми числами Python и увеличивать числитель с помощью достаточно большого множителя.

Ваш ряд находит сходящиеся к непрерывной дроби квадратного корня из двух. Если вы хотите перебрать все конвергенты, вы можете использовать алгоритм, показанный в ответе Чернослива. Но если вы хотите быстро вычислить sqrt (2) с большим количеством цифр, есть лучший способ, известный как метод Героя (или метод Герона). Это частный случай метода Ньютона для вычисления корней алгебраических уравнений. Вместо того, чтобы вычислять слагаемые для каждого i в алгоритме Пруна 1 на 1, мы по существу удваиваем i на каждой итерации, поэтому числитель и знаменатель очень быстро увеличиваются, удваивая точность ответа на каждой итерации цикла.

Вот короткая демонстрация, которая вычисляет sqrt (2) с точностью до 100 цифр. Обычно я делаю это, используя простые целые числа Python (или длинные целые числа в Python 2), но это также легко сделать с помощью дроби.

from __future__ import print_function
from fractions import Fraction as F

digits = 100
m = 10 ** digits

x = F(1, 1)
while x.denominator < m:
    print(x)
    x = x / 2 + 1 / x

print()
print(m * x.numerator // x.denominator)

выход

1
3/2
17/12
577/408
665857/470832
886731088897/627013566048
1572584048032918633353217/1111984844349868137938112
4946041176255201878775086487573351061418968498177/3497379255757941172020851852070562919437964212608
48926646634423881954586808839856694558492182258668537145547700898547222910968507268117381704646657/34596363615919099765318545389014861517389860071988342648187104766246565694525469768325292176831232

14142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

Проверено на Python 2.6 и 3.6

0 голосов
/ 02 мая 2018

Я переписал ваш код, пытаясь решить вашу проблему, потому что я не понимал необходимость limit_denominator. Это результат:

from fractions import *
x = Fraction(1, 2)
for i in range(1000):
    y = 1 + Fraction(x)
    print 'Y', y
    x = 1 / (2 + x)
    print 'X', x

Проблема в том, что компьютеры на самом деле не понимают числа, вместо этого они работают с абстрактным представлением чисел в памяти, которое называется floating point (происхождение float я предполагаю). Это представление имеет заданную точность (предел), которая зависит от объема памяти, зарезервированного для типа данных. Вот почему int32 имеет меньше принятых значений, чем, например, int64.
Однако у python есть умный и эффективный способ вычисления больших чисел. Кроме того, библиотека фракций предоставляет вам способ представления чисел (дробей), которые выходят (не совсем, в конце концов, это компьютер) из ограничения чисел floating point. Если вы хотите больше погрузиться в floating point arithmetic, я рекомендую всемогущим Numerical Analysis от Burden & Faires и Numerical Methods от Dr David Ham.

0 голосов
/ 02 мая 2018

Значения сходятся к sqrt (2.0), что дает вам узкий диапазон дробей, которые будут точно представлять 64-битное значение с плавающей запятой. Ваша рациональная дробь не может быть более точной, чем float, которую вы ей даете.

Если вы хотите увеличить знаменатели, вам нужно указать больший предел знаменателя. Вы по-прежнему ограничены точностью float: если вы сходитесь в пределах точности вашего вычислительного типа (вероятно, float64), вы не получите большей точности в своем рациональном представлении этого. Если вы хотите большей точности, конвертируйте все в вычисления fraction:

from fractions import *

x = Fraction(1,2)

for i in range(40):
    y = Fraction(1) + x
    x = Fraction(1) / (Fraction(2) + x)
    print("Fraction = " + str(y))

Выход:

Fraction = 3/2
Fraction = 7/5
Fraction = 17/12
Fraction = 41/29
Fraction = 99/70
Fraction = 239/169
Fraction = 577/408
Fraction = 1393/985
Fraction = 3363/2378
Fraction = 8119/5741
Fraction = 19601/13860
Fraction = 47321/33461
Fraction = 114243/80782
Fraction = 275807/195025
Fraction = 665857/470832
Fraction = 1607521/1136689
Fraction = 3880899/2744210
Fraction = 9369319/6625109
Fraction = 22619537/15994428
Fraction = 54608393/38613965
Fraction = 131836323/93222358
Fraction = 318281039/225058681
Fraction = 768398401/543339720
Fraction = 1855077841/1311738121
Fraction = 4478554083/3166815962
Fraction = 10812186007/7645370045
Fraction = 26102926097/18457556052
Fraction = 63018038201/44560482149
Fraction = 152139002499/107578520350
Fraction = 367296043199/259717522849
Fraction = 886731088897/627013566048
Fraction = 2140758220993/1513744654945
Fraction = 5168247530883/3654502875938
Fraction = 12477253282759/8822750406821
Fraction = 30122754096401/21300003689580
Fraction = 72722761475561/51422757785981
Fraction = 175568277047523/124145519261542
Fraction = 423859315570607/299713796309065
Fraction = 1023286908188737/723573111879672
Fraction = 2470433131948081/1746860020068409
...