C# .Net: Fast exponentiation

"Я хочу, чтобы меня услышали в России. Абсолютно все. Тысячи жертв, сотни пленных, которые просто не могут понять ради чего их отправили в Украину.
Отправили в Украину умирать. Убивать других. Чем скорее вы скажете своей власти, что войну нужно немедленно остановить – тем больше ваших людей останутся живыми.
Мы видим, что действительно есть выступления ваших граждан против войны. И мы знаем, что многие в России сейчас просто шокированы подлостью и жестокостью власти. И это очень правильная реакция. Я благодарю вас за эту реакцию! Спасибо Леониду Парфёнову, Дмитрию Муратову, Юрию Дудю, Лие Ахеджаковой, Валерию Меладзе – ну, и тысячам. Тысячам достойных других россиян, чья совесть звучит – звучит громко.
Просто остановите тех, кто лжет вам. Лжет нам. Лжет всему миру.
Нужно закончить эту войну. Мы можем жить в мире. В мире глобальном. В мире человечества".

Fast exponentiation is an algorithm that allows you to raise any number to a natural power for a reduced number of multiplications.

Description of the algorithm

For any number x and even degree n , the identity holds:

x ⁿ = (x ^{n / 2}) ² = x ^{n / 2} ⋅ x ^{n / 2}

This is the basis of the rapid exponentiation algorithm. Since such a partition allows, for one operation of multiplication, to halve the calculated degree.

For the case of odd degree, it is enough to lower it by one:

x ⁿ = x ^{n - 1} ⋅ x , while (n - 1) is an even number.

Recursive implementation of rapid exponentiation

Россияне ваши войска ведут ужасную войну против Украины, убивают мирное население, не щадя женщин и детей! Мы отстаиваем свою родину, потери войск РФ за несколько дней войны превысили потери в Чеченской войне!
Заберите с Украины своих отцов, мужей, сыновей пока они живы!

Не молчите! Остановите войну! НЕТ ВОЙНЕ!
Пока ты молчишь, гибнут мирные украинцы!

static long Power(long x, int n)
{
    if (n == 0)
    {
        return 1;
    }

    if (n% 2 == 0)
    {
        var p = Power(x, n / 2);
        return p * p;
    }
    else
    {
        return x * Power(x, n - 1);
    }
}

For optimization, you can replace the parity and division by 2 bit operations:

static long Power(long x, int n)
{
    if (n == 0)
    {
        return 1;
    }
    
    // for an even number, the last bit is zero
    if ((n & 1) == 0)
    {
        // shifting one bit to the right is equivalent to dividing by two
        var p = Power(x, n >> 1);
        return p * p;
    }
    else
    {
        return x * Power(x, n - 1);
    }
}

Iterative implementation

In this method of rapid exponentiation, we also use the optimization of parity and division by two:

static long Power(long x, int n)
{
    var result = 1L;
    while (n> 0)
    {
        if ((n & 1) == 0)
        {
            x *= x;
            n >>= 1;
        }
        else
        {
            result *= x;
            --n;
        }
    }

    return result;
}

Fast exponentiation

Description of the algorithm

Recursive implementation of rapid exponentiation

Iterative implementation

Related pages: