> более открытая платформа
Прошу извинить меня за занудство, но мне не понятно, как вы определяете меру открытости? Что значит «более»? Linux — открытая платформа, Windows — закрытая. Другого не дано.
Ну это уже отдельная большая тема. Вообще да, «проще тупо через матрицы считать». Обобщить просто так не получится, нужно каждый раз выводить эти формулы для разных рекуррентных функций. Более точно сказать не могу, ибо не обладаю достаточным уровнем математической подготовки. Если бы мне нужно было считать для любых линейно-рекуррентных функций, я бы юзал матричный способ.
По поводу битовой магии: она там просто для явного подсчёта количества шагов алгоритма. Сам по себе алгоритм простейший — обычный метод Дихотомии (последовательного деления на 2).
Вот эта строчка
Там используются формулы для чётного и нечётного N, вроде бы в википедии есть эти формулы. Они, насколько я помню, получаются из матричных. Я где-то видел хорошую публикацию на эту тему, там неплохо разжеваны все формулы и свойства последовательности Фибоначчи, попробую найти.
Обычный стандартный алгоритм, не достоин отдельной статьи. К тому же описали вы банальные вещи.
Вот вам ещё короче версия O(log N) по модулю M (использует рекуррентные формулы)
typedef unsigned long long uint64;
uint64 fib_mod_m (uint64 n, uint64 m)
{
uint64 x = 1, y = 0, xx, t;
if (n <= 1)
return n;
int b = 62 - __builtin_clzll(n);
for (; b >= 0; b--)
{
xx = (x * x) % m;
x = (xx + 2 * x * y) % m;
y = (xx + y * y) % m;
if ((n << (63 - b)) >> 63)
{
t = x;
x = (x + y) % m;
y = t;
}
}
return x;
}
Тут тоже за логарифм, ведь нужно возводить в степень N. В принципе эту формулу с учётом возведения в степень реально уместить в одну строку, но она верно считает только для N<70.
Можно написать за логарифм N-ое число Фибоначчи по модулю M, но если попробовать уместить реализацию в одну строку, получается каша мала. Только что пробовал :) Всё равно же, если считать не по модулю, то 50-ый элемент не уместится даже в int64, смысла нет его считать.
Дело не в знании, а в отсутствие желания учиться. Тут многие почему-то думают, что если кто-то не может писать двоичный поиск, то он не программист. Это не так. Если человек не знает, но при этом пробовал написать и изучил правильную версию — респект таким людям. Если может написать — тоже респект. А вот те, кто недоумевают, мол, зачем мне оно надо, если уже есть куча готовых версий — таким не место в программировании. Каким образом они будут решать сложные задачи, если с простыми справиться не способны? Будут писать кривые неоптимальные алгоритмы. Понятное дело, что умение писать двоичный поиск — это не гарант успеха, но у таких намного больше шансов решить сложную задачу.
Это если часы двигаются со скоростью, близкой к скорости света :) Обычная же ситуация, сидишь, а мимо тебя часы пролетают. Оказывается, это тоже не учитывают программисты.
Для слияния O(N log K) наилучшая асимптотика. Правда там константа очень маленькая, и можно реализовать не-рекурсивную версию, будет ещё быстрее.
Но можно подойти с другой стороны, и перед сортировкой обработать массив неким подобием quicksort, который не сортирует, а просто разбивает массив на K частей (при этом K — степень двойки) таким образом, что каждый элемент 1-ой части меньше любого элемента 2-ой части и т.д. Т.е. после сортировки в K потоков мы получаем уже окончательный массив.
В этом алгоритме получается после фазы разбиения запустить сортировки подчастей параллельно.
Не очень удачное решение с точки зрения параллельности. Мне кажется, более thread-friendly было бы разбить массив на N одинаковых частей и запустить для каждой части quicksort в своем потоке.
Прошу извинить меня за занудство, но мне не понятно, как вы определяете меру открытости? Что значит «более»? Linux — открытая платформа, Windows — закрытая. Другого не дано.
Вот эта строчка
эквивалентна
Вот вам ещё короче версия O(log N) по модулю M (использует рекуррентные формулы)
Никто же не спрашивал, зачем в школе изучать математику. «Математику уже затем учить надо, что она ум в порядок приводит» © Ломоносов. Здесь то же самое.
Но можно подойти с другой стороны, и перед сортировкой обработать массив неким подобием quicksort, который не сортирует, а просто разбивает массив на K частей (при этом K — степень двойки) таким образом, что каждый элемент 1-ой части меньше любого элемента 2-ой части и т.д. Т.е. после сортировки в K потоков мы получаем уже окончательный массив.
Не очень удачное решение с точки зрения параллельности. Мне кажется, более thread-friendly было бы разбить массив на N одинаковых частей и запустить для каждой части quicksort в своем потоке.