Integer Arithmetic

The tools on this page implement algorithms for integer arithmetic and consider besides radix-B and B-complement numbers also signed digit numbers and Residue Number Systems (RNS) for more efficient parallel computations.

Base Conversion of Radix-B and B-Complement Numbers

This tool converts a given radix-B or B-complement number for some base oldB to a new base newB. The digits of the number should be written as decimal numbers and have to be separated by "." in case of radices greater than 10.

format	Radix-B B-complement
old base	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
new base	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
number

Radix-B and B-Complement Algorithms

This tool provides basic radix-B and B-complement arithmetic operations. The two operands given refer to selected base (radix) B given. The names of radix-B algorithms are prefixed with "Nat" and the names of B-complement algorithms are prefixed with "Int".

radix	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
operation	NatAdd NatSub NatMul NatDiv IntAdd IntSub IntMul IntDiv
first operand
second operand

Radix-B Circuit Generators

This tool generates gate-level implementations of some radix-2 arithmetic circuits. To that end, you have to select a circuit and provide inputs as bitvectors. The tool will then generate the general circuit and will simulate it with the given input vectors.

operation	NatAddCRA NatAddCLA NatMulCRA NatMulCSA NatMulWallace NatMulDadda
first operand
second operand

Radix-B and B-Complement Circuit Verification

This tool verifies a given gate-level implementation of an arithmetic circuit. You can select the specification that should be checked, and the tool will then check the correctness of the circuit. It will either report that the circuit is correct or it will list counterexamples where it will not compute the correct results. The following gates can be used to implement a circuit:

• y = AND(x1,x2) implements y = x1∧x2
• y = XOR(x1,x2) implements y = x1⊕x2
• y = OR(x1,x2) implements y = x1∨x2
• (c,s) = HA(x1,x2) implements c = x1∧x2 and s = x1⊕x2
• (c,s) = FA(x1,x2,x3) implements c = x1∧x2∨x3∧(x1⊕x2) and s = x1⊕x2⊕x3
• (g,p) = PG(g1,p1,g2,p2) implements g = g2∨(p2∧g1) and p = p2∧p1
• y = MX(c,x0,x1) implements y = (c?x1:x0)
• (y0,y1) = SW(c,x0,x1) implements y0 = (c?x1:x0) and y1 = (c?x0:x1)

module NatDivNonrestore([?x0,?x1,?x2,?x3],[?y0,?y1,?y2,?y3],[!q0,!q1,!q2,!q3]) { // -------------------------------------------------------- // subtract <0;0;0;x3> - <y3;y2;y1;y0> // -------------------------------------------------------- ny30 = NOT(y0); ny31 = NOT(y1); ny32 = NOT(y2); ny33 = NOT(y3); (c30,s31) = FA(ny30,x3,1); (c31,s32) = HA(ny31,c30); (c32,s33) = HA(ny32,c31); (q3,s34) = HA(ny33,c32); // -------------------------------------------------------- // if q3 subtract else add: <s33,s32,s31,x2> +/- <y3;y2;y1;y0> // -------------------------------------------------------- ny20 = XOR(y0,q3); ny21 = XOR(y1,q3); ny22 = XOR(y2,q3); ny23 = XOR(y3,q3); (c20,s21) = FA(ny20,x2,q3); (c21,s22) = FA(ny21,s31,c20); (c22,s23) = FA(ny22,s32,c21); (c23,s24) = FA(ny23,s33,c22); qq2 = XOR(c23,q3); nq2 = XOR(s34,qq2); q2 = NOT(nq2); // -------------------------------------------------------- // if q2 subtract else add: <s23,s22,s21,x1> +/- <y3;y2;y1;y0> // -------------------------------------------------------- ny10 = XOR(y0,q2); ny11 = XOR(y1,q2); ny12 = XOR(y2,q2); ny13 = XOR(y3,q2); (c10,s11) = FA(ny10,x1,q2); (c11,s12) = FA(ny11,s21,c10); (c12,s13) = FA(ny12,s22,c11); (c13,s14) = FA(ny13,s23,c12); qq1 = XOR(c13,q2); nq1 = XOR(s24,qq1); q1 = NOT(nq1); // -------------------------------------------------------- // if q1 subtract else add: <s13,s12,s11,x0> +/- <y3;y2;y1;y0> // -------------------------------------------------------- ny00 = XOR(y0,q1); ny01 = XOR(y1,q1); ny02 = XOR(y2,q1); ny03 = XOR(y3,q1); (c00,s01) = FA(ny00,x0,q1); (c01,s02) = FA(ny01,s11,c00); (c02,s03) = FA(ny02,s12,c01); (c03,s04) = FA(ny03,s13,c02); qq0 = XOR(c03,q1); nq0 = XOR(s14,qq0); q0 = NOT(nq0); }
specification	NatAdd NatSub NatMul NatDiv IntAdd IntSub IntMul IntDiv

Residue Number Systems

RNS numbers are tuples of integers (x[0],...,x[n-1]) that refer to a base tuple (prime[0],...,prime[n-1]) of pairwise relatively prime numbers such that the represented number x is represented by x[i] := x mod p[i]. Addition, subtraction, multiplication, and equality testing can be done componentwise on these tuples in the representation chosen for these. Testing for the sign and division is however not directly possible. The tool below does not consider these operations, and just considers the decoding of given RNS numbers, i.e., their conversion into signed radix-10 numbers (all inputs are assumed to be given as signed radix-10 numbers).

prime numbers	8,7,5,3
RNS numbers	3,2,4,2; 0,0,1,1; 2,2,2,2; 1,0,0,0; 0,1,0,0; 0,0,1,1;

Schönhage-Strassen Multiplication

Schönhage-Strassen multiplication was the first quasilinear algorithm for multiplication of radix-B numbers. It is based on a special Fast Fourier transform that works on a ring modulo 2²ⁿ+1 and perform the multiplication of n-bit radix-B numbers in sequential time O(n*log(n)*log(log(n))). It can be easily implemented as PRAM algorithm that runs in parallel time O(log(n)) with work O(n*log(n)*log(log(n))). While the algorithm was developed in 1971, there were no improvements until 2007, where Fürer, and then De/Saha/Kurur/Saptharishi improved it to O(n*log(n)*log*(n)). Further improvements were presented in 2015-2018 by Covanov/Thomé and Harvey/van der Hoeven/Lecerf to O(n*log(n)*2^2log*(n)).

operand 1	123456789
operand 2	999999999