Binary Logarithm - Example Code

Example Code

The following Python program computes the binary logarithm using the recursive method outlined above, showing the steps along the way: (This code fails when finding the binary logarithm of any number 2^n where n is any integer.)

def lg(x): ip = 0 rem = x # Integer part while rem<1: ip -= 1 rem *= 2 while rem>=2: ip += 1 rem /= 2 print("lg(%g) = %d + lg(%g)" % (x, ip, rem)) # Brackets required for Python 3 # Fractional part res = ip + frac_lg(rem) return res def frac_lg(x, fp=1.0, tol=1e-10): assert 1<=x<2 # terminate the recursion if we're close enough if fp= 2 rem = x m = 0 while rem < 2: m += 1 fp /= 2 rem *= rem # now: # rem = x**2**m, fp = 2**-m # => lg(rem) = lg(x)*2**m = lg(x)/fp # => lg(x) = fp * ( lg(rem/2) + 1 ) # = fp + fp*lg(rem/2) # time for recursion! print("lg(x=%g) \t= 2**%d * ( 1 + lg(%g) )" % (x, -m, rem/2)) return fp + frac_lg(rem/2, fp, tol) if __name__ == '__main__': value = 4.5 print " X =", value result = lg(value) print("lg(X) =", result)# Brackets required for Python 3 # Sample output # # $ python log2.py # X = 4.5 # lg(4.5) = 2 + lg(1.125) # lg(x=1.125) = 2**-3 * ( 1 + lg(1.28289) ) # lg(x=1.28289) = 2**-2 * ( 1 + lg(1.35435) ) # lg(x=1.35435) = 2**-2 * ( 1 + lg(1.68226) ) # lg(x=1.68226) = 2**-1 * ( 1 + lg(1.415) ) # lg(x=1.415) = 2**-1 * ( 1 + lg(1.00111) ) # lg(x=1.00111) = 2**-10 * ( 1 + lg(1.55742) ) # lg(x=1.55742) = 2**-1 * ( 1 + lg(1.21278) ) # lg(x=1.21278) = 2**-2 * ( 1 + lg(1.08166) ) # lg(x=1.08166) = 2**-4 * ( 1 + lg(1.75563) ) # lg(x=1.75563) = 2**-1 * ( 1 + lg(1.54113) ) # lg(x=1.54113) = 2**-1 * ( 1 + lg(1.18753) ) # lg(x=1.18753) = 2**-3 * ( 1 + lg(1.97759) ) # lg(x=1.97759) = 2**-1 * ( 1 + lg(1.95543) ) # lg(x=1.95543) = 2**-1 * ( 1 + lg(1.91185) ) # lg(x=1.91185) = 2**-1 * ( 1 + lg(1.82758) ) # lg(X) = 2.16992500139 #

Since Python does not optimize tail recursion, this can be implemented more efficiently with iteration. Here is an iterative version of the same algorithm in Perl:

sub lg { my $x = shift; my $tol = shift || 1e-13; my $res = 0.0; while ($x < 1) { $res -= 1; $x *= 2; } while ($x >= 2) { $res += 1; $x /= 2; } my $fp = 1.0; while ($fp >= $tol) { $fp /= 2; $x *= $x; if ($x >= 2) { $x /= 2; $res += $fp; } } $res } printf "x = %g\nlg(x) = %g\n", 4.5, lg(4.5);

Read more about this topic:  Binary Logarithm

Famous quotes containing the word code:

    “Acknowledge your will and speak to us all, “This alone is what I will to be!” Hang your own penal code up above you: we want to be its enforcers!”
    —Friedrich Nietzsche (1844–1900)

    “Motion or change, and identity or rest, are the first and second secrets of nature: Motion and Rest. The whole code of her laws may be written on the thumbnail, or the signet of a ring.”
    —Ralph Waldo Emerson (1803–1882)