A graphical number representation system based on the formal logic foundation of a recursively defined function is presented. The function exposes a one-to-one correspondence between the natural numbers and the set of rooted trees. Secondly, a relation between pairs of natural numbers is shown to partition the integers into disjoint finite sets each visualized as a tree in the forest of all finite trees. This relation encapsulates in visual form the natural structure and distribution of primes in a manner not previously investigated. These representations allow arithmeticians to visually experience natural numbers in a 2D graphical layout. This form is free of cultural choices such as the number of symbols in an alphabet and/or one-dimensional symbol strings. The fundamental nature of these mappings is argued to be accessible to a creative mind independent of formal schooling. This short note includes examples illustrating the simplicity of the constructions.

We investigate the problem of efficient computation of a partition of a Random Geometric Graph (RGG) into a limited number of densely packed bipartite grid subgraphs. The study focuses on the collection of subgraphs each individually having similar size and structure and the union employing most (e.g. over 85%) of the vertices. The residual vertices we seek to minimize are attributed to the inherent variations in densities of the randomly placed vertices and to any shortcomings of our greedy algorithms. RGG's have been extensively employed in recent times to model the deployment of numerous instances of Wireless Sensor Networks (WSN's). The properties investigated in our selected bipartite grid backbones are those deemed most relevant for applications to the foundations of this widely growing field. Distributed algorithms are primarily used to determine backbones. Our results review what backbone grid partitions exist in the data. This provides a metric to measure the effectiveness of any distributed algorithm against an existing optimal result. The visual display of selected backbone grids suggests local algorithm design strategies. Furthermore, these partitions must be efficiently computable for highly scalable computation, e.g. WSN's with 100's of thousands of vertices and millions of edges in the resulting RGG. We consider distributions over a segment of the plane and over the surface of the sphere to model sensor distributions both in limited planar regions, all around the globe or on distant planets.

We present an alternative linear programming formulation of the maximum concurrent flow problem (MCFP) termed the triples formulation. The standard formulations in the literature are the edge‐path and node‐edge formulations, which are known to be equivalent due to the Flow Decomposition Theorem. We present algorithms for deriving a triples solution from an edge‐path solution and vice versa, and hence show that all three formulations are equivalent. Our new formulation leads to more compact linear programs than either the edge‐path or node‐path formulations. We show that the triples formulation often has half the number of rows and half the number of columns compared to the node‐edge formulation. We report computational results comparing the solution times using the three formulations and the state‐of‐the‐art linear programming solver CPLEX on a set of popular problem instances from the literature and a set of instances defined on random geometric graphs. The results indicate that the triples formulation can be solved more efficiently than the other two. We found that the CPLEX linear programming solvers solved 89% of the MCFP instances in our computational study faster with the triples formulation than it did with the other two formulations, typically two to four times faster than the node‐edge formulation when available computer memory allowed both to be solved. The triples formulation appears to be particularly well suited for problem instances defined on dense graphs; on average, CPLEX solved these types of problems in our study 10 times faster with the triples formulation. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 68–87. 2015

We introduce a division procedure where a normalized quotient approximation is derived as a product of four independent closed form factors. Specific derivations of the method for IEEE-754 standard binary single and double precision division are developed in detail. Theoretical error bounds are derived to prove correctness for obtaining properly rounded single precision quotients by rounding the product of these four factors. The proofs include exhaustive verification for the single precision extremal cases. For double precision quotient approximations, the error bounds verify suitable accuracy so that further determination of the remainder sign is sufficient to obtain precisely rounded double precision quotients. Selected experimental results are provided to illustrate the double precision level quotient approximations. A prescaling process is introduced to reduce the table size requirements for these double precision approximations to less than 5-Kbytes.

We investigate the utilization of additive prescaling for reducing the input range for determining a divisor reciprocal approximation. In particular, we demonstrate that a single precision (24-bit) ulp accurate monotonic approximate reciprocal operation can be obtained employing three back-to-back three term additions and bipartite table lookup with total table size less than 6 Kbytes.

For a random geometric graph G(n, r) of minimum degree δ, we introduce an efficient algorithm for selecting (δ + 1) backbones with disjoint node sets that are each independent (1 − ∊) dominating sets of G. The backbone node sets are determined by a graph coloring algorithm employing only the topology (not the geometry) of G(n, r), and the backbone links are selected with link lengths in a narrow window between r and 2r and further to form a planar graph backbone. For large vertex sets (n = 1600, 3200) the resulting backbones are shown to each cover typically over 99% of the vertices of G (i.e. ∊ < 0.01), with about 30% being fully dominating, which is consistent with the 1/4 constant approximation factor algorithm proposed recently in [23] for the domatic partition problem in Unit Disk Graphs. We establish experimentally by measures of node degrees, link lengths, and interior triangular face counts that each individual backbone has most of the coverage behavior and routing convenience of the triangular “perfect packing” lattice. We further show for each sample G(n, r) that the relatively few vertices not covered by all (δ + 1) backbones are covered by most of the backbones. Hence backbone rotation in a wireless sensor network would reach all sensors (vertices) sufficiently frequently. Our novel backbone generation algorithm confirms experimentally the existence of these (δ + 1) backbones in a random geometric graph, and provides an efficient topologically based centralized algorithm for determining the backbones. We also point out that our novel backbone construction method is flexible such that any efficient coloring algorithm can be plugged into it. In this paper, we experiment with several coloring algorithms: Smallest Last, Largest First, Lexicographic, Radial Sweep and Random and we compare their respective performance. Our emphasis is, however, on SL since it offers robust properties and interesting expected behavior. We also experiment with several random node distributions: uniform, skewed and normal in both unit square and disk of which we also discuss the results.

