I've been struggling to make a program that can calculate a^b (1<=a,b<=1000) but the best I did was 1<=a<=9 & 1<=b<=10000

Question

//anyone who could help me with an advice?
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<short> num (9543,0);
num[0]=1;
int no, pow_, cifra, carry=0, k=1;
cin>>no>>pow_;
for(int l=0;l<pow_;l++){
for(int i=0; i<k; i++){
cifra=(num[i]*no+carry)%10;
carry=(num[i]*no+carry)/10;
num[i]=cifra;}
if(carry!=0){
num[k++]=carry;
carry=0;}}
for(int i=k-1; i>=0; i--)
cout<<num[i];
return 0;
}
//this can only calculate digits to a certain pow

Answer 1

The problem is that the number in carry gets extremely huge for big numbers no and pow_, so it overflows, thus giving a false result.

Answer 2

It works the same as with power, just go from right to left, you keep the %10 and carry over the /10.
12 * 12
So you start with 2 * 12 (the 2 from 12) is 24, that's 4 and you carry over the 2.
Now you have 1 * 12 + 2 (the 2 you carried over, the 1 from 12) is 14, so 4 and you carry over 1.
Now it's 0 * 12 + 1 = 1.
The result is 144

Answer 3

So, did you manage to change your code so that it works with 1<=a,b<=1000?

Answer 4

Does the algorithm have a name?

Answer 5

You work in base 10, so as soon as no is bigger than 10 carry will grow more and more until it reaches the highest possible integer. If that happens the result will be wrong. So unless you store carry different or use a different base this will keep happening for any no > 10.

Answer 6

You multiply digit by digit, the largest digit is 9 and you carry over /10, so whatever you carry over will be less than the number you multiply with. As you /10 every step the carry will always(!) be smaller than the number you multiply with.

Answer 7

Btw, if you want to make your algorithm faster you should try this, it greatly reduces the number of multiplications:

/* calculates x^n */
int pow(int x, int n){
int y = 1;
while (n > 0){
if (n%2 == 0){
x = x*x;
n = n/2;
} else {
y = y*x;
n = n-1;
}
}
return y;
}

(Of course you'd need to change y and x to vectors)

Answer 8

not really, as it involves just the multiplication of 2 large numbers, stored in an array, I just posted a code that can do the work, calculate 1000^1000 and so on, but I could post the function as well if you want

Answer 9

the code above works just fine, his purpose is to calculate a maximum of 9^10000, but I need help to improve it so it could go above 9, up to 1000

Answer 10

it would still give a wrong answer because multiplication with numbers larger than 9 doesn't work the same, for example if you have 12*12 you will multiply the first number with the digits of the second one by one, 12*2=24 and 12*1=12, then sum them, considering that the 1 come from 10, so 24+10*12=144, this is the logic to follow, but I have big troubles implementing this

Answer 11

but there will be a problem when the carry becomes larger than 9, right?

Answer 12

sorry, I was at school, I tried to use more that 1 carry (up to 6) but that didnt end up well, as I had several issues, but I think I found an algorithm for a function that multiplies large numbers, if you want I could translate it (it's in my Romanian) and post it for you to see as well