Logarithm Function (Python)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Pascal | Python | Python, functional

Contents

[edit]

Logarithm function

The logarithm function performs a mathematical operation that is the inverse of an exponentiation function (raising a constant, the base, to a power). The logarithm of a number x in base b is any number n such that x = bn. It is usually written as

\log_b(x) = n . \,\!

Finding the logarithm in base b of a positive real number x can be done in two parts:

  • Finding the integer part of the logarithm
  • Finding the fractional part of the logarithm
[edit]

1. Finding the integer part

Finding the integer part can be done by simply dividing the number x by the base b until it is no longer larger than the base b. The integer part is the number of iterations we do the division.

For example: Find log base 3 of 161.64

iteration no 1 161.64 / 3 = 53.88
iteration no 2 53.88 / 3 = 17.96
iteration no 3 17.96 / 3 = 5.9866
iteration no 4 5.9866 / 3 = 1.9955

As it takes 4 iterations, the integer part of the logarithm is 4.

[edit]

2. Finding the fractional part

To find the fractional part, we use the fact that multiplying a logarithm number by two is equivalent to squaring.

Example: find fractional part of 161.64 in log base 3

161.64 = 3^{\,\,\! 4 + f_0} = 3^4 \times 3^{f_0} \,
thus
3^{f_0} = \frac{161.64}{3^4} = 1.9955 \,

Next we square both sides

(3^{f_0})^2 = 1.9955^2 \,
3^{2 f_0} = 3.9822419753086402 \,

Because 3.98 is greater than 3, we can write:

3^{2 f_0} = 3^{1 + f_1} = 3^1 \times 3^{f_1} = 3.9822419753086402 \,
thus
2 f_0 = 1 + f_1 \,
f_0 = \frac{1}{2} + \frac{1}{2} \times f_1 \,

Next we concentrate on f1

3^1 \times 3^{f_1} = 3.9822419753086402 \,
becomes
3^{f_1} = \frac{3.9822419753086402}{3^1} = 1.3274139917695467 \,

Next we repeat the trick of squaring both sides

(3^{f_1})^2 = 1.3274139917695467^2 \,
3^{2 f_1} = 1.7620279055455621 \,

Because 1.76 is less than 3, we can write:

3^{2 f_1} = 3^{0 + f_2} = 3^0 \times 3^{f_2} = 1.7620279055455621 \,

thus:

2 f_1 = 0 + f_2 \,
f_1 = \frac{0}{2} + \frac{1}{2} \times f_2 \,

Next we concentrate on f2

3^0 \times 3^{f_2} = 1.7620279055455621 \,
becomes
3^{f_2} = \frac{1.7620279055455621}{3^0} = 1.7620279055455621 \,

With the general procedure established above, we can calculate f_3 \, , f_4 \, , f_5 \, , f_6 \, and so on.

Recapping, we have:

f_0 = \frac{1}{2} + \frac{1}{2} \times f_1 \,

and

f_1 = \frac{0}{2} + \frac{1}{2} \times f_2 \,

thus creating

f_0 = \frac{1}{2} + \frac{1}{2} \times ( \frac{0}{2} + \frac{1}{2} \times f_2 ) \,
f_0 = \frac{1}{2^1} + \frac{0}{2^2} + \frac{1}{2^2} \times f_2 \,


In general, we have

f_0 = \frac{a_1}{2^1} + \frac{a_2}{2^2} + \frac{a_3}{2^3} + \frac{a_4}{2^4} + ... + \frac{a_{n-1}}{2^{n-1}} + \frac{1}{2^n} \times f_n \,

or

f_0 = \sum_{k=1}^\infty \, \frac{a_k}{2^k} \,
Where a_k \, is either 1 or 0
[edit]

Source Code

<<logN.py>>=
#!/usr/bin/python

from __future__ import division
import math

def logN(X, base=math.e, epsilon=1e-12):
  # logN is logarithm function with the default base of e
  integer = 0
  if X < 1 and base < 1:
    raise ValueError, "logarithm cannot compute"
  while X < 1:
    integer -= 1
    X *= base
  while X >= base:
    integer += 1
    X /= base
  partial = 0.5               # partial = 1/2 
  # list = []                   # Prepare an empty list, it seems useless
  X *= X                      # We perform a squaring
  decimal = 0.0
  while partial > epsilon:
    if X >= base:             # If X >= base then a_k is 1 
      decimal += partial      # Insert partial to the front of the list
      X = X / base            # Since a_k is 1, we divide the number by the base
    partial *= 0.5            # partial = partial / 2
    X *= X                    # We perform the squaring again
  return (integer + decimal)

if __name__ == '__main__':
  value = 4.5
  print "       X  = ", value
  print "    ln(X) = ", logN(value)
  print "  log4(X) = ", logN(value, base=4)
[edit]

Sample Run

$ python logN.py
       X = 4.5
    ln(X)= 1.50407739678
  log4(X)= 1.08496250072
[edit]

Extension

Given the equation:

x = base^{Integer + f_0}


The algorithm above computes

f_0 = \sum_{k=1}^\infty \, \frac{a_k}{2^k} \qquad \mbox{where} \,\,\, a_k \,\, \mbox{is either 1 or 0}

However, by modifying the algorithm slightly, it's possible to compute

f_0 = \sum_{k=1}^\infty \, \frac{b_k}{10^k} \qquad \mbox{where} \,\,\, b_k \, \in \left \{ 0,1,2,3,4,5,6,7,8,9 \right \}

This will allow us to stop the computation at a particular decimal place.

[edit]

Source Code

<<logNdp.py>>=
#!/usr/bin/python

from __future__ import division
import math

# Note: compute the log of X>=1. Doesn't work for X<1. Ex: logN(0.5) returns -1.698970... instead of -0.301029...

def logN(X, base=math.e, decimalplaces=12):
  integer = 0
  while X < 1:
    integer -= 1
    X *= base
  while X >= base:
    integer += 1
    X /= base
  result = str(integer) + '.'
  while decimalplaces > 0:
    X = X ** 10                     # Calc X to the 10th power
    digit = 0
    while X >= base:
      digit += 1
      X /= base
    result += str(digit)
    decimalplaces -= 1
  return result


if __name__ == '__main__':
  value = 4.5
  print "                        X  = ", value
  print " 3 decimal places   LOG(X) = ", logN(value, base=10, decimalplaces=3)
  print " 6 decimal places   LOG(X) = ", logN(value, base=10, decimalplaces=6)
  print "12 decimal places   LOG(X) = ", logN(value, base=10)
[edit]

Sample Run

$ python logNdp.py
                        X  = 4.5
 3 decimal places   LOG(X) = 0.653
 6 decimal places   LOG(X) = 0.653212
12 decimal places   LOG(X) = 0.653212513775
Download code
Retrieved from "http://en.literateprograms.org/Logarithm_Function_%28Python%29"
Personal tools