We introduce a novel left-to-right leading digit first dual recoding of an operand for the purpose of designing the squaring operation on that operand. Our dual recoding yields an array of non-negative partial squares of size essentially one half that of a comparable multiplier partial product array for both radix-4 and radix-8 designs. For radix-8 design the 128-bit square of a 64-bit operand can be obtained from a consolidated partial square array of just 11 rows. We describe advantages of our left-to-right recoding compared to a previous right-to-left Booth-folding encoding applicable to radix-4. We also show simplifications available to the designs of a rounded floating point square operation and to a low precision approximate square.

An implementation of a radix-4 approximate squaring circuit is described employing a new operand dual recoding technique. Approximate squaring circuits have numerous applications including use in computer graphics, digital radio modules, implementation of division and function approximation in ALU circuits. The theory of operation of the circuit is described including radix-4 operand dual recoding. Our recoding yields non negative partial squares and other features which simplify the design of the approximate squaring circuit. Results of the implementation in terms of delay, power, and area in both 130 nm and 90 nm technologies are presented and analyzed. The results show the circuit is power, area and performance efficient, yielding reduction factors by three or more when compared to a truncated multiplication approach using state-of-the-art logic synthesis tools. The radix-4 squaring circuit is also shown to be more efficient than a radix-2 state-of-the-art binary squaring circuit.

We present a k-bit encoding of the k-bit binary integers based on a discrete logarithm representation. The representation supports a discrete logarithm number system (DLS) that allows integer multiplication to be reduced to addition and integer exponentiation to be reduced to multiplication. We introduce right-to-left bit serial conversion, deconversion, and unified conversion/deconversion algorithms between binary and DLS. The conversion algorithms utilize O(k) additions, do not require the use of a multiplier, and are applicable at least up to 128-bit integers. We illustrate the use of the representation in determining a novel and efficient integer power modulo 2koperation |xy|2kand compare hardware performance with a current state-of-the-art method. Furthermore, we describe properties of the conversion mappings that allow compact table lookup structures to be employed for direct conversion to and deconversion from the DLS encoding. Our lookup architecture allows 16-bit conversion and deconversion mappings to be realized with table sizes of order 2-8 Kbytes, which is up to a 64\times size reduction of the 128 Kbytes of an arbitrary 16-bits-in, 16-bits-out function table. Performance and area results that demonstrate the effectiveness of the table lookup architecture are given. The lookup methodology extends to other 16-bit integer functions such as multiplicative inverse and squaring operations.

We describe several integer function properties which in combination allow direct lookup tables to be reduced in size and structure to simpler lookup trees. Our principal result is a novel table lookup method based on a mapping of a lookup tree to a row-by-column ROM with pre and post processing logic substantially reducing the table size. Our lookup architecture allows common 16-bit integer functions such as multiplicative inverse, square, and the discrete log to be realized with table size of order 2-8 Kbytes, in comparison to the 128 Kbyte size of an arbitrary 16-bits-in 16-bits-out function table. The lookup methodology is illustrated with specific development of the 16-bit integer discrete-log function. Implementation for both unnormalized and normalized indices are synthesized into standard cell netlists and performance and area results are given that demonstrate their effectiveness.

We utilize a formal model of division for determining a testbench of p-bit (dividend, divisor) pairs whose output 2p-bit quotients have properties characterizing these instances as the most challenging for verifying any division algorithm design and implementation. Specifically, our test suites yield 2p-bit quotients where the leading p-bits traverse all or a pseudo-random sample of leading bit combinations, and the next p-bits comprise a round bit followed by (p-1) identical bits. These values are proven to be closest to the p-bit quotient rounding boundaries and shown to possess other desirable coverage properties. We introduce an efficient method of generating these testbenches. We also describe applications of these testbenches at the design simulation stage and the product evaluation stage

We introduce a right-to-left digit serial algorithm for the integer power operation xy where x and y are positive integers. For n-bit words the algorithm utilizes o(n) additions and does not require use of a multiplier. We describe a hardware implementation and evaluate the effectiveness employing a Synopsys tool set with a standard cell implementation. Out digit serial algorithm compares favorably with a popular iterative square and multiply algorithm implemented with the same tool set.

Summary form only given. The edge connectivity of a graph G = (V, E) is defined as the function, /spl lambda/: V /spl times/ V /spl rarr/ N, that associates to any pair of vertices (u, v) the maximum number of edge-disjoint paths connecting the two vertices, /spl lambda/(u, v). In this paper, we present a method for determining the function /spl lambda/(u,v) for all vertex pairs in a 4-regular graph which achieves O(|V|) running time (with a small constant factor) and O(|V|) space complexity. We show with our method that determination and traversal of an Eulerian tour of each component of the 4-regular graph along with appropriate bookkeeping is enough for determining /spl lambda/(u, v) for all pairs (u,v).

We develop the foundations for confirming monotonicity of a multi-term reciprocal function approximation. We introduce the concept of operand recoding to improve the accuracy of multipartite approximation. The results are applied to provide a proposed four-partite reciprocal implementation with total table size /spl sim/27 Kbytes, that yields an IEEE standard, single precision sized format (24 bit) reciprocal instruction, that is a one-ulp monotonic reciprocal.

