Friday 29 May 2015

computer science - Computing the iterated logarithm (log-star) by hand

I'm having trouble figuring out how to compute the iterated logarithm (log-star) by hand without using a calculator or programming language. I wrote out the following program in Java to check my answers as I practice but can't seem to wrap my head around how to do this without a computer.



public class Recurrences {

public static void main(String[] args) {

// Compute log-star (base 2) of 100,000
System.out.println((int) logStar(100000, 2));

}


/**
* log-star recursive method
* @param n Value of input
* @param base Base value for the logarithm (i.e. log base 2 would give 2)
* @return If n > 1.0, return 1 + logStar( log2(n) ), else return 0.
*/
public static double logStar(double n, int base) {

if (n > 1.0) { // Recursive case


return 1.0 + logStar((Math.log(n)) / (Math.log(base)), base);

} else { // Base case. If n <= 1, return 0.

return 0;

}

}


}


Do you have any tips as to how you would calculate log-star of say, 100000? My program says the answer should be 5 but I don't know how I would go about getting that answer with pen and paper. Also, as shown above in the code, I'm working in log base 2.



Edit: here is a link that explains the concept. Sorry for the initial lack of info.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...