[программирование] Интересная задача

google: Формула Бине

Чёрт а я O(lnN) придумывал :(

http://ru.wikipedia.org/wiki/Формула_Бине

И как эта формула поможет, всё же не совсем понимаю.

И как эта формула поможет, всё же не совсем понимаю.

она поможет не считать цикл из 1000000 итераций, а посчитать одну формулу вместо этого.

Чтобы эту формулу точно подсчитать для n = 1000000, нужно будет подсчитать sqrt(5) с очень большой точностью, зависящей от n, подсчитать нужные логарифмы и экспоненты (для возведения в степень), опять же с большой точностью, что выливается в ряды. В общем не очевидно.

> И как эта формула поможет, всё же не совсем понимаю.

Если будете пользоваться этой формулой, то обращаю Ваше внимание на \sqrt(5). Это достаточно проблемное место при больших N. Советую посчитать с нужной точностью этот корень заранее и потом просто использовать эти данные.

>...очень большой точностью, зависящей от n, подсчитать нужные логарифмы и экспоненты (для возведения в степень), опять же с большой точностью, что выливается в ряды.

Ограничение на N известно. Maxima посчитает sqrt(5) c нужной точностью. Сама программа (на си или джаве) будет только складывать или перемножать эти корни (т.е. последовательности чисел - результат работы maxima).

ну при том способе который я использовал, самих промежуточных чисел считается мало, для 2000000 было подсчитано 71 число, просто начиная с какого то момента они становятся большими, f(2000000) занял 86 килобайтов, и каждое сложение/умножение уже получается достаточно долгим. Считать вещественную арифметику, имхо, будет не быстрее. При том что ещё нужно вывести формулу, говорящую с какой точностью надо считать каждый компонент.

> sqrt(5) c нужной точностью

Есть целочисленное решение: возвести матрицу [1 1; 1 0] в степень N.

Я что-то не думаю, что стоит заморачиваться с формулой Бине.

Посчет числа Фиббоначи в лоб потребует n сложений.

Формула Бине требует возведение в степень (log n умножений), а умножение - более дорогая операция. И главное потом еще и деление. Сомневаюсь, что это быстрее.

> Считать вещественную арифметику, имхо, будет не быстрее.

Быстрее. Возведение в степень займет [log(N)]^ операций умножения ([]^ -целая часть сверху). Всего нужно провести две операции возведения в степень и одно вычитание. Причем возведение в степень можно делать с точностью до первого знака после запятой.

При том что ещё нужно вывести формулу, говорящую с какой точностью надо считать каждый компонент.

Способность это сделать как раз и отделяет программиста от быдло-программмста.

+ 1 деление.

Это тоже стоит почитать.

Ну и наверняка масса самых разных оптимизаций уже придумано.

> Рекомендуется использовать многопоточность.

На двуядерном процессоре самое то запустить параллельно 2 операции возведения в степень.

fib n = fib' (n-1) (1, 0)
    where fib' 0 (!a, !b) = a
          fib' !n (!a, !b) = fib' (n-1) (a+b, a)

main = print $ fib 1000000

real	0m20.990s
user	0m20.489s
sys	0m0.210s

Не знаю, чего у тебя жаба скопытилась

> Ну и наверняка масса самых разных оптимизаций уже придумано.

Интересней всего как это сделать, например, на CUDA.

>На двуядерном процессоре самое то запустить параллельно 2 операции возведения в степень.

Да все равно. Деление займет много времени. Чуть ли не больше, чем n сложений.

Я просто нетерпеливый, для миллиона у меня в итоге после микрооптимизаций стало 10 секунд считать.

Попробуй эрланг, в какой-нибудь локалке. Думаю даже 50 машин дадут офигительный прирост производительности.

> Да все равно. Деление займет много времени. Чуть ли не больше, чем n сложений.

Вызывающе не верная информация. Деление займет меньше всего времени. Вы в итоге должны получить целое число. => Делить придется на очень короткую последовательность чисел.

>Вызывающе не верная информация. Деление займет меньше всего времени. Вы в итоге должны получить целое число. => Делить придется на очень короткую последовательность чисел.

NO U. Короче ты не прав. В данном случае делить надо будет на асимптотически такую же, как и результат.

А вообще в хаскеле очень быстрая арифметика, удивлён, аналогичный вариант в джаве медленнее.

>А вообще в хаскеле очень быстрая арифметика, удивлён, аналогичный вариант в джаве медленнее.

Вот этим я тоже удивлен. Где-то слышал как раз обратное про хаскель =)

> NO U. Короче ты не прав. В данном случае делить надо будет на асимптотически такую же, как и результат.

1. Деление в данном случае это умножение на 1/sqrt(5) — последовательность получена заранее (0.447213595...).

2. Умножение:

sum_k(a_k*10^k)*sum_m(b_m*10^-m)=sum_k,m(a_k*b_m*10^(k-m)).

Сколько членов нужно суммировать? Чтобы получить число с точностью до 10^-1 ?

s/10/2

>Вы в итоге должны получить целое число. => Делить придется на очень короткую последовательность чисел.

Вот тут у тебя ошибка. Не важно, целое/не целое. Важно количество значащих цифр.

d(a/x) = -a/x^2 * dx = -a/x * (dx/x)

a/x - больше 200000 значащих цифр.

