0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you please give the definition of the log-star operator (by editing your question to include it)? I don't necessarily trust your code, or (more importantly) my ability to properly parse it. Also, I'm not really sure how this is a question about computer science (except, perhaps, tangentially, as you have included code in your question)---you may want to consider removing the tag. $\endgroup$ – Xander Henderson Dec 6 '17 at 3:32
  • $\begingroup$ You should define what you mean by log-star, not provide uncommented code and expect people to figure it out. $\endgroup$ – Ross Millikan Dec 6 '17 at 3:32
  • $\begingroup$ I added more clarification, sorry. $\endgroup$ – Jackson Blankenship Dec 6 '17 at 3:44
  • $\begingroup$ @JacksonBlankenship The table on that Wikipedia page gives you all the answers you need. Or at least all the answers you'll be able to verify with your Java program. $\endgroup$ – Derek Elkins Dec 6 '17 at 5:07
  • $\begingroup$ You still did not define the function except to give a link. Please make the question self contained. $\endgroup$ – Ross Millikan Dec 6 '17 at 5:07
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's easier to go the other way and calculate the tower of $2$s and then see what "bucket" the number falls into by simply comparison. Of course, we quickly go beyond numbers which are physically able to be written out in standard notation. Non-standard representations become necessary if one wants to continue. $\endgroup$ – Derek Elkins Dec 10 '17 at 1:29
  • $\begingroup$ @DerekElkins You may be right about efficiency. My suggestion works by hand and clearly fits the definition. I chose it because is related to the the continuous bijective function $f:\mathbb R_{\ge0} \to \mathbb R_{\ge0}$ with $f(x)=x$ when $0 \le x \le 1$ and $f(x)=1+f(\log x)$ when $x \ge 1$; when the base of the logarithm is $e$, you find $f(x)$ also differentiable $\endgroup$ – Henry Dec 10 '17 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.