Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 54
Мне кажется что C# не оптимизирует хвостовую рекурсию (хотя я могу ошибаться).
Интереснее было бы для сравнения привести вариант на F# (и сравнить скорость).
Интереснее было бы для сравнения привести вариант на F# (и сравнить скорость).
Забыли еще про способ с возведением в степень золотого сечения.
Он менее эффективен(целые перемножаются быстрее) и дает неточный ответ, но вспомнить про него надо было.
Он менее эффективен(целые перемножаются быстрее) и дает неточный ответ, но вспомнить про него надо было.
Вспоминать про него необязательно, так как на самоме деле описанный способ можно слегка переделать и получить то, что Вы говорите, а именно: если расписать матрицу [[1,1],[1,0]] в жордановой форме, то там получится диагональная матрица, у которой на месте (1,1) как раз золотое сечение. Ну и степень будет соответственная.
Но, как правильно отмечено, перемножать и складывать единички получается быстрее, чем иррациональное число в степень возводить.
Но, как правильно отмечено, перемножать и складывать единички получается быстрее, чем иррациональное число в степень возводить.
[занудство]
Все же для чисел фибоначчи с номером в районе 40 быстрее и понятнее будет так:
А дальше все равно нужно либо считать по модулю, либо реализовывать длинную арифметику (как с ней обстоят дела в фреймворке 4.0, кстати?). ДА проще реализовать для сочетания двух длинных чисел, чем для умножения. В общем за матрицу вам плюс, а вот пример, зачем она нужна, неудачен: матрица даст существенный прирост в производительности только при вычислении чисел фибоначчи по модулю с номером в районе >10^8, а если с ДА, то >1000 (чисто интуитивно, возможно я и ошибаюсь).
[/занудство]
Все же для чисел фибоначчи с номером в районе 40 быстрее и понятнее будет так:
static int fib(int n)
{
int[] f = new int[3];
f[1] = 1;
for (int i = 2; i <= n; i++)
{
f[i%3] = f[(i + 1)%3] + f[(i + 2)%3];
}
return f[n%3];
}
* This source code was highlighted with Source Code Highlighter.А дальше все равно нужно либо считать по модулю, либо реализовывать длинную арифметику (как с ней обстоят дела в фреймворке 4.0, кстати?). ДА проще реализовать для сочетания двух длинных чисел, чем для умножения. В общем за матрицу вам плюс, а вот пример, зачем она нужна, неудачен: матрица даст существенный прирост в производительности только при вычислении чисел фибоначчи по модулю с номером в районе >10^8, а если с ДА, то >1000 (чисто интуитивно, возможно я и ошибаюсь).
[/занудство]
Вы неправы.
Ваш алгоритм работает за O(n)
А описаный в статье за O(lg(n))
Ваш алгоритм работает за O(n)
А описаный в статье за O(lg(n))
Даже с учетом медленного умножения при n > 100 алгоритм из статьи будет быстрее.
специально написал простой код для замера производительности.
он становится ощутимо быстрее (в 2 раза) при n > 70 с использованием обычных int'ов.
если использовать long'и — при n == 120 они равны.
сейчас попробую померять время с длинной арифметикой в фреймворке 4.0
он становится ощутимо быстрее (в 2 раза) при n > 70 с использованием обычных int'ов.
если использовать long'и — при n == 120 они равны.
сейчас попробую померять время с длинной арифметикой в фреймворке 4.0
да, согласен. с длинной арифметикой их .net 4.0 они равны при n == 100
Если сравнивать с рекурсивным применением, то матрица дает прирост примерно при N>10. Конечно реализация с кэшированием намного быстрее на начальном этапе, и мы раньге получим overflow чем матрица начнет обгонять эту реализацию по производительности.
В .Net 4 должен появиться System.Numerics.BigInteger, а вот с его производительностью нужно разбираться.
В .Net 4 должен появиться System.Numerics.BigInteger, а вот с его производительностью нужно разбираться.
[занудство]
Так ваш код будет быстрее(без деления по модулю)
[/занудство]
static int fib(int n)
{
int[] f = new int[2];
f[0] = f[1] = 1;
for (int i = 2; i <= n; i++)
f[i & 1] += f[!(i & 1)];
return f[!(n & 1)];
}
* This source code was highlighted with Source Code Highlighter.Так ваш код будет быстрее(без деления по модулю)
[/занудство]
static int fib(int n)
{
return n > 1 ? fib(n - 1) + fib(n - 2) : n;
}Садись, два :)
…
a, b = b, a+1
…
по моему это проще )
a, b = b, a+1
…
по моему это проще )
Хм, не вижу, честно говоря, интереса играться с рекурсией, как приёмом в программировании, с числами Фибоначчи, для которых, вообще говоря, существует формула Бине для вычисления чисел Фибоначчи без рекурсии.
Когда научитесь быстро возводить в степень иррациональные числа, обращайтесь.
Показатель-то целый — тот же самый алгоритм работает. Формула Бине может дать более быстрый результат, чем решение в статье.
Впрочем, если мне нужны быстро и точно числа Фибоначчи, я лучше lookup-table заведу. Статья-то как бы не об этом :-)
Впрочем, если мне нужны быстро и точно числа Фибоначчи, я лучше lookup-table заведу. Статья-то как бы не об этом :-)
>>Формула Бине может дать более быстрый результат
Быстрый, но не точный. Как числа с плавающей точкой в компутере хранятся знаете?
Быстрый, но не точный. Как числа с плавающей точкой в компутере хранятся знаете?
А вы формулу-то поглядели или просто так пишете?
sub fibo_simple($) {
my @list = (1,1);
push @list, $list[-1]+$list[-2] for(3..$_[0]);
@list;
}
use constant { SQRT5 => sqrt(5), PHI => (sqrt(5)+1)/2 };
sub fibo_binet($) {
map {int(PHI**$_/SQRT5+.5)} 1..$_[0];
}
use Test::More tests => 1;
is_deeply([fibo_simple(60)],[fibo_binet(60)],
"Первые 60 чисел — по определению и по формуле Бине");Кстати, 60-е число сильно за пределами 2^32. Извините за перл, но вы легко проведёте тест на своём любимом языке.D:\>perl fibo_test.pl 1..1 ok 1 - Первые 60 чисел — по определению и по формуле Бине
Ну можно организовать числа с плавающей точкой высокой точности или гибрид double/long, где double хранит только дробную часть числа (не знаю, кто придумал, но увидел у П.Митричева) для не очень больших значений N.
Только игра не стоит свеч, лучше всё-таки целочисленно.
Только игра не стоит свеч, лучше всё-таки целочисленно.
public static mtx2x2 IntPower(mtx2x2 x, short power)
{
if (power < 2) return x;Ещё занудство: любая матрица в нулевой степени даст единичную матрицу. У вас не так =)
>C#
дальше не читал, ага.
дальше не читал, ага.
Формула Бине — не? ;)
Факториалы, числа Фибоначчи, я красотой рекурсии проникся, когда увидел рекурсивную сборку ханойской башни. Вот тогда я и захотел понять что это. Алгоритм, кажется, был в «Науке и жизнь» за какой-то бородатый год.
для каждого умножения матриц потребуется 8 умножений.
Лучше использовать эти формулы:
F(2n)=F(n+1)^2-F(n-1)^2
F(2n+1)=F(n+1)^2+F(n)^2
Лучше использовать эти формулы:
F(2n)=F(n+1)^2-F(n-1)^2
F(2n+1)=F(n+1)^2+F(n)^2
Что-то мне странно, человек пишет об «идеальном алгоритме», а в пример даже вариант с мемоизацией не привел.
Например, такой:
Func<ulong, ulong> fib = null;
fib = (x) => x > 1? fib(x-1) + fib(x-2): x;
fib = fib.Memoize();
Что, на мой взгляд, гораздо симпатичнее) Производительность, конечно, надо сравнивать, но не 4 секунды на fib(40), это уж точно.
А за то, что автор, ударился в такие исследования, даже не упомянув такую возможность языка, как мемоизация, на мой взгляд — нереспект(
Например, такой:
Func<ulong, ulong> fib = null;
fib = (x) => x > 1? fib(x-1) + fib(x-2): x;
fib = fib.Memoize();
Что, на мой взгляд, гораздо симпатичнее) Производительность, конечно, надо сравнивать, но не 4 секунды на fib(40), это уж точно.
А за то, что автор, ударился в такие исследования, даже не упомянув такую возможность языка, как мемоизация, на мой взгляд — нереспект(
Алгоритм однозначно хорош. Но я для себя решил попробовать, что же такое «идеальный алгоритм» возведения в целочисленную степень.
Написал его реализацию на С# и сравнил с Math.Pow — два метода дают абсолютно одинаковый результат при любых значениях степени и самого числа, возводимого в степень. Сдается, что в Microsoft работают неглупые парни и знают, что возводить в степень не стоит простым циклом.
Написал его реализацию на С# и сравнил с Math.Pow — два метода дают абсолютно одинаковый результат при любых значениях степени и самого числа, возводимого в степень. Сдается, что в Microsoft работают неглупые парни и знают, что возводить в степень не стоит простым циклом.
Одинаковый результат не в смысле значения, а в смысле производительности. Т.е. тест заключался в возведении в степень массива данных.
Короче говоря, время работы Math.Pow не дольше.
Короче говоря, время работы Math.Pow не дольше.
У вас что-то кардинально не так. На целых числах вы должны получить совершенно разные результаты. Почитайте ветку обсуждений, тут кажется это уже затронули.
Целые не пробовал. Надо посмотреть.
Я как бы не пытаюсь каким-либо образом перекритиковать.
Просто алгоритм действительно очень оптимизирован и кажется его истоки далеко в математике. Из-за этого решил его написать по описанию автора и сравнить с существующими средствами.
Кроме этого, если почитать документацию к процессорам, то там можно найти соответствующие опкоды. Процессоры давно умеют возводить в степень аппаратно, плюс Math.Pow — это extern функция, как многие другие из этого класса. Возможно, процессоры используют некое подобие описанного выше «идеального алгоритма»
Я как бы не пытаюсь каким-либо образом перекритиковать.
Просто алгоритм действительно очень оптимизирован и кажется его истоки далеко в математике. Из-за этого решил его написать по описанию автора и сравнить с существующими средствами.
Кроме этого, если почитать документацию к процессорам, то там можно найти соответствующие опкоды. Процессоры давно умеют возводить в степень аппаратно, плюс Math.Pow — это extern функция, как многие другие из этого класса. Возможно, процессоры используют некое подобие описанного выше «идеального алгоритма»
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Числа Фибоначчи (этюд на C#)