Abstract:
A method is provided to narrow down the exponent range throughout most part of the division and square root calculations, to make both software assistance and precision extension unnecessary. The method adjusts the exponent at the end of the calculation to reach IEEE-754 results.

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to processing systems and particularly to providing floating point calculations in such systems. 
     BACKGROUND 
     It is desired is to provide an accurate division and square root operations in a processing system while minimizing hardware and software. Some conventional methods use software library and end up with slower devices. Other conventional methods extend the precision and end up requiring larger hardware. 
     Accordingly, what is desired is a system and method for addressing the above-identified issues. The present invention addresses such a need. 
     SUMMARY 
     A method and system are provided to narrow down the exponent range throughout most part of the division and square root calculations, to make both software assistance and precision extension unnecessary. The method and system adjusts the exponent at the end of the calculations to reach IEEE-754 industry standard results. 
     A computer implemented method for providing a floating point operation to provide a quotient is disclosed. The quotient is provided by dividing an original dividend value by an original divisor value. In a first aspect, the computer implemented method comprises obtaining a new dividend by reducing an exponent range of the original dividend value and a new divisor by reducing an exponent range of the original divisor value; and obtaining an approximate reciprocal value of the new divisor value. The method also comprises providing an approximate quotient value and one or more error values based upon the new dividend and the approximate reciprocal value of the new divisor value; and utilizing the original dividend value and the original divisor value to generate an adjustment value. Finally the method comprises utilizing a multiplier/adder to provide an accurate quotient based upon the adjustment value, the one or more error values and the approximate quotient value. 
     In a second aspect, a computer implemented method for providing a floating point operation for providing a square root of an original number is provided. The computer implemented method comprises obtaining a new number by reducing an exponent range of the original number; and obtaining an approximate value of a reciprocal square root of the new number. The method further includes providing an approximate square root value and one or more error values based the approximate reciprocal square root value of the new number and utilizing the original number to generate an adjustment value. Finally the method comprises utilizing a multiplier/adder to provide an accurate square root of the original number based upon the adjustment value, the one or more error values and the approximate square root value. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an instruction sequence of a first division embodiment in accordance with the present invention. 
         FIG. 2  is a flow chart for providing a quotient utilizing a floating point operation. 
         FIG. 3  is a block diagram of a first digital device in accordance with the present invention. 
         FIG. 4  is a lookup table for providing an approximate reciprocal value in accordance with the present invention. 
         FIG. 5  is a block diagram of a second digital device in accordance with the present invention. 
         FIG. 6  is a block diagram of a third digital device in accordance with the present invention. 
         FIG. 7  is an instruction sequence of a second division embodiment n accordance with the present invention. 
         FIG. 8  is an instruction sequence of a third division embodiment in accordance with the present invention. 
         FIG. 9  is a block diagram of a fourth digital device in accordance with the present invention. 
         FIG. 10  is an instruction sequence of a first square root embodiment in accordance with the present invention. 
         FIG. 11  is a flow chart for providing a square root of an original number utilizing a floating point operation. 
         FIG. 12  is a lookup table for providing an approximate reciprocal square root value in accordance with the present invention. 
         FIG. 13  is a block diagram of a low power always on voice and gesture recognition application. 
     
    
    
     DETAILED DESCRIPTION 
     The present invention relates generally to processing systems and particularly to providing floating point calculations in such systems. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment and the generic principles and features described herein will be readily apparent to those skilled in the art. Thus, the present invention is not intended to be limited to the embodiment shown but is to be accorded the widest scope consistent with the principles and features described herein. 
     Methods and systems for performing floating point calculations are disclosed. Embodiments described herein can take the form of an entirely hardware implementation, an entirely software implementation, or an implementation containing both hardware and software elements. Embodiments may be implemented in software, which includes, but is not limited to, application software, firmware, resident software, microcode, etc. 
     The steps described herein may be implemented using any suitable controller or processor, and software application, which may be stored on any suitable storage location or computer-readable medium. The software application provides instructions that enable the processor to cause the receiver to perform the functions described herein. 
     Furthermore, embodiments may take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. 
     The medium may be an electronic, magnetic, optical, electromagnetic, infrared, semiconductor system (or apparatus or device), or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state register, register file, memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and an optical disk. Current examples of optical disks include DVD, compact disk-read-only memory (CD-ROM), and compact disk-read/write (CD-R/W). 
     The methods described herein may also be implemented using any suitable instruction set or instruction set architecture (ISA). The devices described herein may be implemented using an operation hardware, an emulation/simulation software, or a combination thereof. One with ordinary skills in the art understands that described methods or devices are applicable to floating point number calculations, fixed point number calculations, or a combination thereof. 
     A register or register file may be used to store a floating number or other data type, as an operand, an intermediate value, a final result, or a combination thereof. Any suitable addressing mode and memory architecture may be used to communicate, propagate or transport the operand, intermediate value, or final result. 
     Floating point numbers may be a native or intrinsic data type in the suitable ISA. A floating point number may be encoded according to IEEE Std 754™, another standard, a proprietary format, or a combination thereof. Throughout this disclosure, “Binary32” binary interchange format of IEEE Std 754™-2008 is used for illustration purposes, though the disclosure anticipates and allows other formats or a combination of formats. 
     IEEE754 Binary32 uses a sign-magnitude format, with a 1-bit sign (S), an 8-bit biased exponent (E) with bias 127, and a 23 trailing significand field (T) representing the binary digits to the right the binary point, as shown in the FIG. 3.1 of IEEE Std 754™ 2008, and an implicit leading significand bit to the left of the binary point. Thus, the value of a normal number (v) is:
 
 v =(−1) 3 ×2 E-127 ×implicit.trailing
 
     For example, the representation (r) for 1.0 is 0x3F800000, with a sign of 0, biased exponent of 127, a trailing significand of 0, and an implicit leading significand of 1, in Binary32. The representation (r) for Not A Number (NaN) is E=0xFF and T≠0 regardless of S. The representation (r) for positive infinity (−∞) is E=0xFF, T=0 and S=0. The representation (r) for negative infinity (−∞) is E=0xFF, T=0 and S=1. The representation (r) for positive zero is E=0, T=0 and S=0. The representation (r) for negative zero is E=0, T=0 and S=1. 
     Throughout this disclosure, the term “infinity” or “∞” may represent positive infinity, negative infinity, or both. The term “zero” may represent positive zero, negative zero, or both. The term “significand” may represent the implicit leading significand, the trailing significand, or their combination. 
     To describe the features of the present disclosure in more detail refer now to the following description in conjunction with the accompanying Figures. 
     The floating point Division(a,b) operation is to compute a/b. Division(0,0), Division(∞,∞), or Division(a,b) wherein either a or b is NaN may be considered invalid operations as no usefully definable result can be produced. In these cases, a NaN may be produced as the result to signal invalid operations. 
     The Division(a,b) operation may be implemented using a low gate count and reasonable speed method based on iterative calculations. The method doesn&#39;t use many extra gates over or above the fused multiplier/adder which presumably exists. The reasonable speed is achievable by avoiding software library, routine or function to handle the invalid operations or other special conditions. The method also achieves Binary32 accuracy or another predetermined precision by utilizing iterative calculations, such as Newton-Raphson approximations as an example. 
     The method implements the Division(a,b) operation using a sequence of instructions. Each of the instruction may be implemented as a hardware device or a portion of a hardware device. Instruction hardware may read one or more operands from a register, a register file, a memory, or a combination thereof. The instruction hardware may write one or more results to a register, a register file, a memory, or a combination thereof; such that a following instruction in the sequence may continue any remaining portion of the operation. The last instruction of the sequence may write the Division(a,b) result, which may be a quotient or a NaN, to a register, a register file, a memory, or a combination thereof. 
       FIG. 1  illustrates an embodiment of a first Division(a,b) instruction sequence. 
       FIG. 2  is a flow chart for providing a quotient utilizing a floating point operation in accordance with an embodiment. The flow chart implements a Division(a,b) Sequence by obtaining a new dividend and a new divisor, obtaining an approximate reciprocal value of the new divisor, providing an approximate quotient value and at least one error, generating an adjustment based on the original dividend and the original divisor, and utilizing a multiplier/adder to provide an accurate quotient. 
     In an embodiment, a new dividend is obtained by reducing an exponent range of the original dividend value and a new divisor is obtained by reducing an exponent range of the original divisor value, via step  202  and an approximate reciprocal value of the new divisor value is obtained, via step  204 . Thereafter, an approximate quotient value and one or more error values based upon the new dividend and the approximate reciprocal value of the new divisor value is provided via step  206 . The original dividend value and the original divisor value are then utilized to generate an adjustment value via step  208 . Finally a multiplier/adder is utilized to provide an accurate quotient based upon the adjustment value, the one or more error values and the approximate quotient value via step  210 . 
     An embodiment implements the above described steps with instruction hardware, stores a sequence of instructions in a memory, and allows the instructions to be ordered in various ways in order to maximize an execution speed. 
     A system and method in accordance with an embodiment anticipates different orders of steps in and for each described method, and breaking down a step into multiple sub-steps wherein the sub-steps of the steps may interleave with each other in various ways. 
     The obtaining a new dividend and a new divisor may be achieved by reducing or narrowing an exponent range of the original dividend and the original divisor. An embodiment considers the original dividend and the original divisor as original operands, and utilizes a digital device to generate new operands comprising a sign, an exponent, and a significand. 
       FIG. 3  illustrates an embodiment of a first digital device NEXP 01   300  comprising a first element  302  for generating the exponent of the new operand. NEXP 01  also comprises a second element  304  for generating the sign of the new operand by copying or negating the sign of the original operand. NEXP 01  further comprises a third element  306  to generate the significand by copying the significand of the original operand. NEXP 01  may be used to produce either the new dividend or the new divisor. 
     The first element  302  of NEXP 01  generate the exponent of the new operand by reducing the exponent range of the original operand so that it is numerically in the range of [1.0, 4.0) or (−4.0, −1.0]. 
     By reducing the exponent range of both the dividend and the divisor, the division will be computed with the narrowed exponent range and with fully accurate significands, to avoid underflow or overflow an exponent range of for example Binary32 during intermediate calculation. As intermediate exponent underflows and overflows are avoided, extended precision hardware becomes unnecessary and the embodiment achieves a smaller hardware. 
     If the original operand is a subnormal or denormalized number, having an implicit leading significand bit of 0, NEXP 01   300  may utilize a fourth element (not shown) to normalize the original operand and to generate a normalized operand. The normalized operand, instead of the original operand, is used by the first element and the third element of NEXP 01   300 . NEXP 01   300  is used as Instruction # 1  to produce aN from a, the dividend. Instruction # 5  used NEXP 01   300  again, this time, to produce bN from b, the divisor. 
     NEXP 01   300  may further include a fifth element (not shown) to generate an optional predicate based upon whether the original operand is zero, infinity, NaN, or a predetermined value (such as a subnormal). The optional predicate may represent a false value, when the original dividend is zero, infinity, NaN or a predetermined value, when the original divisor is zero, infinity, NaN or a predetermined value. The false predicate value may be used to skip any unfinished activities of obtaining a dividend and a new divisor, obtaining an approximate reciprocal value, or providing an approximate quotient value and one or more error values. 
     The obtaining an approximate reciprocal value of the new divisor may be achieved by looking up at least one lookup table. An embodiment implements a hardware element for generating a new operand by utilizing an exponent, a significand, or a combination thereof as an index to a lookup table. The hardware element is incorporated as a sixth element (not shown), using the exponent generated by the first element, the significand generated by the third element, or a combination thereof as the index. 
     An embodiment of such device with the sixth element (not shown) is called DIV 0 . According to the index, the lookup table generates an output. The output is an approximate reciprocal value of the new divisor. DIV 0  provides the approximate reciprocal value of the new divisor as the new operand. In  FIG. 1 , DIV 0  is used as Instruction # 2  to provide the approximate reciprocal value of the new divisor. 
       FIG. 4  illustrates an embodiment of the lookup table for generating an approximate reciprocal value. The row in the table is determined by a first three trailing significand bits in the new divisor. Which entry in the row is determined by a next four significand bits. The decimal numbers in the table are converted to 8-bit values, which determine a first eight bits of the approximate reciprocal, including an implicit significand bit. 
     Providing an approximate quotient value and at least one error may be achieved by utilizing the new dividend, the approximate reciprocal value of the new divisor value. Based on the new dividend, the approximate reciprocal value of the new divisor value, the embodiment provides an approximate quotient value and at least one or values by utilizing iterative calculations such as Newton-Raphson approximations, to achieve a predetermined precision such as Binary32. In  FIG. 1 , Instruction # 6  to Instruction # 22  utilize the new dividend aN and the approximate reciprocal value y 0  to provide an approximate quotient value q and two errors (r and y). 
     Generating an adjustment based on the original dividend and the original divisor may be achieved by utilizing the original dividend value and the original divisor value to generate an adjustment value. The embodiment implements an instruction hardware such as a digital device with elements similar to some of the elements of NEXP 01   300 . With the similar elements, the instruction hardware digital device is able to calculate or anticipate a difference between the original dividend and the new dividend and a difference between the original divisor and the new divisor as generated by NEXP 01   300 . 
       FIG. 5  illustrates an embodiment of a second digital device (MKDADJ)  500 . MKDADJ  500  generates the adjustment number based on at least one original operand. In this case, there are two original operands—one is the original dividend, and the other is the original divisor. MKDADJ  500  comprises a first element  502  to calculate at least one difference between at least one exponent of the at least one operand and at least one predetermined exponent value. MKDADJ  500  also comprises a second element  504  to generate at least one comparison result by comparing the least one original operand to infinity, NaN, or a predetermined value (such as a subnormal). MKDADJ  500  further comprises a third element  506  to generate the adjustment number based on the at least one difference calculated by the first element, at least one predetermined adjustment numbers, the at least one comparison result generated by the second element. 
     MKDADJ  500  may generate at least one special adjustment value when either the original dividend or the original divisor is NaN or upon other special conditions. 
     Like NEXP 01   300 , MKDADJ  500  may generate an optional predicate value based on the at least one comparison result generated by the second element. A false predicate value may be used to skip some unfinished executions, in order to maximize an execution speed when invalid operations or other special conditions occur. 
     Again like NEXP 01   300 , MKDADJ  500  may further include a fourth element (not shown) to generate at least one normalized operand by normalizing the at least one original operand. In this case, the first element  502  utilizes the at least one normalized operand instead of the at least one original operand. In  FIG. 1 , the original divisor b is copied to a first operand of Instruction # 3  (ex) first, then MKDADJ  500  (Instruction # 4 ) considers both the original divisor (now also stored in ex) and the original dividend a to generate an adjustment value. MKDADJ  500  stores the adjustment value to ex. 
     Utilizing a multiplier/adder to provide an accurate quotient may be achieved by basing the new quotient upon the adjustment value, the one or more error values and the approximate quotient value. The embodiment utilizes a digital device capable of multiplying, adding and fused multiplying-adding at least one operand to provide the accurate quotient. 
       FIG. 6  illustrates an embodiment of a third digital device DIVN. DIVN comprises a first element  602  to generate a first intermediate number based upon the at least one operand. In this case, there are three operands—one is the approximate quotient value; the other two are two error values. The first element  602  generates the first intermediate value by fused multiplying-adding the three operands. 
     DIVN  600  also comprises a second element  604  to generate a second intermediate number by adjusting an exponent of the first intermediate number upon the adjustment number, to account for the exponents of the original dividend and the original divisor. DIVN  600  further comprises a third element  606  to generate a final number by rounding the second intermediate number. 
     The final number is the accurate quotient output from the division sequence in the embodiment. The third element  606  may generate NaN, zero or infinity as the final number when the adjustment number is a predetermined special adjustment value. 
     As MKDADJ  500  is capable of generating special adjustment values under special conditions and DIVN  600  is capable of generating NaN, zero or infinity as the accurate quotient output of the Division Sequence. The embodiment may handle special conditions without software library or other forms of software assistance. Without calling any software, the embodiment is able to produce accurate quotients in a faster speed. In  FIG. 1 , Instruction # 23  uses DIVN  600  to generate the accurate quotient based on the approximate quotient q, two errors r and y, and the adjustment value ex. 
       FIG. 7  illustrates an embodiment of a second Division(a,b) instruction sequence. The second Division(a,b) instruction sequence shares the same Instruction # 1  to Instruction # 22  as the first Division(a,b) instruction sequence ( FIG. 1 ). In  FIG. 7 , MULN is used as Instruction # 23  to multiply r and y and to produce a product ry. In  FIG. 7 , Instruction # 24  uses a second embodiment of DIVN, which takes only one error ry, to generate the accurate quotient based on the approximate quotient q, the error ry, and the adjustment value ex. 
       FIG. 8  illustrates an embodiment of a third Division(a,b) instruction sequence, which utilizes encoding and decoding. The third Division(a,b) instruction sequence shares the same Instruction # 1  to Instruction # 22  as the first Division(a,b) instruction sequence ( FIG. 1 ). In  FIG. 8 , ADDEXPM and ADDEXP are used as Instruction # 23  and Instruction # 24  respectively. ADDEXPM and ADDEXP may be implemented as a digital device to encode a first half and a second half of the adjustment value ex into the approximate quotient q, and an error y, respectively. In  FIG. 8 , Instruction # 25  uses a third embodiment of DIVN, which decodes the adjustment value from q and y, and utilizes the decoded adjustment value. The third embodiment of DIVN utilizes one less operand by being able to decode the adjustment value from other operands. 
       FIG. 9  illustrates an embodiment of a fourth device ADDEXP  900 . ADDEXP  900  comprises a first element  902  to generate an exponent based on at least one exponent of the at least one original operand, at least one significand of the at least one original operand, or a combination thereof. In this case, there are two original operands—one is the original approximate quotient q; the other is the adjustment value ex. The first element  902  generates the exponent based on an exponent of q, and a significand of ex. ADDEXP  900  also comprises a second element  904  to generate a sign based on at least one sign of the least one original operand, at least one significand of the at least one original operand, or a combination thereof. In this case. The second element  904  generates the sign based on a sign of q and a significand bit of ex. ADDEXP  900  further comprises a third element  906  to generate the encoded operand based on the exponent generated by the first element  902 , the sign generated by the second element  904 , at least one original significand of the at least one original operand, or a combination thereof. In this case, the third element  906  generates the encoded approximate quotient by combining the exponent from the first element, the sign from the second element, and an original significand of q. 
       FIG. 10  illustrates an embodiment of a first Square Root(a) instruction sequence. 
       FIG. 11  is a flow chart for providing a square root utilizing a floating point operation in accordance with an embodiment. The flow chart implements a Square Root(a) Sequence by obtaining a new number via step  1102 , obtaining an approximate reciprocal square root of the new number via step  1104 , providing an approximate square root value and at least one error via step  1106 , generating an adjustment via step  1108 , and utilizing a multiplier/add to provide an accurate square root via step  1110 . 
     Like the first Division(a,b) Sequence ( FIG. 1 ), The Square Root(a) Sequence ( FIG. 10 ) utilizes NEXP 01   300  as Instruction # 1  to obtain a new number hN. NEXP 01   300  may be capable of normalizing the original number. 
     The obtaining an approximate reciprocal square root of a new number may be achieved by looking up at least one lookup table. An embodiment implements a hardware element for generating the approximate reciprocal square root by utilizing an exponent, a significand, or a combination thereof as an index to a lookup table. The hardware is incorporated as a sixth element (not shown) onto an embodiment of NEXP 01   300 . An embodiment of such device with the sixth element (not shown) is called SQRT 0 . As DIV 0  ( FIG. 1 ) generates an approximate reciprocal value, SQRT 0  ( FIG. 10 ) generates an approximate reciprocal square root value. In  FIG. 10 , SQRT 0  is used as Instruction # 2  to provide the approximate reciprocal square root y. 
       FIG. 12  illustrates an embodiment of the lookup table for generating an approximate reciprocal square root. The row in the table is determined by a low bit of a biased exponent of the new number concatenated with a first two trailing significand bits of the new number. Which entry in the row is determined by a next four significand bits. The decimal numbers in the table are converted to 8-bit values, which determine a first eight bits of the reciprocal square root approximation, including an implicit significand bit. 
     The providing an approximate square root value and at least one error may be achieved by utilizing the approximate reciprocal square root value. Like the Division(a,b) Sequence ( FIG. 1 ), Square Root(a) Sequence ( FIG. 10 ) utilizes Newton-Raphson approximations to achieve Binary32 precision. In  FIG. 10  Instruction # 4  to Instruction # 26  utilize the approximate reciprocal square root y to provide an approximate square root value R and two errors (dN and HN). 
     The generating an adjustment based on the original number may be achieved by utilizing the original number to generate an adjustment value. An embodiment implements the second digital device for Square Root(a) Sequence as MKSADJ (not shown). Similar to MKDADJ  500 , MKSADJ (not shown) generates the adjustment number based on at least one original operand. In this case, there is one original operand—the original number. Like MKDADJ  500 , MKSADJ (not shown) may generate a special adjustment value if the original number is zero, infinity or NaN. Also like MKDADJ  500 , MKSADJ (not shown) may generate an adjustment value by calculating or anticipating a difference between the original number and the new number. Furthermore, MKSADJ (not shown) may generate an optional predicate value. A false predicate value may be used to skip some unfinished executions, in order to maximize an execution speed when invalid or other special conditions occur. 
     The utilizing a multiplier/adder to provide an accurate square root may be achieved by basing the new square root upon the adjustment value, the one or more or values and the approximate square root value. Like Division(a,b) instruction sequence, the Square Root(a) instruction sequence utilizes DIVN as the multiplier/adder. Again like Division(a,b) instruction sequence, an embodiment of a second Square Root(a) instruction sequence may utilize encoding and decoding, by utilizing ADDEXPM, ADDEXP or a combination thereof. 
     As shown with the above examples, the Division(a,b) instruction sequences can be readily modified and become Square Root(a) instruction sequences, by replacing a lookup table for reciprocal with a lookup table for reciprocal square root, by modifying the second digital device from MKDADJ to MKSADJ to account for a different number of operands, and by selecting a suitable iterative calculation. Similar modifications are anticipated to alter disclosed methods, flows, devices or sequences for calculations of reciprocal, reciprocal square root, sine or other trigonometric functions, arcsine or other cyclometric functions, and more. Additionally, Lookup tables may have more or less numbers of entries, the entries of the lookup tables may have a wider or narrower width, and values of the entries may vary. 
     Advantages 
     The advantages are faster calculations and smaller hardware, and still achieving the same accuracy as specified by IEEE-754 standards. 
     System Overview 
     The advantages of faster calculations, smaller hardware and same accuracy may enable a low power always on voice or gesture recognition application. 
       FIG. 13  illustrates an example use case of the voice or gesture recognition application  1300 . The sensor processor  1306  is supplied with an always on power, in order to detect a wake up command by a user. Recognition of the wake up command, such as a verbal password or a predetermined gesture, may result in the sensor processor  1306  signaling a power management integrity circuit (PMIC)  1302  to power on a host processor. Utilizing the disclosed methods and devices, the sensor processor  1306  consumes less active power by performing voice/gesture recognition with a short execution time and consumes less leakage power by having smaller hardware. 
     A microphone input  1310  may capture the verbal password. An image sensor  1308  may capture the predetermined gesture. The password or the gesture may be pre-filtered in an analog way and then converted into a digital signal in a floating point format. A series of floating point numbers happens as the user speaks or gesticulates. The sensor processor  1306  may apply Viterbi algorithm on the series of floating point numbers for recognizing the wake up command. 
     Although the present invention has been described in accordance with the embodiments shown, one of ordinary skill in the art will readily recognize that there could be variations to the embodiments and those variations would be within the spirit and scope of the present invention. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.