Согласен по всем статьям. Во-первых, действительно, если и использовать стандартные типы, то лучше будет double - там 16 значащих цифр. Во-вторых, округление результата при помощи delta и приведения типа к Int64 имеет смысл до 1Е17 максимум (для использования типа double), а дальше можно вообще не париться с округлением, и просто s возвращать.
Для повышения точности можно использовать тип BigInteger, тогда вроде всё будет работать бог знает до куда, главная проблема будет вычислить соответствующее количество значащих цифр для констант (1+sqrt(5))/2 и 1/sqrt(5).
Показанный выше алгоритм я изначально планировал как быстрый, но с ограниченной точностью. Главный вопрос, какова от него от такого польза? Вечный вопрос, нужно ли вообще писать алгоритм, если заранее не знаешь, понадобится ли он вообще кому-нибудь?
Без каких-либо претензий, предлагаю такой вариант.
// быстрое вычисление чисел Фибоначчи для х => 0 по формуле Бине
public static Int64 FastFibonacci(int x)
{
const float cp = 1.6180339887498948482046f; // (1+sqrt(5))/2
const float sqrt5 = 0.4472135954999579392818f; // 1/sqrt(5)
const float delta = 0.4999999999f; // для округления вправо
float s = sqrt5;
float v = cp;
int c = x;
while (c != 0)
{
if (c % 2 == 1)
{
s = s * v;
}
c = c >> 1;
v = v * v;
}
return (Int64)(s + delta);
}
Благодарю Вас за положительную оценку моей первой статьи.
И, пользуясь возможностью, обращаюсь к читателям: пишите мне, пожалуйста, свои предложения по оптимизации/ускорению кода функций из этой статьи. Уверен, его можно сделать ещё быстрее. Заранее благодарю.
И в статье, и в коде ещё полнО мест, где можно (и нужно) внести корректировку. И если на счёт текста (именно текста) статьи я уже определился, что менять ничего не стану (причина в п. 11 статьи "Как писать, чтобы тебя читали"), то с кодом всё диаметрально противоположно. Более того, я очень прошу читателей вносить свои предложения/замечания. Дельные идеи я внесу в код, пусть функции будут ещё быстрее!
PS: Откровенно говоря, я ожидал, что народ возбудится на рисунок 4 с мешаниной графиков. Сначала хотел его облагородить (или вообще заменить на что-то более информативное), но подумав, оставил как есть.
Согласен, измерено в сепульках, для любого другого компьютера будут другие сепульки. Но главное было сравнить полученную функцию с существующей - для этого сойдут и сепульки.
(На самом деле BenchmarkDotNet пока никогда не использовал, будет время - обязательно попробую)
Согласен по всем статьям. Во-первых, действительно, если и использовать стандартные типы, то лучше будет double - там 16 значащих цифр. Во-вторых, округление результата при помощи delta и приведения типа к Int64 имеет смысл до 1Е17 максимум (для использования типа double), а дальше можно вообще не париться с округлением, и просто s возвращать.
Для повышения точности можно использовать тип BigInteger, тогда вроде всё будет работать бог знает до куда, главная проблема будет вычислить соответствующее количество значащих цифр для констант
(1+sqrt(5))/2 и 1/sqrt(5).Показанный выше алгоритм я изначально планировал как быстрый, но с ограниченной точностью. Главный вопрос, какова от него от такого польза? Вечный вопрос, нужно ли вообще писать алгоритм, если заранее не знаешь, понадобится ли он вообще кому-нибудь?
Без каких-либо претензий, предлагаю такой вариант.
Прошу не судить строго, может чего не понял.
Благодарю Вас за положительную оценку моей первой статьи.
И, пользуясь возможностью, обращаюсь к читателям: пишите мне, пожалуйста, свои предложения по оптимизации/ускорению кода функций из этой статьи. Уверен, его можно сделать ещё быстрее. Заранее благодарю.
И в статье, и в коде ещё полнО мест, где можно (и нужно) внести корректировку. И если на счёт текста (именно текста) статьи я уже определился, что менять ничего не стану (причина в п. 11 статьи "Как писать, чтобы тебя читали"), то с кодом всё диаметрально противоположно. Более того, я очень прошу читателей вносить свои предложения/замечания. Дельные идеи я внесу в код, пусть функции будут ещё быстрее!
PS: Откровенно говоря, я ожидал, что народ возбудится на рисунок 4 с мешаниной графиков. Сначала хотел его облагородить (или вообще заменить на что-то более информативное), но подумав, оставил как есть.
И оно, таки, есть! :)
Прямо в первом предложении. Между прочим, именно эта константа когда-то привлекла моё внимание к статье в Википедии, а затем и на Хабре.
Согласен, измерено в сепульках, для любого другого компьютера будут другие сепульки. Но главное было сравнить полученную функцию с существующей - для этого сойдут и сепульки.
(На самом деле BenchmarkDotNet пока никогда не использовал, будет время - обязательно попробую)