Ultraleap Patent | Hardware algorithm for complex-valued exponentiation and logarithm using simplified sub-steps

Patent: Hardware algorithm for complex-valued exponentiation and logarithm using simplified sub-steps

Drawings: Click to check drawins

Publication Number: 20210109712

Publication Date: 20210415

Applicants: Ultraleap

Abstract

A method of generating complex exponentiation and logarithms in hardware is described that uses half the number of bits of lookup tables as the state-of-the-art. By splitting up each of the iterations into more simplified stages or using more iterations, the amount of precomputed information that must be held by the circuitry is reduced. This allows synthesis tools to take this more succinct logical description of the algorithm and make it into efficient gate level logic for fabrication into more compact integrated circuitry.

Claims

1. A system comprising: a hardware component having at least one input and at least one output; wherein the hardware component implements a switchable complex-valued unit having a to-logarithm functionality and a to-exponential functionality; wherein the at least one input and the at least one output are complex valued; wherein shift-and-add processes are applied to values in the hardware component that effect a separable multiplication of: i) the at least one input; ii) (1+c); and (1+di); wherein "c" is a real value and "di" is an imaginary value.

2. The system of claim 1, wherein a logarithm process implemented by the unit is an affine logarithm process; and wherein an exponential processes implemented by the unit are an affine exponential process.

3. The system of claim 2, wherein the relation: 2 tan - 1 2 - p .pi. .apprxeq. 1 2 log 2 1 + 2 - p , ##EQU00046## is used to approximate a lookup value of an arctangent expression as an existing lookup value of a binary logarithm expression and a smaller delta table.

4. The system of claim 2, wherein an imaginary part of the input in the affine logarithm process is tested and, if less than -1/2 or greater than or equal to +1/2, rotated by 45 degrees prior to an iteration.

5. The system of claim 1, wherein the to-logarithm functionality completes a division of an auxiliary value in parallel on an iteration.

6. The system of claim 1, wherein the to-exponential functionality completes a division of an auxiliary value in parallel on an iteration.

7. The system of claim 1, wherein the to-logarithm functionality conducts an iteration test on a value that is an existing value subtracted by +1.

8. The system of claim 1, wherein the to-exponential functionality conducts an iteration test on a value that is an existing value subtracted by +1.

9. The system of claim 1, wherein "c" is also a non-zero value and "di" is also a non-zero value.

10. The system of claim 9, wherein a logarithm process implemented by the unit is an affine logarithm process; and wherein an exponential processes implemented by the unit are an affine exponential process.

11. The system of claim 10, wherein the relation: 2 tan - 1 2 - p .pi. .apprxeq. 1 2 log 2 1 + 2 - p , ##EQU00047## is used to approximate a lookup value of an arctangent expression as an existing lookup value of a binary logarithm expression and a smaller delta table.

12. The system of claim 10, wherein an imaginary part of the input in the affine logarithm process is tested and, if less than -1/2 or greater than or equal to +1/2, rotated by 45 degrees prior to an iteration.

13. The system of claim 9, wherein the to-logarithm functionality completes a division of an auxiliary value in parallel on an iteration.

14. The system of claim 9, wherein the to-exponential functionality completes a division of an auxiliary value in parallel on an iteration.

15. The system of claim 9, wherein the to-logarithm functionality conducts an iteration test on a value that is an existing value subtracted by +1.

16. The system of claim 9, wherein the to-exponential functionality conducts an iteration test on a value that is an existing value subtracted by +1.

17. The system of claim 9, wherein when iterations of the shift-and-add processes are applied to the values in the hardware component, an aggregation of the values in the hardware component substantially follow a Fibonacci sequence.

Description

PRIOR APPLICATIONS

[0001] This application claims the benefit of U.S. Provisional Patent Application No. 62/914,487 filed on Oct. 13, 2019, which is incorporated by reference in its entirety.

[0002] The prior application, U.S. application Ser. No. 15/839,184 filed on Dec. 12, 2017, is incorporated by reference in its entirety.

[0003] The prior application, U.S. Application No. 62/594,687 filed on Dec. 5, 2017, is incorporated by reference in its entirety.

FIELD OF THE DISCLOSURE

[0004] The present disclosure relates generally to developing and applying hardware algorithms for complex-valued exponentiation and logarithm using simplified sub-steps.

BACKGROUND

[0005] The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex logarithms (L-mode) and exponentials (E-mode) using a method similar to the algorithm Henry Briggs used to compute logarithms. By using a precomputed table of logarithms of negative powers of two, the BKM algorithm computes elementary functions using only integer add, shift, and compare operations.

[0006] BKM is similar to CORDIC but uses a table of logarithms rather than a table of arctangents. On each iteration, a choice of coefficient is made from a set of nine complex numbers, 1, 0, -1, i, -i, 1+i, 1-i, -1+i, -1-i, rather than only -1 or +1 as used by CORDIC. BKM provides a simpler method of computing some elementary functions, and unlike CORDIC, BKM needs no result scaling factor. The convergence rate of BKM is approximately one bit per iteration, like CORDIC, but BKM requires more precomputed table elements for the same precision because the table stores logarithms of complex operands.

[0007] As with other algorithms in the shift-and-add class, BKM is particularly well-suited to hardware implementation. The relative performance of software BKM implementation in comparison to other methods such as polynomial or rational approximations will depend on the availability of fast multi-bit shifts (i.e. a barrel shifter) or hardware floating point arithmetic.

[0008] Previously disclosed was an approach to recast the complex exponentiation and logarithm problem from the classical manipulation r+i.theta.e.sup.r+i.theta. using the BKM algorithm, to the manipulation r+i.theta.2.sup.r(e.sup..pi./2).sup.i.theta. using a revised algorithm which shall be referred to as the BKML algorithm. This revised BKML algorithm takes the form of two algorithms, each the reverse of the other, one to compute:

f(r+i.theta.)=2.sup.r(e.sup..pi./2).sup.i.theta.,

as well as its inverse:

f - 1 ( r + i .theta. ) = arg ( r + i .theta. ) .pi. / 2 i + log 2 r + i.theta. | , ##EQU00001##

wherein the real part of the logarithm has a base of 2 and the imaginary part has a base of e.sup..pi./2.

[0009] With some modifications, this can apply to any power-of-two base for the real part, and any power-of-two multiplied by pi and exponentiated for the base of the imaginary part. As the real and imaginary part of the process has a different base, the mathematical part of the process described that was implemented was novel and was not named initially. In this document, it shall be described and claimed as an `affine logarithm` or `affine exponential`. The process shall be described as an `affine logarithm process` or `exponential-to-logarithm process` and an `affine exponential process` or `logarithm-to-exponential process` interchangeably. This is proceeded by a series of n steps choosing a value d.sub.n for each in turn, where:

d.sub.n.di-elect cons.{0,+1,+i,-1,+i,-1-i,-1+i,+1-i,+1+i},

and on the first of the complex values, we multiply by:

1+2.sup.-n

and use the logarithm of this value precomputed in table to attenuate the second complex value.

[0010] Through repeated choices of d.sub.n over n iterations, the iteration causes the first value to converge to the exponential and the second value converge to zero. The reverse operation is also possible using much the same process allowing for much the same hardware to be run in a logarithm or exponentiation `mode`. Without loss of generality, due to the structure of the set from which d.sub.n is chosen, the storage cost of table is the number of bits to compute, say N, multiplied by the number of symmetries (usually the total number of non-zero choices of d.sub.n) here eight (if the existing algorithm is expanded fully, this is five real lookups and three imaginary ones). This is a lookup size of 8N over each of N stages, yielding 8N.sup.2 bits dedicated to lookup tables when an implementation of the BKML algorithm is used.

[0011] A further reason that the use of the prior art BKM algorithm is not well known and in widespread use is because the tabulated values take up a large amount of room in a silicon implementation that could be dedicated to other tasks. This is a weakness shared by the BKML implementation of the revised algorithm computing r+i.theta.2.sup.r(e.sup..pi./2).sup.i.theta. disclosed previously.

[0012] While it is difficult to determine precisely, it is quite possible that if eight lookup tables are necessary, computing the real and imaginary parts of the logarithm separately without using the combined iteration demonstrated by the BKM algorithm and the previously disclosed BKML algorithm will in many cases be more efficient with respect to hardware logic complexity and area--a drawback shared by the original BKM algorithm.

[0013] The requirement for eight lookup tables is considered to be due to the difficulty in achieving convergence in its classical r+i.theta.e.sup.r+i.theta. form when the BKM algorithm was conceived by its authors. However, it is shown that with the change of base actioned when the BKML algorithm was invented previously, a new algorithm may be created that can overcome the need for eight look-up tables by requiring less stringent convergence criteria and therefore may be defined to need fewer resources.

[0014] In practice, in the process of looking for a form of the algorithm that requires fewer look-up tables, methods were found that may be applied even to the BKM algorithm.

SUMMARY

[0015] A method of generating complex exponentiation and logarithms in hardware is described that uses half the number of bits of lookup tables as the state-of-the-art. By splitting up each of the iterations into more simplified stages or using more iterations, the amount of precomputed information that must be held by the circuitry is reduced. This allows synthesis tools to take this more succinct logical description of the algorithm and make it into efficient gate level logic for fabrication into more compact integrated circuitry.

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] The accompanying figures, where like reference numerals refer to identical or functionally similar elements throughout the separate views, together with the detailed description below, are incorporated in and form part of the specification, serve to further illustrate embodiments of concepts that include the claimed invention and explain various principles and advantages of those embodiments.

[0017] FIGS. 1A and 1B show illustration of errors in the complex plane in the logarithm-to-exponential process (floating-point implementation) for the BKML4m iteration.

[0018] FIGS. 2A and 2B show illustrations of errors in the complex plane in the exponential-to-logarithm process (floating-point implementation) for the BKML4m process.

[0019] FIGS. 3A and 3B show illustrations of errors in the complex plane in the logarithm-to-exponential process (floating-point implementation) for the BKML3dm iteration prior to the inclusion of the reduced entropy tables.

[0020] FIGS. 4A and 4B show illustration of errors in the complex plane in the exponential-to-logarithm process (floating-point implementation) for the BKML3dm prior to the inclusion of the reduced entropy tables.

[0021] Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.

[0022] The apparatus and method components have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.

DETAILED DESCRIPTION

[0023] This disclosure describes the orthogonalization of the sub-steps in real and imaginary parts to achieve a reduction in the number of lookup tables required for the algorithm and simplifications in the iterative procedure. Applying the orthogonalization to the previously disclosed BKML algorithm results in two algorithms. The first algorithm is more effective when low radix methods are considered, so when throughput and area are prioritized over latency (suitable for implementation in FPGA technologies). The second algorithm is more effective when high radix methods are considered, so when throughput and latency are prioritized over area (suitable for implementation into an application-specific integrated circuit (ASIC) or as an extended capability for a central processing unit (CPU) design).

