The task is to raise a large number n (0 <= n <= 10 ^ 50) to the power of m (0 <m <1000). For this, of course, I use long arithmetic

typedef vector<long long> largen;

And also binary exponentiation.

 largen recbinpow(largen a, int n) { largen e; e.push_back(1); if (n == 0) return e; if (n % 2 == 1) return multiply(recbinpow(a, n - 1), a); else { largen b = recbinpow(a, n / 2); return multiply(b, b); } }

But it still turned out to be too slow. I found out that if we take the base of the number system more, for example 10 ^ 9, then the exponentiation will be much faster.

 const int base = 1000 * 1000 * 1000; largen multiply(largen a, largen b) { largen c(a.size() + b.size()); for (size_t i = 0; i<a.size(); ++i) for (int j = 0, carry = 0; j < (int)b.size() || carry; ++j) { long long cur = c[i + j] + a[i] * 1ll *(j < (int)b.size() ? b[j] : 0) + carry; carry = (long long)(cur / base); c[i + j] = (long long)(cur % base); } while (c.size() > 1 && c.back() == 0) c.pop_back(); return c; }

But, for reasons unknown to me, the program does not work correctly on some values, for example, 999,999,999.

Debugging hours did not lead to anything. Please help me find an error program .

  • If there is a written algorithm for the discrete Fourier transform and convolution, then the multiplication can be written almost without perdoling. - typemoon

1 answer 1

And you do not want to consider that your conclusion

 for (int i = result.size() - 1; i >= 0; i--) { cout << result[i]; }

should, in general, also output leading zeros (if there are any)? ... Ie if your element of the vector is less than the same billion, then it must still be displayed in 9 familiarity?

  • Leading zeros are removed after each multiplication. The conclusion is all right. - Keltar Helviett
  • @KeltarHelviett I just entered 100 into your program and raised it to the 20th degree. got 1 with 8 zeros. But if your output is rewritten like this: cout << setw(9) << setfill('0') << result[i]; - it turns out a unit with 40 zeros, as it should ... So what about the conclusion you are not exactly all right? it is you who got excited, saying that everything is OK ... - Harry
  • Understood my mistake. Indeed, it was necessary to simply add zeros if the number in the vector does not consist of 9 digits. Thank you very much. - Keltar Helviett