We introduce an inheritance property and related table lookup structures applicable to simplified evaluation of the modular operations "multiplicative inverse", "discrete log", and "exponential residue" in the particular modulus 2/sup k/. Regarding applications, we describe an integer representation system of Benschop for transforming integer multiplications into additions which benefits from our table lookup function evaluation procedures. We focus herein on the multiplicative inverse modulo 2/sup k/ to exhibit simplifications in hardware implementations realized from the inheritance property. A table lookup structure given by a bit string that can be interpreted with reference to a binary tree is described and analyzed. Using observed symmetries, the lookup structure size is reduced allowing a novel direct lookup process for multiplicative inverses for all 16-bit odd integers to be obtained from a table of size less than two KBytes. The 16-bit multiplicative inverse operation is also applicable for providing a seed inverse for obtaining 32/64-bit multiplicative inverses by one/two iterations of a known quadratic refinement algorithm.

For progressively higher radices, the reduction in partial products obtained by the well-known modified Booth multiplier recoding is offset by the need to precompute a rapidly increasing store of odd multiples of the multiplicand as inputs to each partial product generator (PPG). We propose secondary radix multiplier recoding schemes reducing the number of odd multiples required in the store for very high radix recodings (e.g., radix 2/sup r/ for 5 /spl les/ r /spl les/ 16). The proposed recoding schemes allow reduction of the number of partial products in the implementation by factors between and beyond the reduction factors of 2, 3, and 4 that can be achieved by traditional Booth recodings to radices 4, 8, and 16, respectively. We develop the theory of these recodings and provide methodology for secondary radix selection. Finally, we summarize latency and cost evaluations of selected implementations indicating potential cost and performance/cost advantages for practical operand sizes.

We describe a high radix integer division algorithm where the divisor is prescaled and the quotient is postscaled without modifying the dividend to obtain an identity N=Q/sup *//spl times/D+R/sup */ with the quotient Q/sup */ differing from the desired integer quotient Q only in its lowest order high radix digit. Here the "oversized" partial remainder R/sup */ is bounded by the scaled divisor with at most one additional high radix digit selection needed to reduce the partial remainder and augment the quotient to obtain the desired integer division result N=Q/spl times/D+R with 0/spl les/R/spl les/D-1. We present a high radix multiplicative version of this algorithm where a k/spl times/p digit base /spl beta/ rectangular aspect ratio multiplier allows quotient digit selection in radix /spl beta//sup k-1/ with a cost of only one k/spl times/p digit multiply per high radix digit, plus the fixed pre- and post-scaling operation costs. We also present a Booth radix 4 additive version of this algorithm where appropriately compressed representation of the partial remainder with Booth digits {-2, -1, 0, 1, 2} allows successive quotient digit selection from the leading partial remainder digit without the iterative table lookups required in SRT division.

Many function approximation procedures can obtain enhanced accuracy by an efficient table lookup of a product z=f(x)g(y). Both x and y are represented by indices of i leading bits (typically 7<i<16) for arguments normalized to [0, 1] or [1, 2]. Direct bipartite lookup employs 1/2 bits each of x and y yielding roughly an 1/2 bit result which can lose 2 to 3 bits of accuracy when f and g are nonlinear. Indirect bipartite lookup first generates i/2 bit interval index values for f(x) and g(y) using separate j-bits-in 1/2bits-out tables for f(x) and g(y) where i/2<j

Postscaled division is a non-iterative algorithm delivering a quotient of single precision accuracy by the three term product (xy/spl circ/)c and of double precision accuracy by the formula [(xy/spl circ/)c][2-(yy/spl circ/)c]. Here x is the dividend, y/spl circ/ is a low order part complemented form of the divisor y, and c is a table lookup value approximating a "reciprocal function" 1/(yy/spl circ/) to a precision of over 27 bits. Table lookup latency is hidden by performing the lookup in parallel with the first multiplication (xy/spl circ/), with the second multiplication the "postscaling" by the lookup function value. Our contribution is the description of two new lookup algorithms for approximating the reciprocal function 1/yy/spl circ/ to high accuracy in fewer cycles than a typical floating point multiply latency. Our indirect bipartite lookup procedure has a latency of two successive lookups followed by a small integer addition. This first algorithm generates a 27 bit approximation of 1/yy/spl circ/ with total table size about 5 Kbytes. Our second lookup algorithm generates a 34 bit approximation with latency determined by 11 and 12 bit table lookups and a 4-1 addition. This second approximation employs some 20 Kbytes of tables to allow for a double extended precision division result in the same number of cycles as a double precision result.

We investigate two sets of hard to round p/spl times/p bit fractions arising from division of a normalized p bit floating point dividend by a normalized p bit floating point divisor. These sets are characterized by the p/spl times/p bit fraction's quotient bit string, beginning with or just after the round bit, having the maximum number (p-1) of repeating like bits, specifically 00...01 or 11...10 for the directed rounding "RD-hard" set and 100...01 or 11...10 for the round-to-nearest "RN/sub -/hard" set. We show both the p/spl times/p bit RD-hard and RN-hard sets to be of size at least 2/sup p-2/ and at most 2/sup p-1/. Two dimensional quotient vs. divisor plots empirically reveal both the RD-hard and RN-hard sets of p/spl times/p bit fractions to be jointly widely distributed. Analysis of patterns and linear sequences of fractions visible in the quotient vs. divisor plots leads to simplified procedures for generating test suites of hard to round fractions. Our strongest computational result is the derivation of formulas that allow 2/sup (p/2)+O(1)/ RD-hard and RN-hard p/spl times/p bit fractions to be enumerated based on sequential incrementation of respective numerators and denominators.

