Комментарии 14
Большинство людей могут сообразить, как сделать это за константное время. Но под силу ли нам улучшить этот показатель? Даже не сомневайтесь.
Большинство людей найдет в Гугле формулу Бине, которая даст ответ за константное время (или логарифмическое, смотря как считать возведение в степень):
![image](https://habrastorage.org/getpro/habr/comment_images/afb/9cf/ede/afb9cfedee46ca6dd8f7b774ff525177.png)
И я не понял, с каких пор логарифмическая сложность считается лучше константной?
Или я что-то фундаментальное не понимаю в этой статье? Может, нужна оговорка, что алгоритм не может оперировать нецелыми числами?
+5
Просто константная перепутана с линейной)
+2
С какого члена ряда Фибоначчи у вас будет потеря точности в младших разрядах?
+2
Примерно с 65 числа Фибоначчи (17 167 680 177 565) погрешность будет около 0.037.
В любом случае это сильно больше, чем может поместится в
P.S. Я не утверждаю, что формула Бине является удобным на практике способом решения данной задачи, просто не упомянуть ее в контексте сложности вычисления чисел Фибоначчи было странно.
В любом случае это сильно больше, чем может поместится в
int
, который используется в коде в статье.P.S. Я не утверждаю, что формула Бине является удобным на практике способом решения данной задачи, просто не упомянуть ее в контексте сложности вычисления чисел Фибоначчи было странно.
+1
Что ж, это повод не использовать int в статье. :)
Расхождение в 1 начинается с 76 члена 3 416 454 622 906 707.
Ничего странного нет, ибо точного ответа эта формула не даёт.
Расхождение в 1 начинается с 76 члена 3 416 454 622 906 707.
Ничего странного нет, ибо точного ответа эта формула не даёт.
+2
График
![](https://habrastorage.org/r/w1560/webt/vp/kl/s8/vpkls8quhxy4g6jdqgps043ltfs.png)
![](https://habrastorage.org/webt/vp/kl/s8/vpkls8quhxy4g6jdqgps043ltfs.png)
Для формулы Бине использовался numpy.float64, для матричной формулы — numpy.uint64. После 93 члена uint64 переполняется.
Думал глянуть на numpy.float128, но там 128 полезных бит даже документация не гарантирует.
+1
При всём уважении к Алану Чену, на Хабре эту тему уже раскрыли куда лучше.
+9
В прошлый раз эта тема на хабре была раскрыта лучше https://habr.com/ru/post/261159/
+4
Наивное вычисление знаменитой последовательности Фибоначчи производится за экспоненциальное время. Большинство людей могут сообразить, как сделать это за константное время.
Наивное решение — цикл — дает линейное время.
Как посчитать за константное сказать не берусь. Разве что заранее посчитать до нужной точности.
Впрочем, дальше вы пишете Naive: O(n). Так какой вариант имелся в виду? Обычный линейный, рекурсивный или константный (каким бы он ни был)?
Да, переписал вашу реализацию на Си с заменой int на long long, так вот, после 46-го числа наступает переполнение, тогда как обычная циклическая вроде считает нормально. Забавно что ломается только на нечетных
0
Плюс ко всему вышеперечисленному, у вас ошибка тут:
Поменяются местами не строки, а столбцы.
Если мы поменяем местами две строки единичной матрицы и умножим ее на другую матрицу, это будет эквивалентно перестановке тех же двух строк у другой матрицы
Поменяются местами не строки, а столбцы.
0
Или я совсем забыл принципы умножения матриц, или после «это будет эквивалентно перестановке тех же двух строк у другой матрицы» результирующая матрица записана неправильно.
Если я правильно понимаю, то перемножаемые матрицы нужно поменять местами, потому что порядок имеет значение.
Если я правильно понимаю, то перемножаемые матрицы нужно поменять местами, потому что порядок имеет значение.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисляем последовательность Фибоначчи за логарифмическое время