Logarithm algorithm

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 - ¹/₂x² + ¹/₃x³ - ¹/₄x⁴ + ...

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.

1. 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 ( . ).
2. 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 = = = = .
3. 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).
4. 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.

An explanation of how the above algorithm works:

Start with the identity log₁₀(x) =
(y + log₁₀(x) - y) =
(y + log₁₀(x) - log₁₀(10^y)) =
(y + log₁₀(x * 10^-y)) =
(y + ((1 / 10) * log₁₀((x * 10^-y) ¹⁰)))

The first step in calculating log₁₀(x) is to calculate floor(log₁₀(x)). This is quite easily accomplished by counting the number of divisions by 10 necessary to get a value from 1 to 10 [excluding 10]. This is a useful value for y.

The number you get after dividing x by 10 y times is (x * 10^-y). You see where this is going.

The purpose of step 1 is to get y and (x * 10^-y). The purpose of step 2 is to get (x * 10^-y)¹⁰. The purpose of the recursion is to calculate log₁₀((x * 10^-y)¹⁰). The purpose of writing the value as a string of digits and concatenating the single-digit results of the second and subsequent y values is to perform the addition and incorporate the (1 / 10) factor.

If the value to start with were less than 1, the easiest way to adapt this algorithm would be to calculate the log of the reciprocal (multiplicative inverse) of the value, then invert the sign of the result.