@Lesage

Самое быстрое вычисление чисел Фибоначчи?

Читая книгу Кнута, встретил упражнение "вычислить и вывести на экран первые 1000 чисел Фибоначчи". Т.к. у меня есть python, numpy и интернет, я решил, что упражнение слишком простое, и решил сделать самое быстрое вычисление чисел Фибоначчи на своём компьютере (без фанатизма как например вычисления матриц на GPU)
Я сравнил два подхода: через перемножение матриц и через формулу Бине. Сравнивал результаты без print, что бы вывод не замедлял выполнение программы. Вот код обеих подходов:

import numpy as np
import time
start_time = time.time()
for i in range (1000):
np.linalg.matrix_power(np.array([[1, 1], [1, 0]], dtype='O'),i)[1,0]
print("--- %s seconds ---" % (time.time() - start_time))

Что дало 0.08997 секунд на моём компьютере

import time
start_time = time.time()
fi = (1+5**0.5)*0.5
srt5 = 5**0.5
for i in range (1000):
round(fi**i/srt5)
print("--- %s seconds ---" % (time.time() - start_time))

Что даёт 0.000999 секунды на моём компьютере. Однако при попытке протестировать оба решения для первых 10 000 чисел, я упёрся в то, что round (а точнее сам тип данных float) не может переварить такие большие числа.

У меня появилось два вопроса касательно данной задачи:
1. Можно ли сделать быстрее без использования GPU для перемножения матриц?
2. Как посчитать первые 10 000 чисел Фибоначи при помощи формулы Бине?
  • Вопрос задан
  • 336 просмотров
Пригласить эксперта
Ответы на вопрос 1
@vabka
Токсичный шарпист
Использовать формулу Бинне тут нет смысла, тк вам надо первые 10к чисел посчитать, а не какое-нибудь единственное миллионное число.
Итеративный способ тут самый быстрый будет.

И сделать эффективнее не выйдет, тк вычисление следующего числа фибоначи - это одно сложение и два присваивания (куда уж проще).
Использовать GPU/SSE/AVX тоже нет смысла, тк данные сильно зависят друг от друга и только на передачу данных из ОЗУ в видеопамять уйдёт много времени

ЗЫ: мерять время надо без print, тк print в вашем случае будет занимать больше всего времени
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы