Machine method to perform newton iterations for reciprocal square roots
FIELD OF THE INVENTION 
     This invention relates to equipment for producing mathematical computations, and particularly for iterative calculations. Such equipment sometimes referred to as a mathematical &#34;engine&#34;, usually is incorporated into a computer processor circuit, such as a CPM or a co-processor. 
     BACKGROUND OF THE INVENTION 
     Newton&#39;s Method is an iterative method that has proven to be an effective way to solve for the roots of a polynomial equation. It is particularly attractive as a computational method in a high speed computer when the computer has a hardware floating point multiplier and a hardware floating point adder-subtractor. 
     In the above case, a hardware implementation of Newton&#39;s method can be used to rapidly compute the floating point reciprocal or floating point reciprocal square root of an unknown value C which in turn can be used to compute floating point divide or square root operations. 
     In general, the Newton&#39;s method solves F(x)=0 given that the function F(x) is defined and twice differentiable on the interval (a,b). The algorithm is given as: 
     
         x.sub.(m+1) =x.sub.m -F(x.sub.m)/F&#39;(x.sub.m) 
    
     where: x 0  =is an initial approximation for F(x)=0, x m  =is the mth iteration, 
     x.sub.(m+1) =is the (m+1)st iteration, and 
     F&#39;(x m )=is the first derivative of F() evaluated at x m . 
     Newton&#39;s Method for the specific case of determining reciprocal involves the solving: 
     
         F(x)=x.sup.-1 -C 
    
     and the Newton Iteration is given by: 
     
         x.sub.(m+1) =x.sub.m {2-cx.sub.m } 
    
     for F(x)=0, x -1  =c and x is equal to the reciprocal of C. 
     Prior state-of-the-art hardware implementations have revolved around decomposing each Newton Iteration into the following successive computations: 
     
         ______________________________________                                    
1.      cx.sub.m     form the product of x.sub.m and C                    
2.      {2 - cx.sub.m }                                                   
                     subtract the product from 2                          
3.      x.sub.m {2 - cx.sub.m }                                           
                     form the product                                     
______________________________________                                    
 
    
     Each step requires only the use of a multiplier or an adder. Hence, each Newton Iteration requires three operations. 
     The improved method forms the Newton Iteration in the following two steps versus the three steps as in prior art: 
     
         ______________________________________                                    
1.     cx.sub.m    form the product of x.sub.m and C                      
2.     x.sub.m {2 - cx.sub.m }                                            
                   form the product and difference                        
                   simultaneously.                                        
______________________________________                                    
 
    
     Newton&#39;s Method for the specific case of determining reciprocal square roots involves solving: 
     
         F(x)=x.sup.-2 -C=0 
    
     and the Newton Iteration is given by: 
     
         x.sub.(m+1) =0.5x.sub.m {3-cx.sub.m.sup.2 } 
    
     for F(x)=0, x -2  =C and x is the reciprocal square root of C. 
     Prior state of the art hardware implementations have revolved around decomposing each Newton Iteration into the following successive computations: 
     
         ______________________________________                                    
1.     x.sub.m.sup.2                                                      
                    square x.sub.m                                        
2.     cx.sub.m.sup.2                                                     
                    multiply the square of x.sub.m by C                   
3.     3 - cx.sub.m.sup.2                                                 
                    subtract the product from 3                           
4.     x.sub.m {3 - cx.sub.m.sup.2 }                                      
                    multiply the difference by x.sub.m                    
5.     .5x.sub.m {3 - cx.sub.m.sup.2 }                                    
                    multiply the quantity by .5                           
______________________________________                                    
 
    
     Each step requires only the use of a multiplier or an adder. Hence, each Newton Iteration requires five operations. 
     The improved method forms the Newton Iteration in the following three steps versus the five steps as in prior art: 
     
         ______________________________________                                    
1.     x.sub.m.sup.2                                                      
                    square x.sub.m                                        
2.     cx.sub.m.sup.2                                                     
                    multiply the square of x.sub.m by C                   
3.     .5x.sub.m {3 - cx.sub.m.sup.2 }                                    
                    form the product and difference                       
                    simultaneously.                                       
______________________________________                                    
 
    
     SUMMARY OF THE INVENTION 
     The preferred embodiment of this invention provides an improved method for computing the reciprocal square root of an unknown value C using Newton&#39;s method. 
     The improved method forms the reciprocal square root Newton Iteration in the following three steps versus the five steps as in prior art: 
     
         ______________________________________                                    
1.     x.sub.m.sup.2                                                      
                    square x.sub.m                                        
2.     cx.sub.m.sup.2                                                     
                    multiply the square of x.sub.m by C.                  
3.     .5x.sub.m {3 - cx.sub.m.sup.2 }                                    
                    steps 3 through 5 merged                              
                    into one.                                             
______________________________________                                    
 
    
     Unlike prior art, each of the new steps requires only the use of a multiplier-accumulator. The improved method is 40% more efficient and hence computationally faster than prior methods. 
     The implementation of steps 1 and 2 as well as the initial seed generation of x 0  by lookup tables is well known in the art. The implementation of step 3 is of particular interest for the most widely used floating point number formats, the IEEE standard 32-bit and 64-bit formats. The improved method is detailed for the IEEE 64-bit floating point format but is readily applicable to IEEE single precision format as well. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a functional unit used for reciprocal and reciprocal square root derivation of a value C. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     The optimized implementation of Newton&#39;s method applied to the reciprocal and reciprocal square root is of particular interest for the most widely used floating point number formats, the IEEE standard 32-bit and 64-bit formats. The value of a normalized IEEE floating point number is given by: 
     
         z={-1.sup.S }{2.sup.(ex-bias) }{1.fz} 
    
     where: 
     1. s is the sign of z, s={0 or 1}; 
     2. ex is the biased exponent field (8 bits for single precision and 11 bits for double precision); 
     3. bias is the exponent bias where the bias=127 for single precision and the bias=1023 for double precision; 
     4. 1.fz is the mantissa, fz is the fraction field, and the 1 is the hidden bit; and 
     5. fz=z.sub.(n-2) z.sub.(n-3). . . z 0 , where n=24 for single precision and n=53 for double precision floating point operands. 
     A complete specification of the IEEE floating point standard is found in Introduction to Arithmetic for Digital Systems Designers, CBS College Publishing, Dryden Press, 1982, by M. Flynn. 
     FIG. 1 illustrates an embodiment of the present invention as implemented by a functional unit 5 capable of performing single and double and mixed precision IEEE floating point multiplication, fixed point multiplication, floating point reciprocal and floating point reciprocal square root operations. The functional unit shown has a first internal pipeline register 10, a second internal pipeline register 11, a third internal pipeline register 12, a main mantissa pipeline register and format block 16, an exponent pipeline register and format block 17, and a seed mantissa output pipeline register 19. 
     The functional unit 5 has an XS input 20, an XR input 21, and a clock signal 24 used for internal timing of processing signals in the first internal pipeline register 10 and the main mantissa pipeline register and format block 16. The functional unit has a control signal 22 generated in a control circuit 23 according to a generated instruction opcode and the value of alpha. The opcode of an instruction contains the mnemonic for the instruction to be performed. For example, an add mnemonic indicates the instruction should do addition. Alpha is generated according to the reciprocal and reciprocal square root derivations of Tables 1 and 2 respectively. 
     Table 1 being the algorithm description for the reciprocal computation step x.sub.(m+1) =2-p m . 
     
                       TABLE 1                                                     
______________________________________                                    
RECIPROCAL COMPUTATION OF x(m+1):                                         
______________________________________                                    
where:                                                                    
x(m+1) =                                                                  
        x(m)(2 - p(m)                                                     
p(m) =  cx(m)                                                             
p(m) =  2**(alpha))(1.fp), fp = p(n-2)p(n-3) . . . p(0)                   
alpha = exponent value of p(m)                                            
x(m) =  (-1)**sx 2**(xexp - bias)( 1.fx)                                  
xexp =  biased exponent of x(m)                                           
bias =  IEEE bias value 1023 for double and 127 for single                
        precision floating point                                          
fx =    x(n-2)x(n-3) . . . x(0), x(m) fraction field                      
CASE 1. p(m) exponent value (alpha) = -1                                  
x(m+1) =                                                                  
 ##STR1##                                                                 
2**(-n){ 1.x(n-2)x(n-3) . . . x(0) }} {(-1)**sx} 2**(xexp -               
bias)                                                                     
CASE 2. p(m) exponent value (alpha) = 0                                   
x(m+1) =                                                                  
 ##STR2##                                                                 
2**(-n+2){ 1.x(n-2)x(n-3) . . . x(0) }} {(-1)**sx} 2**(xexp -             
bias -1)                                                                  
______________________________________                                    
 
    
     Table 2 being the algorithm description for the reciprocal square root computation step x.sub.(m+1) =0.5x m  (3-p m ). 
     
                       TABLE 2                                                     
______________________________________                                    
RECIPROCAL                                                                
SQUARE ROOT COMPUTATION OF x(m+1):                                        
______________________________________                                    
where:                                                                    
x(m+1) =                                                                  
        .5x(m)(1 - p(m)                                                   
p(m) =  cx(m)**2                                                          
p(m) =  2**(alpha))(1.fp), fp = p(n-2)p(n-3) . . . p(0)                   
alpha = exponent value of p(m)                                            
x(m) =  (-1)**sx 2**(xexp - bias)( 1.fx)                                  
xexp =  biased exponent of x(m)                                           
bias =  IEEE bias value 1023 for double and 127 for single                
        precision floating point                                          
fx =    x(n-2)x(n-3) . . . x(0), x(m) fraction field                      
CASE 1. p(m) exponent value (alpha) = 0                                   
x(m+1) =                                                                  
 ##STR3##                                                                 
2**(-n+1){ 1.x(n-2)x(n-3) . . . x(0) }} {(-1)**sx} 2**(xexp -             
bias - )                                                                  
CASE 2. p(m) exponent value (alpha) = -1                                  
SUBCASE 1. p(0) = 0                                                       
x(m+1) =                                                                  
 ##STR4##                                                                 
2**(-n-1){ 1.x(n-2)x(n-3) . . . x(0) }} {(-1)**sx} 2**(xexp -             
bias)                                                                     
SUBCASE 2. p(0) = 1                                                       
x(m+1) =                                                                  
 ##STR5##                                                                 
2**(-n){ 1.x(n-2)x(n-3) . . . x(0) }} {(-1)**sx} 2**(xexp -               
bias)                                                                     
______________________________________                                    
 
    
     The XS input 20 and the XR input 21 are variable according to which iteration the unit is processing and are determined in an input select circuit 25. 
     The functional unit 5 is composed of a mantissa processing section 26, an exponent section 27 and a seed unit section 30. The mantissa processing section 26 has an XS mantissa operand format block 35, an XR mantissa operand format block 40, and an accumulator format block 45 for providing input parts 46, 47 and 48 for XS, XR and accumulate input operands respectively to a fixed point multiplier-accumulator array 50. 
     The exponent section 27 has an XS exponent operand format block 55 and an XR exponent operand format block 60. Seed unit section 30 has a seed format block 65. 
     The fixed point multiplier-accumulator array 50 has a multiplier format block 75 for controlling the format of the multiplier so that a two&#39;s complement or binary multiplication can be performed. 
     An exponent processing unit 76 is used in the multiplication of floating point numbers and in the generation of a seed exponent for reciprocal and reciprocal square root operations. The seed lookup tables unit 80 is used in the generation of mantissa seed values for either the reciprocal or reciprocal square root of an input. The control signals 22 are used to select the desired input format select options (i.e. control the multiplexers) as well as select the main mantissa pipeline register and format block 16, the exponent pipeline register and format block 17, and the seed mantissa output pipeline register 19. In the case of fixed point operations, the full 64-bit main mantissa pipeline register and format block 16 is selected. In any case the final computation of the reciprocal square root of the value C is available at output node 30. 
     The second stage operations of the mantissa processing section 26 are performed in circuitry located below the first internal pipeline register 10. The second stage operations include the addition of the sum and carry outputs of the fixed point multiplier-accumulator array 50. The result of any preceding fixed point computation is also added as required to perform a two cycle double precision operation. Furthermore, the mantissa processing section 26 performs rounding and exception handling of the result in the multi-input adder tree rounder and exception handler 85. Control is bidirectional to and from the multi-input adder tree rounder and exception handler 85 and the second stage of a renormalization and exception processing unit 90 in the exponent section 27. The general operation of the multi-input adder tree rounder and exception handler 85 and renormalization and exception processing unit 90 is understood by those versed in the art and is described in Journal of Research and Development, Vol. 34, No. 1, pp. 111-120, Jan. 1990. 
     The XS input and the XR input are determined by an input selection circuit 25 in order to accommodate the steps of the iteration shown in Tables 3 and 4. 
     Table 3 indicates the complete sequence for a double precision reciprocal operation. 
     
                                           TABLE 3                                 
__________________________________________________________________________
RECIPROCAL ITERATIONS                                                     
COMPUTATION  XR OPERAND                                                   
                      XS OPERAND                                          
                              COMMENTS                                    
__________________________________________________________________________
  x(0)       c        --      seed lookup                                 
  p(0) = cx(0)                                                            
             x(0)     c       mixed precision with                        
                              feedback = 0                                
  x(1) = x(0) (2 - p(0))                                                  
             x(0)     p(0)    mixed precision with                        
                              feedback = 0                                
  p(1) = cx(1)                                                            
             x(1)     c       mixed precision with                        
                              feedback = 0                                
  x(2) = x(1) (2 - p(1))                                                  
             x(1)     p(1)    mixed precision with                        
                              feedback = 0                                
  p(2) = cx(1)                                                            
             x(1)     c       fixed point, full c                         
                              LSB&#39;s of x(1)                               
  p(2) = cx(1)                                                            
             x(1)     c       mixed precision with                        
                              feedback from step 6.                       
  x(3) = x(2) (2 - p(2))                                                  
             x(2)     p(2)    fixed point, full p(2)                      
                              LSB&#39;s of x(2)                               
  x(3) = x(2) (2 - p(2))                                                  
             x(2)     p(2)    mixed precision with                        
                              feedback from step 8.                       
__________________________________________________________________________
 
    
     Table 4 indicates the complete sequence for a double precision reciprocal square root operation. 
     
                                           TABLE 4                                 
__________________________________________________________________________
RECIPROCAL SQUARE ROOT ITERATIONS                                         
COMPUTATION   XR OPERAND                                                  
                       XS OPERAND                                         
                               COMMENTS                                   
__________________________________________________________________________
  x(0)        c        --      seed lookup                                
  q(0) = x(0)x(0)                                                         
              x(0)     x(0)    mixed precision with                       
                               feedback = 0                               
  p(0) = cq(0)                                                            
              q(0)     c       mixed precision with                       
                               feedback = 0                               
  x(1) = .5X(0) (3 - p(0))                                                
              x(0)     p(0)    mixed precision with                       
                               feedback = 0                               
  q(1) = x(1)x(1)                                                         
              x(1)     x(1)    mixed precision with                       
                               feedback = 0                               
  p(1) = cq(1)                                                            
              q(1)     c       mixed precision with                       
                               feedback = 0                               
  x(2) = .5X(1) (3 - p(1))                                                
              x(1)     p(1)    mixed precision with                       
                               feedback = 0                               
  q(2) = x(2)x(2)                                                         
              x(2)     x(2)    fixed point, full x(2)                     
                               LSB&#39;s of x(2)                              
  q(2) = x(2)x(2)                                                         
              x(2)     x(2)    mixed precision with                       
                               feedback from step 8.                      
10.                                                                       
  p(2) = cq(2)                                                            
              q(2)     c       fixed point, full c                        
                               LSB&#39;s of q(2)                              
  p(2) = cq(2)                                                            
              q(2)     c       mixed precision with                       
                               feedback from step 10.                     
  x(3) = .5x(2) (3 - p(2))                                                
              x(2)     p(2)    fixed point, full p(2)                     
                               LSB&#39;s of x(2)                              
  x(3) = .5x(2) (3 - p(2))                                                
              x(2)     p(2)    mixed precision with                       
                               feedback from step 12.                     
  q(3) = x(3)x(3)                                                         
              x(3)     x(3)    fixed point, full x(3)                     
                               LSB&#39;s of x(3)                              
  q(3) = x(3)x(3)                                                         
              x(3)     x(3)    mixed precision with                       
                               feedback from step 14.                     
  p(3) = cq(3)                                                            
              q(3)     c       fixed point, full c                        
                               LSB&#39;s of q(3)                              
  p(3) = cq(3)                                                            
              q(3)     c       mixed precision with                       
                               feedback from step 16.                     
  x(3) = .5x(3) (3 - p(3))                                                
              x(3)     p(3)    fixed point, full p(3)                     
                               LSB&#39;s of x(3)                              
  x(3) = .5x(3) (3 - p(3))                                                
              x(3)     p(3)    mixed precision with                       
                               feedback from step 18.                     
__________________________________________________________________________
 
    
     Tables 5 through 9 and the value of alpha from Tables 1 and 2 are used internally in the XS mantissa operand format block 35, XR mantissa operand format block 40, accumulator format block 45, XS exponent format block 55, and XR exponent operand format block 60 to select the input mantissa and exponent fields of the XS input and the XR input and the fixed point multiplier-accumulator according to a given control signal in order to normalize the inputs. 
     Table 5 indicates outputs a53f-a0f that will be selected in the XS mantissa operand format block 35 depending on which control signal, A-J, is selected. 
     Table 6 indicates outputs b31f-b0f that will be selected in the XR mantissa operand format block 40 depending on which control signal, A-H, is selected. 
     Table 7 indicates outputs z33-z0 that will be selected in the accumulator operand format block 45 depending on which control signal, A-E, is selected. 
     Table 8 indicates outputs se10-se0 that will be selected n the XS exponent operand format block 55 depending on which control signal, A-F, is selected. 
     Table 9 indicates outputs re10-re0 that will be selected in the XR exponent operand format block 60 depending on which control signal, A-F, is selected. 
     
                                           TABLE 5                                 
__________________________________________________________________________
select the output a53f-a0f according to the select control                
terms A through J (--- denotes bit complement)                            
select terms                                                              
      a53f                                                                
          a52f                                                            
              a51f                                                        
                  a50f                                                    
                      a49f                                                
                          . . .  a2f                                      
                                    a1f                                   
                                       a0f                                
__________________________________________________________________________
A     1   xs51                                                            
              xs50                                                        
                  xs49                                                    
                      xs48                                                
                          . . .  xs1                                      
                                    xs0                                   
                                       0                                  
B     1   0   0   0   0   . . .  0  0  0                                  
 C                                                                        
       ##STR6##                                                           
           ##STR7##                                                       
               ##STR8##                                                   
                   ##STR9##                                               
                       ##STR10##                                          
                           . . .                                          
                                  ##STR11##                               
                                     0  0                                 
 D     1   0                                                              
               ##STR12##                                                  
                   ##STR13##                                              
                       ##STR14##                                          
                           . . .                                          
                                  ##STR15##                               
                                     ##STR16##                            
                                        ##STR17##                         
E     1   xs22                                                            
              xs21                                                        
                  xs20                                                    
                      xs19                                                
                          . . . xs0 . . .                                 
                                 0  0  0                                  
F     1   xs54                                                            
              xs53                                                        
                  xs52                                                    
                      xs51                                                
                          . . . xs32 . . .                                
                                 0  0  0                                  
G     xs31                                                                
          xs30                                                            
              xs29                                                        
                  xs28                                                    
                      xs27                                                
                          . . . xs0 . . .                                 
                                 0  0  0                                  
H     xs63                                                                
          xs62                                                            
              xs61                                                        
                  xs60                                                    
                      xs59                                                
                          . . . xs32 . . .                                
                                 0  0  0                                  
 I     1                                                                  
           ##STR18##                                                      
               ##STR19##                                                  
                   ##STR20##                                              
                       ##STR21##                                          
                           . . .                                          
                                  ##STR22##                               
                                     ##STR23##                            
                                        0                                 
 J     1   0   0                                                          
                   ##STR24##                                              
                       ##STR25##                                          
                           . . .                                          
                                  ##STR26##                               
                                     ##STR27##                            
                                        ##STR28##                         
__________________________________________________________________________
 
    
     
                                           TABLE 6                                 
__________________________________________________________________________
select the bf31f-b0f outputs according to the select control A through H  
select terms                                                              
      b31f                                                                
         b30f                                                             
            b29f                                                          
               b28f                                                       
                  b27f                                                    
                     . . .   b2f                                          
                                b1f                                       
                                   b0f                                    
__________________________________________________________________________
A     1  xr51                                                             
            xr52                                                          
               xr51                                                       
                  xr50       xr23                                         
                                xr22                                      
                                   xr21                                   
B     xr20                                                                
         xr19                                                             
            xr18                                                          
               xr17                                                       
                  xr16                                                    
                     . . .                                                
                        xr0 . . .                                         
                             0  0  0                                      
C     1  0  0  0  0          0  0  0                                      
D     1  0  0  0  0          0  0  0                                      
E     1  xr22                                                             
            xr21                                                          
               xr20                                                       
                  xr19                                                    
                     . . .                                                
                        xr0 . . .                                         
                             0  0  0                                      
F     1  xr54                                                             
            xr53                                                          
               xr52                                                       
                  xr51                                                    
                     . . .                                                
                        xr32 . . .                                        
                             0  0  0                                      
G     xr31                                                                
         xr30                                                             
            xr29                                                          
               xr28                                                       
                  xr27                                                    
                     . . .   xr2                                          
                                xr1                                       
                                   xr0                                    
H     xr63                                                                
         xr62                                                             
            xr61                                                          
               xr60                                                       
                  xr59                                                    
                     . . .   xr34                                         
                                xr33                                      
                                   xr32                                   
__________________________________________________________________________
 
    
     
                                           TABLE 7                                 
__________________________________________________________________________
a. Select the z33-z0 bits according to the control signals A through E    
select terms                                                              
      z33                                                                 
         z32                                                              
            z31                                                           
               z30                                                        
                  z29                                                     
                     z28                                                  
                        z27                                               
                           z26                                            
                              . . .                                       
                                 z0                                       
