It is required to raise the number a to the power n. a and n are input to the string type. At the moment I have done only the multiplication of long numbers, but I don’t know how to make a construction in an indecently large degree. All that is at the moment:

int main() { string a,n; int *A, *B, *C, cc; // cin>>a; //cin>>n; a="11111111111548484544876466666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666664548484"; n="11111111111111111111111111111111111111111111111111111115"; A=new int [a.size()]; for (int i=0; i<a.size(); i++) A[i]=a[a.size()-i-1]-'0'; //Умножение числа string само на себя length = a.size() * 2 - 1 ; l=length; C=new int [length]; for (int ix = 0; ix < length; ix++) { C[ix] = 0; } for (int ix = 0; ix < a.size(); ix++) { for (int jx = 0; jx < a.size(); jx++) { C[ix + jx] += A[ix] * A[jx]; } } for (int ix = 0; ix < length-1; ix++) { C[ix + 1] += C[ix] / 10; C[ix] %= 10; } while (C[length] == 0) length-- ; for(int i=length-1; i>-1; i--) cout<<C[i]; system("PAUSE"); }

    1 answer 1

    Is there multiplication? so multiply, decomposing the degree. For ordinary numbers this is approximately like this (it’s rather not a code, but pseudocode :))

     long pow(long x, long p) { if (x == 0 || x == 1) return x; long r = 1; while(p) { if (p%2 == 1) r*= x; x *= x; p /= 2; } return r; }

    Those. as a matter of fact simply we sort degree on bittik.

    If the degree is 2k+1 , then it is the same as x^2 to the power of k and multiplied by x . If 2k , then simply x^2 to the power k . So if the odd - the result (initially 1) multiplied by x , all, x no longer needed, only x^2 - squared, the degree divided in half ...

    Say x at 11

      pxr 11 x 1 10 xx 5 x^2 x 4 x^2 x*x^2=x^3 2 x^4 x^3 1 x^8 x^3 0 x^8 x^3*x^8 = x^11

    I think, despite my inert language, you will understand :)

    • My main question is how to set the dimension of the C array in which the desired number will be stored? The dimension of the array C is defined as: the number of characters of the original number * per degree. Because when multiplying one number by another (the number of characters is the same) - the resulting number has twice as many characters. - Maxitt
    • Well, think in terms of lg x^N = N*lg x - i.e. Signs will need, roughly speaking, a degree times more. But if you have taken seriously writing long maths, then believe me, it will be much faster (but simple) to take, say, an array of int 4 bytes, and store in each a value of no more than 2 bytes. All multiplications will be placed at you (only hyphenation must be done immediately), and the number 10 uncomfortable for the machine will not have divisions - there will only be divisions by powers of 2. Yes, there will be a complicated translation into and out of a string, but all the math will be done essentially faster ... - Harry
    • Well, or at least keep decimal chunks in int - but up to 10,000 - all the less and less memory is required and actions ... - Harry
    • I understood about the decomposition of the degree, I wanted to do something like this. But about the size of the array has not reached, or rather, about the storage of the elements of the array. Here is the piece where the size for multiplying two numbers is given: length = a.size () * 2 - 1; l = length; C = new int [length]; Can you help the code in this plan at least? I did not understand just. - Maxitt
    • @Harry I may not fully understand your approach, but would there be a risk of overflowing int but if you take only 2 bytes for each digit? and what basis do you take in this case, binary? Wash it, it is better to take a large number as a base - say 10 ^ 9 then one digit will be 9 decimal digits representing it as for example, the type long long - the array will be 9 times smaller, which will also speed up all operations on a long number 9 times - ampawd