[решено] Haskell числа фибоначчи (скорость)

[frp]

Нашел туториал по Haskell. Первый пример:

Код: Выделить всё

fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

- ghci:
>:load file.hs
>fib 1
1
>fib 5
5
>fib 50
... и тут очень долго ждем, пока оно посчитает ...

А все, насколько я понял, очень просто - функция рекурсивная и одно и то же вычисляется очень много раз. Как сделать быстрее?

PS. Никакого опыта функционального программирования не имею

[drBatty]

А все, насколько я понял, очень просто - функция рекурсивная и одно и то же вычисляется очень много раз. Как сделать быстрее?

PS. Никакого опыта функционального программирования не имею

никак.
есть формула, связанная с золотым сечением, поищите в вике, она считает сразу, и формула примитивная.
(она даёт нецелые числа - округлите)
но если у вас алгоритм изначально рекурсивный, то вы его не развернётё. Может математики и будут со мной спорить, но на практике это так - например возмите структуру файловой системы, она рекурсивная, и все программы для её обработки - тоже. Ваша формула тоже рекурсивная, и она не разворачивается.

[drBatty]

PS: тут можно оптимизировать - допустим функция даёт 2 результата: fib(n-1) и fib(n). тогда не надо вычислять 2 раза в каждом вызове, а тот тут в каждой итерации приходится считать например для 4
(2 + 1) + ((2 + 1) + 3)
а можно просто
1) fib(3) = (2+1), 2
2) fib (4) = fib(3) + fib(2)
что даёт нам 2 сложения, а не 4.

[t.t]

Математики спорить не будут, только одно уточнение сделают: та прямая формула, о которой Вы говорите, и была получена "развёртыванием" рекурсивной последовательности. В остальном всё верно: программными методами её развернуть не удастся; математическими можно лишь заново вывести ту же самую формулу.

[drBatty]

PS: это так называемая "хвостовая рекурсия", применяется в любых языках начиная с машинных кодов, если нам надо выполнить 2 рекурсивных действия, то мы выполняем рекурсивно только первое, а второе может выполнить и сама программа. не сомневаюсь, такое есть и в вашем языке. только я не знаю как (да и не очень хочу знать - мозг сломаю)

[neol]

Haskell не знаю, следующий код взял с одного очень древнего холивара (ссылка). Кое-какое описание там приводится.

Код: Выделить всё

import IO
import CPUTime
import Numeric

fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

main = do
  putStrLn (show (fib!!46))
  time <- getCPUTime
  putStrLn (showFFloat (Just 6) (fromInteger time / 1e12) "")

[Portnov]

Собственно, всё уже объяснили. Код в первом посте хорош наглядностью. Но использует т.н. "древовидную рекурсию" (когда каждый вызов fib вызывает fib ещё 2 раза, те, в свою очередь - каждый ещё по 2, итд). Вот вам и тормоза. Собственно, то же самое получим при попытке этот код переписать дословно, скажем, на паскале или С.

Методов избавления от таких тормозов два. Первый - тот же, что императивных языках: мемоизация. Тут, правда, свои методы. Вот код в посте neol использует именно мемоизацию. Определяемый в нём список fib - это бесконечный ленивый список, к моменту вычисления n-го элемента списка все предыдущие уже вычислены.

Кстати, ту же строчку можно записать покрасивее:

Код: Выделить всё

fib = 1: 1: zipWith (+) fib (tail fib)

Другой метод "избавления от тормозов" специфичен для ФЯ: преобразование рекурсии к виду хвостовой рекурсии, такую компилятор развернёт в цикл.

Незнакомые термины см. в википедии ;)

[Crazy]

Я понимаю, что рекурсия от бога, а итерация от человека, но числа Фибоначчи не тот случай.
Это как раз тот случай, когда лучше использовать итерацию.

[watashiwa_daredeska]

Haskell не знаю, следующий код взял с одного очень древнего холивара

Квинтэссенция холивара: The Evolution of a Haskell Programmer. Как раз про факториалы :)

[Crazy]

Haskell не знаю, следующий код взял с одного очень древнего холивара

