# "Searching and sorting" algorithm to find the natural logarithim of a number?

Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm not allowed to use strategies that involve integration, bit manipulation, approximation formulas, or Taylor Series. Instead, we're asked to generate an array of values where at least one of them will be the answer, and then to find the correct value in that array. There must be some kind of established algorithm for this, but this and other resources haven't been helpful. I'm stuck. What should I be thinking about here?

• What class is this? What have you discussed in class, what can you assume from earlier courses? (I must confess that the question has got me completely stumped.) Feb 20, 2020 at 22:59
• Can't be quite sure without more detail, but to me this sounds like they are asking for a binary search type approach. Feb 20, 2020 at 23:25
• @vonbrand This is for CMSC389O (Cracking the Coding Interview, 1 credit class) at the University of Maryland. My only experience with algorithms is what I've learned thus far in the Intro to Algorithms course I'm taking concurrently with this so there's not much I can assume, except that the question is looking for some kind of binary search style solution. Feb 21, 2020 at 0:13

Suppose you have an array $$A = [e^0, e^1, e^2, \dots]$$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $$x$$.

1. You find this value at position $$n$$. What is the value of $$A[n]$$?

2. What can you say about $$\ln(x)$$ in relation to $$n$$?

3. Can you find the correct $$n$$ quickly? Does it help that $$A$$ is sorted?

• How do you generalize this to get the “correct” answer, which I assume is floating point rne? Or is the value found by the approach above, using the list above, considered the right answer?
– user46107
Feb 21, 2020 at 23:37
• @DanielMGessel It is correct but an approximation. To generalize this you could add more tables to get the decimal digits, e.g. $[e^0, e^{0.1}, e^{0.2}, \dots, e^{0.9}]$ and $[e^0, e^{0.01}, e^{0.02}, \dots, e^{0.09}]$.
– orlp
Feb 22, 2020 at 0:11