«Большие» фракции в Юлии - PullRequest
Новая
       42

«Большие» фракции в Юлии

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

Я столкнулся с небольшой проблемой при попытке решить проблему Project Euler в Джулии.Я в основном написал рекурсивную функцию, которая производит дроби со все более крупными числителями и знаменателями.Я не хочу публиковать код по понятным причинам, но последние несколько фракций выглядят следующим образом: 

1180872205318713601//835002744095575440
2850877693509864481//2015874949414289041
6882627592338442563//4866752642924153522

В этот момент я получаю OverflowError(), предположительно потому, что теперь числитель и / или знаменательпревышает 19 цифр.Есть ли способ обработки «больших» дробей в Джулии (то есть с числителями и знаменателями типа BigInt)?

Приложение:

ОК, я упростил код и замаскировал его:немного.Если кто-то захочет разобраться с 650 проблемами Project Euler, чтобы попытаться решить, какой это вопрос, удачи им - вероятно, будет найдено около 200 лучших решений! 

function series(limit::Int64, i::Int64=1, n::Rational{Int64}=1//1)
    while i <= limit
        n = 1 + 1//(1 + 2n)
        println(n)
        return series(limit, i + 1, n)
    end
end

series(50)

Если я запусту вышеуказанную функцию сскажем, 20 в качестве аргумента, он работает нормально.С 50 я получаю OverflowError().

1 Ответ

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

Юлия по умолчанию использует целые числа машин. Для получения дополнительной информации об этом см. FAQ: Почему Джулия использует целочисленную арифметику машинной машины? .

Короче говоря: наиболее эффективные целочисленные операции на любом современном CPU включают вычисления с фиксированным числом битов. На вашей машине это 64 бита. 

julia> 9223372036854775805 + 1
9223372036854775806

julia> 9223372036854775805 + 2
9223372036854775807

julia> 9223372036854775805 + 3
-9223372036854775808

Вау! Что сейчас произошло!? Это определенно неправильно! Это более очевидно, если вы посмотрите, как эти числа представлены в двоичном виде: 

julia> bitstring(9223372036854775805 + 1)
"0111111111111111111111111111111111111111111111111111111111111110"

julia> bitstring(9223372036854775805 + 2)
"0111111111111111111111111111111111111111111111111111111111111111"

julia> bitstring(9223372036854775805 + 3)
"1000000000000000000000000000000000000000000000000000000000000000"

Итак, вы можете видеть, что эти 63 бита «закончились» и перевернулись - 64-й бит называется «знаковым битом» и сигнализирует отрицательное число.

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

julia> Base.Checked.checked_add(9223372036854775805, 3)
ERROR: OverflowError: 9223372036854775805 + 3 overflowed for type Int64

Или вы можете использовать больший целочисленный тип - например, неограниченный BigInt: 

julia> big(9223372036854775805) + 3
9223372036854775808

Таким образом, простое решение - удалить аннотации типов и динамически выбирать целочисленные типы на основе limit: 

function series(limit, i=one(limit), n=one(limit)//one(limit))
    while i <= limit
        n = 1 + 1//(1 + 2n)
        println(n)
        return series(limit, i + 1, n)
    end
end

julia> series(big(50))
#…
1186364911176312505629042874//926285732032534439103474303
4225301286417693889465034354//3299015554385159450361560051
...