Multipliers are used at many different places in microprocessor design. As the non-memory sub-blocks of the microprocessor with the largest size and delay, multipliers have a big impact on the cycle time of the microprocessor. Targeting deeper pipelines and higher clock frequencies, there is a growing demand for multiplier designs that can be split into shorter stages. For this purpose, the use of Booth recoding has been a popular method to cut down the number of partial products in a multiplier to reduce the delay of the partial product accumulation and to simplify the partition of the multiplier into several shorter stages. The complexity to pre-compute an increasing number of digit multiples of the multiplicand within the multiplier unit limits the use of Booth recoding mainly to radices 4 and 8. We propose novel encoding schemes for the implementation of higher radix multiplication. In particular we consider multiplication radix-32 and radix-256. The features provide more flexible multiplier designs that can be implemented in shorter pipeline stages. We compare the proposed designs with multipliers that use traditional Booth recoding.

We investigate two sets of hard to round p/spl times/p bit fractions arising from division of a normalized p bit floating point dividend by a normalized p bit floating point divisor. These sets can be characterized by the p/spl times/p bit fraction's quotient bit string, beginning with or just after the round bit, having the maximum number (p-1) of repeating like bits, specifically 00...01 or 11:..10 for the directed rounding "RD-hard" set and 100...01 or 011...10 for the round-to-nearest "RN-hard" set. We describe an algorithm for generating both the RD-hard and RN-hard sets in order of quotient value for any p, and use properties of fractions and continued fractions to characterize the distribution of these sets based on numerator, denominator, and quotient values. As a practical chip test example we summarize test runs showing our hard to round test suites are several orders of magnitude more efficient than random testing in finding erroneous quotients computed by the 1993 Pentium Processor having the well known fdiv flaw.

Past recorders have added critical path delay for the more frequent case where both inputs are non redundant. Our proposed circuit does not lengthen the time of one multiplication compared to the state-of-the-art encoding, if both inputs are non redundant. We have slightly modified an existing cell to accept a redundant binary number in place of the non redundant number by changing some connections. The recoding operators associated with a high level quantity (the fraction range) all defined in this paper are used to rule out some possibilities as inputs of this newly created cell. We check that the modified cell yields the correct output for the remaining possible inputs.

The aim of this paper is to accelerate division, square root, and square root reciprocal computations when the Goldschmidt method is used on a pipelined multiplier. This is done by replacing the last iteration by the addition of a correcting term that can be looked up during the early iterations. We describe several variants of the Goldschmidt algorithm, assuming 4-cycle pipelined multiplier, and discuss obtained number of cycles and error achieved. Extensions to other than 4-cycle multipliers are given. If we call G/sub m/ the Goldschmidt algorithm with m iterations, our variants allow us to reach an accuracy that is between that of G/sub 3/ and that of G/sub 4/, with a number of cycle equal to that of G/sub 3/.

This paper presents a floating-point addition algorithm and adder pipeline design employing a packet forwarding pipeline paradigm. The packet forwarding format and the proposed algorithms constitute a new paradigm for handling data hazards in deeply pipelined floating-point pipelines. The addition and rounding algorithms employ a four stage execution phase pipeline with each stage suitable for implementation in a short clock period, assuming about 15 logic levels per cycle. The first two cycles are related to addition proper and are the focus of this paper. The last two cycles perform the rounding and have been covered in a paper by D.W. Matula and A.M. Nielsen (1997). The addition algorithm accepts one operand in a standard binary floating-point formal at the start of cycle one. The second operand is represented in the packet forwarding floating-point format: namely, it is divided into four parts: the sign bit, the exponent string, the principal part of the significant, and the carry-round packet. The first three parts of the second operand are input at the start of cycle one and the carry-round packet is input at the start of cycle two. The result is output in two formats that both represent the rounded result as required by the IEEE 754 standard. The result is output in the packet forwarding floating-point format at the end of cycles two and three to allow forwarding with an effective latency of two cycles. The result is also format at the end of cycle four for retirement to a register. The packet forwarding result is thus available with an effective two cycle latency for forwarding to the start of the adder pipeline or to a cooperating multiplier pipeline accepting a packet forwarding operand. The effective latency of the proposed design is two cycles for successive dependent operations while perceiving IEEE 754 binary floating-point compatibility.

Quotients, reciprocals, square roots and square root reciprocals all have the property that infinitely precise p-bit rounded results for p-bit input operands can be obtained from approximate results of bounded accuracy. We investigate lower bounds on the number of bits of an approximation accurate to a unit in the last place sufficient to guarantee that correct round and sticky bits can be determined. Known lower bounds for quotients and square roots are given and/or sharpened, and a new lower bound for root reciprocals is proved. Specifically for reciprocals, quotients and square roots, tight bounds of order 2p+O(1) are presented. For infinitely precise rounding of the root reciprocal, a lower bound can be found at 3p+O(1), but exhaustive testing for small sizes of the operand suggests that in practice (2+/spl epsiv/)p for small /spl epsiv/ is usually sufficient. Algorithms can be designed for obtaining the round and sticky bits based on the bit pattern of an approximation computed to the required accuracy. We show that some improvement of the known lower bound for reciprocals and division is achievable at the cost of somewhat more complex hardware for rounding. Tests for the exactness of the quotient and square root are also provided.

