Рекурсия VS Циклы

[Kostia]

Интересно стало, вот и начал эксперимент. Задача вычисления быстрого вычисления числа в натуральной степени. Вот пара решений на C++:

inline __uint64_t myPowHlp(const __uint64_t &A, const __uint64_t &n, const __uint64_t &res)
{
    if(n == 0) return res; else
    if(n & 1)  return myPowHlp(A*A, n >> 1, res * A);
    else       return myPowHlp(A, n - 1, res * A);
}

inline __uint64_t myPow(const __uint64_t &A, const __uint64_t &n)
{
    return myPowHlp(A,n,1);
}

VS

inline __uint64_t fastPow(__uint64_t base, __uint64_t exponent)
{
    __uint64_t res = 1;
    while(exponent > 0)
    {
        if (exponent & 1)
        {
            exponent >>= 1;
            res *= base;
            base *= base;
        }
        else
        {
            exponent--;
            res *= base;
        }
    }
    return res;
}

тест:

    gettimeofday(&tstart, NULL);
    for(int i = 0; i < 10000000; i++) myPow(2, rand()%63); //fastPow
    gettimeofday(&tstop, NULL);
    seconds  = tstop.tv_sec  - tstart.tv_sec;
    useconds = tstop.tv_usec - tstart.tv_usec;
    std::cout << ((seconds) * 1000 + useconds/1000.0) + 0.5;

Рекурсия ~436.052 мСек
Цикл ~327.317 мСек

Но насколько я понимаю, в рекурсии используется концевая рекурсия и компилятор мог бы допереть до этого и сделать очень мощную оптимизацию, которая бы обошла "обычный" способ.

И еще, есть ли еще способы, не прибегая к асму, оптимизировать оба метода?

[pu4koff]

Это не хвостовая рекурсия, т.к. два разных рекурсивных вызова может быть.

[waleri]

Продлите експеримент дальше - сделайте стек у вашего приложения 4КБ и дерзайте с рекурсией....

[Kostia]

Это не хвостовая рекурсия, т.к. два разных рекурсивных вызова может быть.

Ok. Поменял так:

inline __uint64_t myPowHlp(const __uint64_t &A, const __uint64_t &n, const __uint64_t &res)
{
if(n == 0) return res;// else
//if(n & 1) return myPowHlp(A*A, n >> 1, res * A);
else return myPowHlp(A, n - 1, res * A);
}

~95.736 мСек
WTF o_O.

Теперь появилась потребность выразить быстрое возведение в натуральную степень с хвостовой рекурсией. Хм, и как? Есть идеи или это невозможно?

Продлите експеримент дальше - сделайте стек у вашего приложения 4КБ и дерзайте с рекурсией....

Просто их нужно правильно готовить

[Abstraction]

И еще, есть ли еще способы, не прибегая к асму, оптимизировать оба метода?

Не очень понятно, почему Вы так разделяете действия при чётном и нечётном exp:

inline __uint64_t fastPow(__uint64_t base, __uint32_t exponent)//64 бита на показатель степени? Гм...
{
    __uint64_t res = 1;
    while(exponent != 0)
    {
        if (exponent & 1) res *= base;
        base *= base;
        exponent >>= 1;
    }
    return res;
}

То же в первом примере:

inline __uint64_t myPowHlp(const __uint64_t A, const __uint32_t n, const __uint64_t acc)
{
    if(n == 0) return acc;
    if(n & 1)  return myPowHlp(A*A, n >> 1, acc * A);
    else       return myPowHlp(A*A, n >> 1, acc);
}

P.S. Вообще-то, первый пример можно ещё скорректировать:

__uint64_t myPowHlp(const __uint64_t A, const __uint32_t n, const __uint64_t acc)
{
    if(n == 0) return acc;
    return myPowHlp(A*A, n >> 1, (n&1) ? acc*A : acc);
}

[Abstraction]

Это не хвостовая рекурсия, т.к. два разных рекурсивных вызова может быть.

Это почему? Хвостовая рекурсия - когда возвращается строго результат вызова самой функции с другими аргументами. Независимо от того, сколько есть разных логических путей, каждый можно заменить на изменение значений аргументов и goto в начало.

[Kostia]

(n&1) ? acc*A : acc

Чем не еще один if?

//64 бита на показатель степени? Гм...

//32 бита на степень?
вообще раньше был __uint8_t, но потом все превратилось в 64 бита

Ok. Ваши варианты уравняли производительность.
Еще для меня стало непонятным то, что если в рекурсии передавать значения по ссылке, то скорость резко падает, почему?

Как-то так на haskell перевел:

fastPow :: Int -> Int -> Int
fastPow a b = fastPow' a b 1
fastPow' a b acc | b == 0 = acc
                 | (.&.) b 1 == 1 = fastPow' (a*a) (shiftR b 1) (acc * a)
                 | otherwise = fastPow' (a*a) (shiftR b 1) acc

main =do
    start <- (getClockTime >>= toCalendarTime)
    print (fastPow 2 62)
    stop <- (getClockTime >>= toCalendarTime)
    print (makeTime stop - makeTime start)

еще такой вариант:

fastPow :: Int -> Int -> Int
fastPow a b = fastPow' a b 1
fastPow' a b acc | b == 0 = acc
                 | otherwise = fastPow' (a*a) (shiftR b 1) (r a b acc)
                     where 
                        r a b acc | (.&.) b 1 == 1 = acc * a
                                  | otherwise = acc

~95.736 мСек
WTF o_O.

Не правильно, значение функции просто напросто не считалось, т.к. было не нужно, вычислялся только rand().

[pu4koff]

Сообщение от Abstraction

Это почему? Хвостовая рекурсия - когда возвращается строго результат вызова самой функции с другими аргументами. Независимо от того, сколько есть разных логических путей, каждый можно заменить на изменение значений аргументов и goto в начало.

Хотя да. Пожалуй всё же там хвостовая рекурсия. Просто такую конструкцию проблематично оптимизатору развернуть, т.к. там условный вызов идёт, а условия имеют привычку предсказываться и выполняться наперёд.

[Kostia]

есть еще такой вариант и он работает быстрее, вполне возможно что это из-за лишнего вызова функции?

__uint64_t myPow2(const __uint64_t A, const __uint64_t n)
{
    if(n == 0) return 1;
    return myPow2(A*A, n >> 1) * ((n&1) ? A : 1);
}

[Abstraction]

есть еще такой вариант и он работает быстрее, вполне возможно что это из-за лишнего вызова функции?

Полагаю, что из-за отсутствия ветвления в аргументах. Но это в нерекурсивный вызов компилятор не преобразует заведомо.

//32 бита на степень?

Машинное слово, почему нет.