0

I am trying to calculate very large 'long' type numbers using a recursive Exponentiation by Squaring algorithm, as seen below. I am encountering stack overflow errors when increasing the size of the exponent, and I want to find out how I can allow it to loop and not take up so much space on the stack. I want to achieve this without using the Math library, so only in vanilla Java code.

public long exp(long base, long exponent, long accum){
    if (power > 0) {
        return exp(base, exponent - 1, accum * base);
    } else {
        return accum;
    }
}
user207421
  • 305,947
  • 44
  • 307
  • 483
Matt Vincent
  • 59
  • 1
  • 6
  • 2
    `if (power > 0) {` yeah power to the people, but where is it declared, where does it change? – Scary Wombat Oct 11 '19 at 01:14
  • There is no squaring here, and no need for recursion either. There is a well-known iterative algorithm that *does* involve squaring and that is far more efficient than this. – user207421 Oct 11 '19 at 01:16
  • This is not the "exponentiation by squaring" algorithm. This is just straight repeated multiplication. – Dawood ibn Kareem Oct 11 '19 at 01:42
  • `power` should be `exponent`, and IMHO, you have to use loops(`for` or `while`) to achieve this. – meng Oct 11 '19 at 02:31
  • And you aren't handling the zero case correctly. – user207421 Oct 11 '19 at 04:49
  • Sorry, my mistake, the power variable was renamed to put on here and in my code is the same as the exponent variable. – Matt Vincent Oct 11 '19 at 09:16
  • Which still leaves you with the zero-exponent bug and the complete lack of squaring. – user207421 Oct 11 '19 at 09:33
  • Perform the tail recursion elimination yourself and transform the recursion into a loop. Or have a look at Trampolining, e.g. here: https://stackoverflow.com/questions/189725/what-is-a-trampoline-function – sfiss Oct 11 '19 at 09:46
  • @meng Don't edit questions to show the answer. Edit rejected. – user207421 Oct 11 '19 at 19:05

0 Answers0