Возведение в степень C++

Значит, так. Чтоб закрыть тему - бегом набросал умножение, сложение и возведение в степень. Только - набросано за полчаса, вроде работает, но кое-где веревочками перевязано :) - типа нормализации после умножения вместо корректного расписывания переносов.

Об оптимальности говорить не приходится :( Тем не менее вроде работает.

Только консультаций по тому, что делает та или иная строчка кода, простите, но - не будет. Разбирайтесь сами. Числа храню для простоты в виде кусков по 9 цифр.

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
class superLong
{
public:
    using ullong = unsigned long long;
    superLong(ullong x = 0) { d.push_back(x); };
    superLong(string s);
    operator string() const;
    friend superLong operator *(const superLong&a, const superLong&b);
    friend superLong operator +(const superLong&a, const superLong&b);
private:
    vector<ullong> d;
    static constexpr ullong max = 1000000000ull;
};

superLong operator *(const superLong&a, const superLong&b)
{
    superLong r;
    for(size_t i = 0, e = a.d.size(); i < e; ++i)
    {
        for(size_t j = 0, f = b.d.size(); j < f; ++j)
        {
            superLong::ullong v = a.d[i]*b.d[j];
            superLong::ullong carry = v/superLong::max;
            v = v%superLong::max;
            if (i+j >= r.d.size()) r.d.resize(i+j+1,0);
            r.d[i+j] += v;
            if (carry)
            {
                if (i+j+1 >= r.d.size()) r.d.resize(i+j+2,0);
                r.d[i+j+1] += carry;
            }
        }
    }
    for(size_t i = 0, e = r.d.size(); i < e-1; ++i)
    {
        if (r.d[i] > superLong::max)
        {
            r.d[i+1] += r.d[i] / superLong::max;
            r.d[i] %= superLong::max;
        }
    }
    return r;
}
superLong operator +(const superLong&a, const superLong&b)
{
    superLong d((a.d.size() > b.d.size()) ? a : b);
    superLong c((a.d.size() > b.d.size()) ? b : a);
    c.d.resize(d.d.size(),0);
    superLong::ullong carry = 0;
    for(size_t i = 0; i < d.d.size(); ++i)
    {
        d.d[i] += c.d[i]+carry;
        carry = d.d[i]/superLong::max;
        d.d[i] %= superLong::max;
    }
    if (carry) d.d.push_back(carry);
    return d;
}
superLong::superLong(string s)
{
    superLong q;
    int len = s.length()%9;
    if (len)
    {
        string val = s.substr(0,len);
        s = s.substr(len,s.length()-len);
        q = stoll(val);
    }
    while (s.length())
    {
        string val = s.substr(0,9);
        s = s.substr(9,s.length()-9);
        q = q * superLong::max + stoll(val);
    }
    d = std::move(q.d);
}
superLong::operator string() const
{
    string s;
    for(size_t i = 0; i < d.size(); ++i)
    {
        char buf[12];
        snprintf(buf,12,"%09lld",d[i]);
        s = buf + s;
    }
    return s;
}
superLong superPow(superLong x, unsigned long long p)
{
    superLong r(1);
    while(p)
    {
        if (p&0x01) r = r * x;
        p >>= 1;
        x = x*x;
    }
    return r;
}
int main(int argc, const char * argv[])
{
    superLong l1("111111111111111111111253672373");
    superLong l2("552345678012345678012898234897");
    cout << string(l1*l2) << endl<<endl;;
    cout << string(superPow(2,1000)) << endl;
}

Вы приняли правильное решение хранить сомножители с обратным порядком цифр.

Однако, мне кажется, что просто умножение 2-х чисел лучше запрограммировать более очевидным способом, сразу записывая в результат правильную цифру и запоминая перенос.

/* 
   Умножение целых десятичных чисел без знака
   c = a * b
   a[], b[] содержат значимые цифры чисел в обратном порядке
   (старшие цифры числа справа), 
   la -- количество цифр в a[]
   lb -- количество цифр в b[]
   Результат получается в массиве c[], 
   под который в вызывающем коде должно быть выделено достатчно памяти (la + lb)
   Возвращает количество значимых цифр в результате
*/
int
mult (char a[], int la, char b[], int lb, char c[])
{
  int cc = 0,     // цифра переноса
    lc = la + lb; // максимальное количество значимых цифр результата

  for (int i = 0; i < lc; i++)
    c[i] = 0;
  for (int i = 0; i < la; i++) {
    for (int j = 0; j < lb; j++) {
      int r = c[i + j] + cc + a[i] * b[j];
      c[i + j] = r % 10;
      cc = r / 10;
    }
    c[i + lb] = cc;
    cc = 0;
  }
  return c[lc - 1] ? lc : lc - 1;
}

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

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

Update

Вот пример вычислений степени (с показателем степени оперирую в int)

#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>
using namespace std;
int
mult (char a[], int la, char b[], int lb, char c[])
{
   ....
}
int 
main (int ac, char *av[])
{
  string s = av[1] ? av[1] : "123";
  int p = av[1] && av[2] ? atoi(av[2]) : 2;
  if (p < 1) {
    cout << "invalid power: " << p << '\n';
    return 1;
  }
  int i, j, l = s.size(), lr = l;
  char a[l];
  for (i = l - 1, j = 0; i >= 0; --i)
    if (s[i] >= '0' && s[i] <= '9')
      a[j++] = s[i] - '0';
    else {
      cout << "invalid number: " << s << '\n';
      return 1;
    }
  char b[l * p + 1], r[l * p + 2];
  cout << s << " ** " << p << " = ";
  memcpy(b, a, l);
  while (--p) {
    lr = mult(a, l, b, lr, r);
    if (p > 1)
      memcpy(b, r, lr);
  }
  for (i = 0, j = lr - 1; i < j; i++, j--) {
    r[i] += '0';
    char t = r[j] + '0';
    r[j] = r[i];
    r[i] = t;
  }
  if (i == j)
    r[i] += '0';
  r[lr] = 0;
  cout << r << '\n';
}