Wednesday, July 02, 2014

Four Centuries of Logarithms

I just returned from visiting my former student Rahul Santhanam in Edinburgh. The National Museum of Scotland has an exhibit on logarithms, first published in a book by John Napier in 1614.

Napier invented logarithms to make calculations like multiplication, division and exponentiation easier, using identities like log(ab)=log(a)+log(b). Logarithmic tables and slide rules came soon thereafter. Slide rules became the standard way to do mathematical computations for your typical scientist/engineer until reasonably priced calculators appeared in the late 70's. My chemistry teacher in 1980 taught us how to use a slide rule, even though we all had calculators, and I even (foolishly) tried using my father's slide rule on a chemistry test.

The exhibit struggled to find current uses for logarithms, mentioning only the Richter scale. In theoretical computer science we use logarithms all the time. Here's an incomplete list off the top of my head.
  • As part of a running time usually as a result of divide and conquer. Sorting, for example, takes Θ(n log n) comparisons.
  • The size of a number, pointer or counter. To count up to n requires log n bits of storage.
  • The representation of a small amount of space as in the complexity classes L and NL.
  • To capture entropy, coupon collector and other topics in probability and information.
  • Roughly captures the sum of 1/i or exactly capturing the integral of 1/x.
  • The inverse of exponential growth.
Thanks John Napier for the logarithm and making our lives just a little less linear.

4 comments:

  1. The idea is due to the Babylonians, 2000 BC.

    Rafee Kamouna.

    ReplyDelete
  2. Statistics: log-likelihhod.

    ReplyDelete
  3. From wikipedia:

    The decibel (dB) is a logarithmic unit used to express the ratio between two values of a physical quantity, often power or intensity.

    Notice that this is a natural scale in the sense that what we perceive to be a sound twice as loud is actually exponentially bigger. I.e. the intensity meters in our ears/brains have a built in log term.

    ReplyDelete
  4. Come now, Lance. Eurocentrism is a disease that inflicts most of western historical writing - a hangover from colonialism. Do we really have to be ignorant here in this otherwise enlightened blog?

    Much of pre-modern mathematics and computing has roots in the much older cultures (read: 5000 years old) of China, Iraq, India, and Egypt, not in Europe. Logarithms is no exception. Even logarithms with different bases were studied by the Indian mathematician Virasena (8th Century AD) including properties of base 2 (arda-ksheddam), base 3 (trika-ksheddam) and base 4 (chatur-kshedam).

    P.S: Ardha means half in Sanskrit, and Virasena defined log to the base 2 as the number of times a number could be halved. Hence, the name.

    ReplyDelete