Квинтэссенция холивара: The Evolution of a Haskell Programmer. Как раз про факториалы

Не Haskell, но все равно выглядит убого.

Код: Выделить всё

#include <iostream>

typedef unsigned int uint;

void fibonachi( uint& Rez,  uint n, uint pos, uint old1, uint old2)
{
    switch(n)
    {
        case 0: Rez = 0; break;
        case 1: Rez = 1; break;
    }
    if( n != pos)
    {
        Rez = old1;
        fibonachi(Rez, n, pos+1, old1 + old2, Rez);
    }
}
int recFib(int n)
{
    if( n == 2)    return 1;
    if( n == 1) return 0;
    return ( recFib(n-1) + recFib(n-2) );
}

int main()
{
    uint rez = 0;
    fibonachi(rez, 10, 0, 0 , 1);
    std::cout<< rez  <<std::endl;
    std::cout<< recFib(10) <<std::endl;
    return 0;
}

[NickLion]

Это как раз тот случай, когда лучше использовать итерацию.

Это как раз тот случай, когда лучше использовать формулу
tau = (sqrt(5.0)+1.0)/2.0;
Fibb(n) = (int) floor(0.5+(pow(tau,n)-pow(-tau,-n))/sqrt(5.0)));

PS извиняюсь, что не Хаскелль, а С, в связи с полным незнанием первого.

PPS формула точна - округление - для борьбы с эффектами ограниченной точности FPU.

[frp]

Я понимаю, что рекурсия от бога, а итерация от человека, но числа Фибоначчи не тот случай.
Это как раз тот случай, когда лучше использовать итерацию.

Покажите мне итерацию в чисто функциональном ЯП.
А с приведенными примерами разобрался.

[Crazy]

Это как раз тот случай, когда лучше использовать итерацию.

Это как раз тот случай, когда лучше использовать формулу

Это скучно и не интересно.

[NickLion]

Это скучно и не интересно.

Не скажите, вывести эту формулу и её запрограммировать намного интереснее, нежели в сотый раз писать цикл.

[sash-kan]

Это как раз тот случай, когда лучше использовать формулу

как насчёт числа фибоначчи от, к примеру, 500000? предупреждаю — у меня в буфер терминала точное значение не поместилось. последние цифры, для сверки с точностью вашего алгоритма: 18469780453125.

[Portnov]

Покажите мне итерацию в чисто функциональном ЯП.

Итерация она разная бывает тоже. Ну хотя бы:

Код: Выделить всё

$ ghci
Prelude> map (^2) [1..10]
[1,4,9,16,25,36,49,64,81,100]

Или там:

Код: Выделить всё

Prelude> import Control.Monad
Prelude Control.Monad> forM [1..10] print
1
2
3
4
5
6
7
8
9
10
[(),(),(),(),(),(),(),(),(),()]

:)

[sash-kan]

upd. вычисления, кстати, заняли 8 секунд.

Код: Выделить всё

11> Start=time(),F=fibonacci:f(500000),End=time().
{22,31,37}
12> Start.
{22,31,29}

для 1000000 считалось немножко дольше. одну минуту:

Код: Выделить всё

13> f().
ok
14> Start=time(),F=fibonacci:f(1000000),End=time().
{22,34,18}
15> Start.
{22,33,18}

последние цифры: 9893411568996526838242546875

p.s. это erlang.

[NickLion]

Это как раз тот случай, когда лучше использовать формулу

как насчёт числа фибоначчи от, к примеру, 500000? предупреждаю — у меня в буфер терминала точное значение не поместилось. последние цифры, для сверки с точностью вашего алгоритма: 18469780453125.

Немного не понял к чему это. Какой бы алгоритм ни использовать, для получения точного значения 500000-го числа Фиббоначчи нужно использовать длинную арифметику.
Впрочем, проверил - приближённое значение тоже не влезло в тип double. Так что надо писать длинку.

[t.t]

Это как раз тот случай, когда лучше использовать формулу

