Числа Фибоначи (1'000'000 займет меньше половины терабайта!)

1) Forbidden

Remote Host: [111.222.333.444] You do not have permission to access http://www.denx.gq.nu/bin/fibo.tar.bz2

Data files must be stored on the same site they are linked from.

Thank you for using FreeServers;

2) есть такой раздел Development;

3) зачем тебе числа Фибоначчи? В школе домашнее задание по информатике задали? Делом бы лучше занялся.

Извиняюсь за ссылку, но мой дайнлоадер закачивает ее в таком виде, но при открытии я вижу твориться ужас... на этой странице лежит проект: http://www.denx.gq.nu/whats_new.html

А вообще заняться есть чем, а это скажем так отдых от объективной и суровой а также и несправедливой реальности (наверное Вы видели фотореалистичные картинки на моем сайте, - это не просто так)

История программы начиналась с простого примера, где эти числа считались в рекурсии: int F(int X) { if ((X == 1) || (X == 2)) F = 1; else F = F(X-1) + F(X-2); }

и т.д. Я же решил рассмотреть этот алгортм подробнее и то что получилось у меня - программа способная посчитать (на моем компьютере пока что 143.000 - это рекорд, т.к. ограничение размера файла на моей ФС - 2048 Мб (2 ГБ), а чисто теоретически ограничения нет, поэтому единственное ограничение - размер файла) почти любое кол-во чисел(!)

Если бы в школе задавали такое делать... то я не знаю что было бы...

А Вы разве не знаете, что существует формула для n-го числа Фиббоначи? Надо знать только номер n и никакой рекурсии... Правда формула довольно сложная в плане вычислений (внешний вид простой), но сдается мне будет быстрее считать по ней а не по рекурсивному алгоритму. Раздел алгебры, позволяющий получить упомянутую формулу F(n) называется "Возвратные последовательности". Но если вам лениво и неинтересно, можете просто глянуть формулы 6 и 7 по линку http://mathworld.wolfram.com/FibonacciNumber.html

fibz = 1 : 1 : [ x+y | (x,y) <- zip fibz (tail fibz)]
main = print (fibz !! 10000)

Милионное число он, конечно, задолбается считать, 
но 10000-е находит за пару секунд. В отличие от
рекурсии :D И это такой тормоз, как Хаскелл.
При чём находит, естественно, все знаки числа.

Эта формула с корнями (по крайней мере та, которую я помню). Поэтому будут погрешности.

:) Я ровно этот же пример на Haskell-е хотел привести. Но все дело уткнулось в то, что Hugs98 не смог посчитать число большее 10000 - говорит, то C-стек кончился, то память кончилась...

>Эта формула с корнями (по крайней мере та, которую я помню). Поэтому >будут погрешности

Там есть формула с корнями, которые потом округляются, это раз. Более простецкая формула в результате ,будет содержать [sqr(5)]^n-[sqr(5)]^n. Не бойтесь, компутер посчитает оба корня с одинаковой точностью (инча бы он наку ненужен был) и вычтя получит нули после запятой. Вам надо лишь округлить что-то типа 8.00000 до int.

>Там есть формула с корнями, которые потом округляются, это раз. Более простецкая формула в результате ,будет содержать [sqr(5)]^n-[sqr(5)]^n. Не бойтесь, компутер посчитает оба корня с одинаковой точностью (инча бы он наку ненужен был) и вычтя получит нули после запятой. Вам надо лишь округлить что-то типа 8.00000 до int.

Писал ответ, но нашел такую вот ссылку http://algolist.manual.ru/maths/count_fast/fibonacci.php

>дело уткнулось в то, что Hugs98 не смог посчитать число большее 10000 - говорит, то C-стек кончился, то память кончилась...

Я, вроде, 40000-е считал. Но могу и ошибиться, а сейчас он у меня не установлен, чтобы проверить :)