Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

NEED URGENT HELP

Name: edo-chan 2011-12-28 11:11

sup /prog/

Ive asked this everywer already but peopl seem too lame to make even a simple program like so i hope the mighty anon programers of 4chan are more skilled

what im trying to do is to Write a method taking two parameters x and n that computes the nth power of x without using ^ or declaring a new variable inside the method or using Math lib.
and it has to be coded in JAVA (i know it sux but dont ask why i use dat shit)
hep plox!

Name: Anonymous 2011-12-29 16:54

>>69

the recursive ones that don't use tail recursion that also make p recursive calls will likely stack overflow for large values of p. But if you use a solution that only makes log(p) recursive calls, you are likely safe. Anyways, I think that one can be made tail recursive. You just have to go from the most significant bits down to the least significant bits:


unsigned long long square(unsigned long long x) {
  return x*x;
}

unsigned long long power_(unsigned long long x, unsigned long long p, unsigned long long bit_mask, unsigned long long accumulation_product) {
  if(bit_mask == 0) {
    return accumulation_product;
  } else if(p & (1<<bit_index)) {
    return power_(x, p & ~bit_mask, bit_mask, accumulation_product*x);
  } else {
    return power_(x, p, bit_mask>>1, square(accumulation_product));
  }
}


I should test this though. Also there is a chance to optimize the odd case.

(x)^(2n+1) = (x^(2n))*x = ((x^(n))^2)*x = x*square(power(x,n))

so it would go to the next bit, regardless if it was even or odd, rather than making the odd power even and relying on the next recursive call to go to the next bit.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List