1

Possible Duplicate:
How to find a binary logarithm very fast? (O(1) at best)

how does the log function work. How the log of a with base b is calculated.

Community
  • 1
  • 1
sunmoon
  • 1,448
  • 1
  • 15
  • 27
  • http://en.wikipedia.org/wiki/Logarithm#Calculation – Tim Mar 15 '11 at 06:00
  • 2
    Possible [Duplicate 1](http://stackoverflow.com/questions/2169641/where-to-find-algorithms-for-standard-math-functions) and [Duplicate 2](http://stackoverflow.com/questions/2668248/how-to-find-a-binary-logarithm-very-fast-o1-at-best) – Sanjeevakumar Hiremath Mar 15 '11 at 06:01
  • Get your hands dirty: http://repo.or.cz/w/glibc.git/blob/HEAD:/sysdeps/ieee754/dbl-64/e_log.c – Josh Lee Mar 15 '11 at 06:03
  • Maybe you will find something here too : http://graphics.stanford.edu/~seander/bithacks.html –  Mar 15 '11 at 06:10

1 Answers1

0

There are many algorithms for doing this. One of my favorites (WARNING: shameless plug) is this one based on the Fibonacci numbers. The code contains a pretty elaborate comment that goes into how the math works. Given a and ab, it runs in time O(lg b) and O(1) space.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065