This paper describes a graphical user interface propelled by a simulation engine for performance analysis of a channel assignment model for high-volume cellular networks. It also discusses some experimental results.

Infinite planar cellular networks are embedded on a torus to obtain a symmetric regular finite network sample region for performance analysis. We show that a "hexagonal wrap" toroidal embedding preserves translational and rotational symmetry on all three axes of a hexagonal lattice and is preferable to a "Cartesian wrap" embedding. Hexagonal tilings and embeddings are obtained for all rhombic tile sizes. Certain tilings are shown to provide modular based neighbor addressing schemes that simplify distributed channel assignment algorithms. Hierarchical "hexagons within a hexagon" tilings are illustrated with the large hexagon exhibiting the sample repeat and comprising a multiplicity of channel frequency repeat small hexagonal the clusters. The symmetric hexagonal sample region repeat embeddings are noted to be useful for probabilistic analysis of high utilization channel assignment performance both theoretically and by simulation.

The paper presents the foundations for a packet forwarding floating point format and the design of a rounder ensuring compatibility between packet forwarding format and the standard binary IEEE 754 floating point format. The packet forwarding format and related addition and multiplication algorithms described in this series propose a new ALU pipeline paradigm for handling data hazards in pipelined floating point operations. The execution phases for the adder and multiplier packet forwarding pipelines are illustrated by a proposed implementation having four stages. The latter two stages in each pipeline employ the rounder described herein. The stages of the execution phase are intended to map to logic designs, with only some fifteen logic levels per stage allowing stages to be mapped to reasonably short cycles. The packet forwarding format provides for input and output in packet format with only two cycle effective latency between cooperating adder and multiplier pipelines. The designs we propose cut the effective latency in half and reduce the stall cycles by a factor of three compared to conventional forwarding pipelines processing data dependent operations. The speedup is realized, with preservation of IEEE 754 binary floating point compatibility.

For pt.I see ibid., p.140-7 (1997). The paper presents a floating point addition algorithm and adder pipeline design employing a packet forwarding pipeline paradigm. The packet forwarding format and the proposed algorithms constitute a new paradigm for handling data hazards in deeply pipelined floating point pipelines. The addition algorithm employs a four stage execution phase pipeline with each stage suitable for implementation in a short clock period, assuming about fifteen logic levels per cycle. The first two cycles are related to addition proper and are the principal focus of the paper. The last two cycles perform the rounding. The addition algorithm accepts one operand in a standard binary floating point format at the start of cycle one. Packets comprising the other operand in our packet forwarding floating point format are input at the start of cycles one and two. Output of the result occurs in the packet format after cycles two and three with the format representing a floating point value equal to the standard IEEE 754 rounded result. The same result in a standard binary floating point format is available after cycle four for retirement to a register. The packet forwarding result is thus available with an effective two cycle latency for forwarding to the start of the adder pipeline or to a cooperating multiplier pipeline accepting a packet forwarding operand. The effective latency of the proposed design is two cycles for successive dependent operations while preserving IEEE 754 binary floating point compatibility.

Describes a table compression method employing finite-precision linear interpolation in reciprocal tables. The interpolation method employs a compressed look-up table and a small-sized multiplier to yield an output reciprocal as a simple direct operation. The leading bits of the arbitrarily precise input are used to index the table, and a limited number of succeeding fractional bits are used to interpolate on the table employing a multiply/add operation. The low-order bits of the product are rounded off so that the output reciprocals are guaranteed to be correct to a unit in the last place and provide a round-to-nearest reciprocal for over 90% of arbitrarily precise input arguments. The interpolation method generates 2k-bit faithful reciprocals employing a k-bits-in, (2k+2)-bits-out table and a (k+3)/spl times/(k+3)-bit multiplier. A single-precision faithful reciprocal can be generated employing a table of size 13 kBytes and a 15/spl times/15-bit multiplier, compared to a table size of 46 MBytes for conventional reciprocal tables. The table and dedicated small multiplier efficiently characterize a functional reciprocator unit with, at most, a 2-cycle latency.

The dot product operation is very prevalent in scientific computation and has therefore been incorporated as a primitive operation in some languages. The implementation of the dot product operation by a sequence of IEEE standard multiplications and additions does not prevent a substantial accumulation of the round-off errors or warn the user about a catastrophic cancellation. We present the design of a double precision dot product operation employing sticky accumulation, where the final rounded result is validated by raising a new exception flag if the result incurred catastrophic cancellation. Sticky accumulation can be implemented in a pipeline or parallel environment to sustain double precision with an extended control of the error. Our design allows that, in the absence of catastrophic cancellation, one ulp accuracy is guaranteed.

We investigate the efficiencies attainable pursuing Booth recoding directly from redundant binary input with limited carry propagation. As a digit conversion problem we extend the important result that each radix 4 Booth recoded digit can be determined from 5 consecutive input signed bits to obtain that each radix 2/sup k/ Booth recoded digit can be determined from 2k+1 consecutive input signed bits and prove this to be the minimum possible for any k/spl ges/2. Analysis of alternative bit pair encodings of signed bits yields the improved result that each radix 2/sup k/ Booth recoded digit can be determined from only 2k encoded bit pairs employing sign and magnitude bit encoding, a result which does not extend to conventional borrow-save or carry-save redundant binary digit encodings. Radices 4 and 8 gate level designs are illustrated for alternative encodings, with our signed bit design shown to yield smaller depth and fewer gates than existing redundant binary Booth recoding circuits from the literature.>

