Рекурсия: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 54:
Конечно, пока числа не выходят за пределы машинной точности (на компьютерах с 32-битной архитектурой это означает «меньше <math>2^{32}</math>»), сложение выполняется за фиксированое число тактов. Но, начиная с <math>F(48)</math>, уже нельзя использовать элементарные 32-битные целочисленные типы и нужно использовать 64-битные или писать «свою» ''длинную арифметику'', то есть представлять числа в виде массивов цифр в некоторой системе счисления (обычно используют систему с основанием 10000) и писать процедуры сложения таких чисел «столбиком». Например, число десятичных знаков в 1000-м числе Фибоначчи равно 209, и для сложения <math>F(1001) = F(1000) + F(999)</math> «столбиком» в десятичной системе счисления потребуется примерно 209 элементарных операций. Определение сложности задачи вычисления <math>F(n)</math> при больших <math>n</math> довольно трудная задача.
Указанный пошаговый алгоритм вычисления чисел Фибоначчи с учётом затрат на сложения длинных чисел является
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке [[w:Mathematica|Mathematica]] (см. http://www.wolfram.com):
|