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:
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:
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
"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
http://www.dspvlsi.uniroma2.it/pubs/iscas01a/iscas01a.html
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
This system was suggested by George Spelvin1, who also suggested some integer-only microfloat formats. MBCI integers are used to express integer values from a universe in which all the prime factors are in a fairly small set. For example, if the eligible primes are 2, 3, and 5, an MBCI system will represent any integer of the form 2a3b5c for integer values of a, b and c. Such values form the sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, ... (Sloane's A051037).
For fixed-length representations, the typical strategy is to limit the exponent of each eligible prime to a range that can be expressed in a given number of binary digits. For example, using the primes 2 3 and 5 again, one could limit the exponent of 2 to fall in the range 0..15, and the exponents of 3 and 5 to fall in the range 0..3; this allows the exponents to be stored in 4, 2, and 2 bits respectively for a total of 8 bits. Such a system encodes lots of commonly used integer values, including most of the commonly-encountered highly-composite numbers (such as 24, 144, 3600, etc.), all of the common video resolution heights and widths (like 640, 480, 1024, 768, 720 and 1080), and all of the common modem baud rates (like 2400, 19200, and 57600).
Another fixed-width representation does not use explicit bit fields for each exponent, but instead simply indexes into a (hypothetical infinite) list of all integers with the eligible prime factors. For example, a 5-bit representation would be used to specify any of the 32 smallest positive integers of the form 2a3b5c, which are the 32 values of sequence A051037 shown above.
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
"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 Zurich, 1997.
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.
| s | r | l | 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: [2] , [3], [4], [5], [6], [7], [8], [9], [10]
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
CORDIC algorithms
C. W. Schelin, "Calculator function approximation", Amer. Math. Monthly 90 (1983), 317--325.
Neil Eklund, "CORDIC: Elementary Function Computation Using Recursive Sequences"
"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
Composite and Hybrid Systems
"Towards Exact Geometric Computation" (To Appear, Computational Geometry: Theory and Applications) Chee-Keng Yap, 1994
"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
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
[2] Clenshaw, C. W. and Olver, F. W. J.: "Beyond floating point." J. Assoc. Comput. Mach. 31 (1984), 319--328.
[3] 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.
[4] 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.
[5] Clenshaw, C. W. and Olver, F. W. J. 1987. "Level-index arithmetic operations." SIAM J. Num. Anal. 24, 2 (Apr.), 470--485.
[6] C. W. Clenshaw and P. R. Turner, "The symmetric level-index system", IMA J. Numer. Anal. 8 (1988), 517--526.
[7] Peter R. Turner. "A software implementation of SLI arithmetic." In Proc. 9th Symp. on Computer Arithmetic, pp. 18--24. IEEE Computer Society Press, 1989.
[8] 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.*
[9] D.W. Lozier and P.R. Turner, "Error-Bounding in Level-Index Computer Arithmetic", in G. Alefeld and J. Herzberger, eds., Numerical Methods and Error Bounds, Akademie Verlag, Berlin, 1996, pp. 138-145.
[10] Michael A. Anuta, Daniel W. Lozier, Nicolas Schabanel, And Peter R. Turner, "Basic Linear Algebra Operations In Sli Arithmetic", Euro-Par '96, LNCS 1124, Vol. II, Springer-Verlag (1996), pp. 193-202.
[11] Michael A. Anuta, Daniel W. Lozier, and Peter R. Turner, "The MasPar MP-1 As a Computer Arithmetic Laboratory" J. Res. Nat. Inst. Standards and Technology 101,2 (1996) pp. 165-174. http://nvl.nist.gov/pub/nistpubs/jres/101/2/j2anut.pdf
Very good survey, includes several other number systems as well
1 : George Spelvin, email correspondence.
Robert Munafo's home pages on HostMDS (c) 1996-2010 Robert P. Munafo. about contact
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13