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 X = 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 is classical and requires (Nb. weights  1) addition to approximate the bread's weight Y. The weights values are such that to compute the exponential of this approximation of Y requires also one extra addition per weight.
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 the partial remainder 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 pseudo 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 "qj" 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

Circuit for exponential computation X = exp ( Y )

A "pseudo division" ( the divider is different for each digit qj of the quotient Q ) computes Sj log(1 + qj2-j) + R = Y. A sequence of "pseudo multiplications" computes X = exp(Sj log(1 + qj2-j). The two computations run simultaneously, without carry propagation thanks to redundant notations, consequently the final result must be converted from "CS" to standard notation.

exponential computation

 Numerical example for pseudo division

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 [ .
  When "Nb. bits" is less than 14, there is enough room to display the involved constants log(1 ± 2-j ) (in red) as well as the partial remainders Rj value (in black). Let us recall than R is written with the digits '-1', '0' and '1'. The first digit of the constants is '1' or '-1' while the others are '1' or '0'.

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 missed later on for Sine and Cosine, allows to avoid all carry propagation but the final one. Clicking the vertical arrow "view" changes the presentation. The key "Reset" allows to control 'manually' the convergence.