We describe bipartite reciprocal tables that employ separate table lookup of the positive and negative portions of a borrow-save reciprocal value. The fusion of the parts includes a rounding so the output reciprocals are guaranteed correct to a unit in the last place, and typically provide a round-to-nearest reciprocal for over 90% of input arguments. The output rounding can be accomplished in conjunction with multiplier recoding yielding practically no cost in logic complexity or time in employing bipartite tables. We demonstrate these tables to be 2 to 4 times smaller than conventional 4-bit reciprocal tables. For 10-16 bit reciprocal table lookup the compression grows from a factor of 4 to over 16, making possible the use of larger seed reciprocals than previously considered cost effective.>

We prove that a convenient ROM reciprocal table construction algorithm generates tables that minimize the relative error. The worst case relative errors realized for such optimally computed k-bits-in, m-bits-out ROM reciprocal tables are then determined for all table sizes 3/spl les/k,m/spl les/12. We next prove the table construction algorithm always generates a k-bits-in, k-bits-out table with relative errors never any greater than 3/4 2/sup -k/, and more generally with g guard bits that for (k+g)-bits-out the relative error is never any greater than 2-(k+1)(1+1/(2g+1)). To provide for determining extreme case test data and to compute the precision of a reciprocal table without prior construction of the full ROM reciprocal table, we describe a procedure that requires generation and inspection of only a small portion of such a table to identify input values guaranteed to include the worst case relative errors in the table.>

The authors describe a numeric processor with a kernel that is a tree of redundant binary adders and effects either a 17 /spl times/ 69-b multiply-and-add or a 19 /spl times/ 69-b multiply with exact redundant binary output and single cycle latency. Feedback paths selectively allow a high-order or low-order part of the adder tree output to be fed back in redundant binary form to the multiplicand and/or addend inputs to the adder tree. The authors describe algorithms iteratively using this adder tree kernel for IEEE double extended multiplication, division, and square root; conversions between 18-digit BCD integers and 64-b binary integers; and transcendental function evaluation. The multiplier design described was implemented in the Cyrix 83D87 numeric coprocessor (typically 33 MHz). Results for this coprocessor as compared with competitive x87 units are included.>

A double precision dot product operation is designed in which the final rounded result is validated by raising exception flags if either the result incurs catastrophic cancellation or the result is not accurate to one unit in the last place (ulp). The design guarantees one ulp accuracy in the absence of catastrophic cancellation. The user can thus obtain validated results at marginal extra cost with the ability to trap to alternative routines in those cases where the results are suspicious.>

It is proved that a conventional ROM reciprocal table construction algorithm generates tables that minimize the relative error. The worst case relative errors realized for such optimally computed k-bits-in, m-bits-out ROM reciprocal tables are then determined for all table sizes 3 /spl les/ k, m /spl les/ 12. It is then proved that the table construction algorithm always generates a k-bits-in, k-bits-out table with relative errors never any greater than 3(2/sup -k/)/4 for any k, and, more generally with g guard bits, that for (k + g)-bits-out the relative error is never any greater than 2/sup -(k+1)/(1 + 1/(2/sup g+1/)). To provide for determining test data without prior construction of a full ROM reciprocal table, a procedure that requires generation and searching of only a small portion of such a table to determine regions containing input data yielding the worst case relative errors is described.>

Semantics are given for the four elementary arithmetic operations and the square root, to characterize what are termed exact floating point operations. The operands of the arithmetic operations and the argument of the square root are all floating point numbers in one format. In every case, the result is a pair of floating point numbers in the same format with no accuracy lost in the computation. These semantics make it possible to realize the following principle: it shall be a user option to discard any information in the result of a floating point arithmetic operation. The reliability and portability previously associated with only mathematical software implementations in integer arithmetic can thus be attained exploiting the generally higher efficiency of floating point hardware.>

An efficient implementation of the Euclidean GCD (greatest common divisor) algorithm employing the redundant binary number system is described. The time complexity is O(n), utilizing O(n)4-2 signed 1-b adders to determine the GCD of two n-b integers. The process is similar to that used in SRT division. The efficiency of the algorithm is competitive, to within a small factor, with floating point division in terms of the number of shift and add/subtract operations. The novelty of the algorithm is based on properties derived from the proposed scheme of normalization of signed bit fractions. The implementation is well suited for systolic hardware design.>

The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of entities can send and receive flow concurrently. The ratio of the flow supplied between a pair of entities to the predefined demand for that pair is called throughput and must be the same for all pairs of entities for a concurrent flow. The MCFP objective is to maximize the throughput, subject to the capacity constraints. We develop a fully polynomial-time approximation scheme for the MCFP for the case of arbitrary demands and uniform capacity. Computational results are presented. It is shown that the problem of associating costs (distances) to the edges so as to maximize the minimum-cost of routing the concurrent flow is the dual of the MCFP. A path-cut type duality theorem to expose the combinatorial structure of the MCFP is also derived. Our duality theorems are proved constructively for arbitrary demands and uniform capacity using the algorithm. Applications include packet-switched networks [1, 4, 8], and cluster analysis [16].

The authors introduce a redundant binary representation of the rationals and an associated algorithm for computing the sum, difference, product, quotient, and other useful functions of two rational operands, using this representation. The algorithm extends R.W. Gosper's (1972) partial quotient arithmetic algorithm and allows the design of an online arithmetic unit with computations granularized at the signed bit level. Each input or output port can be independently set to receive/produce operands/result in either binary radix or the binary rational representation. The authors investigate by simulation the interconnection of several such units for the parallel computation of more complicated expressions in a tree-pipelined manner, with particular regard to measuring individual and compounded online delays.>