__________________________________________________________________________
A     0  0  0  0  0  0  0  0     0                                        
B     1  xr51                                                             
            xr50                                                          
               xr49                                                       
                  xr48                                                    
                     xr47                                                 
                        xr46                                              
                           xr45                                           
                              . . .                                       
                                 xr19                                     
C     0  1  xr51                                                          
               xr50                                                       
                  xr49                                                    
                     xr48                                                 
                        xr47                                              
                           xr46                                           
                              . . .                                       
                                 xr20                                     
D     0  0  1  xr51                                                       
                  xr50                                                    
                     xr49                                                 
                        xr48                                              
                           xr47                                           
                              . . .                                       
                                 xr21                                     
E     0  0  0  1  xr51                                                    
                     xr50                                                 
                        xr49                                              
                           xr48                                           
                              . . .                                       
                                 xr22                                     
__________________________________________________________________________
 
    
     
                                           TABLE 8                                 
__________________________________________________________________________
a. generate se10-se0 using the control select terms A through F           
se10                                                                      
   se9                                                                    
      se8                                                                 
         se7                                                              
            se6                                                           
               se5                                                        
                  se4                                                     
                     se3                                                  
                        se2                                               
                           se1                                            
                              se0                                         
                                 control select                           
__________________________________________________________________________
xs62                                                                      
   xs61                                                                   
      xs60                                                                
         xs59                                                             
            xs58                                                          
               xs57                                                       
                  xs56                                                    
                     xs55                                                 
                        xs54                                              
                           xs53                                           
                              xs52                                        
                                 A                                        
0  0  0  0  0  0  0  0  0  0  0  B                                        
0  1  1  1  1  1  1  1  1  1  0  C                                        
0  1  1  1  1  1  1  1  1  1  1  D                                        
xs30                                                                      
   xs29                                                                   
      xs28                                                                
         xs27                                                             
            xs26                                                          
               xs25                                                       
                  xs24                                                    
                     xs23                                                 
                        0  0  0  E                                        
xs62                                                                      
   xs61                                                                   
      xs60                                                                
         xs59                                                             
            xs58                                                          
               xs57                                                       
                  xs56                                                    
                     xs55                                                 
                        0  0  0  F                                        
__________________________________________________________________________
 
    
     
                                           TABLE 9                                 
__________________________________________________________________________
generate the re10-re0 output bits control select terms A through F        
re10                                                                      
   re9                                                                    
      re8                                                                 
         re7                                                              
            re6                                                           
               re5                                                        
                  re4                                                     
                     re3                                                  
                        re2                                               
                           re1                                            
                              re0                                         
                                 control term                             
__________________________________________________________________________
xr62                                                                      
   xr61                                                                   
      xr60                                                                
         xr59                                                             
            xr58                                                          
               xr57                                                       
                  xr56                                                    
                     xr55                                                 
                        xr54                                              
                           xr53                                           
                              xr52                                        
                                 A                                        
0  1  1  1  1  1  1  1  1  1  0  B                                        
0  1  1  1  1  1  1  1  0  0  0  C                                        
0  1  1  1  1  1  1  1  1  1  0  D                                        
xr30                                                                      
   xr29                                                                   
      xr28                                                                
         xr27                                                             
            xr26                                                          
               xr25                                                       
                  xr24                                                    
                     xr23                                                 
                        0  0  0  E                                        
xr62                                                                      
   xr61                                                                   
      xr60                                                                
         xr59                                                             
            xr58                                                          
               xr57                                                       
                  xr56                                                    
                     xr55                                                 
                        0  0  0  F                                        
