I can't quite figure out the time complexity of this algorithm I've written for finding the modulo. I've added it here in psuedocode.
Modulo(int x, int n) // x is the dividend, n is the divisor e := 1; while(n^e < x) e++; end e--; //This first part above is clearly O(log x) while(e >= 1) while(n^e <= x) x -= n^e; end e--; end //This second part above is more challenging. The outer loop goes through log x cycles, while the inner loop goes through (x mod (n^(e+1)))/(n^e) cycles. return x; end
Hopefully I'm not missing anything obvious, but this doesn't seem like an easy problem to solve. Thanks in advance.
EDIT: By the way,
^ represents exponentiation in this case, just to avoid confusion.