You can calculate x^p by multiplying x p times: x*x*x*x....x*x. The "cost" will be n multiplications.
I know it is possible to create a more effective algorithm, with the "cost" log n, by using divide and conquer, and the fact that x^p = x^(p/2)*x^(p/2)^...
Thankful for your help,
Danne
> ... calculate x^p by multiplying x p times:
> x*x*x*x....x*x. The "cost" will be n multiplications.
> ... using divide and
> conquer, and the fact that x^p = x^(p/2)*x^(p/2)^...
>
> ... how can i write it in pseudocode?
Imagine x to the power of 19.
Break down 19 to binary: 10011, read this from lsb.
Result starts as 1.
Intermediate value starts as x.
Repeat
.Multiply intermediate value into result if the current bit of the exponent is 1.
.Square intermediate value.
When you run out of digits in the exponent, you have the result.