2
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 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$ – vonbrand Feb 20 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$ – Tassle Feb 20 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$ – superfeen Feb 21 at 0:13
4
$\begingroup$

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?

| cite | improve this answer | | | | |
$\endgroup$
  • $\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$ – Daniel M Gessel Feb 21 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$ – orlp Feb 22 at 0:11

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.