[программирование] Интересная задача

0

0

Написать программу, считающую n-e число фибоначчи: f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)
Программе передаётся один параметр - целое число от 0 до 2^31-1. Программа должна подсчитать соответствующее число фибоначчи и записать его в некий файл (или выдать в stdout) в бинарной форме (255 = 0xff, 256 = 0x0100, ...). Рекомендуется использовать многопоточность.

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

Полагаю, оптимальный вариант - многопоточное решение на C с GMP, но не уверен. Может что-нибудь ленивое на хаскеле себя покажет )

Я на джаве простой вариант накидывал, но оно тормозит и жрёт память :) f(1000000) не дождался.

Ссылка

←	Вопрос по lds скриптам (скриптам линкера)

[c++] iterator exception

→

← 1 2 →

Ответ на: комментарий от dilmah 28.04.10 14:47:55 MSD

> Есть целочисленное решение: возвести матрицу [1 1; 1 0] в степень N.

Ура, первый правильный ответ! Возводится в степень N естественно за O(log(N)).

balodja ★★★
(29.04.10 01:49:03 MSD)

Ответ на: комментарий от hired777 28.04.10 21:54:47 MSD

> Я вроде помню решение за logN - там нужно матрицу 2х2 возвести в эту степень. Если интересно - могу вспоминать дальше.

Тред почитай. Прям перед тобой решение это написано на сях, а еще раньше dilmah озвучил.

balodja ★★★
(29.04.10 01:53:12 MSD)

Ссылка

Ответ на: комментарий от balodja 29.04.10 01:49:03 MSD

Тут особенность в том, что logN операций сложения/умножения, а не операций процессора. С какого то момента числа становятся большими, и складываются/перемножаются всё дольше и дольше.

~~Legioner~~ ★★★★★
(29.04.10 07:33:58 MSD) автор топика

в gmp, как помню, есть функции для вычисления числа фибоначчи: mpz_fib_ui and mpz_fib2_ui. Считают очень быстро.

najar ★
(29.04.10 10:56:55 MSD)

Ссылка

В SICP был алгоритм O(1). Ищи: http://newstar.rinet.ru/~goga/sicp/sicp.pdf

naryl ★★★★★
(29.04.10 11:14:39 MSD)

Ответ на: комментарий от Legioner 29.04.10 07:33:58 MSD

Ага, и сколько требуется операций процессора на умножение N*N? Берем http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

В итоге получаем O(log(N)^2 * log(log(N)) * log(log(log(N)))) , короче, почти O(log(N)^2). И чо? С помощью фиксированной точки надеешься получить лучше?

balodja ★★★
(29.04.10 12:03:55 MSD)