F# фибоначчи!

[vak]

Я писал про .NET для Линукс - продолжаю забавляться с ним. В его составе, кроме C#, идёт также компилятор F#. Несмотря на хулиганское название, это весьма серьёзный функциональный язык программирования. Давайте попробуем сваять на нём функцию вычисления чисел Фибоначчи.

В языке F# есть поддержка целых чисел неограниченного размера, чем мы и воспользуемся. Для литералов типа bigint надо указывать суффикс I.

Для вычислений задействуем хвостовую рекурсию, как и положено в порядочном функциональном языке.

let fibonacci n =

    let rec fibrec n f0 f1 =
        match n with
        | 0 -> f0
        | 1 -> f1
        | _ -> fibrec (n - 1) f1 (f0 + f1)

    fibrec n 0I 1I

Запускаем (можно онлайн на https://repl.it/languages/fsharp).

printfn "%A" (fibonacci 10)

55

Неплохо для начала, двинем дальше.

printfn "%A" (fibonacci 100)

354224848179261915075

Таки оно работает! Поддадим жару.

printfn "%A" (fibonacci 1000)

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

У-у-у! - сказали суровые сибирские мужики, и сунули в пилу стальную рельсу.

printfn "%A" (fibonacci 10000)

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

Ну что тут поделаешь. Я проверял на миллионе - вычисляет за 25 секунд на моём лаптопе.

Comments

[mopexod]

Первый раз в жизни вижу, что ленту растянуло вширь не от картинки с котиком, а от числа Фибоначчи!

[vak]

Давай уберу под кат.

[mopexod]

Спасибо! Но я не жаловался - я правда поразился!

[mikerrr]

Блин, и рельсу перепилило... А если под виндоуз запустить?

[pappadeux]

?

це ж универсальный дивайс

выдало те же цифры

[spamsink]

А если бы распознавал pure functions и делал memoization, то и миллион вычислял бы мгновенно, но поди ж ты.

[ircicq]

на C# результат для миллиона 18 s:

static BigInteger Fib(BigInteger n) {
    BigInteger f0 = 0, f1 = 1;
    while (n --> 0)
        (f0, f1) = (f1, f0 + f1);
    return f0;
}

А по-честному сравнивать лучше на функции Аккермана, которая не может быть сведена к концевой рекурсии

[vak]

Ну, так-то и Питон за 8 секунд миллион вычисляет.

def fib(n):
    f0 = 0
    f1 = 1
    for i in range(n):
        f0, f1 = f1, f0 + f1
    return f0

Но мне охота была именно рекурсию проверить.