Patent Description:
The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in <NUM> 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.

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, <NUM>, <NUM>, -<NUM>, i, -i, <NUM>+i, <NUM>-i, -<NUM>+i, -<NUM>-i, rather than only -<NUM> or +<NUM> 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.

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.

Previously disclosed was an approach to recast the complex exponentiation and logarithm problem from the classical manipulation r + iθ ↔ er+iθ using the BKM algorithm, to the manipulation <MAT> 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: <MAT> as well as its inverse: <MAT> wherein the real part of the logarithm has a base of <NUM> and the imaginary part has a base of <MAT>.

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 dn for each in turn, where: <MAT> and on the first of the complex values, we multiply by: <MAT> and use the logarithm of this value precomputed in a table to attenuate the second complex value.

Through repeated choices of dn 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 dn 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 dn) here eight (if the existing algorithm is expanded fully, this is five real lookups and three imaginary ones). This is a lookup size of <NUM>N over each of N stages, yielding 8N<NUM> bits dedicated to lookup tables when an implementation of the BKML algorithm is used.

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 <MAT> disclosed previously.

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.

The requirement for eight lookup tables is considered to be due to the difficulty in achieving convergence in its classical r + iθ ↔ er+iθ 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.

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.

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.

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.

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).

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 dn in a similar way to BKML from nine candidates but with notable changes in the candidate set of dn drawn from. The BKML4m algorithm requires no extra iterations over the extant previously disclosed BKML algorithm, requiring N radix-<NUM> iterations to converge.

The second, denoted BKML3dm, requires three lookup values per bit of result, has a simplified method for choosing dn from four candidates, essentially eliminating zero and on-axis dn choices. BKML3dm requires some extra iterations to achieve convergence, taking approximately N + log N radix-<NUM> 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.

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.

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 zinteger, 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.

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.

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.

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 <MAT>, 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.

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 <MAT> in size (thus in the interval <MAT>), which would if greater or equal to <NUM> require a divide-by-two and exponent increment to place into the region [<NUM>, <NUM>) in which the integer part of the exponent is completely described by the exponent of the floating-point value.

Noticing that each iteration requires that we multiply the running product by: <MAT> if we choose the real part of dn separately from the imaginary part we can choose: <MAT> <MAT> The iteration may be modified to perform the running product multiplied by the further product: <MAT> on each iteration. As a result, the diagonal dn which have both a real and an imaginary part have an extra factor of <MAT> which results in an extra shift (by <NUM>n 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.

Using dn 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 dn due to the cross terms. This can be written out as an effectively expanded table for a general dn: <MAT>.

Since the extra <NUM>-n terms in dn 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 dn 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.

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: <MAT>.

Of these four, it is also possible to reduce it to effectively three and a half via the observation: <MAT> where the preceding factor of a half may be a bit shift. By reusing table entries for <MAT>and extending to <MAT>only for even values (or producing a table of <MAT> only for even values after the other table has been exhausted) the remainder may be filled by using only half a table.

Then the logarithms to use for the addition/subtraction portion will be:
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
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.

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 dn 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 <MAT> term, which has much less effect than the other terms in the expansion of the multiplication step.

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.

Assuming the fractional part of the input logarithms to be the input, the algorithm for the domain of convergence zinput ∈ R = [-<NUM>, +<NUM>) + i[-<NUM>, +<NUM>) is:.

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 <MAT>, <MAT>) 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.

An illustration of the application of this procedure to values zinput ∈ R = [-<NUM>. <NUM>, +<NUM>) + i[-<NUM>, +<NUM>) is shown in <FIG>.

<FIG> 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.

In <FIG>, 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).

In <FIG>, 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" " R"=[ -<NUM>┤, ├ +<NUM>)+i[-<NUM>┤, ├ +<NUM>)) 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.

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.

Assuming the fractional part of the output logarithms to be the output, the algorithm for the domain of convergence zinput ∈ R = [+<NUM>, +<NUM>) + <MAT> is:.

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 <MAT> 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.

<FIG> 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.

In <FIG>, 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).