как насчёт числа фибоначчи от, к примеру, 500000? предупреждаю — у меня в буфер терминала точное значение не поместилось. последние цифры, для сверки с точностью вашего алгоритма: 18469780453125.

Насколько я помню, формула Бине точна для любых значений n.

[Portnov]

Формула-то точна, а в сопроцессор не любые числа влезают :) А если использовать длинную арифметику, так не всё ли равно - складывать по определению или возводить в степень по формуле? Кстати, если будут оценки, что быстрее - тоже интересно.

[sash-kan]

upd2. ага, это я слишком примитивный алгоритм использовал.
вот тут он как номер два изложен.
а если воспользоваться номером три, то 1000000 вычисляется за четыре секунды.

Немного не понял к чему это.

вы написали, что вычисление происходит точное. я и предложил проверить.

Насколько я помню, формула Бине точна для любых значений n.

это которую NickLion предлагает? звыняйтэ, в арифметике не силён. может и точно посчитает, только где ж такой компьютер взять, чтоб, допустим fib(1000000) посчитать?

[Portnov]

Мдя, а эрланг оказывается медленный :) Тот же "алгоритм 3" по той же ссылке, но на хаскеле:

Код: Выделить всё

fibo 0 _ pair = pair
fibo n (fib1,fib2) pair
  | n `mod` 2 == 0 = let squareFib = fib1*fib1
                     in  fibo (n `div` 2) (2*fib1*fib2 - squareFib, squareFib + fib2*fib2) pair
fibo n pair@(fibA1,fibA2) (fibB1,fibB2) =
  fibo (n-1) pair (fibA1*fibB2 + fibB1*(fibA2 - fibA1), fibA1*fibB1 + fibA2*fibB2)

fibo3 n = fst $ fibo n (1,1) (0,1)

main = forM_ [500000, 1000000] (print . fibo3)

(печатает значения по очереди для 500000 и 1000000):

Код: Выделить всё

$ time ./fib
./fib  0,40s user 0,01s system 72% cpu 0,564 total

[sash-kan]

а эрланг оказывается медленный

а кто говорил, что он быстрее компилируемого языка? не в плавках его сила.

p.s. да и машина у меня по нынешним меркам — слабачок. amd64 800MHz, 1Gb memory.
p.p.s. в мегагерцах не уверен. по крайней мере так говорит:
$ grep -i hz /proc/cpuinfo
cpu MHz : 800.000

[frp]

Натолкнулся на еще одну проблему.

Код: Выделить всё

fact = 0:1:2:[ fact!!(n-1) * n | n <- [3,4..] ]

Список факториалов (ниоткуда не копировал, сам написал). Дальше 15 выдает неправильный результат. В чем проблема?

UPD. Происходит переполнение. Как его избежать?

[frp]

UPD. Происходит переполнение. Как его избежать?

Пока решил через костыли:

Код: Выделить всё

natural :: [Int]
natural = [3,4..]
fact :: [Integer]
fact = 0:1:2:[ fact!!(n-1) * toInteger n | n <- natural ]

[frp]

Костыль получилось значительно сократить и сделать не костылем:

Код: Выделить всё

fact = 0:1:2:[ fact!!(n-1) * toInteger n | n <- [3,4..] ]

[Portnov]

Ну про факториалы-то выше вон хорошую ссылку привели :)

[t.t]

Формула-то точна, а в сопроцессор не любые числа влезают А если использовать длинную арифметику, так не всё ли равно - складывать по определению или возводить в степень по формуле? Кстати, если будут оценки, что быстрее - тоже интересно.

Ответ очевиден: зависит от реализации длинной арифметики. (: Да и от реализации развёртывания рекурсии, строго говоря, тоже. Так что в общем случае эта задача решения не имеет. (:

[Crazy]

Это как раз тот случай, когда лучше использовать формулу

как насчёт числа фибоначчи от, к примеру, 500000? предупреждаю — у меня в буфер терминала точное значение не поместилось. последние цифры, для сверки с точностью вашего алгоритма: 18469780453125.

Насколько я помню, формула Бине точна для любых значений n.

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

[frp]

что-то можно вычислять сколь угодно точно.

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