[Math] Computing the iterated logarithm (log-star) by hand

computer sciencelogarithmsrecursive algorithms

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.

Best Answer

By hand

  • $2^{16} =65536 \lt 100000 \le 131072=2^{17}$

  • $2^4 \le 16 \lt \log_2(100000) \le 17 \le 2^5$

  • $2^2 \le 4 \lt \log_2(\log_2(100000)) \le 5 \le 2^3$

  • $2^1 \le 2 \lt \log_2(\log_2(\log_2(100000))) \le 3 \le 2^2$

  • $2^0 \le 1 \lt \log_2(\log_2(\log_2(\log_2(100000)))) \le 2 \le 2^1$

  • $0 \lt \log_2(\log_2(\log_2(\log_2(\log_2(100000))))) \le 1$

Five $\log_2$s in the final expression

Related Question