Elementary Functions

Elementary functions

Realization of operators for Exponential, Logarithm, Sine, Cosine, Tangent, inverse Tangent, inverse Sine relying on additions/subtractions and shifts. The shifts cost and delay is negligible since they are wired. The additions/subtractions can be carry-propagation free.   cost max. delay addition/subtraction/shift n2 n table reading (ROM) n * 2n log2(n) A table reading (ROM) would usually be faster, but the table size, and consequently the cost, grows exponentially with the number of bit demanded for the precision. Nevertheless the table partition reduces this size.

From a bread loaf weighting to the exponential computation

We want to compute exp ( Y ), we have available a scale, a white bread whose weight is actually just Y and a set of weights with values log(1 + 2-j ). The weighting gives the sought-after result in the form of a product of rationals (2j + 1) / 2j . The multiplication by each rational amount to a mere addition and shift. A weight put down on the right plate (the bread's one) has it value changed into -log(1 – 2-j ). Thank to this trick, the weighting can be restoring, non-restoring or "SRT".

Carry propagation free division for exponential

The scale is replaced by a "SRT" divider whose "Robertson's diagram" is drawn below.

"SRT" divider for exponential

The constants log(1 + 2-j ) and -log(1 – 2-j ) fed into the "tail" cells are wired . Thus there are 4 variants for the cell according to the values of the two bits.

Operations of a slice of "SRT" divider for exponential

The value of each qj is selected by a "head" cell according to j , the weighted sum of the two most significant digits r1 and r0 of the representation of Rj. if j > 0 then { qj = '1' ; s0 = j - 1 ; Rj+1 = Rj + log(1 – 2-j ) }// subtraction if j = 0 or j = - 0.5 then { qj = '0' ; s0 = j ; Rj+1 = Rj + 0 } // identity if j < - 0.5 then { qj = '-1' ; s0 = j + 1 ; Rj+1 = Rj + log(1 + 2-j ) } //addition

Sequence of multiplications

The sequence of conditional multiplications by 1, by (1 + 2-j ) or by (1 – 2-j ) requires only one final carry propagation thanks to "CS" adders and to wired shifts. The "CS" additions are truncated to 2n +1 digits, of whom three before the decimal point. The third most significant digit (on the left) is the sign. Although the intermediate results are all positive, doing subtraction in "CS" sometimes lead to unresolved signs. The final result at the bottom must be converted from "CS" to standard binary (a subtraction). The colored window makes it easy to compare the "real" multiplication result (without truncation) and the circuit output (with truncation)

"ME" cell

The "ME" cell derives from the add cell "CS" fitted with an extra input "aj" to control either the addition, the identity or the subtraction. Notice that the activity of the carry-in "e" never propagates to the carry-out "h". if qj = '-1' then 2*co + s = eg + ed + ci // addition if qj = '0' then 2*co + s = eg + ci // identity if qj = '1' then 2*co + s = eg + 2 – ed + ci // subtraction

The series of rational products is given by the concatenation of the quotient Q ( left ) and the final remainder R (bottom). Actually for high values of j, 2j * log(1 + 2-j ) becomes very close to 1. If the divider is close to 1, then the remainder becomes an acceptable approximation for the quotient. The applet gives all the successive partial remainders. The dividend Y (top) must be within ] -1 , +1 [ .

Notation conversion

The stack of conditional multipliers by (1 + 2-j ) or by (1 – 2-j ) needs only one final carry propagation thanks to the "CS" adders and wired shifts.

Additions are truncated to 2 n digits, two of which before the decimal point. The third most significant digit ( fully left) is the sign. Despite the fact that all partial results are positive, the execution of subtraction in "CS" sometimes brings about an unresolved sign. The final result (bottom line) must be converted from "CS" to binary by an addition (with carry propagation). The previous circuit works with X in the range ] -1 , +1 [ . For the exponential of any number Y, Y is written Y = Q*log(8) + R, where Q is the integer quotient of the division of Y by log(8) and R < log(8) < 1. Then exp(X) = 8Q * exp(R) = 23Q * exp(R). Since exp(R) < 1, it is acceptable by the above circuit.

Logarithm and exponential

The same operator computes either the Logarithm or the Exponential with additions/subtractions (it is the same operation), shifts and constants. The constants are log(1 + 2-j ) and -log (1 – 2-j ) and the digits qj Î{ '-1' , '0' , '1' }. The slack selection of the digit value, which will unfortunately be missing later on for Sine and Cosine, allows to avoid all carry propagation but the final one.