Alternative Number Formats

Residue Number System (RNS)

A base is chosen consisting of a set of relatively-prime numbers. Each normal integer is represented in the RNS as a set of digits, each digit is the number's value modulo each of the relatively-prime numbers in the base. For example, if the base is {2,3,5} the numbers 0 through 29 can be represented as follows:


{2,3,5} {2,3,5} {2,3,5} 0 0,0,0 10 0,1,0 20 0,2,0 1 1,1,1 11 1,2,1 21 1,0,1 2 0,2,2 12 0,0,2 22 0,1,2 3 1,0,3 13 1,1,3 23 1,2,3 4 0,1,4 14 0,2,4 24 0,0,4 5 1,2,0 15 1,0,0 25 1,1,0 6 0,0,1 16 0,1,1 26 0,2,1 7 1,1,2 17 1,2,2 27 1,0,2 8 0,2,3 18 0,0,3 28 0,1,3 9 1,0,4 19 1,1,4 29 1,2,4


For example, 17 is (1,2,2) because 17 = 1 mod 2, 17 = 2 mod 3 and 17 = 2 mod 5. Notice that none of the other numbers in the table has the representation (1,2,2), in fact no two numbers in the table have the same representation.

To add, subtract or multiply, you perform a modulo addition, subtraction or multiplication within each field. For example, to multiply 3 by 7:


{2,3,5} 3 = (1,0,3) 1 x 1 = 1 mod 2 (2's column) 7 = (1,1,2) because 0 x 1 = 0 mod 3 (3's column) 21 = (1,0,1) 3 x 2 = 1 mod 5 (5's column)


Converting between binary and RNS is a little difficult, and is based on the Chinese Remainder Theorem.

Division is very difficult, and is the subject of much research.

Articles on residue number systems:

"Residue Number System Based Multiple Code DS-CDMA Systems", Lie-Liang Yang and Lajos Hanzo, The IEEE Vehicular Technology Conference, Houston, Texas, USA, May 16-19, 1999, pp1450-1454 http://www-mobile.ecs.soton.ac.uk/lly/papers/VTC99_RNS1-web.pdf Yang1999.pdf

"Novel High-Radix Residue Number System Processors", V. Paliouras and T. Stouraitis, IEEE Transactions on Circuits and Systems-Part II, vol. 47, no. 10, pp. 1059-1073, October 2000. http://www.vlsi.ee.upatras.gr/Users/Associates/Paliuras/47csii10-paliouras.pdf Paliouras2000.pdf

http://www.dspvlsi.uniroma2.it/pubs/iscas01a/iscas01a.html

"The MasPar MP-1 As a Computer Arithmetic Laboratory" Michael A. Anuta, Daniel W. Lozier, and Peter R. Turner, J. Res. Nat. Inst. Standards and Technology 101 (1996), to appear. http://nvl.nist.gov/pub/nistpubs/jres/101/2/j2anut.pdf Anuta1996.pdf Very good survey, includes several other number systems as well

Double-Base Number System (DBNS)

This is a form of alternate representation being studied for use in digital signal processing at the University of Windsor, Ontario Canada. Numbers are expressed as a sum of one or more terms of the form 2a3b. Each term is either present or absent, represented by a coefficient of 1 or 0 respectively. DBNS representation allows for addition, subtraction and multiplication that are very efficient (by gate count) so is well suited for signal processing or similar applications; the only drawback is conversion to and from standard representation.

"Theory and Applications of the Double-Base Number System", Vassil S. Dimitrov, Graham A. Jullien, and William C. Miller, IEEE Transactions on Computers, Vol. 48, No. 10, October 1999 Dimitrov1999.pdf

Logarithmic Number System (LNS)

Some articles on "logarithmic" number systems:

M. Arnold, T. Bailey, J. Cowles: "Comments on 'An Architecture for Addition and Subtraction of Long Word Length Numbers in the Logarithmic Number System'. , IEEE Trans. on Computers, Jun 1992, pp 786-788

"Semi-Logarithmic Number Systems", J.-M. Muller, A. Scherbyna, and A. Tisserand, IEEE Trans. on Computers, Feb 1998 http://www.ens-lyon.fr/~jmmuller/IEEETC-Fev98.pdf Muller1998.pdf

"Efficient algorithms for binary logarithmic conversion and addition", Y. Wan and C.L. Wey, IEEE Trans. on Computers and Digital Techniques, May 1999, p.168

"Efficient conversion algorithms for long-word-length binary logarithmic numbers and logic implementation", Y. Wan, M.A. Khalil and C.-L. Wey, IEEE Trans. on Computers and Digital Techniques, Nov 1999, p.295

R. Zimmermann, "Computer Arithmetic: Principles, Architectures, and VLSI Design," Lecture notes, Integrated Systems Laboratory, ETH Zürich, 1997.

Level-Index (LI) and Symmetric Level-Index (SLI) Number Systems

This is also called the anti-tetrational number system.

LI and SLI use the same presentation for numbers greater than or equal to 1: A real-number base is chosen (usually e=2.71828... but sometimes 2, or could be any other base). A number x is represented as a triple (s,l,i). s is a sign (0 or 1), l is the level and is a positive integer, i is the index and is in the range [0,1). l and i are related to x in the following way:

x = -1s Fge(l,i)
Fge(l,i) = ei, if i=0
Fge(l,i) = eFge(l-1,i), if i>0

To represent numbers in the range (-1,1), the LI system uses l=0 and i=|x|. In the SLI system, a reciprocal bit r is added, indicating that the quantity being represented is -1s/Fge(l,i). Both systems add a sign bit s to represent negative quantities.

Here are some examples of numbers in the SLI system listed in ascending numerical order. These are all 32-bit word representations, so the i (index) field has 27 bits, shown in hexadecimal. In the rightmost column, extra digits are used to show the size of the difference between adjacent values. You can clearly see how there is more precision for small numbers (like 5) than for big numbers (like 5×10^100). I have not seen any descriptions of the handling of special numbers like 0 and infinity, so I had to guess.


srl i represents the value
1 1 7 7FFFFFF negative infinity
1 0 7 7FFFFFE -1 × 101010109.7×101656518
1 0 7 0000000 -1 × 1010101.01×101656520
1 0 6 0000000 -1 × 10101.01×101656520
1 0 5 0000000 -1 × 101.01×101656520
1 0 4 0000000 -2.3×101656520
1 0 3 7FFFFFF -7.2×101656519
1 0 3 0000000 -3814279.1
1 0 2 7FFFFFF -3814277.9
1 0 2 0000000 -15.1542622
1 0 1 7FFFFFF -15.1542619
1 0 1 0000000 -2.71828183 = -e
1 0 0 7FFFFFF -2.71828180
1 0 0 0000001 -1.0000000075
1 1 0 0000000 -1 (exact)
1 1 0 0000001 -0.9999999925
1 1 0 58B90BF -0.5000000028
1 1 0 58B90C0 -0.4999999990
1 1 1 0000000 -0.3678794411 = -1/e
1 0 0 0000000 -0 (not used)
0 0 0 0000000 0 (exact)
0 1 1 0000000 0.3678794411 = 1/e
0 1 0 7FFFFFF 0.3678794439
0 1 0 58B90C0 0.4999999990
0 1 0 58B90BF 0.5000000028
0 1 0 0000001 0.9999999925
0 1 0 0000000 1 (exact)
0 0 0 0000001 1.0000000075
0 0 0 58B90BF 1.999999988
0 0 0 58B90C0 2.000000003
0 0 0 7FFFFFF 2.71828180
0 0 1 0000000 2.71828183 = e
0 0 1 3CE9CCA 4.999999948 note 8 usable digits
0 0 1 3CE9CCB 5.000000008 and no exact value for 5
0 0 2 0000000 15.1542622 = ee
0 0 3 0000000 3814279.1 = eee
0 0 3 4389695 4.999954139×10100 note 5 usable digits
0 0 3 4389696 5.000033872×10100
1 1 0 0000000 infinity

Papers about LI and SLI:

Clenshaw, C. W. and Olver, F. W. J.: "Beyond floating point." J. Assoc. Comput. Mach. 31 (1984), 319--328.

C.W. Clenshaw, F.W.J. Olver, and P.R. Turner. "Level-index arithmetic: an introductory survey." In P.R. Turner, editor, Numerical Analysis and Parallel Processing, pages 95--168. Springer-Verlag, 1987. Lecture Notes in Mathematics, No.1397.

Lozier And Turner, "Error-Bounding in Level-Index Computer Arithmetic"

"Basic Linear Algebra Operations In Sli Arithmetic", Michael A. Anuta, Daniel W. Lozier, Nicolas Schabanel, And Peter R. Turner, Euro-Par, Vol. II (1996), 193--202.

D.W.Lozier and F.W.J.Olver, "Closure and precision in level-index arithmetic", SIAM J. Numer. Anal. 27 (1990), 1295-1304. *In this paper he shows that arithmetic using the four standard operators is closed in a level-index system with level <= 6 and mantissa <= 5,500,000 bits.*

C. W. Clenshaw and P. R. Turner, "The symmetric level-index system", IMA J. Numer. Anal. 8 (1988), 517--526.

Peter R. Turner. "A software implementation of SLI arithmetic." In Proc. 9th Symp. on Computer Arithmetic, pages 18--24. IEEE Computer Society Press, 1989.

C. W. Clenshaw, D. W. Lozier, F. W. J. Olver, and P. R. Turner, "Generalized exponential and logarithmic functions", Comput. Math. Appl. 12B (1986), 1091--1101.

Clenshaw, C. W. and Olver, F. W. J. 1987. "Level-index arithmetic operations." SIAM J. Num. Anal. 24, 2 (Apr.), 470--485.

Alternative Algorithms for Standard Formats

Exception Handling

  John R. Hauser, "Handling Floating-Point Exceptions in Numeric Programs", ACM trans. on Prog. Lang. and Systems, v 18 no 2 (Mar 1996), 139--174 Hauser1996.pdf

CORDIC algorithms

  C. W. Schelin, "Calculator function approximation", Amer. Math. Monthly 90 (1983), 317--325.

"The Initial Point CORDIC: Elementary Function Computation Using Recursive Sequences" Neil Eklund... EklundInit.pdf

"A Survey of CORDIC Algorithms for FPGA Based Computers", Ray Andraka, FPGA '98. Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, Feb. 22-24, 1998, Monterey, CA. pp. 191--200 http://www.andraka.com/files/crdcsrvy.pdf Andraka1998.pdf

Composite and Hybrid Systems

  "Towards Exact Geometric Computation" (To Appear, Computational Geometry: Theory and Applications) Chee-Keng Yap, 1994 Yap1994.pdf

"Floating Point and Composite Arithmetics", W.N.Holmes, Proceedings of the Eighth Biennial Computational Techniques and Applications Conference, Adelaide, South Australia, Sep 20 - Oct 1, 1997 Holmes1997.pdf

Neville Holmes, "Composite Arithmetic: Proposal for a New Standard." IEEE Computer 30(3): 65-73 (1997) Not online, but see: HolmesArith.pdf, HolmesDisp.pdf and HolmesStor.pdf

Unevaluated Sum of Multiple Native Floating-Point Values

This format is a simple way to get higher precision, without higher range, from another existing format. It relies on certain properties of rounding that are followed by most hardware floating point formats including IEEE 754. See this page for more details.

Dekker, T. (1971) A floating-point technique for extending the available precision. In Numerische Mathematik 18, 224-242.

Wyatt, W.T., et. al. (1976) A portable extended precision arithmetic package and library with Fortran precompiler. ACM Trans. Math. Softw. 2(3), 209-231.

Brent, R. (1978) A Fortran multiple-precision arithmetic package. ACM Trans. Math. Softw. 4(1), 57-70.

Briggs, K. (1998) Doubledouble floating point arithmetic. http://keithbriggs.info/software.html

Li, X., et. al. (2000). Design, implementation and testing of extended and mixed precision BLAS. Lawrence Berkeley National Laboratory. Technical Report LBNL-45991

Hida, Y., et. al. (2001) Quad-double arithmetic: algorithms, implementation, and application. Lawrence Berkeley National Laboratory, Technical Report LBNL-46996.

Priest (1991) Algorithms for Arbitrary Preciion Floating Point Arithmetic. Proc. 10th Symposium on Computer Arithmetic, IEEE Computer Society Press, Caif., 1991.

Priest (1992) On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations.

Shewchuk (1997) Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete and Computational Geometry 18(3), 305-363.

Arbitrary Precision

  R.P. Brent, "Fast multiple-precision evaluation of elementary functions", Journal of the ACM, 23(2), 1976, pp. 242-251.

General and Survey papers

  "Computer Arithmetic: Principles, Architectures, and VLSI Design (1999)", Reto Zimmermann, Lecture notes March 16, 1999 Zimmer1999.pdf


Robert Munafo's home pages at Pair Networks

Men Core Values


© 1996-2008 Robert P. Munafo. Email the author

Creative Commons License This work is licensed under a Creative Commons Attribution 2.5 License.

Back to my main page s.13