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?
3
-
1$\begingroup$ 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.) $\endgroup$– vonbrandFeb 20, 2020 at 22:59
-
2$\begingroup$ Can't be quite sure without more detail, but to me this sounds like they are asking for a binary search type approach. $\endgroup$– TassleFeb 20, 2020 at 23:25
-
$\begingroup$ @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. $\endgroup$– superfeenFeb 21, 2020 at 0:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
You find this value at position $n$. What is the value of $A[n]$?
What can you say about $\ln(x)$ in relation to $n$?
Can you find the correct $n$ quickly? Does it help that $A$ is sorted?
-
$\begingroup$ 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? $\endgroup$– user46107Feb 21, 2020 at 23:37
-
$\begingroup$ @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}]$. $\endgroup$– orlpFeb 22, 2020 at 0:11