Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

bluebrandon

  • 4 years ago

Can someone help me write a non-recursive version if this function in C? http://db.tt/0NISjQXX I just started learning C after Scheme and loops are still kind of confusing for me.

  • This Question is Closed
  1. DBhatta
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    The code doesn't look like c. if it is which version or type is it?

  2. rivermaker
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    If you can describe the functionality I can help

  3. rivermaker
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Ok is it computing \[x^{e} \mod m\] And you can write a recursive C version.

  4. rivermaker
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    int xsqrm( int x, int m) { return (x * x) % m int powermod2(int x, int e, int m) { if (e == 0) return 1; if (e % 2 == 0) return powermod2(xsqrm(x, m), e/2); return (x * powermod2(xsqrm(x, m), e/2)) % m ; }

  5. bluebrandon
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    for anyone curious this is the solution I came up with int powmod2(int x, int e, int m) { int y = 1; while (e!= 0) { if (e%2 == 0) { e = e/2; x = (x*x)%m; } else { e = (e-1)/2; y = (x*y)%m; x = (x*x)%m; } } return y; } My problem was that I was missing a step in the odd case that I was able to introduce with the y variable. The original I needed to convert this was a recursive version written in scheme. Thanks for your help though!

  6. rivermaker
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    e = e/2 is enough in both cases; because integer division truncates. So you can remove the two statements inside the if and else and replace by e /= 2 in the while loop

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy