Читая книгу Кнута, встретил упражнение "вычислить и вывести на экран первые 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 чисел Фибоначи при помощи формулы Бине?
Использовать формулу Бинне тут нет смысла, тк вам надо первые 10к чисел посчитать, а не какое-нибудь единственное миллионное число.
Итеративный способ тут самый быстрый будет.
И сделать эффективнее не выйдет, тк вычисление следующего числа фибоначи - это одно сложение и два присваивания (куда уж проще).
Использовать GPU/SSE/AVX тоже нет смысла, тк данные сильно зависят друг от друга и только на передачу данных из ОЗУ в видеопамять уйдёт много времени
ЗЫ: мерять время надо без print, тк print в вашем случае будет занимать больше всего времени
