Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]

In the line

result = mymod((result * x),d);

in result * x your both result and x can be as large as d (more precisely, d-1), so you need a data type that can hold integers as big as d*d. For your cases, this may be long long int.

Another approach will be not to use library operator* for ints, but implement a manual multiplication function with a similar divide and conquer approach using only additions. This way you will need a data type that can hold integers as big as 2d only.

Also note that you do not need to call mymod each time in the main loop. You can call it only once before the loop to make x positive (x=mymod(x,d)), and then use just the operator%.

Browse More Popular Posts

Leave a Comment