Traditional
mathematics knows a whole bunch of ways to compute the
logarithm of a number.
My favorite is the Maclaurin series, which is a kind of
Taylor Series:
ln(1 + x) = x
- 1/2x2
+ 1/3x3
- 1/4x4
+ ...
While this looks cool and elegant, this algorithm is not (usually) built into (scientific) calculators or runtime libraries, because it's... well, it's not very efficient and for some values it's not very accurate either, or rather it doesn't yield as much accuracy for a given amount of work as some other algorithms do. These days, the most popular implementations are Polynomial functions using a table of numbers pre-computed according to a method thought up by an Indian gentleman with a name I can neither spell nor even remember. ariels tells me his name is probably Ramanujan, and my follow-up shows
the he may well be the one I'm thinking of. But they also show that calculators apparently use something called
the CORDIC algorithm developed by Jack E. Volger in 1959. Jack worked for Hewlett-Packard (HP) and this would explain how the algorithm ended up in calculators.
I'm happy that people have come up with "best practices" for calculating things like this, but if I were ever
stuck on a small island with only a four-function calculator and without those tables, I'd be... stuck. Never
mind of what use logarithms would be to me on an island. I'm much happier to announce that I've come up with a very cool and simple alternative! Done on a pocket calculator, it calculates decimal logarithms (based on powers of the number 10), but the algorithm can be easily adapted to dual (based on powers of the number 2) logarithms.
I'll demonstrate the method with an example: Say we want to find the decimal log of 604800, the number of seconds in a week.
- repeatedly divide by 10 until the number is in the range between 1 and 10
(I'll call this normalizing from now on).
Count and write down the number of divisions (5 in this case), and a decimal point ( . ).
- Take the normalized number (6.048) to the tenth power.
On most simple calculators, this is easiest done by squaring and then taking to the fifth power.
A sequence which works on many models, using automatic constants, is
X X = X X = = = = .
- Normalize the resulting number again, and write the number of divisions down to the right of the decimal point (or following any digits that are already there).
- repeat from step #2 as often as desired. Each step yields an additional digit, but remember the accuracy of the result will never be greater than the accuracy of your calculator. Generally, 8 digits or so can be trusted, no more.
Presto, instant simple logarithms. This is probably pretty trivial stuff to a mathematician, but I'm pretty proud to have hit upon this by myself as a high school student of 15 or so. Until someone challenges me with prior art, I'll call this Smotricz's Algorithm in honor of... myself.
On a computer, it would probably be simpler to keep squaring and dividing by 2 to obtain successive binary digits.