[0024] The first, denoted BKML4m, requires four lookup values (which with some rewiring may be reduced to effectively three-and-a-half) per bit of result and chooses d.sub.n in a similar way to BKML from nine candidates but with notable changes in the candidate set of d.sub.n drawn from. The BKML4m algorithm requires no extra iterations over the extant previously disclosed BKML algorithm, requiring N radix-2 iterations to converge.

[0025] The second, denoted BKML3dm, requires three lookup values per bit of result, has a simplified method for choosing d.sub.n from four candidates, essentially eliminating zero and on-axis d.sub.n choices. BKML3dm requires some extra iterations to achieve convergence, taking approximately N+log N radix-2 iterations to converge. These extra steps are a problem at low radices, but the simplified choice mechanisms and reduced candidate pool means that this technique may be readily extended to very high radices, necessary for designing high-speed modern hardware. This is especially true since dealing with propagation delays makes arithmetic that need only be synchronized and resolved at key points in the algorithm valuable. Due to this, decision making based on fully resolved result values must be minimized, meaning that when this process generates multiple bits of result per decision step (has high radix) it is particularly effective at reducing latencies.

[0026] The value N takes is for brevity both the number of fraction bits and the number iterations of the method, without loss of generality. While these two properties can take different values, algorithms including such definitions are often of reduced effectiveness, involve trivial changes to the method and are thus are effectively included in the scope of this disclosure.

I. OPTIONAL MULTIPLICATION AND DIVISION

[0027] The exponentiation mode iteration for the method described may also be modified to provide a complex multiplication with the exponential value. If this is to be achieved, this must be pre-loaded before the range reduction steps if the output is to be correct. It should also be noted that this would replace the output exponentiation value and so should be not used if this value is required. It is also feasible to store and wait to apply the solution from the integer parts of the logarithm (the value z.sub.integer, output) to the end of the process. This may reduce the storage required for the intermediate registers in which the processing occurs, although this should be weighed against the extra requirements of storage needed for the integer parts of the solution.

[0028] Alternatively, multiplication with the final exponentiation value may be achieved in parallel by creating extra registers and ensuring that equivalent operations occur in these extra registers. In this way, the exponentiation process may complex multiply the output exponential value with almost arbitrarily many other complex values with parallel hardware.

[0029] The logarithm mode iteration described may also be modified to provide a complex division with the input value. If this is to be achieved, it can only occur in parallel by creating extra registers and ensuring that equivalent operations occur in these extra registers. This contrasts with the auxiliary multiplication, where the original register could be overloaded, which cannot be achieved here because the modification of the exponentiation register in this mode would prevent convergence of the algorithm. However, using auxiliary registers can circumvent this, allowing the logarithm process to, if desired, produce complex-valued division of almost arbitrarily many other numerator complex values with the value input to this process as denominator.

II. RANGE REDUCTION

[0030] More efficient range reduction was one of the primary motivations for the previously disclosed BKML algorithm. This is preserved as an integral part of the algorithm in the presented reduced resource version in this disclosure. In the logarithm-to-exponential iteration, the integer real part of the logarithm input denotes the bit shift applied to either the output registers at the end of the process or initialization of the output registers to a power-of-two at the beginning of the process. The integer imaginary part of the input logarithm, due to the base of e.sup..pi./2, denotes the quadrant (aligned to the axes) of the complex plane in which the resulting exponentiation result must lie. In the exponential-to-logarithm process the reverse is mostly true. The quadrant (aligned to the diagonals) of the complex plane is determined through testing the sign bits and absolute value of the real and imaginary components to give the integer part of the imaginary logarithm. By permuting signs of the real and imaginary parts and potentially swapping them, this rotation can be removed to yield a real part that is guaranteed to be positive and larger than the imaginary part. Counting leading zeroes of this real and larger part allows the integer part of the logarithm to be substantially determined. This substantial determination may be removed by bit shifting both components, such that the remaining portion of the real logarithm may be obtained via the iteration.

[0031] It may also be desirable to keep the integer portion determined by the range reduction step separate from the calculation for as long as possible. This allows the method to perform complex logarithm to floating-point complex exponential conversions that are highly useful in the context of wave physics applications. To achieve a true conversion to a standard floating-point type, the fractional part of the exponentiation may be tested to determine whether the result is too large or small for the mantissa to fit into a particular format, depending on the region of convergence decided upon by the reduced range algorithm. This is necessary because only the larger real part is tested to determine whether the value lies within the convergent region of the complex plane and the size of imaginary part is untested at this time but must be in a known range of values. A final test on the real part of the exponential mantissa and an increment or decrement on the exponential integer exponent then finalizes the representation ready for storage into the floating-point format. In the implementation described here, the complex value may be up to V in size (thus in the interval [0.5, {square root over (2)})), which would if greater or equal to 1 require a divide-by-two and exponent increment to place into the region [0.5, 1) in which the integer part of the exponent is completely described by the exponent of the floating-point value.

III. MULTIPLICATIVE ITERATIONS IN THE COMPLEX PLANE

[0032] Noticing that each iteration requires that we multiply the running product by:

1+2.sup.-n

if we choose the real part of d.sub.n separately from the imaginary part we can choose:

.di-elect cons.{0,-1,+1},

{0,-i,+i}.

The iteration may be modified to perform the running product multiplied by the further product:

(+2.sup.-n)(1+2.sup.-n)=1+2.sup.-n(+)+2.sup.-2n=1+2.sup.-n(++2.sup.-n).

on each iteration. As a result, the diagonal d.sub.n which have both a real and an imaginary part have an extra factor of 2.sup.-2n which results in an extra shift (by 2n bit places) and add requirement for these schemes in the exponential part and a potential extra subtraction in the logarithm part. As using this scheme allows the number of lookup tables to be reduced from eight to four in the worst case, the extra shift and add requirement is more than compensated for as the four extra tables can be dropped as will be demonstrated.

IV. THE BKML4M VARIANT

[0033] Using d.sub.n as highlighted in the previous section but keeping the structure of the algorithm mostly the same leads us to a similar algorithm to that disclosed previously but with a slightly different choice of d.sub.n due to the cross terms. This can be written out as an effectively expanded table for a general d.sub.n:

d n .di-elect cons. { 0 , - 1 , + 1 , - i , + i , - 1 - i + 2 - n i , - 1 + i - 2 - n i , + 1 + i + 2 - n i , + 1 - i - 2 n i , } , ##EQU00002##

[0034] Since the extra 2.sup.-n terms in d.sub.n are n bit places away from the bit currently under scrutiny at any given time, while these extra terms need to be accounted for, they only negligibly affect the convergence of the method. For the most part, this then converges in almost the same way as the original revised method in previous disclosures (although the previous method would necessarily have the disadvantage of requiring eight lookup tables). The changes to the choice of d.sub.n amount to an extra shift-and-add in the product of the exponentials and an extra addition in the summation of the logarithms per iteration.

V. TABLE LOOKUP CONSTRUCTION

[0035] When considering the logarithm portion of each iterative method (both logarithm-to-exponential and exponential-to-logarithm), it can be shown that only four lookup tables containing the bit patterns of the logarithms need be constructed. These are:

l n , + = log 2 | 1 + 2 - n | , l n , - = log 2 | 1 - 2 - n | , l n , d = log 2 | 1 .+-. 2 - n i | = log 2 1 2 + ( .+-. 2 - n ) 2 = 1 2 log 2 ( 1 + 2 - 2 n ) , l n , = 2 .pi. arg | 1 + 2 - n i = 2 .pi. tan - 1 2 - n , ##EQU00003##

[0036] Of these four, it is also possible to reduce it to effectively three and a half via the observation:

=1/2

where the preceding factor of a half may be a bit shift. By reusing table entries for and extending to only for even values (or producing a table of only for even values after the other table has been exhausted) the remainder may be filled by using only half a table.

[0037] Then the logarithms to use for the addition/subtraction portion will be:

(1)=0,

(1-2.sup.-n)=

(1+2.sup.-n)=

(1-2.sup.-ni)-

(1+2.sup.-ni)=+

((1-2.sup.-n)(1-2.sup.-ni)=+-

((1+2.sup.-n)(1-2.sup.-ni)=+-

((1-2.sup.-n)(1+2.sup.-ni)=++

(1+2.sup.-n)(1+2.sup.-ni))=++

These are then added to the running total of the logarithm upon whose upper bits the decision as to the direction to take is chosen for the next iteration.

VI. BKML4M: EXPONENTIATION MODE ITERATION

[0038] With the mechanism using four look-up tables established, the method to achieve complex exponentiation using this approach can be described. The method and region cut-offs for choosing each d.sub.n from the input are very similar to the revised algorithm which required eight look-up tables in the BKML algorithm disclosed prior to this. This allows the method to not require extra iterations to be inserted, because the only difference in the convergence between the previous revised algorithm and this is the extra 2.sup.-2n term, which has much less effect than the other terms in the expansion of the multiplication step.

[0039] Alternatively, multiplication with the final exponentiation value may be achieved in parallel by creating extra registers and ensuring that equivalent operations occur in these extra registers, as described in previous sections. In this way, the exponentiation process may complex multiply the output exponential value with almost arbitrarily many other complex values.

[0040] Assuming the fractional part of the input logarithms to be the input, the algorithm for the domain of convergence z.sub.input.di-elect cons.R=[-0.5,+0.5)+i[-0.5,+0.5) is: [0041] 1. Assuming there are four basic registers, labelled (z.sub.log), (z.sub.log), (z.sub.log) and (z.sub.log). Alongside, there are two extra slave multiplication registers (z.sub.log) and (z.sub.log) to demonstrate how the method operates when used for auxiliary complex multiplication. The initial values of these registers are:

[0041] (z.sub.log):=(z.sub.input),

(z.sub.log):=(z.sub.input),

(z.sub.exp):=(z.sub.integer input, output.times.z.sub.premultiply),

(z.sub.exp):=(z.sub.integer input, output.times.z.sub.premultiply), where z.sub.premultiply=1.0, if there are no requirements for pre-multiplication. The slave multiplication registers may also be similarly constructed with:

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply),

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply). [0042] 2. Iterate through the values 1, . . . N-1 as the index n: [0043] 3. Shift right by N-n and then truncate (z.sub.log) to form (z.sub.log, test) such that it has three bits; one sign bit and two integer bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 1. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0044] 4. Shift right by N-(n+1) and then truncate (z.sub.log) to form (z.sub.log, test) such that it has three bits; one sign bit, one integer bit and one fraction bit in two's complement such that the range is [-2.0,+2.0) with the smallest change being 0.5. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0045] 5. Test the 3-bit values to determine d.sub.n:

