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

[t.t]

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

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

Интересная у Вас забава. (: Только Вы подзабыли, что речь идёт о целочисленной последовательности. Или Вы хотите сказать, что с какой точностью по такой формуле ни считай, погрешность всё равно рано или поздно превысит единицу? Довольно смелое утверждение.

[Crazy]

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

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

Интересная у Вас забава. (: Только Вы подзабыли, что речь идёт о целочисленной последовательности. Или Вы хотите сказать, что с какой точностью по такой формуле ни считай, погрешность всё равно рано или поздно превысит единицу? Довольно смелое утверждение.

Забыл про машинное эпсилон и неравномерную сетку чисел с большим порядком?
В формуле Бине используются иррациональные числа.

[Portnov]

Проверил ради интереса. При использовании типа Double для формулы погрешность превышает 1 уже для n=76. Понятно, что если сделать какой-нибудь long double, его хватит на дольше, но тем не менее. Единственный способ не потерять точность, видимо - длинная арифметика.

[Crazy]

Проверил ради интереса. При использовании типа Double для формулы погрешность превышает 1 уже для n=76. Понятно, что если сделать какой-нибудь long double, его хватит на дольше, но тем не менее. Единственный способ не потерять точность, видимо - длинная арифметика.

Из формулы Бине абсолютная погрешность только по вычислению корня из пяти будет 2*delta^(n-1), поэтому от lond double толка будет мало.
На длинную арифметику смотрю скептически, тем более что в случае итерации будет n сложений целых чисел, а по формуле 2*n умножений вещественных чисел.

[t.t]

Забыл про машинное эпсилон и неравномерную сетку чисел с большим порядком?
В формуле Бине используются иррациональные числа.

Ещё раз: для "чисел с большим порядком" всё равно нужна длинная арифметика, которая совершенно не обязана быть целочисленной (более того, все виденные мною быстрые реализации не целочисленные). При чём здесь "машиное эпсилон", если арифметика используется программная?

На длинную арифметику смотрю скептически, тем более что в случае итерации будет n сложений целых чисел, а по формуле 2*n умножений вещественных чисел.

Это уже совершенно другой вопрос. Конкретно в той дискуссии, на которую я отвечал, речь шла только о точности, а не о скорости.

[drBatty]

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

а почему нет?

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

doc@bx:~$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
scale=100
sqrt(2)
1.414213562373095048801688724209698078569671875376948073176679737990\
7324784621070388503875343276415727

...поставил 10000 - задумалась...
...806MHz.
зыж ну секунд 20 думала.

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

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