The authors develop and analyze a redundant continued-fraction representation of the rationals in the implementation of an arithmetic unit for computing the sum, difference, product, quotient, and other useful functions of two rational operands. Their representation of operands and results allows the computations of the unit to be performed in a signed bit-serial, online fashion. Several such units can then be interconnected for the computation of more complicated expressions in a pipelined manner. Redundancy is used to help achieve a small bounded online delay and uniform throughput.>

We describe a binary implementation of an algorithm of Gosper to compute the sum, difference, product, quotient and certain rational functions of two rational operands applicable to integrated approximate and exact rational computation. The arithmetic unit we propose is an eight register computation cell with bit serial input and output employing the binary lexicographic continued fraction (LCF) representation of the rational operands. The operands and results are processed in a most-significant-bit first on-line fashion with bit level logic leading to less delay in the computation cell when compared to operation on the full partial quotients of the standard continued fraction representation. Minimization of delay is investigated with the aim of supporting greater throughput in cascaded parallel computation with such computation cells.

We describe an algorithm that determines the edge connectivity of an n-vertex m-edge graph G in O(nm) time. A refinement shows that the question as to whether a graph is k-edge connected can be determined in O(kn2). For dense graphs characterized by m = Ω(n2), the latter result implies that determination of whether a graph is k-edge connected for any fixed k can be accomplished in time linear in input size.

Lexicographic continued fraction binary (LCF) representation provides an order preserving bitstring representation of the non negative real numbers where every rational number has a finite length bitstring representation. We investigate the precision of k-bit LCF approximation. The maximum gap size over [0,1] for (k+1)-bit LCF representation is shown to be less than 2−.81k, comparable to binary coded decimal in worst case representation efficiency. The distribution of gap sizes for (k+1)-bit LCF representation over [0,1] is shown on a logarithmic scale to be bell shaped between 2−.81kand 2−1.39k, becoming more peaked near the value corresponding to uniform spacing, 2−k, with increasing k.

Fraction number systems characterized by fixed-slash and floating-slash formats are specified. The structure of arithmetic over such systems is prescribed by the rounding obtained from "best rational approximation." Multitiered precision hierarchies of both the fixed-slash and floating-slash type are described and analyzed with regards to their support of both exact rational and approximate real computation.