__________________________________________________________________________
 
    
     It is highly desirable that the XS input and XR input be normalized, as this eliminates the time consuming task of a renormalization that would otherwise be required prior to multiplication. The handling of denormalized inputs are performed under the direction of a trap handling routine which is well-known in the art. 
     The embodiment shown in the Functional Unit 5 of FIG. 1 performs a full rounded floating point multiply in two cycles by combining the first cycle fixed point product result via the feedback path 91 with the second stage mixed precision floating point result. In this manner, a full double precision operation can be performed every two machine cycles. The mantissa and multiplicand of the fixed point multiply product are the full mantissa of the XS mantissa operand (1.XS53-XS0) and the lower 21 bit mantissa of (XR20-XR0) for the XR mantissa operand. The fixed point product result is right shifted. It is then added via the feedback path 91 with the result from a mixed precision floating point computation. This computation consists of the full double precision XS mantissa and exponent operand and mixed precision XR operand. The XR operand of the mixed precision product consists of the entire XR exponent and sign field and the most significant 32 bits of the mantissa full (1.XR51-XR0), i.e. (1XR51-XR21). 
     Tables 3 and 4 are specific examples of the steps performed in the iterative method of the present embodiment. The XS input 20 and the XR input 21 are determined by an input selection circuit 25 in order to accommodate the steps. The XS and XR inputs are normalized in the operand format blocks before any circuit computations take place. Table 3 provides a useful example of the iterative steps. The value C becomes the first XR input and there is no XS input. Using seed lookup, the computation x is performed by the seed unit section 30 using C as its input. The result x 0  from step 1 becomes the XR input with C as the XS input to compute the product p 0  =cx 0  of step 2. In step 2, the mixed computation p 0  =cx 0  is performed with 0 feedback. In step 3, the XR input is result x 0  from step 1 and the XS input is result p 0  from step 2. In step 3, the mixed precision computation x 1  =x 0  (2-p 0 ) is performed with 0 feedback. In step 4, the XR input is the result x 1  from step 3 and the XS input is C. In step 4, the mixed precision computation p 1  =cx 1  is performed with 0 feedback. In step 5, the XR input is the result x 1  from step 3 and the XS input is the result p 1  from step 4. In step 5, the mixed computation x 2  =x 1  (2-p 1 ) is performed with 0 feedback. In step 6, the XR input is result x 1  from step 3 and the XS input is C. In step 6, the fixed point computation p 2  =cx 1  is performed on the full C operand and the LSB&#39;s of x 1 . In step 7, the XR input is the result x 1  from step 3 and the XS input is C. In step 7, the mixed precision computation p 2  =cx 1  is summed with the feedback from step 6 to form a double precision result, p 2 . In step 8, the XR input is the result x 2  from step 5 and the XS input is the result p 2  from step 6. In step 8, the fixed point computation x 3  =x 2  (2- p 2 ) is performed for the full p 2  and the LSB&#39;s of x 2 . In the final step 9, the XR input is the result x 2  from step 5 and the XS input is the result p 2  from step 6. In step 9, the mixed precision computation x 3  =x 2  (2-p 2 ) is summed with feedback from step 8 to form the double precision result, x 3 . 
     Single precision floating point operations, mixed precision operations (one operand full double precision, one operand with full exponent but truncated mantissa) and fixed point operations each require one machine cycle. 
     FLOATING RECIPROCAL COMPUTATION OF x.sub.(m+1) =x m  (2-p m ) 
     The implementation of the optimized reciprocal operations by the Functional Unit 5 shown in FIG. 1 is better understood by referring to Table 1 and the operand format Tables 5-9. From Table 1, the optimized operation at the mth iteration x.sub.(m+1) =x m  (2-p m ), where p m  =2.sup.α (1.fp) is broken down into two cases according to the key observation that the exponent value of p m  is either -1 or 0. Indeed, for performing the computation x.sub.(m+1) both the instruction opcode generated and the value of alpha are used to control the XS mantissa operand format block 35 and the XS exponent operand format block 55 as well as the accumulator format block 45. 
     For the case of alpha=-1, the iteration x.sub.(m+1) is formed as indicated in Table 1 and Tables 5-9 with the XS mantissa operand selected as term D from Table 5 and the XS exponent operand selected as term D from Table 8. The accumulator operand is selected as term A from Table 7 for the first cycle of a two cycle full precision computation and as term D from Table 7 for the second cycle. The XR mantissa operand is selected as term A from Table 6 for the second iteration as term B from Table 6 for the first iteration of the two cycle full precision floating point operation of x.sub.(m+1). Similarly, the XR exponent operand is selected as term A from Table 9 for the second iteration. For all fixed point operations and in particular the first iteration of a two cycle floating point operation, the XR and XS exponent operands are not applicable. 
     Referring to Tables 1 and Tables 5-9 once again, the optimized reciprocal computation of x.sub.(m+1) for the case of alpha=0 requires from Table 5 the term C for the XS mantissa operand for both the first and second cycle of a double precision computation of x.sub.(m+1) =x m  (2-p m ). From Table 8, the term C is selected for the XS exponent operand. From Table 7, the accumulator operand is selected as term C for the second cycle of the two cycle double precision operation and zero, and as term A from Table 7 for the first cycle. Similarly, for the case of alpha=0, the XR mantissa operand is selected from Table 6 as term B for the first cycle and as term A from Table 6 for the second cycle. Finally, from Table 9 the XR exponent is selected as term A for the second cycle and is not applicable for the fixed point first cycle of the two cycle double precision computation of x.sub.(m+1). 
     As Newton&#39;s method approximately doubles precision upon every iteration, only the last iteration requires performing the two cycle full double precision operation. Hence, for all computations of x.sub.(m+1) leading up to the last iteration, only the single cycle operation using the mixed precision operation using item A of the XR Table 6 is required. 
     Table 3 illustrates the complete sequence for a double precision reciprocal computation. Note, that a mixed precision operation is sufficient for steps 2 through 5 and that a two cycle double precision operation is required for steps 6-9 since these steps are associated with the final iteration. The round to nearest rounding mode specified by the IEEE floating point format should be enabled for all operations for full accuracy. 
     FLOATING RECIPROCAL SQUARE ROOT COMPUTATION OF x.sub.(m+1) =0.5x m  (3-p m ) 
     The implementation of the optimized reciprocal operations by the Functional Unit 5 in FIG. 1 is better understood by referring to Table 2 and the operand format Tables 5-9. From Table 2, the optimized operation at the mth iteration x.sub.(m+1) =0.5x m  (3-p m ), where p m  =2.sup.α (1.fp) is broken down into two cases according to the key observation that the exponent value of p m  is either -1 or 0. Indeed, for performing the computation x.sub.(m+1) both the instruction opcode generated control and the value of alpha are used to control the XS mantissa operand format block 35, the XS exponent operand format block 55 as well as the accumulator format block 45. 
     For the case of alpha=-1, there are two additional subcases that permit the full accuracy result to be computed without the need to increase the multiplier width from 54 to 55 bits. From Table 2, the two subcases for alpha=-1 correspond to the value of the least significant bit p 0 . The value of p 0  effects a change in the accumulator format block only. For p 0  =0, the iteration x.sub.(m+1) is formed as indicated in Table 2 with the XS mantissa operand selected as term J from Table 5 and the XS exponent operand selected as term D from Table 8. The accumulator operand is selected from Table 7 as term A for the first cycle of a two cycle full precision computation and as term D from Table 7 for the second cycle. The XR mantissa operand is selected from Table 6 as term A for the second iteration and as term B for the first iteration of the two cycle full precision floating point operation of x.sub.(m+1). Similarly, the XR exponent operand is selected from Table 9 as term A for the second iteration. For the subcase of p 0  =1 only the accumulator selection is different with term C selected from Table 7 for the second cycle and term A selected from Table 7 for the fixed point first cycle computation. For all fixed point operations and in particular the first iteration of a two cycle floating point operation, the XR and XS exponent operands are not applicable. 
     Referring to Table 2, and Tables 5-9 once again, the optimized reciprocal computation of x.sub.(m+1) for the case of alpha=0, requires from Table 5 the term I for the XS mantissa operand for both the first and second cycle of a full precision double precision computation of x.sub.(m+1) =0.5x m  (3-p m ). From Table 8, the term C is selected for the XS exponent operand. From Table 7, the accumulator operand is selected as term C for the second cycle of the two cycle double precision operation and zero; term A from Table 7 is selected for the first cycle. Similarly, for the case of alpha=0, the XR mantissa operand is selected from Table 6 as term B for the first cycle and as term A for the second cycle. Finally, from Table 9 the XR exponent is selected as term A for the second cycle and is not applicable for the fixed point first cycle of the two cycle double precision computation of x.sub.(m+1). 
     Table 4 illustrates the complete sequence for a double precision reciprocal square root computation. Note, that a mixed precision operation is sufficient for steps 2 through 7 and that a two cycle double precision operation is required for all steps associated with the final iteration. The round to nearest rounding mode should be enabled for all operations. 
     DERIVATION OF THE RECIPROCAL SQUARE ROOT COMPUTATION x.sub.(m+1) =0.5x m  (3-p m ) 
     In order to implement x.sub.(m+1) directly with an optimized IEEE floating point multiplier, the computation x.sub.(m+1) =0.5x m  (3-p m ) must be rewritten in an equivalent form such that it&#39;s input operands XS and XR from FIG. 1 are normalized IEEE floating point numbers. In order to accomplish this as fast as possible it is imperative that no large carry look ahead or carry select additions be required to compensate the mantissa operands. This is made possible by designing the fixed point mantissa multiplier as a multiplier accumulator. 
     The quantity p m  as indicated in the computation 
     
         x.sub.(m+1) =0.5x.sub.m (3-p.sub.m) 
    
     where: p m  =cx m   2   
     can be written in terms of a floating point number as 
     
         p.sub.m =2.sup.α (1.fp) 
    
     where: alpha is the exponent value (ex-bias) and (1.fp) is the mantissa value with fp being the friction value 
     
         fp=p.sub.(n-2) p.sub.n-3) p.sub.(n-4). . . p.sub.0 
    
     where: n is a variable typically representing a bit of a word. 
     The key observation is made that for each iteration, the value of alpha is either minus one or zero. This permits the efficient implementation of x(m+1) in one cycle using only a multiplier unit. 
     Recall, x m  is an approximation for 1/c -5 . Hence, p m  =cx m   2  is a quantity close to one. The particular choice of an IEEE floating point format yields two possible cases: 
     Case 1. alpha=-1 
     p m  =2 -1  (1.1111 . . . ) 
     Case 2. alpha=0 
     p m  =2 0  (1.0000 . . . ) 
     The improved method makes use of the fact that the quantity p m  can be partitioned into the case of alpha=-1 or alpha=0 and involves the bit manipulation of the {1.5-0.5p m  } so that x.sub.(m+1) can be implemented with an optimized floating point multiplier capable of operating on normalized floating point operands. 
     Consider now the quantity q={1.5-0.5p m  } for each case of alpha: 
     Case 1. alpha=0 
     q=1.5-0.5p m  =1.1-(0.5)(2.sup.α)(1.fp) 
     q=1.5-0.5p m  =(1.1000 . . . )-(2 -1 )(1.fp) 
     But {-2 -1  (1.fp)}=-(00.1fp) 
     {-2 -1  (1.fp)}=11.0 p.sub.(n-2) p.sub.(n-3). . . p 0  +2 -n   
     Hence, 
     (1.1000. . . )-2 -1  (1.fp)=00.1 p.sub.(n-2) p.sub.(n-3). . . p 0  +2 -n   
     Note the quantity 00.1 p.sub.(n-2) p.sub.(n-3). . . p 0  +2 -n  is not normalized but two times this quantity is. Recall, a normalized quantity is highly desired in order to avoid a renormalization step prior to performing the floating point multiplication. 
     Therefore we can write 
     {1.5-0.5p m  }=2 -1  {1.p.sub.(n-2) p.sub.(n-3)  . . . p 0  2.sup.(-n+1) } for the case alpha=0. 
     In summary, for the case of alpha=0, q=1.5-0.5p m  is not a normalized floating point number but 2q=2{1.5-0.5p m  } is, so that x.sub.(m+1) can be computed by forming the product of x m  and the quantity q=2 -1  {1.p.sub.(n-2) p.sub.(n-3) . . . p 0  +2.sup.(-n+1) } 
     where: p.sub.(n-2). . . p 0  are the bitwise complement of the mantissa fraction bits of the mth iteration p m . 
     Note: For single precision floating point numbers in the IEEE format there are 23 fraction bits and thus n=24. For double precision floating point numbers there are 52 fraction bits and n=53. 
     The quantity 2 -1  is the exponent value that corresponds to the quantity {1.5-0.5p m  } for the case of alpha=0 and is used to compensate for the fact that the mantissa needs to be multiplied by 2 to make it a normalized value. 
     The fixed point multiplication that corresponds to the product of x m  and 
     
         q=2.sup.-1 {1.p.sub.(n-2) p.sub.(n-3). . . p.sub.0 +2.sup.(-n+1) } 
    
     consists of two operands: 
     {1.x.sub.(n-2) x.sub.(n-3). . . x 0}   
     and qman={1.p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n+1) } 
     This computation can be implemented by forming the required addition of 2.sup.(-n+1) as indicated in the brackets prior to the product formation or by breaking the quantity in brackets up and forming a fixed point multiply-accumulate operation. It is highly desirable to avoid using a full carry adder to form the quantity qman but instead use the accumulate input of the fixed point multiplier-accumulator. 
     Use of a fixed point multiply-accumulator for the mantissa is desirable as it eliminates the delay associated with the full adder required to form the quantity qman directly. 
     The multiply-accumulate product and accumulate terms are given as: 
     product input terms: 
     {1.x.sub.(n-2) x.sub.(n-3). . . x 0  } 
     {1.p.sub.(n-2) p.sub.(n-3). . . p 0  } 
     accumulate input term: 
     2.sup.(-n+1) {1.x.sub.(n-2) x.sub.(n-3). . . x 0  } 
     Hence, the x n  mantissa term is right shifted and injected into the accumulator port to form the desired product. 
     Case 2. alpha=-1 
     For the case of alpha=-1 
     q=1.5-0.5p m  ={1.100 . . . 00}-0.5{2.sup.α }{1.fp}=1.100 . . . 00-2 -2  (1.fp) 
     But -2 -2  (1.fp)=-00.01fp=11.10p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) 
     Hence, 
     1.5-0.5p m  =01.00p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) 
     In summary, this case, q=1.5-0.5p m  is a normalized floating point number and x.sub.(m+1) can be formed as the product of x m  and 2 0  {1.00p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) } 
     where: p.sub.(n-2). . . p 0  are the bit complement of the mantissa fraction bits of p m . 
     The fixed point multiplication that corresponds to the product of x m  and {1.00p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) } 
     consists of two terms: 
     }1.x n-2 ) x.sub.(n-3). . . x 0  } 
     and {1.00p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) } 
     This computation can be implemented by forming the required addition of 2.sup.(-n-1) as indicated in the brackets prior to the product formation or more desirably by breaking the quantity in brackets up and forming a fixed point multiply-accumulate operation. 
     Use of a multiply-accumulator is more desirable as it eliminates need and the delay associated with a full adder that would otherwise be required to form the quantity {1.00p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n-1) } directly. 
     The multiply-accumulate product and accumulate terms are given as: 
     product terms: 
     {1.x.sub.(n-2) x.sub.(n-3). . . x 0  } 
     {1.00p.sub.(n-2) p.sub.(n-3). . . p 0  } and 
     accumulate term: 
     2.sup.(-n-1) {1.x.sub.(n-2) x.sub.(n-3). . . x 0  } 
     Hence, the x m  mantissa term is right shifted and injected into the accumulator port to form the desired product. 
     DERIVATION OF THE RECIPROCAL COMPUTATION x.sub.(m+1) =x m  (2-p m ) 
     In order to implement x.sub.(m+1) directly with an optimized IEEE floating point multiplier, the computation x.sub.(m+1) =x m  (2-p m ) must be rewritten in an equivalent form such that it&#39;s input operands XS and XR from FIG. 1 are normalized IEEE floating point numbers. In order to accomplish this as fast as possible it is imperative that no large carry look ahead or carry select additions be required to compensate the mantissa operands. This is made possible by designing the fixed point mantissa multiplier as a multiplier-accumulator. 
     The quantity p m  as indicated in the computation 
     
         x.sub.(m+1) =x.sub.m (2-p.sub.m) 
    
     where: p m  =cx m   
     can be written in terms of a floating point number as 
     
         p.sub.m =2.sup.α (1.fp) 
    
     where: alpha is the exponent value (ex-bias) and (1.fp) is the mantissa value with fp being the fraction value 
     
         fp=p.sub.(n-2) p.sub.(n-3). . . p.sub.0 
    
     The key observation is made that for each iteration, the value of alpha is either minus one or zero. This permits the efficient implementation of x.sub.(m+1) in one cycle using only a multiplier unit. 
     Recall, x m  is an approximation for 1/c. Hence, p m  =cx m  is a quantity close to one. The particular choice of an IEEE floating point format yields two possible cases 
     alpha=0 and alpha=-1. 
     Case 1. alpha=-1 
     In this case: ##STR29## 
     Thus the iteration becomes: 
     x.sub.(m+1) =x m  (2-p m ) ={{1.0p.sub.(n-2) p.sub.(n-3). . . p 0  }{1.x.sub.(n-2) x.sub.(n-3). . . x 0  }+2 -n  {1.x.sub.(n-2) x.sub.(n-3). . . x 0  }}{(-1) SX  }{2.sup.(xexp-bias) } 
     Case 2. alpha=0. 
     In this case 2-p m  is not normalized but 2(2-p m ) is normalized. Thus, 
     2(2-p m )=2{10.+01.p.sub.(n-2) p.sub.(n-3). . . p 0  +2.sup.(-n+1) }=p.sub.(n-2) ·p.sub.(n-3). . . P 0  +2.sup.(-n+2) 
     Therefore: 
     x.sub.(m+1) =x m  (2-p m ) ={{p.sub.(n-2) ·p.sub.(n-3). . . p 0  }{1.x.sub.(n-2) x.sub.(n-3). . . x 0  }+2.sup.(-n+2) {1.x.sub.(n-2) x.sub.(n-3). . . x 0  }}{(-1) sx  }{2.sup.(exp-bias-1) } 
     While a preferred embodiment of the invention has been disclosed, various modes of carrying out the principles disclosed herein are contemplated as being within the scope of the following claims. Therefore, it is understood that the scope of the invention is not to be limited except as otherwise set forth in the claims.