Предположим, после всех вычислений числитель принял вид a+b*sqrt(5). Здесь a и b могут быть только целыми (поскольку все исходные данные целые, а мы складываем, умножаем и вычитаем). Но если a+b*sqrt(5) разделить на sqrt(5) (обычным образом), то получится a/sqrt(5)+b. Величина a/sqrt(5) не может быть целой ни при каком b, кроме нуля. Примерно так.
А разве я писал про «сложности»? Я сравнивал сортировку и вставку в упорядоченный массив для поиска m максимумов. И показал, что даже простая вставка быстрее. Хотя теоретически это вполне очевидно. Но решил проверить — насколько быстрее.
У Питона максимальное время (для 500тыс.чисел) — 120 миллисекунд.
«А по оптимизированной реализации ещё хуже: 60000 против 50» — какая это оптимизированная версия? Вы о чем?
Но если бы a и b были рациональными, а не целыми, то поле получилось бы (о чем, собственно, Вы и написали).
Я и чувствовал, что поле все-таки не получится... Спасибо за очень важную поправку!
Именно!
Да, спасибо. Описка
Предположим, после всех вычислений числитель принял вид a+b*sqrt(5). Здесь a и b могут быть только целыми (поскольку все исходные данные целые, а мы складываем, умножаем и вычитаем). Но если a+b*sqrt(5) разделить на sqrt(5) (обычным образом), то получится a/sqrt(5)+b. Величина a/sqrt(5) не может быть целой ни при каком b, кроме нуля. Примерно так.
Да, матричный метод "естественнее" для вычисления чисел Фибоначчи. Но суть заметки - в "реабилитации" формулы Бине.
На самом деле - дело привычки!
и да - getd делает именно это. Но не я это придумал. В основе HomeLisp лежит книга С.С.Лаврова и Г.С.Силагадзе, там такая функция была (кажется)...
Да, у меня тоже была такая мысль.
О, спасибо! Подумаю об этом!
«А по оптимизированной реализации ещё хуже: 60000 против 50» — какая это оптимизированная версия? Вы о чем?