Logarithm Function (Python, functional)
Calculate base-10 logarithms to a specified number of decimal places.
Contents |
[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 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 + log_{10}x = l + s + log_{10}x / 10^{s}, 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: logx^{10} = 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)
<<alog10.py>>= 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:
<<alog10.py>>= e = 2.7182818284590451 print alog(10**e) print 10**alog(e) print e
The output should be:
0.653 0.653212 0.653212513775 2.71828182846 2.71828182846 2.71828182846
[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 |