Отправили в Украину умирать. Убивать других. Чем скорее вы скажете своей власти, что войну нужно немедленно остановить – тем больше ваших людей останутся живыми.
Мы видим, что действительно есть выступления ваших граждан против войны. И мы знаем, что многие в России сейчас просто шокированы подлостью и жестокостью власти. И это очень правильная реакция. Я благодарю вас за эту реакцию! Спасибо Леониду Парфёнову, Дмитрию Муратову, Юрию Дудю, Лие Ахеджаковой, Валерию Меладзе – ну, и тысячам. Тысячам достойных других россиян, чья совесть звучит – звучит громко.
Просто остановите тех, кто лжет вам. Лжет нам. Лжет всему миру.
Нужно закончить эту войну. Мы можем жить в мире. В мире глобальном. В мире человечества".
Fast exponentiation is an algorithm that allows you to raise any number to a natural power for a reduced number of multiplications.
For any number x and even degree n , the identity holds:
x n = (x n / 2 ) 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 n = x n - 1 ⋅ x , while (n - 1) is an even number.
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);
}
}
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;
}