[0045] ( d n ) : = { - 1 , if ( z log , test ) < 3 ' sb 111 ( or < - 1 . 0 ) , + 1 , if ( z log , test ) > 3 ' sb 000 ( or .gtoreq. + 1 .0 ) , 0 , if neither , ( d n ) := { - i , if ( z log , test ) < 3 ' sb 111 ( or < - 0.05 ) , + i , if ( z log , test ) > 3 ' sb 000 ( or .gtoreq. + 0.5 ) , 0 , if n either . ##EQU00004## [0046] 6. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0046] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , 0 , if n either , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , 0 , if n either . And : ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , i f ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , i f ( d n ) = + 1 , 0 , if n either , + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , i f ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , i f ( d n ) = + i , 0 , if n either . ##EQU00005## Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication process to these also. [0047] 7. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0048] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2ni:

[0048] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n), [0049] Whereas if (d.sub.n=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n=+2.sup.-2ni:

[0049] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n), [0050] wherein the signs are reversed in the latter case. [0051] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication process to these also. [0052] 8. Subtract the corresponding entry in the logarithm tables from the registers:

[0052] ( z log , n ) := ( z log , n - 1 ) - ( log 2 1 + 2 - ' d n , + log 2 1 + 2 - n d n , ) , = ( z lo g , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) , ( z log , n ) := ( z log , n - 1 ) - ( 2 arg ( 1 + 2 - n d n , ) + 2 arg ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) . ##EQU00006## [0053] This is achieved using the look-up table constructions described in the previous section by log [0054] 9. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain their final values:

[0054] (z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.2(e.sup..pi./2)),

(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.2(e.sup..pi./2)),

And:

'(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.2(e.sup..pi./2)),

'(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.2(e.sup..pi./2)),

[0055] Having appreciated the form of the process, it is easy to find other testing procedures that are convergent, even sometimes in the required domain, by forming (z.sub.log, test), (z.sub.log, test) or both using different number of bits or different comparison values, although we have endeavored to reduce complexity by specifying the required value tests in the simplest known form.

[0056] An illustration of the application of this procedure to values z.sub.input.di-elect cons.R=[-2.0,+2.0)+i[-2.0,+2.0) is shown in FIGS. 1A and 1B.

[0057] FIGS. 1A and 1B show illustration of errors in the complex plane in the logarithm-to-exponential process (floating-point implementation) for the BKML4m iteration. These figures correspond to illustrative tests of the iterative scheme in floating-point and with no range reduction steps to demonstrate the mathematical viability of the dynamical system rather than being a faithful reproduction of the iterative procedures outlined.

[0058] In FIG. 1A, shown is a simulation 1100A where the x-axis 1120A is real, and the y-axis 1110A is imaginary in the input to the algorithm. Shading denotes the error (where a black shading 1130A implies the error is linearly related to the bits and iterations of the algorithm).

[0059] In FIG. 1B, shown is a simulation 1100B where the x-axis 1120B is real, and the y-axis 1110B is imaginary in the input to the algorithm. The white square 1130B is constructed by inverting the color and denotes the portion of the domain (z_"input" ".di-elect cons.R"=[-0.5 , +0.5)+i[-0.5 , -+0.5)) which is required to be convergent. Therefore, if the algorithm functions in this zone, it is expected for the region to be shaded solid white.

VII. BKML4M: LOGARITHM MODE ITERATION

[0060] The logarithm mode described in this section may also be modified to provide a complex division with the input value. If this is to be achieved, it can only occur in parallel by creating extra registers and ensuring that equivalent operations occur in these extra registers. This contrasts with the auxiliary multiplication, where the original register could be overloaded, which cannot be achieved here because the modification of the exponentiation register in this mode would prevent convergence of the algorithm. However, using auxiliary registers can circumvent this by mirroring operations, allowing the logarithm process to, if desired, produce complex-valued division of almost arbitrarily many other complex values with the value input to this process as denominator.

[0061] Assuming the fractional part of the output logarithms to be the output, the algorithm for the domain of convergence z.sub.input.di-elect cons.R=[+0.5,+1.0)+i[(R),+(R)) is: [0062] 1. Assuming there are four basic registers, labelled (z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp). Alongside, there are two extra slave division registers (z'.sub.exp) and (z'.sub.exp) to demonstrate how the method operates when used for auxiliary complex division. The initial values of these registers are:

[0062] (z.sub.log):=(z.sub.integer output, output),

(z.sub.log):=(z.sub.integer output, output),

(z.sub.exp):=(z.sub.input)-1.0,

(z.sub.exp):=(z.sub.input), [0063] The slave division registers may also be similarly constructed with:

[0063] (z.sub.exp):=(z.sub.numerator/z.sub.integer output, input),

(z.sub.exp):=(z.sub.numerator/z.sub.integer output, input). [0064] Noting that the -1.0 is not applied to the registers (z'.sub.exp) and (z'.sub.exp). [0065] 2. Iterate through the values 0, . . . , N-1 as the index n: [0066] 3. Shift right by N-(n+3) and then truncate (z.sub.exp) to form (z.sub.exp, test) such that it has six bits; one sign bit, two integer bits and three fraction bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 0.125. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0067] 4. Shift right by N-(n+1) and then truncate (z.sub.exp) to form (z.sub.exp, test) such that it has four bits; one sign bit, two integer bits and one fraction bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 0.5. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0068] 5. Test the two values to determine d.sub.n:

[0068] ( d n ) := { + 1 , if ( z exp , test ) < 6 ' sb 111011 ( or < - 0.625 ) , - 1 , if ( z exp , test ) > 6 ' sb 000100 ( or .gtoreq. + 0.625 ) , 0 , if n either , ( d n ) := { + i , if ( z exp , test ) < 4 ' sb 1111 ( or < - 0.5 ) , - i , if ( z exp , test ) > 4 ' sb 0000 ( or .gtoreq. + 0.5 ) , 0 , if n either . ##EQU00007## [0069] 6. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0069] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( ( z exp , n - 1 ) + 1 ) = - ( sll ( 1 , F - n ) + sra ( ( z exp , n - 1 ) , n ) ) , if ( d n ) = - 1 , + 2 - n ( ( z exp , n - 1 ) + 1 ) = + ( sll ( 1 , F - n ) + sra ( ( z exp , n - 1 ) , n ) ) , if ( d n ) = + 1 , 0 , if z zero is set , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , 0 , if z zero is set , ##EQU00008## And:

( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , 0 , if z zero is set , + { - 2 - n ( ( z exp , n - 1 ) + 1 ) = - ( sll ( 1 , F - n ) + sra ( ( z exp , n - 1 ) , n ) ) , if ( d n ) = - i , + 2 - n ( ( z exp , n - 1 ) + 1 ) = + ( sll ( 1 , F - n ) + sra ( ( z exp , n - 1 ) , n ) ) , i f ( d n ) = + i , 0 , if z zero is set ##EQU00009## [0070] Do the same to any auxiliary registers such as (z'.sub.exp) and (z'.sub.exp) to apply the division process to these. However, the register will not require the correction for the 1 in the real part so instead the procedure would be:

[0070] ' ( z exp , n ) := ' ( z exp , n - 1 ) + + { - 2 - n ( z ' exp , n - 1 ) = - sra ( ( z ' exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z ' exp , n - 1 ) = + sra ( ( z ' exp , n - 1 ) , n ) , if ( d n ) = + 1 , 0 , if z zero is set , + { + 2 - n ( z ' exp , n - 1 ) = + sra ( ( z ' exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z ' exp , n - 1 ) = - sra ( ( z ' exp , n - 1 ) , n ) , if ( d n ) = + i , 0 , if z zero is set . ' ( z exp , n ) := ' ( z exp , n - 1 ) + + { - 2 - n ( z ' exp , n - 1 ) = - sra ( ( z ' exp , n - 1 ) , n ) , i f ( d n ) = - 1 , + 2 - n ( z ' exp , n - 1 ) = + sra ( ( z ' exp , n - 1 ) , n ) , i f ( d n ) = + 1 , 0 , if z zero is set , + { - 2 - n ( z ' exp , n - 1 ) = - sra ( ( z ' exp , n - 1 ) , n ) , i f ( d n ) = - i , - 2 - n ( z ' exp , n - 1 ) = + sra ( ( z ' exp , n - 1 ) , n ) , i f ( d n ) = + i , 0 , if z zero is se t ##EQU00010## [0071] 7. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0072] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2ni:

[0072] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-(sll(1,F-2n)+sra((z.sub.exp, n-1),2n)), [0073] Whereas if (d.sub.n)=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n=+2.sup.-2ni:

[0073] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+(sll(1,F-2n)+sra((z.sub.exp, n-1),2n)), [0074] wherein the signs are reversed in the latter case. [0075] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the division process to these also. Crucially, in these cases the correction for the +1 should be omitted. [0076] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2ni:

[0076] (z'.sub.exp, n):=(z'.sub.exp, n)+sra((z'.sub.exp, n-),2n),

(z'.sub.exp, n):=(z'.sub.exp, n)-sra((z'.sub.exp, n-),2n), [0077] Whereas if (d.sub.n)=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n+2.sup.-2ni:

[0077] (z'.sub.exp, n):=(z'.sub.exp, n)-sra((z'.sub.exp, n-),2n),

(z'.sub.exp, n):=(z'.sub.exp, n)+sra((z'.sub.exp, n-),2n), [0078] 8. Subtract the corresponding entry in the logarithm tables from the registers:

[0078] ( z log , n ) := ( z log , n - 1 ) - ( log 2 1 + 2 - ' d n , + log 2 1 + 2 - n d n , ) , = ( z lo g , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) , ( z log , n ) := ( z log , n - 1 ) - ( 2 arg ( 1 + 2 - n d n , ) + 2 arg ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) . ##EQU00011## [0079] This is achieved using the look-up table constructions described in the previous section by . [0080] 9. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain their final values:

[0080] (z.sub.log, N):=log.sub.2.parallel.(z.sub.input)+i(z.sub.input).parallel.,

(z.sub.log, N):=2/.pi. arg((z.sub.input)+i(z.sub.input)),

And:

(z'.sub.exp, N):=(z.sub.numerator/(z.sub.integer output, input.times.z.sub.input)),

(z'.sub.exp, N):=(z.sub.numerator/(z.sub.integer output, input.times.z.sub.input)),

[0081] Having appreciated the form of the process, it is possible to find other testing procedures that are convergent, often even in the required domain of the form of range reduction used here, by forming (z.sub.exp, test), (z.sub.exp, test) or both using different number of bits or different comparison values, although we have endeavored to reduce complexity by specifying the required value tests in the simplest known form.

[0082] An illustration of the application of this procedure to values z.sub.input.di-elect cons.R=[-2.0,+2.0)+i[-2.0,+2.0) is shown in FIGS. 2A and 2B.

[0083] FIGS. 2A and 2B show illustrations of errors in the complex plane in the exponential-to-logarithm process (floating-point implementation) for the BKML4m process. These figures correspond to illustrative tests of the iterative scheme in floating-point and with no range reduction steps to demonstrate the mathematical viability of the dynamical system rather than being a faithful reproduction of the iterative procedures outlined.

[0084] In FIG. 2A, shown is a simulation 1200A where the x-axis 1220A is real, and the y-axis 1210A is imaginary in the input to the algorithm. Shading denotes the error (where a black shading 1230A implies the error is linear related to the bits and iterations of the algorithm).

[0085] In FIG. 2B, shown is a simulation 1200B where the x-axis 1220B is real, and the y-axis 1210B is imaginary in the input to the algorithm. The white trapezoid 1230B is constructed by inverting the color and denotes the portion of the domain (z.sub.input.di-elect cons.R=[+0.5,+1.0)+i[-(R), +(R))) which is required to be convergent. Therefore, if the algorithm functions in this zone, it is expected for the region to be shaded solid white. Branch cut artifacts have been compensated for on the real line.

VIII. BKML4M: UNIFIED LOGARITHM-TO-EXPONENTIAL AND EXPONENTIAL-TO-LOGARITHM ALGORITHM

[0086] Both directions can be unified into a single algorithm that can flip direction based on a bit switch.

IX. SIMPLIFICATION OF THE CONVERGENCE TEST

[0087] The first point to note when unifying the algorithms is that the `correction` of the exponential in the exponential-to-logarithm, wherein the value is shifted so the origin is moved to zero by subtracting one, is only required by the test step. This means that the correction can be temporarily applied to the value under test on each iteration. This is further simplified by the fact that adding or subtracting high bits affects only the bits to the left of the other operand value, so a relatively large change of 1 can be made to affect only a single bit which is flipped when the exponential-to-logarithm mode is engaged via the bit switch.

X. REDUCED ENTROPY TABLE

[0088] It can be observed that:

2 tan - 1 2 - p .apprxeq. 1 2 log 2 1 + 2 - p , ##EQU00012##

therefore, at the expense of an extra operation to correct for the error, a smaller table of corrections to the value log.sub.2 1+2.sup.-p may be stored instead of a lookup table for the value

2 tan - 1 2 - p .pi. . ##EQU00013##

As the extra operation is inexpensive in logic compared to the full storage of the table, this is a way to encode operations using the fourth table storing the imaginary logarithm using reduced entropy.

XI. REDUCED BI-DIRECTIONAL BKML4M

[0089] As the logarithm BKML4m requires one extra iteration with n=0, this means that the bidirectional method also requires a zero iteration. Pulling this extra iteration out from the logarithm iteration and into the preprocessing stages generates further effects that allow for further savings in complexity and thus cost, as the zeroth iteration is the most non-linear in terms of the tests required for the iteration, so the form of the later iterations may be simplified.

XII. BI-DIRECTIONAL BKML4M DESCRIPTION

[0090] The full algorithm required, including the range reduction steps, convergence simplification, reduce entropy table and hoisted zeroth iteration is then described by: [0091] 1. Assuming there are four basic input registers, labelled (z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp), to being with these may contain d at is beyond the region of convergence of the algorithms described. Therefore, we range reduce values outside the region of convergence to allow results for all real values to be found: [0092] a. If the process is taking logarithmic input and producing exponential output, then take the rounded integer part away from the real logarithm, leaving an (z.sub.log) value in the range [-0.5, +0.5). This integer real part is to be saved for later as (z.sub.integer,log). Further, take the quadrant number out from the imaginary part, leaving only the fraction of the quadrant, (z.sub.log) again in the range [-0.5, +0.5). The quadrant number may be 0, 1, 2 or 3, but any other upper bits in the imaginary logarithm are unnecessary and are ignored. The quadrant number is also saved for later as (z.sub.integer,log). (z.sub.exp) is generally initialized to 1, although any value may be passed through from the input. Equally, the imaginary part (z.sub.exp) is generally zero. The initial value of z.sub.exp will be multiplied by the antilog (base ) of the logarithm registers. Auxiliary registers will also have the multiplication through by the input antilog (base ) applied. [0093] b. If the process is taking exponential input and producing logarithmic output, then the sign bits are first considered. The sign bits can be used to conditionally negate the values to compute absolute values of both the real and imaginary parts. By determining which of the real or imaginary part is larger in absolute value, the value may be moved via an effective complex multiplication to the quadrant wherein .parallel.(z.sub.exp).parallel.<(z.sub.exp) and (z.sub.exp)>0, while encoding the quadrant move in (z.sub.integer,log). Once completed, since the real part (z.sub.exp)>0, the leading zeroes may be counted and the bits of (z.sub.exp) (and also (z.sub.exp)) shifted up into the range such that 0.5.ltoreq.(z.sub.exp)<1, where the number of bit places moved is recorded in (z.sub.integer,log). The logarithm registers are initialized with the values in (z.sub.integer,log) and (z.sub.integer,log). Auxiliary registers will have a division through by the input applied. Preprocess the zeroth iteration of the logarithm-to-exponentiation process with the following steps: [0094] i. Initialize Boolean constants which describe whether the imaginary value is greater in magnitude than the smallest valid real part (b.sub.0:=|((z.sub.exp)|.gtoreq.0.5), and from there whether it is positive (b.sub.+:=(z.sub.exp).gtoreq.+0.5) or negative (b.sub.-:=(z.sub.exp)<-0.5). [0095] ii. If b.sub.0 is set, shift (z.sub.exp) and (z.sub.exp) right by one bit.

[0095] tmp := { + s ra ( ( z exp ) , 1 ) , if b 0 is set , ( z exp ) , otherwise , tmp := { + s ra ( ( z exp ) , 1 ) if b 0 is set , ( z exp ) , otherwise . ##EQU00014## This will effectively add one to the real part of the initial logarithm, making it one if b.sub.0 is set. [0096] iii. Compute a shift-and-add depending on the previously set Boolean constants:

[0096] ( z exp ) := t m p + { + tmp , if b + is set , - tmp , if b - is set , 0 , ot herwise , ( z exp ) := tmp + { + tmp , if b + is se t , - tmp , if b - is set , 0 , ot herwise . ##EQU00015## Which therefore rotates by 45.degree. (.pi./4) while multiplying through by the square root of two if b.sub.0 is set. [0097] iv. The square root of two change in magnitude from the previous step would denote a subtraction of the value of a half from the real part of the logarithm, making the total change a positive half. The imaginary part is also a positive or negative half from the 45.degree. (.pi./4) rotation. This yields changes to the logarithm registers which at this point are usually initialized to zero:

[0097] ( z log ) := ( z log ) + { + 1 / 2 , if b 0 is set , 0 , otherwise , ##EQU00016## ( z , log ) := ( z log ) + { + 1 / 2 , if b + is set , - 1 / 2 , if b - is set , 0 , o therwise . ##EQU00016.2## [0098] 2. Iterate through the values 1, . . . , N-1 as the index n: [0099] 3. Extract the reduced set of bits on which to conduct the tests for this iteration: [0100] a. If the process is taking logarithmic input and producing exponential output, then: [0101] i. Shift right by N-n and truncate (z.sub.log) to form (z.sub.test) such that it has three bits; one sign bit and two integer bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 1. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0102] ii. Shift right by N-(n+1) and truncate (z.sub.log) to form (z.sub.test) such that it has three bits; one sign bit, one integer bit and one fraction bit in two's complement such that the range is [-2.0,+2.0) with the smallest change being 0.5. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0103] b. If the process is taking exponential input and producing logarithmic output, then: [0104] i. Apply a subtraction of 1 from the value while testing (z.sub.exp).

[0105] Due to the range reduction enabled by the removal of the zeroth iteration, this simply means any integer bit in (z.sub.exp) is set for the purposes of testing (and therefore always causes the representation of a negative value). For computation purposes therefore:

(z.sub.tmp,exp):=(z.sub.exp)-1.0, This can be computed in line with the shift right by N-(n+1) and truncate (z.sub.exp) (or (z.sub.tmp,exp)) to form (z.sub.test) such that it has three bits; one sign bit, one integer bit and one fraction bit in two's complement such that the range is [-2.0,+2.0) with the smallest change being 0.5. The multiplication of this value by 2.sup.-n is implied by the shift. [0106] ii. Shift right by N-(n+1) and then truncate (z.sub.exp) to form (z.sub.test) such that it has three bits; one sign bit, one integer bit and one fraction bits in two's complement such that the range is [-2.0,+2.0) with the smallest change being 0.5. The multiplication of this value by 2.sup.-n is implied by the initial shift. [0107] 4. Conduct tests on the two 3-bit values (z.sub.test) and (z.sub.test) to determine d.sub.n. Eliminating any binary point metainformation--these values are signed integers from here on having a sign bit and two integer bits--the further operations may be harmonized, yielding:

[0107] :=(z.sub.test.gtoreq.1,

.sub.>:=(z.sub.test)>-1,

.sub.>:=(z.sub.test).gtoreq.+1,

.sub.>:=(z.sub.test)<-1, where finally, taking isexp as the Boolean value that denotes a process that take logarithmic input and produces exponential output when set:

( d n ) := { - 1 , i f isexp or + 1 , i f , > and isexp or , < and isexp , 0 , otherwise , ( d n ) := { - i , i f , < and isexp or , > and isexp , + i , i f , > and isexp or , < and isexp , 0 , if neither . ##EQU00017## [0108] 5. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0108] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , 0 , if z z e r o is set , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , 0 , if z z e r o is set , ##EQU00018## And:

( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , 0 , if z z e r o is set , + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , 0 , if z z e r o is set , ##EQU00019## Do the same to any auxiliary registers such as (z'.sub.exp,n-1) and (z'.sub.exp,n-1) to apply the multiplication or division process to these also. [0109] 6. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers (in some implementations, this may be replaced by a second application of the previous step if the extra serialization can be amortized into the time cost for the step). As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0110] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2n:

[0110] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n), [0111] Whereas if (d.sub.n)=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n+2.sup.-2ni:

[0111] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n), wherein the signs are reversed in the latter case. [0112] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication or division process to these also. [0113] 7. Subtract the corresponding entry in the logarithm tables from the registers:

[0113] ( z log , n ) := ( z log , n - 1 ) - ( log 2 1 + 2 - n d n , + log 2 1 + 2 - n d n , ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) , ( z log , n ) := ( z log , n - 1 ) - ( 2 / .pi.arg ( 1 + 2 - n d n , ) + 2 / .pi.arg ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) . ##EQU00020## This is achieved using the look-up table constructions described in the previous section by and for the imaginary part may be approximated by the low entropy table method in the previous section. [0114] 8. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain the final values for the fractional portion of the calculation. [0115] 9. Compute range expansion on the values present in the registers, so: [0116] a. If the process is taking logarithmic input and producing exponential output, then the quadrant number held in the integer (z.sub.integer,log) is expanded, rotating back via multiplication of the exponentiated value z.sub.exp, N by the appropriate value from {1, i, -1, -i}. If the integer part of the logarithm was not applied, either this may be applied as a bit shift, or kept as an exponent, allowing the process to emit a floating-point value. [0117] b. If the process is taking exponential input and producing logarithmic output, then if the integer part of the logarithm described by the leading zeroes count of the first step has not yet been applied, add this value.

XIII. THE BKML3DM VARIANT

[0118] A new solution was derived by choosing d.sub.n from the set of four possible values:

d n .di-elect cons. { - 1 - i + 2 - n i , - 1 + i - 2 - n i , + 1 + i + 2 - n i , + 1 - i - 2 - n i , } , ##EQU00021##

requiring only three logarithm lookup tables to obtain the logarithms (base ) for each of the four values. This results in not only fewer lookup tables but has a further side effect of reducing further the complexity of the tests required and the dependency chains for each iteration. As each relies on fewer bits for the result, they may be computed more efficiently, or multiple steps may be calculated within each clock cycle.

[0119] A drawback of this approach is that some iterations (with a seemingly functional heuristic wherein those numbered with Fibonacci numbers must be processed twice) must be repeated to achieve convergence. As the repeated iterations share the same lookup tables, it is likely these may be computed in the same step without expanding the dependencies significantly.

[0120] This approach leads to a binary choice of modifier for each real value and imaginary value at each step. Intuitively, this must be more closely approaching an optimal solution to the overall problem.

[0121] With the proposed changes, the size of the lookup tables is reduced to N discrete groups of 3N bits, with 3N.sup.2 bits overall.

XIV. LOOK-UP TABLE CONSTRUCTION

[0122] When considering the logarithm register (z.sub.log) portion of the exponentiation and logarithm iterations, it can be shown that only three lookup tables need be constructed to contain the bit patterns of the logarithms required. These are:

l n , + = log 2 1 + 2 - n + log 2 1 .+-. 2 - n i , l n , - = log 2 1 - 2 - n + log 2 1 .+-. 2 - n i , l n , = 2 .pi. tan - 1 ( 2 - n ) , ##EQU00022##

Then the logarithms to use for the addition/subtraction portion will be for each possible d.sub.n.di-elect cons.{-1-i+2.sup.-ni,-1+i-2.sup.-ni,+1+i+2.sup.-ni,+1-i-2.sup.-ni}:

((-2.sup.-n)(1-2.sup.-ni))=+-

((-2.sup.-n)(1+2.sup.-ni))=++

((+2.sup.-n)(1+2.sup.-ni))=++

((+2.sup.-n)(1-2.sup.-ni))=+-

These are then subtracted from the running total of the logarithm. In each case, the decision of the d.sub.n to use is based on the sign bit of the logarithm or the exponential with 1.0 subtracted to co-locate the origin of both logarithm-to-exponential and exponential-to-logarithm iterations. It is anticipated that using an estimation scheme may allow high-radix iterations to slice the domain into parallelized operations allowing for lower latency implementations.

XV. BKML3DM: EXPONENTIATION MODE ITERATION

[0123] Assuming the fractional part of the input logarithms to be the input, the algorithm for this method for the domain of convergence z.sub.input.di-elect cons.R=[-0.5,+0.5)+i[-0.5, +0.5) can be written for exponentiation as: [0124] 1. Assuming there are four basic registers, labelled *z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp). Alongside, there are two extra slave multiplication registers (z.sub.exp) and (z.sub.exp) to demonstrate how the method operates when used for auxiliary complex multiplication. The initial values of these registers are:

[0124] (z.sub.log):=(z.sub.input),

(z.sub.log):=(z.sub.input),

(z.sub.exp):=(z.sub.integer input, output.times.z.sub.premultiply),

(z.sub.exp):=(z.sub.integer input, output.times.z.sub.premultiply), where z.sub.premultiply:=1.0, if there are no requirements for pre-multiplication. The slave multiplication registers may also be similarly constructed with:

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply),

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply). [0125] 2. Iterate through the values 1, . . . , N as the index n, but repeating elements part of the Fibonacci sequence. These first few n would therefore be: [0126] n=1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, . . . [0127] 3. Test the sign bits of (z.sub.log,n-1) and (z.sub.log,n-1) to determine d.sub.n:

[0127] ( d n ) := { - 1 , if ( z log , n - 1 ) < 0 , + 1 , if ( z log , n - 1 ) .gtoreq. 0 , ( d n ) := { - i , if ( z log , n - 1 ) < 0 , + i , if ( z log , n - 1 ) .gtoreq. 0 , ##EQU00023## [0128] 4. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0128] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , ##EQU00024## And:

( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , ##EQU00025## [0129] Do the same to any auxiliary registers such as (z'.sub.exp,n-1) and (z'.sub.exp,n-1) to apply the multiplication process to these also. [0130] 5. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0131] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2ni:

[0131] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n), [0132] Whereas if (d.sub.n)=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n=+2.sup.-2ni:

[0132] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n), wherein the signs are reversed in the latter case. [0133] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication process to these also. [0134] 6. Subtract the corresponding entry in the logarithm tables from the registers:

[0134] ( z log , n ) := ( z log , n - 1 ) - ( log 2 1 + 2 - n d n , + log 2 1 + 2 - n d n , ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) , ( z log , n ) := ( z log , n - 1 ) - ( 2 / .pi.arg ( 1 + 2 - n d n , ) + 2 / .pi.arg ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) . ##EQU00026## [0135] This is achieved using the look-up table constructions described in the previous section by . [0136] 7. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain the final values for the fractional portion of the calculation:

[0136] (z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.(e.sup..pi./2)),

(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.(e.sup..pi./2)), And:

(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.(e.sup..pi./2)),

(z.sub.exp, N):=(z.sub.integer input, output.times.z.sub.premultiply.times.(e.sup..pi./2)),

Having appreciated the form of the process, it is easy to find other testing procedures that are convergent, although we have endeavored to reduce complexity by specifying the required domain region tests in the simplest known form.

[0137] An illustration of the application of this procedure to values z.sub.input.di-elect cons.R=[-2.0,+2.0)+i[-2.0,+2.0) is shown in FIGS. 3A and 3B.

[0138] FIGS. 3A and 3B show illustrations of errors in the complex plane in the logarithm-to-exponential process (floating-point implementation) for the BKML3dm iteration prior to the inclusion of the reduced entropy tables. These figures correspond to illustrative tests of the iterative scheme in floating-point and with no range reduction steps to demonstrate the mathematical viability of the dynamical system rather than being a faithful reproduction of the iterative procedures outlined.

[0139] In FIG. 3A, shown is a simulation 900A where the x-axis 920A is real, and the y-axis 910A is imaginary in the input to the algorithm. Shading denotes the error (where a black shading 930A implies the error is linearly related to the bits and iterations of the algorithm).

[0140] In FIG. 3B, shown is a simulation 900B where the x-axis 920B is real, and the y-axis 910B is imaginary in the input to the algorithm. The white square 930B is constructed by inverting the color and denotes the portion of the domain (z_"input" ".di-elect cons.R"=[-0.5 , -+0.5)+i[-0.5 , +0.5)) which is required to be convergent. Therefore, if the algorithm functions in this zone, it is expected for the region to be shaded solid white.

XVI. BKML3DM: LOGARITHM MODE ITERATION

[0141] Assuming the fractional part of the output logarithms to be the output, the algorithm for the domain of convergence z.sub.input.di-elect cons.R=[+0.5,+1.0)+i[-(R),+(R)) is: [0142] 1. Assuming there are four basic registers, labelled (z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp). Alongside, there are two extra slave division registers (z.sub.exp) and (z.sub.exp) to demonstrate how the method operates when used for auxiliary complex division. The initial values of these registers are:

[0142] (z.sub.log):=(z.sub.integer output, output),

(z.sub.log):=(z.sub.integer output, output),

(z.sub.exp):=(z.sub.input),

(z.sub.exp):=(z.sub.input), [0143] The slave division registers may also be similarly constructed with:

[0143] (z'.sub.exp):=(z'.sub.numerator/z.sub.integer output, input),

(z'.sub.exp):=(z'.sub.numerator/z.sub.integer output, input), [0144] 2. Iterate through the values 1, . . . , N as the index n, but repeating elements part of the Fibonacci sequence. These first few n would therefore be: [0145] n=1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, . . . [0146] 3. Test the sign bits of (z.sub.exp,n-1)-1 (where the -1 is computed by permuting the top two bits of the register) and (z.sub.exp,n-1) to determine d.sub.n:

[0146] ( d n ) := { + 1 , if ( ( z exp , n - 1 ) - 1 ) < 0 , - 1 , if ( ( z exp , n - 1 ) - 1 ) .gtoreq. 0 , ( d n . ) := { + i , if ( z exp , n - 1 ) < 0 , - i , if ( z exp , n - 1 ) .gtoreq. 0 , ##EQU00027## [0147] 4. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0147] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , ##EQU00028## And:

( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - s ra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - 1 , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + 1 , + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = - i , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) = + i , ##EQU00029## [0148] Do the same to any auxiliary registers such as (z'.sub.exp,n-1) and (z'.sub.exp,n-1) to apply the multiplication process to these also. [0149] 5. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0150] If (d.sub.n)=-1 and (d.sub.n)=+i or (d.sub.n)=+1 and (d.sub.n)=-i then 2.sup.-2n=-2.sup.-2ni:

[0150] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n), [0151] Whereas if (d.sub.n)=+1 and (d.sub.n)=+i or (d.sub.n)=-1 and (d.sub.n)=-i then 2.sup.-2n=+2.sup.-2ni:

[0151] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n), wherein the signs are reversed in the latter case. [0152] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication process to these also. [0153] 6. Subtract the corresponding entry in the logarithm tables from the registers:

[0153] ( z log , n ) := ( z log , n - 1 ) - ( log 2 1 + 2 - n d n , + log 2 1 + 2 - n d n , ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) , ( z log , n ) := ( z log , n - 1 ) - ( 2 / .pi.arg ( 1 + 2 - n d n , ) + 2 / .pi.arg ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( log ( 1 + 2 - n d n , ) + log ( 1 + 2 - n d n , ) ) , = ( z log , n - 1 ) - ( table [ d n , , n ] + table [ d n , , n ] ) . ##EQU00030## [0154] This is achieved using the look-up table constructions described in the previous section by . [0155] 7. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain their final values:

[0155] (z.sub.log, N):=log.sub.2.parallel.(z.sub.input)+i(z.sub.input).parallel.,

(z.sub.log, N):=2/.pi. arg((z.sub.input)+i(z.sub.input)), And:

(z'.sub.exp, N):=(z'.sub.numerator/(z.sub.integer output, input.times.z.sub.input)),

(z'.sub.exp, N):=(z'.sub.numerator/(z.sub.integer output, input.times.z.sub.input)),

Having appreciated the form of the process, it is possible to find other testing procedures that are convergent, even sometimes in the required domain, by forming (z.sub.exp, test), (z.sub.exp, test) or both using different number of bits or different comparison values, although we have endeavored to reduce complexity by specifying the required value tests in the simplest known form.

[0156] An illustration of the application of this procedure to values z.sub.input.di-elect cons.R=[-2.0,+2.0)+i[-2.0,+2.0) is shown in FIGS. 4A and 4B.

[0157] FIGS. 4A and 4B show illustration of errors in the complex plane in the exponential-to-logarithm process (floating-point implementation) for the BKML3dm prior to the inclusion of the reduced entropy tables. These figures correspond to illustrative tests of the iterative scheme in floating-point and with no range reduction steps to demonstrate the mathematical viability of the dynamical system rather than being a faithful reproduction of the iterative procedures outlined.

[0158] In FIG. 4A, shown is a simulation 1000A where the x-axis 1020A is real, and the y-axis 1010A is imaginary in the input to the algorithm. Shading denotes the error (where a black shading 1030A implies the error is linear related to the bits and iterations of the algorithm).

[0159] In FIG. 4B, shown is a simulation 1000B where the x-axis 1020B is real, and the y-axis 1010B is imaginary in the input to the algorithm. The white trapezoid 1030B is constructed by inverting the color and denotes the portion of the domain (z_"input" ".di-elect cons.R"=[+0.5 , +1.0)+i[-R(R) , +R(R))) which is required to be convergent. Therefore, if the algorithm functions in this zone, it is expected for the region to be shaded solid white. Branch cut artifacts have been compensated for on the real line.

XVII. BKML3DM: UNIFIED LOGARITHM-TO-EXPONENTIAL AND EXPONENTIAL-TO-LOGARITHM ALGORITHM

[0160] With only three lookup tables and four possible values of d.sub.n for both directions of the algorithm, merging these in a bi-directional algorithm can be achieved. The steps are: [0161] 1. Assuming there are four basic input registers, labelled (z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp), to being with these may contain data that is beyond the region of convergence of the algorithms described. Therefore, we range reduce values outside the region of convergence to allow results for all real values to be found: [0162] a. If the process is taking logarithmic input and producing exponential output, then take the rounded integer part away from the real logarithm, leaving an (z.sub.log) value in the range [-0.5, +0.5). This integer real part is to be saved for later as (z.sub.integer,log). Further, take the quadrant number out from the imaginary part, leaving only the fraction of the quadrant, (z.sub.log) again in the range [-0.5, +0.5). The quadrant number may be 0, 1, 2 or 3, but any other upper bits in the imaginary logarithm are unnecessary and are ignored. The quadrant number is also saved for later as (z.sub.integer,log). (z.sub.exp) is generally initialized to 1, although any value may be passed through from the input. Equally, the imaginary part (z.sub.exp) is generally zero. The initial value of z.sub.exp will be multiplied by the antilog (base ) of the logarithm registers. Auxiliary registers will also have the multiplication through by the input antilog (base ) applied. [0163] b. If the process is taking exponential input and producing logarithmic output, then the sign bits are first considered. The sign bits can be used to conditionally negate the values to compute absolute values of both the real and imaginary parts. By determining which of the real or imaginary part is larger in absolute value, the value may be moved via an effective complex multiplication to the quadrant wherein .parallel.(z.sub.exp).parallel.<(z.sub.exp) and (z.sub.exp)>0, while encoding the quadrant move in (z.sub.integer,log). Once completed, since the real part (z.sub.exp)>0, the leading zeroes may be counted and the bits of (z.sub.exp) (and also (z.sub.exp)) shifted up into the range such that 0.5.ltoreq.(z.sub.exp)<1, where the number of bit places moved is recorded in (z.sub.integer,log). The logarithm registers are initialized with the values in (z.sub.integer,log) and (z.sub.integer,log). Auxiliary registers will have a division through by the input applied. [0164] 2. Iterate through the values 1, . . . , N as the index n, but repeating elements part of the Fibonacci sequence. These first few n would therefore be: [0165] n=1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, . . . [0166] 3. Test the sign bits of the appropriate registers to determine d.sub.n. As the sign bits are themselves the set of Boolean tests, this set of tests can almost be elided by taking the exclusive OR of the sign bit with a Boolean digit true when logarithmic output is intended: [0167] a. If the process is taking logarithmic input and producing exponential output, then test the sign bits of (z.sub.log,n-1) and (z.sub.log,n-1):

[0167] ( d n ) := { - 1 , if ( z log , n - 1 ) < 0 , + 1 , if ( z log , n - 1 ) .gtoreq. 0 , ( d n . ) := { - i , if ( z log , n - 1 ) < 0 , + i , if ( z log , n - 1 ) .gtoreq. 0 , ##EQU00031## [0168] So, the computation is:

[0168] :=

:= [0169] b. If the process is taking exponential input and producing logarithmic output, then test the sign bits of (z.sub.exp,n-1)-1 (where the -1 is computed by permuting the top two bits of the register) and (z.sub.exp,n-1) to determine d.sub.n:

[0169] ( d n ) := { + 1 , if ( ( z exp , n - 1 ) - 1 ) < 0 , - 1 , if ( ( z exp , n - 1 ) - 1 ) .gtoreq. 0 , ( d n . ) := { + i , if ( z exp , n - 1 ) < 0 , - i , if ( z exp , n - 1 ) .gtoreq. 0 , ##EQU00032## [0170] So, the computation is:

[0170] :=

:= [0171] 4. Apply the shift-and-add process effecting the multiplication of the 2.sup.-n terms to the exponential registers:

[0171] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , + { + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , ##EQU00033## [0172] And:

[0172] ( z exp , n ) := ( z exp , n - 1 ) + + { - 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , + 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , + { + 2 - n ( z exp , n - 1 ) = - sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , - 2 - n ( z exp , n - 1 ) = + sra ( ( z exp , n - 1 ) , n ) , if ( d n ) , ##EQU00034## [0173] Do the same to any auxiliary registers such as (z'.sub.exp,n-1) and (z'.sub.exp,n-1) to apply the multiplication or division process to these also. [0174] 5. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2n term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0175] Wherein XOR is the logical binary operator of exclusive-or, if XOR then 2.sup.-2n=-2.sup.-2ni:

[0175] (z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n), [0176] Whereas if ( XOR ) then 2.sup.-2n=+2.sup.-2ni:

[0176] (z.sub.exp, n):=(z.sub.exp, n)-sra((z.sub.exp, n-1),2n),

(z.sub.exp, n):=(z.sub.exp, n)+sra((z.sub.exp, n-1),2n), wherein the signs are reversed in the latter case. [0177] Do the same to any auxiliary registers such as (z'.sub.exp, n) and (z'.sub.exp, n) to apply the multiplication or division process to these also. [0178] 6. Subtract the corresponding entries in the logarithm tables from the registers:

[0178] ( z log , n ) := ( z log , n - 1 ) - + { log 2 ( ( 1 - 2 - n ) 1 + 2 - 2 n ) , if ( d n ) , log 2 ( ( 1 + 2 - n ) 1 + 2 - 2 n ) , if ( d n ) , ( z log , n ) := ( z log , n - 1 ) - + { - 2 .pi. tan - 1 2 - n , if ( d n ) , + 2 .pi. tan - 1 2 - n , if ( d n ) , ##EQU00035## [0179] 7. Return to step 2 for the next iteration, until N is reached, at which point the registers will contain the final values for the fractional portion of the calculation. [0180] 8. Compute range expansion on the values present in the registers, so: [0181] a. If the process is taking logarithmic input and producing exponential output, then the quadrant number held in the integer (z.sub.integer,log) is expanded, rotating back via multiplication of the exponentiated value z.sub.exp, N by the appropriate value from {1, i, -1, -i}. If the integer part of the logarithm was not applied, either this may be applied as a bit shift, or kept as an exponent, allowing the process to emit a floating-point value. [0182] b. If the process is taking exponential input and producing logarithmic output, then if the integer part of the logarithm described by the leading zeroes count of the first step has not yet been applied, add this value.

XVIII. BKML3DM: HIGH RADIX IMPLEMENTATIONS, WITH 8-RADIX LOGARITHM-TO-EXPONENTIAL EXAMPLE

[0183] The use of sign bits to drive the possible choices of d.sub.n allows the design to scale with radix, so iterations can be conceived which produce multiple bits of result per iteration. This is because the radix-2 has few serial operations, as described in the table:

TABLE-US-00001 Radix 2 4 8 16 32 64 128 Real condition input (bits) 1 4* 6 7* 8* 9* 10* Imaginary condition input (bits) 1 3* 7 8* 9* 10* 11* Real condition output (bits) 1 2 3 4 5 6 7 Imaginary condition output (bits) 1 2 3 4 5 6 7 Parallelizable additions (logarithm terms) 1 2 3 4 5 6 7 Fully serial shift and add (serial terms) 1 2 3 4 5 6 7 Fully serial shift and add (parallel terms) 3 3 3 3 3 3 3 Fully parallel shift and add (serial terms) 1 1 1 1 1 1 1 Fully parallel shift and add (parallel terms) 3 15 63 255 1023 4095 16385

where * denote estimated values. This suggests that the conditional decision-making portion of an iteration of a radix-16 implementation may be implemented as a 9-bit input, 4-bit output multiplexer or lookup table (LUT) for the real part and an 8-bit input, 4-bit output multiplexer or lookup table (LUT) for the imaginary part. These conditional decision lookup tables are fixed for a given iteration in each direction (logarithm-to-exponential or exponential-to-logarithm) but may for optimality differ between iterations.

[0184] Further, it should be noted that a radix-16 implementation of the multiply in the exponentiation part of the iteration may have 1 serial shift-and-add section, which involves 255 parallel additions, or 2 serial shift-and-add sections which each involve the parallel addition of 15 partial terms or 4 serial shift-and-add sections which each involve 3 parallel additions of shifted terms. Each can trade off calculation dependencies for quickly growing sets of terms.

[0185] A radix-8 implementation of logarithm-to-exponential (chosen because the conditional decision lookup tables required are linear, so can be written for the general case if radix-4 behavior is acceptable due to the limitations of the extra iterations required which can be otherwise mostly overcome) for example may be described by: [0186] 1. Assuming there are four basic registers, labelled (z.sub.log), (z.sub.log), (z.sub.exp) and (z.sub.exp). Alongside, there are two extra slave multiplication registers (z.sub.exp) and (z.sub.exp) to demonstrate how the method operates when used for auxiliary complex multiplication. The initial values of these registers are:

[0186] (z.sub.log):=(z.sub.input),

(z.sub.log):=(z.sub.input),

(z.sub.log):=(z.sub.integer input, output.times.z.sub.premultiply),

(z.sub.log):=(z.sub.integer input, output.times.z.sub.premultiply), where z.sub.premultiply:=1.0, if there are no requirements for pre-multiplication. The slave multiplication registers may also be similarly constructed with:

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply),

(z'.sub.exp):=(z.sub.integer input, output.times.z'.sub.premultiply), [0187] 2. Iterate through the values 1, . . . , N as the index n, but actually use triplets of consecutive bit shift numbers: [0188] [S.sub.n,1, S.sub.n,2, S.sub.n,3].di-elect cons.{[1, 2, 3], [3, 4, 5], [5, 6, 7], [7, 8, 9], [9, 10, 11], [11, 12, 13], . . . }, [0189] 3. Extract the reduced set of bits on which to conduct the tests for this logarithm-to-exponential iteration. This is the upper 8-bits of the real part and the upper 7-bits of the imaginary part: [0190] a. Shift right by N-(S.sub.n,1+3) and truncate (z.sub.log) to form (z.sub.test) such that it has six bits; one sign bit, two integer bits and three fraction bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 0.125. The multiplication of this value by 2.sup.-S.sup.n,1 is implied by the initial shift. [0191] b. Shift right by N-(S.sub.n,1+4) and truncate (z.sub.log) to form (z.sub.test) such that it has seven bits; one sign bit, two integer bit and five fraction bits in two's complement such that the range is [-4.0,+4.0) with the smallest change being 0.0625. The multiplication of this value by 2.sup.-S.sup.n,1 is implied by the initial shift. [0192] 4. Conduct tests on the two values (z.sub.test) and (z.sub.test) to determine d.sub.n. In a production implementation of a uni- or bi-directional algorithm in either direction this may be brute forced to generated the least total error at the end of the iteration. However, for the logarithm-to-exponential iteration, the process appears largely linear, so a consistent choice can be made on that basis, yielding: [0193] a. Real part test value:

[0193] t e s t := { 7 , if ( z test ) < - 18 , 6 , if - 18 .ltoreq. ( z test ) < - 12 , 5 , if - 12 .ltoreq. ( z test ) < - 6 , 4 , if - 6 .ltoreq. ( z test ) < 0 , 3 , if 0 .ltoreq. ( z test ) < + 6 , 2 , if + 6 .ltoreq. ( z test ) < + 12 , 1 , if + 12 .ltoreq. ( z test ) < + 18 , 0 , if + 18 .ltoreq. ( z test ) , ##EQU00036## [0194] b. Imaginary part test value:

[0194] test := { 7 , if ( z test ) < - 15 , 6 , if - 15 .ltoreq. ( z test ) < - 10 , 5 , if - 10 .ltoreq. ( z test ) < - 5 , 4 , if - 5 .ltoreq. ( z test ) < 0 , 3 , if 0 .ltoreq. ( z test ) < + 5 , 2 , if + 5 .ltoreq. ( z test ) < + 10 , 1 , if + 10 .ltoreq. ( z test ) < + 15 , 0 , if + 15 .ltoreq. ( z test ) , ##EQU00037## [0195] 5. Apply the shift-and-add process effecting the multiplication of the 2.sup.-S.sup.n,1 terms to the exponential registers:

[0195] ( z exp , S n , 1 ) := ( z exp ) + + { - 2 - S n , 1 ( z exp ) = - sra ( ( z exp ) , S n , 1 ) , if 4 , + 2 - S n , 1 ( z exp ) = + sra ( ( z exp ) , S n , 1 ) , if ( test 4 ) , + { + 2 - S n , 1 ( z exp ) = + sra ( ( z exp ) , S n , 1 ) , if test 4 , - 2 - S n , 1 ( z exp ) = - sra ( ( z exp ) , S n , 1 ) , if ( test 4 ) , ##EQU00038## And:

( z exp , S n , 1 ) := ( z exp ) + + { - 2 - S n , 1 ( z exp ) = - sra ( ( z exp ) , S n , 1 ) , if 4 , + 2 - S n , 1 ( z exp ) = + sra ( ( z exp ) , S n , 1 ) , if ( 4 ) , + { - 2 - S n , 1 ( z exp ) = - sra ( ( z exp ) , S n , 1 ) , if test 4 , + 2 - S n , 1 ( z exp ) = + sra ( ( z exp ) , S n , 1 ) , if ( test 4 ) , ##EQU00039## [0196] Do the same to any auxiliary registers such as (z'.sub.exp) and (z'.sub.exp) to apply the multiplication process to these also, producing (z'.sub.exp, S.sub.n,1) and (z'.sub.exp, S.sub.n,1). [0197] 6. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2S.sup.n,1 term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0198] Wherein XOR is the logical binary operator of exclusive-or, if ({circumflex over ( )}4) XOR ({circumflex over ( )}4) then 2.sup.-2S.sup.n,1=-2.sup.-2S.sup.n,1i:

[0198] (z.sub.exp):=(z.sub.exp, S.sub.n,1)+sra((z.sub.exp, S.sub.n,1),2S.sub.n,1),

(z.sub.exp):=(z.sub.exp, S.sub.n,1)-sra((z.sub.exp, S.sub.n,1),2S.sub.n,1), [0199] Whereas if ((test{circumflex over ( )}4) XOR (test{circumflex over ( )}4)) then 2.sup.-2S.sup.n,1=+2.sup.-2S.sup.n,1i:

[0199] (z.sub.exp):=(z.sub.exp, S.sub.n,1)-sra((z.sub.exp, S.sub.n,1),2S.sub.n,1),

(z.sub.exp):=(z.sub.exp, S.sub.n,1)+sra((z.sub.exp, S.sub.n,1),2S.sub.n,1), wherein the signs are reversed in the latter case. [0200] Do the same to any auxiliary registers such as (z'.sub.exp, S.sub.n,1) and (z'.sub.exp, S.sub.n,1) to apply the multiplication or division process to these also, producing (z'.sub.exp) and (z'.sub.exp). [0201] 7. Apply the shift-and-add process effecting the multiplication of the 2.sup.-S.sup.n,2 terms to the exponential registers:

[0201] ( z exp , S n , 2 ) := ( z exp ) + + { - 2 - S n , 2 ( z exp ) = - sra ( ( z exp ) , S n , 2 ) , if 2 , + 2 - S n , 2 ( z exp ) = + sra ( ( z exp ) , S n , 2 ) , if ( test 2 ) , + { + 2 - S n , 2 ( z exp ) = + sra ( ( z exp ) , S n , 2 ) , if test 2 , - 2 - S n , 2 ( z exp ) = - sra ( ( z exp ) , S n , 2 ) , if ( test 2 ) , ##EQU00040## And:

( z exp , S n , 2 ) := ( z exp ) + + { - 2 - S n , 2 ( z exp ) = - sra ( ( z exp ) , S n , 2 ) , if 2 , + 2 - S n , 2 ( z exp ) = + sra ( ( z exp ) , S n , 2 ) , if ( 2 ) , + { - 2 - S n , 2 ( z exp ) = - sra ( ( z exp ) , S n , 2 ) , if test 2 , + 2 - S n , 2 ( z exp ) = + sra ( ( z exp ) , S n , 2 ) , if ( test 2 ) , ##EQU00041## [0202] Do the same to any auxiliary registers such as (z'.sub.exp) and (z'.sub.exp) to apply the multiplication process to these also, producing (z'.sub.exp, S.sub.n,2) and (z'.sub.exp, S.sub.n,2). [0203] 8. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2S.sup.n,2 term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0204] Wherein XOR is the logical binary operator of exclusive-or, if ({circumflex over ( )}2) XOR ({circumflex over ( )}2) then 2.sup.-2S.sup.n,2=-2.sup.-2S.sup.n,2i:

[0204] (z.sub.exp):=(z.sub.exp, S.sub.n,2)+sra((z.sub.exp, S.sub.n,2),2S.sub.n,2),

(z.sub.exp):=(z.sub.exp, S.sub.n,2)-sra((z.sub.exp, S.sub.n,2),2S.sub.n,2), [0205] Whereas if (({circumflex over ( )}2) XOR ({circumflex over ( )}2)) then 2.sup.-2S.sup.n,2=+2.sup.-2S.sup.n,2i:

[0205] (z.sub.exp):=(z.sub.exp, S.sub.n,2)-sra((z.sub.exp, S.sub.n,2),2S.sub.n,2),

(z.sub.exp):=(z.sub.exp, S.sub.n,2)+sra((z.sub.exp, S.sub.n,2),2S.sub.n,2), wherein the signs are reversed in the latter case. [0206] Do the same to any auxiliary registers such as (z'.sub.exp, S.sub.n,2) and (z'.sub.exp, S.sub.n,2) to apply the multiplication or division process to these also, producing (z'.sub.exp) and (z'.sub.exp). [0207] 9. Apply the shift-and-add process effecting the multiplication of the 2.sup.-S.sup.n,3 terms to the exponential registers:

[0207] ( z exp , S n , 3 ) := ( z exp ) + + { - 2 - S n , 3 ( z exp ) = - sra ( ( z exp ) , S n , 3 ) , if 1 , + 2 - S n , 3 ( z exp ) = + sra ( ( z exp ) , S n , 3 ) , if ( test 1 ) , + { + 2 - S n , 3 ( z exp ) = + sra ( ( z exp ) , S n , 3 ) , if test 1 , - 2 - S n , 3 ( z exp ) = - sra ( ( z exp ) , S n , 3 ) , if ( test 1 ) , ##EQU00042## And:

( z exp , S n , 3 ) := ( z exp ) + + { - 2 - S n , 3 ( z exp ) = - sra ( ( z exp ) , S n , 3 ) , if 1 , + 2 - S n , 3 ( z exp ) = + sra ( ( z exp ) , S n , 3 ) , if ( 1 ) , + { - 2 - S n , 3 ( z exp ) = - sra ( ( z exp ) , S n , 3 ) , if test 1 , + 2 - S n , 3 ( z exp ) = + sra ( ( z exp ) , S n , 3 ) , if ( test 1 ) , ##EQU00043## [0208] Do the same to any auxiliary registers such as (z'.sub.exp) and (z'.sub.exp) to apply the multiplication process to these also, producing z'.sub.exp, S.sub.n,3) and (z'.sub.exp, S.sub.n,3). [0209] 10. Apply the shift-and-add process effecting the multiplication of the 2.sup.-2S.sup.n,3 term to the exponential registers. As this is the cross-term of a real and imaginary part, it is guaranteed imaginary, so it has a more limited set of possible manifestations. [0210] Wherein XOR is the logical binary operator of exclusive-or, if ({circumflex over ( )}1) XOR ({circumflex over ( )}1) then 2.sup.-2S.sup.n,3=-2.sup.-2S.sup.n,3i:

[0210] (z.sub.exp):=(z.sub.exp, S.sub.n,3)+sra((z.sub.exp, S.sub.n,3),2S.sub.n,3),

(z.sub.exp):=(z.sub.exp, S.sub.n,3)-sra((z.sub.exp, S.sub.n,3),2S.sub.n,3), [0211] Whereas if (({circumflex over ( )}1) XOR ({circumflex over ( )}1)) then 2.sup.-2S.sup.n,3=+2.sup.-2S.sup.n,3i:

[0211] (z.sub.exp):=(z.sub.exp, S.sub.n,3)-sra((z.sub.exp, S.sub.n,3),2S.sub.n,3),

(z.sub.exp):=(z.sub.exp, S.sub.n,3)+sra((z.sub.exp, S.sub.n,3),2S.sub.n,3), wherein the signs are reversed in the latter case. [0212] Do the same to any auxiliary registers such as (z'.sub.exp, S.sub.n,3) and (z'.sub.exp, S.sub.n,3) to apply the multiplication or division process to these also, producing (z'.sub.exp) and (z'.sub.exp). [0213] 11. Subtract the corresponding entries in the logarithm tables from the registers:

[0213] ( z log ) := ( z log ) - ( + { log 2 ( ( 1 - 2 - S n , 1 ) 1 + 2 - 2 S n , 1 ) , if 4 , log 2 ( ( 1 + 2 - S n , 1 ) 1 + 2 - 2 S n , 1 ) , if ( 4 ) , + { log 2 ( ( 1 - 2 - S n , 2 ) 1 + 2 - 2 S n , 2 ) , if 2 , log 2 ( ( 1 + 2 - S n , 2 ) 1 + 2 - 2 S n , 2 ) , if ( 2 ) , + { log 2 ( ( 1 - 2 - S n , 3 ) 1 + 2 - 2 S n , 3 ) , if 1 , log 2 ( ( 1 + 2 - S n , 3 ) 1 + 2 - 2 S n , 3 ) , if ( 1 ) , ) ( z log , n ) := ( z log ) - ( + { - 2 .pi. tan - 1 2 - S n , 1 , if 4 , + 2 .pi. tan - 1 2 - S n , 1 , if 4 , + { - 2 .pi. tan - 1 2 - S n , 2 , if 2 , + 2 .pi. tan - 1 2 - S n , 2 , if 2 , + { - 2 .pi. tan - 1 2 - S n , 3 , if 1 , + 2 .pi. tan - 1 2 - S n , 3 , if 1 , ) ##EQU00044## [0214] 12. Return to step 2 for the next iteration, until N is reached and the set of step-groups are exhausted up to the required precision, at which point the registers will contain the final values for the fractional portion of the calculation. [0215] 13. Compute range expansion on the values present in the registers, so: [0216] a. If the process is taking logarithmic input and producing exponential output, then the quadrant number held in the integer (z.sub.integer,log) is expanded, rotating back via multiplication of the exponentiated value z.sub.exp by the appropriate value from {1, i, -1, -i}. If the integer part of the logarithm was not applied, either this may be applied as a bit shift, or kept as an exponent, allowing the process to emit a floating-point value. [0217] b. If the process is taking exponential input and producing logarithmic output, then if the integer part of the logarithm described by the leading zeroes count of the first step has not yet been applied to the result, add this value.

[0218] This process may be modified to accept different conditional testing tables and be extended to different radices. The multiplication approach to build the conditional testing tables in the earlier steps will not be consistent across all 2.sup.n-radix radices and iterations, but may be instead obtained through brute force, finding a combination of subsets of the input bits which in a particular pattern of cutoff values generate an ascending or descending set of 2.sup.n possible output values which taken in concert generate a lookup for the n sub-iterations that exhibits the desired convergence behavior.

XIX. CLOSING OBSERVATIONS

[0219] This disclosure has demonstrated that a reduction in the number of logarithm lookup tables, from eight values per result bit down to three or four, is possible. This is achieved by treating the real and imaginary parts as separate multiplies when looking up the logarithmic representation via the lookup tables of the logarithm values. Further, the subtraction of one present in the exponential-to-logarithm process can be merged in the conditional decision-making structure with negligible impact.

[0220] High radix functionality has been demonstrated by reducing the possible choices of shift-and-add multiplications, to the point where many simple bit switches computable at the beginning of a single high radix iteration can trigger many parallelizable logarithm subtraction and exponential multiplications, yielding an algorithm suitable for inclusion into modern high speed integrated circuitry.

XX. EXAMPLE USE CASES FOR BI-DIRECTIONAL BKML4M

[0221] It has been shown in BKML4m, which seems to be the most applicable variant of the algorithm taking in account the optimizations for reduced table size, because of the simple implementation coupled with the ability to achieve both logarithm-to-exponential and exponential-to-logarithm modes within the same design. This is useful in that it can be used to reversibly achieve micro-operations potentially dispatching per cycle without flushing and mode switching at a low area cost to complete a greater scope of macro-scale operations than is usually possible. This algorithm is only slightly more expensive than the summed cost of a real binary logarithm and CORDIC unit, but has greater flexibility than any possible implementation that involves these alone in that the operations computed by the unit may be changed on a per-result basis without pipeline flushing.

[0222] In the following, it is shown through an example micro-architecture that operations may be completed by using the given invention to efficiently complete all of the more involved arithmetic operations usually consigned to a plethora of sub-units in complex architectures.

[0223] For simplicity of illustration all registers in this example of a toy instruction set architecture are complex-valued and include an exponent (as real operations are subsets of the complex-valued operations), $r0 contains a constant read-only zero and $r1 contains a constant read-only one (1.0+0.0i). In a real implementation it is assumed that the details of the inputs and outputs are suitably multiplexed or stubbed to a more realistic register set. The mnemonic then used to call the method block (which may be any bi-directional method from the above set) is:

METHOD <in_log><in_exp><out_log><out_exp><dire- ction> where the auxiliary registers have been left out but may be optionally included for fast (and in the case of divide potentially faster) vector-scalar complex multiply and divide. It should also be noted that a non-zero <direction> yields logarithm-to-exponential, whereas a zero-direction yield exponential-to-logarithm.

[0224] Then for example:

Logarithm of $r2 in $r3:

METHOD $r0 $r2$r3 $r0 $r0

Exponential of $r2 in $r3:

METHOD $r2 $r0 $r0 $r3 $r1

[0225] Multiplication of $r2 by $r3 into $r4:

METHOD $r0 $r3 $r5 $r0 $r0

METHOD $r5 $r2 $r0 $r4 $r1

[0226] Division of $r2 by $r3 into $r4:

METHOD $r0 $r3 $r5 $r0 $r0

NEGATE $r5

METHOD $r5 $r2 $r4 $r4$r1

[0227] Square of $r2 into $r3:

METHOD $r0 $r2 $r4 $r0 $r0

SRA $r5 $r4 1

METHOD $r5 $r0 $r0 $r3 $r1

[0228] Square root of $r2 into $r3:

METHOD $r0 $r2$r4 $r0 $r0

SLA $r5 $r4 1

METHOD $r5 $r0 $r0 $r3 $r1

[0229] Multiplications and divisions may be accelerated further through the use of the vector auxiliary registers that are not included in the above. By subdividing the real, imaginary and exponent parts of the registers using packing and unpacking instructions, it can be appreciated that sine, cosine, tangent, arcsine, arccosine, arctangent, conversions between floating-point, fixed-point and integer, other base logarithms, exponentials and powers as well as conversions to degrees and radians may be computed using this system in different configurations alongside simple bitwise operations. This allows for a succinct design when many complex-valued operations are required in beam forming applications such as wireless routing, positioning systems, radar as well as applications involving acoustics and ultrasonics, or a requirement for a single efficient block for computing a high density of mathematical operations.

[0230] A bizarre quirk of this design means that many arithmetic operations have complexities that differ significantly from traditional designs. For instance, complex-valued vector-by-scalar division is the only high-level operation achievable in one call of the method that is not a logarithm or exponential. In practically all traditional systems this is the most expensive operation to perform, which should lead to a simple approach to detecting an infringing implementation within an instruction set architecture.

XXI. ADDITIONAL DISCLOSURE

[0231] 1. A system comprising: An implementation in a hardware component implementing a switchable complex-valued to-logarithm and to-exponential unit wherein; The input and output are complex valued; and Shift-and-add processes are applied to registers that effect a separable multiplication of each complex number by one added to a real value and one added to an imaginary value on each iteration. 2. The system of claim 1, wherein the logarithm and exponential processes implemented by the unit are affine logarithm and affine exponential processes. 3. The system of claim 2, wherein the relation:

2 tan - 1 2 - p .pi. .apprxeq. 1 2 log 2 1 + 2 - p , ##EQU00045##

is used to approximate the lookup value of the arctangent expression as the existing lookup value of the binary logarithm expression and a smaller delta table 4. The system of claim 2, wherein the imaginary part of the input in the affine logarithm process is tested and if less than negative a half or greater than or equal to a positive half, rotated by 45 degrees prior to the iteration 5. The system of claim 1, wherein the to-logarithm process completes a division of an auxiliary value in parallel on each completion of the method. 6. The system of claim 1, wherein the to-logarithm process conducts the iteration test on an existing register with one subtracted from it 7. A system comprising: An implementation in a hardware component implementing a switchable complex-valued to-logarithm and to-exponential unit wherein; The input and output are complex-valued and; Shift-and-add processes are applied to registers that effect a multiplication of each complex number by one added to both a non-zero real value and a non-zero imaginary value on each iteration. 8. The system of claim 7, wherein the logarithm and exponential processes implemented by the unit are affine logarithm and affine exponential processes. 9. The system of claim 7, wherein a division is computed in parallel on each completion of the method. 10. The system of claim 8, wherein the repeated steps have shifts applied in the shift-and-add that when taken together substantially follow a Fibonacci sequence.

[0232] While the foregoing descriptions disclose specific values, any other specific values may be used to achieve similar results. Further, the various features of the foregoing embodiments may be selected and combined to produce numerous variations of improved haptic systems.

XXII. CONCLUSION

[0233] In the foregoing specification, specific embodiments have been described. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present teachings.

[0234] Moreover, in this document, relational terms such as first and second, top and bottom, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. The terms "comprises," "comprising," "has", "having," "includes", "including," "contains", "containing" or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises, has, includes, contains a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element proceeded by "comprises . . . a", "has . . . a", "includes . . . a", "contains . . . a" does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that comprises, has, includes, contains the element. The terms "a" and "an" are defined as one or more unless explicitly stated otherwise herein. The terms "substantially", "essentially", "approximately", "about" or any other version thereof, are defined as being close to as understood by one of ordinary skill in the art. The term "coupled" as used herein is defined as connected, although not necessarily directly and not necessarily mechanically. A device or structure that is "configured" in a certain way is configured in at least that way but may also be configured in ways that are not listed.

[0235] The Abstract of the Disclosure is provided to allow the reader to quickly ascertain the nature of the technical disclosure. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. In addition, in the foregoing Detailed Description, various features are grouped together in various embodiments for the purpose of streamlining the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter lies in less than all features of a single disclosed embodiment. Thus, the following claims are hereby incorporated into the Detailed Description, with each claim standing on its own as a separately claimed subject matter.