The Residue Number System (RNS) offers fast and cheap carry-free integer arithmetic but has slow and expensive overflow detection. The Logarithmic Number System (LNS) offers fast real multiplication, division and powers with floating-point-like relative precision. The Residue Logarithmic Number System (RLNS) is a combination of the two systems that offers advantages for moderate-precision real applications where a-priori analysis allows under-and overflow to be ignored. An arithmetic hardware generator is essential because of the mathematical obscurity of combining RNS and LNS. Unfortunately, real applications often underflow. We consider options to deal with under-and overflow using the RLNSTool generator as a foundation.

The rounding modes of floating point arithmetic are usually simplified in implementations of alternative number systems, including the Logarithmic Number System (LNS), to a single round-to-nearest mode requiring internal guard bits that are exponentially expensive to provide. Noting that rounding takes significant time and hardware, this paper describes two innovations that enhance LNS performance, and we analyze the possible improvements for FFT, matrix inversion, and other application-specific examples where dedicated processor hardware may be preferred.The first innovation is to retain guard bit information for subsequent reuse, leading to relaxed interpolation requirements (i.e. reduced storage and potentially faster multiplication) within the usual logarithmic ALU. Further, we propose that the user may allow results to be returned without rounding, for the many applications where low latency takes priority over higher accuracy. For the sake of clarity in this investigation, a linear interpolator using cotransformation is employed, although these ideas are directly compatible with other published techniques to improve LNS system-level metrics, including higher-order interpolators. We define generalized error characteristics for this scheme, yielding zero-average-error at the cost of slight complexity in table addressing. Rather than `correctly round' all results we demonstrate that keeping the guard information can provide at least 1 bit of additional effective accuracy (two-fold improvement in r.m.s. noise) to the final result without increasing interpolation cost. The storage for interpolation coefficients is reduced to around one fifth (80% reduction) when compared to the most similar published device, with error characteristics better than minimax. To exercise the new error model and the impact of the guard field, experiments have been conducted over a range of wordlengths for important application algorithms. Here we present results for FFT and Gauss-Jordan matrix inversion. The hardware impact is assessed through synthesis targeting a contemporary entry-level FPGA, which confirms that the approach is effectively neutral from an implementation standpoint (a larger number of registers are required for our design, while fewer logic block slices are needed). The theoretical basis and experimental validation together serve to change the trade space in which such alternative arithmetic has hitherto competed.

The well-known generalization of real to complex arithmetic (two reals) extends further to more obscure quaternion arithmetic (four reals), which has applications in signal processing, aerospace, graphics and virtual reality. Quaternion multiplication implements 3D rotation, but is expensive (usually 16 floating-point multiplications and 12 additions). This paper proposes an alternative quaternion representation using logarithms to reduce multiplication cost. The real Logarithmic Number System (LNS) allows fast and inexpensive multiplication and division in embedded and FPGA-based systems. Recent advances in the Complex LNS (CLNS) have made fast log-polar complex representation affordable. Although the quaternion logarithm function is also well-defined, it is not useful to simplify multiplication (in the same way real and complex logarithms are) because quaternion multiplication is not commutative but quaternion addition is. To overcome this, we propose a novel Quaternion Complex (QCLNS) representation using a pair of CLNS numbers. This representation implements quaternion multiplication using only the theoretical minimum, of 8 LNS multipliers (i.e., fixed-point adders) and two CLNS adders. Because CLNS numbers are more compact than ordinary rectangular complex representation, single-precision QCLNS occupies 10.9 percent less memory than conventional quaternion representation. Extrapolating conventional LNS and floating-point synthesis data from Fu et al., QCLNS saves on average 10 percent of FPGA resources for precisions between 13 and 45 bits.

The real logarithmic number system, which represents a value with a sign bit and a quantized logarithm, can be generalized to create the complex logarithmic number system, which replaces the sign bit with a quantized angle in a log/polar coordinate system. Although multiplication and related operations are easy in both real and complex systems, addition and subtraction are hard, especially when interpolation is used to implement the system. Both real and complex logarithmic arithmetic benefit from the use of co-transformation, which converts an addition or subtraction from a region where interpolation is expensive to a region where it is easier. Two co-transformations that accomplish this goal are introduced. The first is an approximation based on real analysis of the subtraction logarithm. The second is based on simple algebra that applies for both real and complex values and that works for both addition and subtraction.

The real logarithmic number system, which represents a value with a sign bit and a quantized logarithm, can be generalized to create the complex logarithmic number system, which replaces the sign bit with a quantized angle in a log/polar coordinate system. Although multiplication and related operations are easy in both real and complex systems, addition and subtraction are hard, especially when interpolation is used to implement the system. Both real and complex logarithmic arithmetic benefit from the use of co-transformation, which converts an addition or subtraction from a region where interpolation is expensive to a region where it is easier. Two co-transformations that accomplish this goal are introduced. The first is an approximation based on real analysis of the subtraction logarithm. The second is based on simple algebra that applies for both real and complex values and that works for both addition and subtraction.

D.M. Lewis (ibid., vol.39, no.11, p.1325-36, Nov. 1990) recently described an architecture for performing addition and subtraction in the logarithmic number system using a Taylor series approximation and ROM tables. Here it is shown that a 25% improvement can be achieved in the table used to implement addition. This improvement is significant when Lewis' technique is used to implement variations of the logarithmic number system which do not require the subtraction logarithm.>

Various features found in standard floating point arithmetic (IEEE 754) are examined in light of their appropriateness for sign/logarithm arithmetic. The emphasis is on a 32-b word size comparable to IEEE 754 single precision, although other word sizes are possible. A multilayer sign/logarithm format is considered. The lowest layer, similar to previous implementations, would provide only normalized representations but would not provide representations for zero, denormalized values, infinities, and NaNs. The highest layer would provide most of the features found in IEEE 754, including zeros, denormalized values, infinities, and NaNs. Novel algorithms for implementing logarithmic denormalized arithmetic are presented. Simulation results show that the error characteristics of the proposed logarithmic denormalized arithmetic algorithms are similar to those of the denormalized floating point arithmetic in IEEE 754.>

A number system that offers advantages in some situations over conventional floating point and sign/logarithmic number systems is described. Redundant logarithmic arithmetic, like conventional logarithmic arithmetic, relies on table lookups to make the arithmetic unit simpler than an equivalent floating point unit. The cost of 32 bit subtraction in a redundant logarithmic number system is lower than previously published logarithmic subtraction methods. The total memory requirement for a 29-bit redundant logarithmic unit is 16 K words compared to 22 K words by the best previously published conventional sign logarithm unit, assuming similar addition techniques are employed. A redundant logarithmic number system can be implemented with online arithmetic, which would be impractical for a conventional sign logarithm number system. The disadvantages of redundant arithmetic are typical of redundant number systems. First, the redundancy doubles the storage requirements for data values. Second, the representation can become ill-conditioned, especially as a result of iterated multiplications. Third, division and square root operations are more difficult to implement in redundant logarithmic arithmetic.>

A new number system that offers advantages over conventional floating-point and sign/logarithm number systems is described. Called redundant logarithmic arithmetic, it relies, like conventional logarithmic arithmetic, on table lookups to make the arithmetic unit simpler than an equivalent floating-point unit. The cost of 32-b subtraction in a redundant logarithmic number system is lower than that of previously published logarithmic subtraction methods. Another advantage of a redundant logarithmic number system is that a single arithmetic unit can use the same hardware to add, subtract, or multiply in similar times.>

Logarithmic number systems are an attractive method of implementing high-speed digital signal-processing systems with a word size of about 14 bits. Larger word sizes pose problems because of the address limitations of the ROMs needed for logarithmic addition. M.G. Arnold (1982) gave several interpolation techniques that can double the precision, but these techniques require the use of a fixed-point multiplier. F.J. Taylor (1983) proposed a modified linear interpolation that could increase the precision by about four bits without using a multiplier. It is shown that an improvement can be made in Taylor's technique by choosing a different constant. Also, by combining one of Arnold's techniques with a variant of Taylor's modification, precision similar to that of Taylor's design can be obtained using a simpler circuit.>

A new characterization of the interior of the convex hull of a finite point set is given. An inclusion test based on this characterization is, on average, almost linear in the number of points times the dimensionality.

We adopt the following measures of clustering based on simple edge counts in an undirected loop-free graph. Let S be a subset of the points of the graph. The compactness of S is measured by the number of edges connecting points in S to other points in S. The isolation or separation of S is measured by the negative of the number of edges connecting points in S to points not in S. The subset S is a cluster if it is compact and isolated. We study the cluster search problem: find a subset S which maximizes a linear combination of the compactness and (negative) isolation edge counts. We show that a closely related decision problem is NP-complete. We develop a pruned search tree algorithm which is much faster than complete search, especially for graphs which are derived from points embedded in a space of low dimensionality.