Logarithm Function (Python, functional)

From LiteratePrograms
Jump to: navigation, search
When the waters of the Flood subsided, Noah spake unto the animals: "Go forth and multiply." All the animals did as they were bid, save a pair of serpents, who said, "We cannot multiply, for we are adders." Then Noah bade them, "Come thou hither, upon the rough furniture where I partake my meals." They did so, and in due time, became exceeding numerous, for even adders can multiply with a log table.trad.

Calculate base-10 logarithms to a specified number of decimal places.


[edit] theory

If one wishes to use logarithms in Python, then the built-in math.log10 is the obvious solution.

Here we take advantage of the algebraic structure of \mathbb{R} to produce an entirely functional expression approximating log10 to a given number of digits.

[edit] practice

For much of this program, we deal with pairs (x,l), where l accumulates an integer approximation to the logarithm, and x encodes the remainder of the argument for which we seek the logarithm.

  • shift, in expressing the identity l + log10x = l + s + log10x / 10s, shifts the decimal point of x.
  • scale is a shift with an argument of -1, 0, or 1, either bringing the x closer to units magnitude while incrementing (or decrementing) l, or, with an s at 0, returning x and l unchanged.
  • ipart is the value which iterated scales converge to, at which point l is the integer part of the logarithm.
<<extracting the integer part>>=
shift = lambda x,l,s: (x/(10.0**s), l+s)
scale = lambda x,l: shift(x, l, (x >= 10)-(x < 1))
ipart = lambda x: fix(scale, (x,0))

To extract the fractional digits, we repeat the steps above for each fractional decimal place. A single digit is l, and the digits which come after it are handled by shifting the effective decimal place in the recursion: logx10 = 10 * logx

In a lazy language, the restriction d on number of decimal places extracted could be handled in the top-level expression, but as python is eager, we must propagate it through the entire expression, truncating with a value of 0.0 after the last decimal place desired.

<<approximating log10>>=
digit = lambda x,l,d: l + alog(x**10, d-1)/10.0
alog  = lambda x,d=12: (d>=0) and digit(*ipart(x)+(d,)) or 0.0

Question: why not write (d<0) and 0.0 or digit(*ipart(x)+(d,))?

Question: which instances of 10 in the code above refer to the base of the logarithm, and which refer to the decimal output?

[edit] wrapping up

We now provide the ancillary detail of arranging for a computation to converge.

Exercise: in this case, there is no danger of scale entering a loop. Write a more general fixpoint, which detects convergence to a loop and terminates properly. In such cases, does it matter which loop element is returned?

<<converging to a fixpoint>>=
fix   = lambda f,v1,v0=None: (v0 == v1) and v0 or fix(f, f(*v1), v1)

Finally, we wrap everything up in a module, which, when run, uses the same test vectors as Logarithm Function (Python)

converging to a fixpoint
extracting the integer part
approximating log10
if __name__ == "__main__":
    value = 4.5
    print alog(value, 3)
    print alog(value, 6)
    print alog(value)

... and add a quick sanity check: log_{10} 10^x = 10^{log_{10} x} = x

    e = 2.7182818284590451
    print alog(10**e)
    print 10**alog(e)
    print e

The output should be:


[edit] agendum

  • Rewrite this article according to the following exercise, but not until several years after the appropriate python version has been available.

Exercise: rewrite alog and fix to use the ternary operator.

Download code