Ну хорошо, если известно 1/sqrt(5), то деление не проблема.

Хотя это конечно читерство, и 1/sqrt(5) заранее считать нельзя.

А то я сразу напишу

print «19532821287077577316...»

Вообще я вроде понял. phi^n = 2^(n * ln2(phi)), а это умножение заранее подсчитанного числа на n и сдвиг десятичной точки в нужную сторону. В итоге получаем из «тяжёлых» операций умножение n на длинное число с плавающей точкой, ещё одно такое умножение, сложение двух чисел и умножение результата на ещё одно длинное число с плавающей точкой. В принципе пока неясным остаётся вопрос о точности этих констант, которые нужно подсчитать перед выполнением, может они по 10 гигабайтов будут занимать для нужной точности, или их вычисление займёт слишком долгое время. Попробую подсчитать нужную точность.

> Хотя это конечно читерство, и 1/sqrt(5) заранее считать нельзя.

Ага, и писать надо на ассемблере. Всегда при вычислительной оптимизации программ на первом этапе разделяют данные которые считают заранее и те, которые считают «на лету». Это как таблицы стрельбы.

>Сколько членов нужно суммировать? Чтобы получить число с точностью до 10^-1 ?

Через суммирование будет дольше метода влоб, кстати.

>> Хотя это конечно читерство, и 1/sqrt(5) заранее считать нельзя.

Ага, и писать надо на ассемблере. Всегда при вычислительной оптимизации программ на первом этапе разделяют данные которые считают заранее и те, которые считают «на лету». Это как таблицы стрельбы.

Нет. Задача по заданному n вычислять fib(n). Этого твоя программа делать для n больших определенного не будет => fail

>Чёрт а я O(lnN) придумывал :(

Реализация алгоритма получения числа Фибоначчи за логарифмическое число шагов давалась как упражнение (1.19) в SICP, разве нет?

> их вычисление займёт слишком долгое время

Это вряд ли, не дольше чем расчет нужного числа. Целочисленный расчет корня из 5 через матрицы тут уже показали.

вопрос о точности этих констант

Требуемая точность зависит от N, можно заранее составить таблицу точности. Впрочем это все больше скатывается в составление таблиц чисел фибоначчи, непонятно почему это нельзя делать заранее.

Решение с заранее известным корнем из 5 более логично для квантовых компьютеров, где операция взятия корня такая же естественная («аппаратная») как и умножение. В классических же вычислениях преимущество будет за таблицами, а вот таблицы должны составляться на мега-кластерах, под них алгоритм не очевиден. Впрочем возможно операция взятия корня хорошо на кластере считается (не знаю).

> Нет. Задача по заданному n вычислять fib(n). Этого твоя программа делать для n больших определенного не будет => fail

Программе передаётся один параметр - целое число от 0 до 2^31-1.

>> Сколько членов нужно суммировать? Чтобы получить число с точностью до 10^-1 ?

Через суммирование будет дольше метода влоб, кстати.

Это я привел для аналитического получения оценки на необходимое число знаков после запятой в операции деления. Так, разумеется, никто не считает.

Может быть, алгоритм там достаточно тривиальный получился.

Числа Ф. это интересная задача? Три раза ха.

Интересная задача это украсть поезд алюминия, загнать налево, откатить кому надо и стать депутатом.

для хаскелля кстати есть один интересный вариант вычисления - сложение двух бесконечных списков.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fib n = fibs ! n

>Интересная задача это украсть поезд алюминия

Решение существует. Неинтересная задача.

Это же решение рекурсивной последовательности, как у на дискретке!)

А нужно с бесконечной точностью считать?

С конечной (пока у компьютеров памяти не хватает для бесконечной точности), но так, чтобы f(n) = round(result), где result - ответ, полученный по этой формуле.

>round(result)

Формула _всегда_ даст целое число.

Кстати, ведь значит можно принять x=sqrt(5), и разложить обе скобки по биному Ньютона, разделяя в процессе на x, потом привести слагаемые чётной степени (нечётные сократятся из условия целости результата). Оба Бинома можно в одном цикле считать.

Надо вычислить только 2^n и потом в цикле за n/2 шагов, в биноме у нас только единица и x, значит нужно высчитать только биноминальные коэффициенты.

Это можно сделать быстро?

Или посчитать n-ый биномиальный коэффициент не менее сложно, чем число Фиббоначи?

#include <stdio.h>
#include <stdlib.h>

void mul (short *dest, const short* src){ //matrix multiplication
    short r0,r1,r2,r3;
    r0 = dest[0]*src[0]+dest[1]*src[2];
    r1 = dest[0]*src[1]+dest[1]*src[3];
    r2 = dest[2]*src[0]+dest[3]*src[2];
    r3 = dest[2]*src[1]+dest[3]*src[3];
    dest[0]=r0;dest[1]=r1;
    dest[2]=r2;dest[3]=r3;
}

int fib (int n){
    short Mpower[] = {0,1,1,1};
    short Mresult[] = {1,0,0,1};
    while (n){
        if (n&1) mul(Mresult,Mpower);
        mul(Mpower,Mpower);
        n>>=1;
    }
    return Mresult[1];
}

запилить длинную математику или реализовать через gmp

Я вроде помню решение за logN - там нужно матрицу 2х2 возвести в эту степень. Если интересно - могу вспоминать дальше.