I am working on a homework problem involving comparing a recursive solution to a problem with its iterative counterpart. Currently I have the recursive function working for the given set of values, however the iterative version seems to work for every value other than the last one which seems odd to me.
The iterative function is as follows
uint64_t
normalPower(uint64_t k, uint64_t n, uint32_t m)
{
uint64_t answer = 1;
for (int i = 1; i <= n; i++)
{
answer = answer * k % m;
}
return answer;
return EXIT_SUCCESS;
}
with the other relevant information being
uint64_t n;
for (int i = 0; i <= 10; i++)
{
n = n * 10;
}
and
uint64_t k = 1835;
uint32_t m = 590623782;
When I run the recursive function I get the answer 424171147 for the final value which I have confirmed with other classmates. I am just confused as to why the algorithm works for all of the previous values but not the final one. Any and all help is greatly appreciated.
On a side note: I am aware the iterative version is wildly inefficient, that is the point of the assignment.
As requested here is the recursive function
uint64_t
fastPower(uint64_t k, uint64_t n, uint32_t m)
{
uint64_t answer = 0;
if (n % 2 == 0 && n > 1)
{
uint64_t kn = fastPower(k, n / 2, m);
answer = (kn * kn) % m;
return answer;
}
else if (n > 1)
{
answer = fastPower(k, 1, m) * fastPower(k, n - 1, m) % m;
return answer;
}
else
answer = k % m;
return answer;
return EXIT_SUCCESS;
}
Also n is initialized as 1 when it is declared.
Your code is 'correct' mathematically. What you're running into is an integer overflow on your loop counter in the iterative function. Since i is a signed int, it is wrapping over into negative numbers (which when compared to your unsigned n, is interpreted as unsigned, which will lead to strange results)
If you change
for (int i = 1; i <= n; i++)
{
answer = answer * k % m;
}
to
for (uint64_t i = 1; i <= n; i++)
{
answer = answer * k % m;
}
Then i will match n in size and sign, and the answers will match