公开(公告)号：US07962537B2

公开(公告)日：2011-06-14

申请号：US11768742

申请日：2007-06-26

Applicant: David W. Matula ,  Mitchell A. Thornton ,  Alexandru Fit-Florea ,  Lun Li

Inventor： David W. Matula ,  Mitchell A. Thornton ,  Alexandru Fit-Florea ,  Lun Li

IPC: G06F7/00

CPC classification number: G06F1/0353 ,  G06F2101/10

Abstract: Determining a table output of a table representing a hierarchical tree for an integer valued function includes determining an address from a table input. A subset of a memory is selected according to the address, where the memory represents the hierarchical tree and the subset represents a subtree of the hierarchical tree. Bit fields are selected from the subset, and bits are extracted from the bit fields. A table output is determined from the extracted bits.

Abstract translation: 确定代表整数值函数的层次树的表的表输出包括从表输入确定地址。 根据地址选择存储器的子集，其中存储器表示分层树，并且子集表示层次树的子树。 从子集中选择位字段，并从位字段中提取位。 从提取的比特确定表输出。

公开(公告)号：US06978289B1

公开(公告)日：2005-12-20

申请号：US10108251

申请日：2002-03-26

Applicant: David W. Matula

Inventor： David W. Matula

IPC: G06F7/38 ,  G06F17/17

CPC classification number: G06F17/17

Abstract: An apparatus and method are disclosed for minimizing accumulated rounding errors in coefficient values in a lookup table for interpolating polynomials. Unlike prior art methods that individually round each polynomial coefficient of a function, the method of the present invention use a “ripple carry” rounding method to round each coefficient using information from the previously rounded coefficient. The “ripple carry” method generates rounded coefficients that significantly improve the total rounding error for the function.

Abstract translation: 公开了一种用于最小化用于内插多项式的查找表中的系数值中的累积舍入误差的装置和方法。 不同于对功能的各个多项式系数进行单独舍入的现有技术方法，本发明的方法使用“波动进位”舍入方法来舍入每个系数，使用来自先前舍入系数的信息。 “纹波进位”方法产生圆整系数，显着提高了该函数的总舍入误差。

公开(公告)号：US06782405B1

公开(公告)日：2004-08-24

申请号：US09876786

申请日：2001-06-07

Applicant: David W. Matula ,  Cristina S. Iordache

Inventor： David W. Matula ,  Cristina S. Iordache

IPC: G06F744

CPC classification number: G06F7/535 ,  G06F7/5525 ,  G06F2207/5354 ,  G06F2207/5356

Abstract: The division and square root systems include a multiplier. The systems also include a multipartite table system, a folding inverter, and a complement inverter, each coupled to the multiplier. The division and square root functions can be performed using three scaling iterations. The system first determines both a first and a second scaling value. The first scaling value is a semi-complement term computed using the folding inverter to invert selected bits of the input. The second scaling value is a table lookup value obtained from the multipartite table system. In the first iteration, the system scales the input by the semi-complement term. In the second iteration, the resulting approximation is scaled by a function of the table lookup value. In the third iteration, the approximation is scaled by a value obtained from a function of the semi-complement term and the table lookup value. After the third iteration, the approximation is available for rounding.

Abstract translation: 除法和平方根系统包括乘数。 该系统还包括一个多部分台系统，一个折叠逆变器和一个互补反相器，每个都耦合到该乘法器。 可以使用三次缩放迭代来执行除法和平方根函数。 系统首先确定第一和第二缩放值。 第一缩放值是使用折叠逆变器来计算输入的所选位的半补码项。 第二个缩放值是从多部分表系统获得的表查找值。 在第一次迭代中，系统将输入缩放为半补码项。 在第二次迭代中，所得到的近似由表查找值的函数进行缩放。 在第三次迭代中，通过从半补码项和表查找值的函数获得的值来缩放近似。 第三次迭代后，近似值可用于舍入。

公开(公告)号：US5060182A

公开(公告)日：1991-10-22

申请号：US402822

申请日：1989-09-05

Applicant: Willard S. Briggs ,  Thomas B. Brightman ,  David W. Matula

Inventor： Willard S. Briggs ,  Thomas B. Brightman ,  David W. Matula

IPC: G06F7/552

CPC classification number: G06F7/5525

Abstract: A method and apparatus for performing the square root function which first comprises approximating the short reciprocal of the square root of the operand. A reciprocal bias adjustment factor is added to the approximation and the result truncated to form a correctly biased short reciprocal. The short reciprocal is then multiplied by a predetermined number of the most significant bits of the operand and the product is appropriately truncated to generate a first root digit value. The multiplication takes place in a multiplier array having a rectangular aspect ratio with the long side having a number of bits essentially as large as the number of bits required for the desired full precision root. The short side of the multiplier array has a number of bits slightly greater by several guard bits than the number of bits required for a single root digit value, which is also determined to be the number of bits in the short reciprocal. The root digit value is squared and the exact square is subtracted from the operand to yield an exact remainder. Succeeding new root digit values are determined by multiplying the short reciprocal by the appropriately shifted current remainder, selectively adding a digit bias adjustment factor and truncating the product. The root digit values are appropriately shifted and accumulated to form a partial root. The described steps are repeated to serially generate root digit values and partial roots with corresponding new exact remainders.