We describe a new binary encoding for numbers termed lexicographic continued fraction (LCF) representation that provides a one-to-one order preserving finite bit string representation for every rational. Conversion either way between binary integer numerator-denominator pair representation and LCF representation is shown feasible in time linear with bit string length, given registers of length sufficient to hold the numerator and denominator. LCF bit string length is about 2 max{log2p, log2q} for the irreducible fraction p/q. Realization of arithmetic (+, −, ×, ÷ on LCF bit string encoded operands is shown feasible. Some relations between the theory of best rational approximation and the values represented by truncated LCF bit strings are noted to assess the feasibility of a finite precision arithmetic based on LCF representation.

Smallest-last vertex ordering and prlonty search are utdlzed to show for any graph G = (IT, E) that the set of all connected subgraphs maxunal with respect to their minimum degree can be determined in O(I EI + I VI) time and 21El + O(I VI) space It is further noted that the smallest-last graph coloring algonthrn can be unplemented in O(I E I + I V[) tune, and particularly effective aspects of the resulting coloring are discussed.

The foundations of an arithmetic unit performing the add, subtract, multiply, and divide operations on rational operands are developed. The unit uses the classical Euclidean algorithm as one unified algorithm for all the arithmetic operations, including rounding. Binary implementations are discussed, based on techniques known from SRT division, and utilizing ripple-free borrow-save and carry-save addition. Average time behavior is investigated.

A fimte set of integer digits D with 0 E D is basic for base 13 ff the set of polynomials ~[D] contains a umque P E ~[D] with P(fl) = i for every mteger t Necessary and sufficient conditions are given for D to be basic for ft.Efficient procedures are exhibited for verifying that D is basic for fl and for computing the P E ~[D] such that P(fl) = i for any l.For digit values in excess ofth© base, it is shown that an infLmte class of basle dtgit sets exists for every base fl with [fl[ >_ 3. Infinite precision radix representations are shown to eXLSt for every real number when D is basic for d, and the inherent redundancy of infinite precision representation is investigated.

Based on the classical Euclidian Algorithm, we develop the foundations of an arithmetic unit performing Add, Subtract, Multiply and Divide on rational operands. The unit uses one unified algorithm for all operations, including rounding. A binary implementation, based on techniques known from the SRT division, is described. Finally, a hardware implementation using ripple-free, carry-save addition is analyzed, and adapted to a floating-slash representation of the rational operands.

An investigation of the feasibility of a finite precision approximate rational arithmetic based on fixed-slash representation of rational numbers is presented. Worst-case and average-case complexity analyses of the involved rounding algorithm (an extended shift-subtract gcd algorithm) are presented. The results are applied to a proposed hardware realization of a fixed-slash arithmetic unit.

Let Z denote the set of integers. A digit set D ⊂ Z is basic for base β ϵ Z if the set of polynomials {dmβm+ dm-1+ ... + d1β+d0| dIϵ D} contains a unique representation for every n ε Z. We give necessary and sufficient conditions for D to be basic for β. We exhibit efficient procedures for verifying that D is basic for β, and for computing the representation of any n ε Z when a representation exists. There exist D, & with D basic for β where max {|d| | d ϵ D} >; |β|, and more generally, an infinite class of basic digit sets is shown to exist for every base β with |β| ≥ 3. The natural extension to infinite precision radix representation using basic digit sets is considered and a summary of results is presented.

Design and analysis of finite precision rational number systems based on fixed-slash and floating-slash representation is pursued. Natural formats for binary fixed-slash and binary floating-slash number representation in computer words are described. Compatibility with standard integer representation is obtained. Redundancy in the' representation is shown to be minimal. Arithmetic register requirements are considered. Worst case and average case rounding errors are determined, and the concept of adaptive variable precision in the rounding is developed.

We are concerned in this paper with the representation of an integer in a (multiple-modulus) residue number system and, in particular, with an algorithm for changing the base vector of the residue number system. Szabo and Tanaka [1, p.47] describe such an algorithm when each modulus of the second base vector is relatively prime to each modulus of the first base vector. However, we show that a much simpler algorithm exists if we allow the moduli of the second base vector to have factors in common with the moduli of the first base vector (even though the moduli of the second base vector are pairwise relatively prime among themselves). Since the algorithm involves the use of "associated" residue and mixed-radix representations for integers, Section 2 contains an elementary survey of the terminology, notation, and theory behind these two types of representation. Section 3 contains the proofs of the basic theorems upon which our algorithm for residue base conversion is based along with a description of the algorithm. It also contains illustrative examples which demonstrate the power of the algorithm. In this paper we lay the foundation for a subsequent paper in which we propose procedures for extending single-precision residue arithmetic to multiple-precision residue arithmetic.

A finite precision rational number system provides for representation of a collection of rational numbers subject to limitations on numerator and denominator magnitude. In fixed-point and floatingpoint radix number systems only rationals of the form i/βj, where β is the base, can be realized. In contrast, a finite precision rational number system will allow representation of practically all simple fractions encountered in applications. In this preliminary report we first propose two types of finite precision rational number systems which we term fixed-slash and floating-slash systems [2]. We then consider the conversion (rounding) problem, that is, the determination of a number satisfying the numerator and denominator constraints approximating a given non representable real value. We show that the rounding problem is solvable by an efficient procedure, which we term mediant conversion, that derives from the theory of continued fractions.

The accumulated roundoff error incurred in long arithmetic computations involving a randomized mixture of addition, subtraction, multiplication, and division operations applied to an initial randomly generated data base is studied via simulation. Truncated and rounded floating-point arithmetic and truncated and rounded logarithmic arithmetic are simultaneously utilized for each of the computation sequences and the resulting roundoff error accumulations for these four systems are compared. The nature of the correlated errors incurred under various arithmetic operator mixes are discussed.

The accumulated round-off error incurred in long arithmetic computations involving a randomized mixture of addition, subtraction, multiplication and division operations applied to an initial randomly generated data base is studied via simulation. Truncated and rounded floating-point arithmetic and truncated and rounded logarithmic arithmetic are simultaneously utilized for each of the computation sequences and the resulting round-off error accumulations for these four systems are compared. Fundamental results related to the nature of the correlated errors incurred under various arithmetic operator mixes are discussed.

Completeness and uniqueness properties for the representation of the base 㬲 digital numbers by finite length radix polynomials with various digit sets are studied. The digit sets guaranteeing completeness and uniqueness are characterized. A digital conversion algorithm is introduced for determining a base β radix polynomial with digits from a specified set D having a particular value whenever such a radix polynomial exists. The notion of precision of a radix polynomial is formalized, and the determination of the precision from the given base β, digit set D, and real value a of the radix polynomial is investigated.

Abstract The maximum edge‐connectivity of any subgraph plus unity is shown to be an upper bound on the chromatic number for any graph. More generally it is shown that every graph possesses a Grundy function bounded at each vertex by the maximum edge‐connectivity of the subgraphs containing that vertex. A discussion of how to construct such a Grundy function is also provided.

By computational arithmetic we shall mean the study of those discrete numeric systems suitable for implementation on a digital computer. The structure and limitations of discrete arithmetic, the notions of mixed base and mixed type arithmetic, the incurred “roundoff error” of psuedo-real arithmetic, and the efficiency of realization of arithmetic operations all form integral parts of this discipline. The foundations for this material are drawn from the logician's analysis of computability, the electrical engineer's analysis of boolean networks, the number theorist's analysis of elementary number theory, and the numerical analyst's study of numerical approximation. The cohesive thread uniting these topics is the relevance to computerized discrete computation, and what emerges is a firm discipline for inclusion in the complete Computer Science Curriculum. The central body of this material certainly should be a prerequisite for anyone who must design hardware and/or software to implement the arithmetic called for in a high level language.

The process of converting arbitrary real numbers into a floating-point format is formalized as a mapping of the reals into a specified subset of real numbers. The structure of this subset, the set of n significant digit base β floating-point numbers, is analyzed and properties of conversion mappings are determined. For a restricted conversion mapping of the n significant digit base δ numbers to the m significant-digit base δ numbers, the one-to-one, onto, and order- preserving properties of the mapping are summarized. Multiple conversions consisting of a composition of individual conversion mappings are investigated and some results of the invariant points of such compound conversions are presented. The hardware and software implications of these results with regard to establishing goals and standards for floating-point formats and conversion procedures are considered.