Logarithmic Number System
From Wikipedia, the free encyclopedia
The Logarithmic Number System (LNS) is an arithmetic system used for representing real numbers in computer and digital hardware. It was first introduced in 1975 by Swartzlander and Alexopoulos[1] as an alternative to the Floating Point Number system, although the mathematical foundations for LNS trace back to Carl Friedrich Gauss, Z. Leonelli [1] and John Napier.
In LNS, a number, X, is represented by the logarithm, x, of its absolute value as follows:
,
where s is a bit denoting the sign of X (s = 0 if X > 0 and s = 1 if X < 0).
The number x is represented by a binary word which usually is in the two's complement format. LNS can be considered as a Floating Point number with the significand being always equal to 1. This formulation simplifies the operations of multiplication, division, roots and powers, since they are reduced down to addition, subtraction, multiplication and division respectively.
On the contrary, the operations of addition and subtraction are more complicated and they are calculated by the formula:
- logb( | X | + | Y | ) = x + sb(z)
- logb( | | X | − | Y | | ) = x + db(z),
where z = y − x, sb(z) = logb(1 + bz), db(z) = logb(1 − bz). sb(z) and db(z) are also known as Gaussian logarithms. The simplification of multiplication, division, roots, and powers is counterbalanced by the cost of evaluating the sb(z) and db(z) functions depicted in the following figures:
[edit] Applications
LNS has been used in the Gravity Pipe (GRAPE) special-purpose supercomputer [2] that won the Gordon Bell Prize in 1999. LNS is commonly used as part of Hidden Markov models, such as the Viterbi algorithm, with applications in speech recognition and DNA sequencing.
A substantial effort to explore the applicability of LNS as a viable alternative to FP for general-purpose processing of single-precision real numbers is described in the context of the European Logarithmic Microprocessor (ELM)[3]. A fabricated prototype of the processor, which has a 32-bit cotransformation-based LNS Arithmetic Logic Unit (ALU), shows that LNS can have better than FP accuracy, with improved speed.
[edit] References
- ^ E. E. Swartzlander and A. G. Alexopoulos, “The Sign/Logarithm Number System,” IEEE Transactions on Computers, vol. 24, pp. 1238-–-1242, Dec. 1975.
- ^ J Makino and M. Taiji, Scientific Simulations with Special Purpose Computers: The GRAPE Systems, Wiley. 1998.
- ^ J. N. Coleman, C. I. Softley, J. Kadlec, R. Matousek, M. Tichy, Z. Pohl, A. Hermanek, and N. F. Benschop, The European Logarithmic Microprocessor, IEEE Transactions on Computers, vol. 57, pp. 532--546, April 2008.
