# 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

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

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.

## 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> - // -------------------------------------------------------- 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: +/- // -------------------------------------------------------- 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: +/- // -------------------------------------------------------- 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: +/- // -------------------------------------------------------- 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 22n+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)*22log*(n)).

 operand 1 123456789 operand 2 999999999