公开(公告)号：US07346642B1

公开(公告)日：2008-03-18

申请号：US10714554

申请日：2003-11-14

Applicant: Willard S. Briggs ,  David W. Matula

Inventor： Willard S. Briggs ,  David W. Matula

IPC: G06F7/38

CPC classification number: G06F7/4873 ,  G06F1/0356 ,  G06F7/483 ,  G06F7/535 ,  G06F7/5525 ,  G06F2101/08 ,  G06F2101/12 ,  G06F2207/5356

Abstract: Methods for determining the square root, reciprocal square root, or reciprocal of a number performed by a processor of a computer system. The methods produce high precision estimates without using iterative steps. In addition, the methods taught herein utilize compressed tables for the coefficient terms A, B, and C from the quadratic expression Ax2+Bx+C, thus minimizing hardware requirements.

Abstract translation: 用于确定由计算机系统的处理器执行的数字的平方根，倒数平方根或倒数的方法。 该方法在不使用迭代步骤的情况下产生高精度估计。 另外，本文教导的方法利用来自二次表达式Ax 2 + B x + C的系数项A，B和C的压缩表，从而最小化硬件要求。

公开(公告)号：US5615113A

公开(公告)日：1997-03-25

申请号：US491182

申请日：1995-06-16

Applicant: David W. Matula

Inventor： David W. Matula

IPC: G06F7/52 ,  G06F7/535

CPC classification number: G06F7/535 ,  G06F2207/5352 ,  G06F7/4991

Abstract: An early no-overflow signaling system and method is used in conjunction with performing nonrestoring division using two's complement 2n bit dividends N and two's complement n bit divisors D--when a no-overflow condition is signaled, a subsequent plurality of iterative partial remainder computations are performed to obtain the quotient Q and remainder R with no possibility of overflow. Dividends N are characterized by a 2-bit sign field N(s1s2) formed by a first sign bit N(s1) and a second sign bit N(s2), a high order n-1 dividend magnitude bits N(himag), and a low order n-1 dividend magnitude bits N(lomag), such that N(s1) and N(himag) form a 2's complement number N(hi), while divisors D are characterized by a leading sign bit D(s) and n-1 divisor magnitude bits D(mag). Early no-overflow signaling logic uses the input dividend N and divisor D, and a 2n-1 bit first partial remainder (which has a value of [N-2.sup.n-1 D]) obtained by computing an n-bit first partial remainder PR1 corresponding to the first n bits of the first partial remainder of value [N-2.sup.n-1 D] (including a leading sign bit PR1(s)), such that the first partial remainder of value [N-2.sup.n-1 D] corresponds to PR1 and N(lomag). No-overflow signaling (illustrated in FIGS. 2a/2b and 4) uses (i) the divisor sign and magnitude D(s) and D(mag), (ii) the two bit sign field of the dividend N(s1s2), (iii) and the first partial remainder of value [N-2.sup.n-1 D]. A no-overflow condition is signaled if (i) the divisor magnitude D(mag) is not equal to zero (FIG. 2a, 102, and FIG. 4, 151), and (ii) the dividend sign bits N(s1) and N(s2) are equal (FIG. 2a, 112, and FIG. 4 , 152), and (iii) the sign of the first partial remainder PR1(s) in not equal to the dividend sign bit N(s2) (FIG. 2b, 131, and FIG. 4, 153), and (iv) the divisor and dividend are not both negative (FIG. 2b, 141, and FIG. 4, 154, 156), or if they are, (v) the first partial remainder corresponding to PR1 and N(lomag) is not equal to zero (FIG. 2b, 141, 142, 143, and FIG. 2b, 155, 156).

公开(公告)号：US5475630A

公开(公告)日：1995-12-12

申请号：US227494

申请日：1994-04-12

Applicant: Willard S. Briggs ,  David W. Matula

Inventor： Willard S. Briggs ,  David W. Matula

IPC: G06F7/52 ,  G06F7/527 ,  G06F7/535

CPC classification number: G06F7/535 ,  G06F7/5375 ,  G06F2207/5351 ,  G06F2207/5355

Abstract: An arithmetic circuit 10 for performing prescaled division uses a rectangular multiplier 16 and accumulator 30 operable to calculate a short reciprocal and scaled dividend and divisor to enable the sequential iterative calculation of large radix quotient digits. Each quotient digit can be calculated using a single pass through the rectangular multiplier 16 and accumulator 30 and can be accumulated to form a full precision quotient in a quotient register 36.

Abstract translation: 用于执行预分频的算术电路10使用矩形乘法器16和累加器30，该矩阵乘法器16和累加器30可操作以计算短的倒数和缩放的除数和除数，以使得能够顺序迭代计算大的基数商数。 可以使用通过矩形乘法器16和累加器30的单次通过来计算每个商数，并且可以累积以在商寄存器36中形成全精度商。