Comments 19
Карацубу забыли :)
Python и так использует Карацубу для больших чисел.
в JS упоролись чуть больше и выбирают алгоритм в зависимости от длины
(удалено)
Как написан fib_closed_form? Возводим double в степень, вычитаем, делим на double, округляем? Тогда вопрос - начиная с какого n даблы начнуть давать ошибки?
На самом деле, вторую скобку можно просто выкинуть, потому что там в n-ную степень возводится число по модулю меньше единицы. А если оценить погрешность, то получится, что ошибки начнутся в районе n=70.
Красота этой формулы в том, что корни всегда сокращаются, а результат оказывается целым числом.
Поэтому есть возможность рассчитать её без 'double' (к сожалению, ценой скатывания алгоритма в линейную сложность).
Можно и без этого. Правда по сути решение скатиться все в ту же линейную алгебру. Надо просто вести вычисления в кольце алгебраического расширения целых чисел через sqrt(5). По-человечески это значит, что числа у нас будут в форме 
Самое неожиданное для меня в этой статье, что линейная алгебра из заголовка не привела к использованию собственного разложения для вычисления степени матрицы.
В аналитической формуле числа, возводимые в степень n, не из воздуха берутся.
Т.е. ещё чуть-чуть текста добавить и было бы гораздо более полно.
Допишете?
Сам не буду, это много раз написано:
https://math.stackexchange.com/questions/1428534/fibonacci-sequence-and-eigenvalues
https://math.hawaii.edu/~pavel/fibonacci
Если автор это сделал, то пришел бы к 3 случаю. Чтобы понять это, достаточно взглянуть на собственные значения матрицы https://matrixcalc.org/ru/vectors.html#eigenvectors({{1,1},{1,0}})
Имеется в виду приведение матрицы к диагональному виду.
не существует способа подобного разбиения напрямую. Вместо этого нужно многократно делить число на два и смотреть на остаток от результата
Эээ... Целочисленное число в двоичном виде уже есть сумма двоек разной степени
Есть эвристика, можно просто заранее закешить важные числа, чтобы каждый раз не считать с начала.
Когда увидел возведение матрицы в степень, первым делом захотелось разложить её по собственным векторам, чтобы свести задачу к паре матричных умножений и возведению в степень двух скаляров
Получится известная формула с золотым сечением. В некоторой степени - не удобно, ибо нельзя считать в целых числах напрямую. А любая попытка сделать это все-равно сведется назад к возведению в степень матрицы.
Действительно! Сразу после своего комментария полез проверять, какие же там собственные значения, и банально получилось, что они соответствуют точной формуле с золотым сечением, которую приводит автор поста.
Следовало ожидать, вообще-то, каюсь XD
Недостатки получаются как раз те, о которых вы говорите. Надеялся, можно хитро избежать работы с вещественными числами, но сэкономить матричные умножения
Трюк из линейной алгебры для быстрого нахождения чисел Фибоначчи