In <FIG>, 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 ( <MAT>) 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.

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

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 <NUM> can be made to affect only a single bit which is flipped when the exponential-to-logarithm mode is engaged via the bit switch.

It can be observed that: <MAT> therefore, at the expense of an extra operation to correct for the error, a smaller table of corrections to the value log<NUM> <NUM> + <NUM>-p may be stored instead of a lookup table for the value <MAT>. 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.

As the logarithm BKML4m requires one extra iteration with n = <NUM>, 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.

The full algorithm required, including the range reduction steps, convergence simplification, reduce entropy table and hoisted zeroth iteration is then described by:.

A new solution was derived by choosing dn from the set of four possible values: <MAT> requiring only three logarithm lookup tables to obtain the logarithms (base <IMG>) 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.

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.

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.

With the proposed changes, the size of the lookup tables is reduced to N discrete groups of 3N bits, with <NUM>N<NUM> bits overall.

When considering the logarithm register (zlog) 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: <MAT> <MAT> <MAT> Then the logarithms to use for the addition/subtraction portion will be for each possible dn ∈ {-<NUM> -i + <NUM>-ni, -<NUM> + i - <NUM>-ni, +<NUM> + i + <NUM>-ni, +<NUM> - i - <NUM>-ni}:
<MAT>
<MAT>
<MAT>
<MAT>
These are then subtracted from the running total of the logarithm. In each case, the decision of the dn to use is based on the sign bit of the logarithm or the exponential with <NUM> 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.

Assuming the fractional part of the input logarithms to be the input, the algorithm for this method for the domain of convergence zinput ∈ R = [-<NUM>, +<NUM>) + i [-<NUM>, +<NUM>) can be written for exponentiation as:.

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.

<FIG> 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.

In <FIG>, 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).

In <FIG>, 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" " R"=[-<NUM>┤, ├ +<NUM>)+i[-<NUM>┤, ├ +<NUM>)) 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.

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 <MAT> 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.

An illustration of the application of this procedure to values zinput ∈ R = [-<NUM>, +<NUM>) + i[- <NUM>, +<NUM>) is shown in <FIG>.

<FIG> 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.

In <FIG>, 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).

In <FIG>, 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" " R"= [+<NUM>┤, ├ +<NUM>)+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.

With only three lookup tables and four possible values of dn for both directions of the algorithm, merging these in a bi-directional algorithm can be achieved. The steps are:.

The use of sign bits to drive the possible choices of dn 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-<NUM> has few serial operations, as described in the table:.

where * denote estimated values. This suggests that the conditional decision-making portion of an iteration of a radix-<NUM> implementation may be implemented as a <NUM>-bit input, <NUM>-bit output multiplexer or lookup table (LUT) for the real part and an <NUM>-bit input, <NUM>-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.

Further, it should be noted that a radix-<NUM> implementation of the multiply in the exponentiation part of the iteration may have <NUM> serial shift-and-add section, which involves <NUM> parallel additions, or <NUM> serial shift-and-add sections which each involve the parallel addition of <NUM> partial terms or <NUM> serial shift-and-add sections which each involve <NUM> parallel additions of shifted terms. Each can trade off calculation dependencies for quickly growing sets of terms.

A radix-<NUM> 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-<NUM> behavior is acceptable due to the limitations of the extra iterations required which can be otherwise mostly overcome) for example may be described by:.

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 <NUM>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 <NUM>n possible output values which taken in concert generate a lookup for the n sub-iterations that exhibits the desired convergence behavior.

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.

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.

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.

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.

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 (<NUM> + <NUM>. 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> <direction>
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.

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.

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.

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", "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.

Claim 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 corresponding to multiplications by a value <NUM>+<NUM>-ndn are applied to values in the hardware component that effect a separable multiplication of: i) the at least one input; ii) (<NUM>+c); and (<NUM>+di);
wherein "c" is a real value and "di" is an imaginary value,
characterised in that
dn is a selected from the group: <NUM>, -<NUM>, +<NUM>, -i, +i, -<NUM>-i+<NUM>-ni, -<NUM>+i+<NUM>-ni, +<NUM>+i+<NUM>-ni, +<NUM>-i+<NUM>-ni.