Как реализовать такой алгоритм?

Question

[Blunker]

Требуется реализовать алгоритм бинарного возведения в степень

std::vector<bool> temp = toBinary(power);
	std::vector<long> result;
	long S = 1, c = base;

	for (auto i = 0; i < temp.size(); ++i)
	{
		if (temp[i] == 1)
		{
			S = (S * c) % mod;
			std::cout << "S = " << S << std::endl;
		}
		else
		{
			c = (c * c) % mod;
			std::cout << "c = " << c << std::endl;
		}
	}

Написал вот что, и оно работает не так как надо. Подскажите что нужно исправить?

Answer 1

[Rsa97]

uint64_t mod_power(uint64_t a, uint64_t b, uint64_t n) {
  uint64_t bit = 0x8000000000000000ui64;
  uint64_t result = a % n;
  while (bit && (bit & b == 0))
    bit = bit >> 1;
  while ((bit = bit >> 1))
    result = (result * result * ((bit & b) ? a : 1)) % n;
  return result;
}

Answer 2

[Matthew Strechen]

Во-первых, long - это int32, так что если у вас mod больше 2^15, лучше всё-таки взять long long.
Во-вторых, строчку

S = (S * c) % mod;

следует заменить на

c*=base;
c%=mod;
c*=c;
c%=mod;

(если вы хотите следовать алгоритму), кроме того, поставить условие на то, что temp[i] - это не последний бит битовой записи числа - иначе мы лишний раз поднесём к квадрату

Следующий код работает правильно:

long long bp(long long base, long long power)
{
  std::vector<bool> temp = toBinary(power);
  std::vector<long> result;
  long long c = 1;

  for (auto i = 0; i<temp.size(); i++)
  {
    if (temp[i] == 1)
    {
      c = (c*base)%mod;
    }
    if(i!=temp.size()-1)
        c*=c;
    c%=mod;
  }
  return c;
}

Я не понял смысла переменной S, если объясните, возможно, ваш код получится править "мягче" (кажется, я переписал половину вашего кода, извините)

Вообще говоря, функция бинарного возведения в рекурсивном виде выглядит так:

long long binpow(long long base, long long power)
{
    if(power==0)
        return 1;
    if(power%2)
        return (binpow(base, power-1)*base)%mod;
    long long tmp = binpow(base, power/2);
    return (tmp*tmp)%mod;
}

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