home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1986 / 03 / camplst.mar < prev    next >
Text File  |  1986-03-31  |  5KB  |  178 lines
  1. Listing One
  2.  
  3. /*  a square root algorithm
  4.     04/21/85,   R. A. Campbell
  5. */
  6.  
  7. #define NUMBER  60000
  8.  
  9. long    number, ndivs,  nshfts;
  10. long    sqrrt, sqrrto;
  11.  
  12. main()          /* a test loop for square root calculation */
  13. {   nshfts = ndivs = 0;
  14.     sqrrto = 100;
  15.     for ( number = 0; number <= NUMBER; ++number )
  16.     {   sqrrt = sqrt ( number );
  17.         /* for timing, comment out next 2 lines */
  18.     if ( sqrrt != sqrrto )
  19.        printf ("sqr %6d=%4d ",number, sqrrt );
  20.     sqrrto = sqrrt;
  21.     }
  22.     printf ("\nTot Divs= %u Ave Divs.(x10)= %u",
  23.     ndivs, (10 * ndivs)/NUMBER);
  24.     printf ("\nTot Shfts= %u Ave Shfts.(x10)= %u",
  25.     nshfts, (10 * nshfts)/NUMBER);
  26. }
  27.  
  28. sqrt ( numb )       /* a `rational' square root */
  29. register    long    numb;
  30. {   register    long guess1, guess2, error;
  31. /*  return;          for timing checks */
  32.     if ( numb != 0 )
  33.     {   guess1 =1;
  34.     guess2 = numb;
  35.     while ( (guess1 << 1) < guess2 )
  36.     {   guess1 <<= 1;      /* multiply guess1 by 2 */
  37.         guess2 >>= 1;      /* divide guess2 by 2 */
  38.         ++nshfts;          /* for statistics */
  39.     }
  40.     do                     /* now, check */
  41.     {   guess1 += guess2;  /* figure sum */
  42.         guess1 >>= 1;      /* fig mean, divide by two */
  43.         guess2 = numb / guess1;    /* figure quotient */
  44.         error = guess1 - guess2;   /* figure error */
  45.         ++ndivs;           /* for statistics */
  46.     } while ( error > 0 );
  47.     return guess1;
  48.    }
  49.    else
  50.     return 0;
  51. }
  52.  
  53. Listing Two
  54.  
  55. ;SCN:v5  (C) 1985
  56.     PROGRAM
  57.     STATIC 1
  58. Qnumber:    DOUBLE
  59. Qndivs:     DOUBLE
  60. Qnshfts:    DOUBLE
  61. Qsqrrt:     DOUBLE
  62. Qsqrrto:    DOUBLE
  63.     PROGRAM
  64.     JUMP    Q_shell
  65. Qmain:  PROC
  66.     VAR
  67.     BEGIN
  68.     MOVQ.D  0,R6
  69.     MOV.D   R6,Qndivs
  70.     MOV.D   R6,Qnshfts
  71.     MOV.D   100,Qsqrrto
  72.     MOVQ.D  0,Qnumber
  73. Q1:     CMP.D   60000,Qnumber
  74.     BLT.S   Q3
  75. Q2:    MOV.D   Qnumber,TOS
  76.     BSR     Qsqrt
  77.     MOV.D   R6,Qsqrrt
  78.     CMP.D   Qsqrrto,Qsqrrt
  79.     BEQ.S   Q5
  80. Q4:    MOV.D   Qsqrrt,TOS
  81.     MOV.D   Qnumber,TOS
  82.     ADDR    Z6,TOS
  83.     JSR    Qprintf
  84.     ADJSP    -8
  85. Q5:    MOV.D    Qsqrrt,Qsqrrto
  86.     ADDQ.D    1,Qnumber
  87.     BR.S    Q1
  88. Q3:    MOV.D    10,R6
  89.     MUL.D    Qndivs,R6
  90.     QUO.D    60000,R6
  91.     MOV.D    R6,TOS
  92.     MOV.D    Qndivs,TOS
  93.     ADDR    Z6+13,TOS
  94.     JSR    Qprintf
  95.     ADJSP    -8
  96.     MOV.D    Qnshfts,R6
  97.     QUO.D    60000,R6
  98.     MOV.D    R6,TOS
  99.     MOV.D    Qnshfts,TOS
  100.     ADDR    Z6+46,TOS
  101.     JSR    Qprintf
  102.     ADJSP    -8
  103.     ENDPROC
  104. Z6:    BYTE    115,113,114,32,37,53,100,61,37,51,100,32
  105.     BYTE    0,10,84,111,116,32,68,105,118,115,61,37
  106.     BYTE    51,117,32,65,118,101,32,68,105,118,115,46
  107.     BYTE    40,120,49,48,41,61,37,50,117,0,10,84
  108.     BYTE    111,116,32,83,104,102,116,115,61,37,51,117
  109.     BYTE    32,65,118,101,32,83,104,102,116,115,46,61
  110.     BYTE    37,50,117,0
  111.  
  112. Listing Three
  113.  
  114. Qsqrt:    PROC        ;square root, dividing version
  115. Znumb:    DOUBLE        ;registers R0, R6 & R7 used by compiler
  116.     VAR        ;registers R1 - R5 for register variables
  117.     BEGIN    <R4,R3,R2,R1,>  ;push used registers
  118. ;    BR    Q15        ;for timing
  119.     MOV.D    Znumb,R1    ;get number into R1
  120.     CMPQ.D    0,R1        ;is number zero?
  121.     BEQ Q8               ;mustn't divide by zero
  122. Q7:    MOVQ.D    1,R2        ;guess1 = 1
  123.     MOV.D    R1,R3        ;guess2 = number
  124. Q9:    MOV.D    R2,R6        ;load guess1
  125.     ASH.D    1,R6        ;guess1 << 1
  126.     CMP.D    R3,R6        ;compare with guess2
  127.     BLE.S    Q11        ;while ( (guess1 << 1) < guess2 )
  128. Q10:    ASH.D    1,R2        ;guess1 <<= 1
  129.     ASH.D    -1,R3        ;guess2 >>= 1
  130.     BR.S    Q9        ;see if done
  131. Q11:
  132. Q13:    ADD.D    R3,R2        ;guess1 += guess2
  133.     ASH.D    -1,R2        ;guess1 /= 2
  134.     MOV.D     R1,R6        ;numb
  135.     QUO.D    R2,R6        ;numb / guess1
  136.     MOV.D    R6,R3        ;guess2 = numb / guess1
  137.     MOV.D     R2,R6
  138.     SUB.D    R3,R6
  139.     MOV.D    R6,R4        ;error = guess1 - guess2
  140.     CMPQ.D    0,R4
  141.     BGE.S    Q14        ;while ( error > 0 )
  142.     BR.S    Q13
  143. Q14:    MOV.D     R2,R6        ;return guess1
  144.     BR.S     Q15
  145. Q8:    MOVQ.D    0,R6        ;return 0
  146. Q16:
  147. Q15:    ENDPROC            ;exit
  148.     IMPORT     Q_shell 00
  149.     IMPORT    Qprintf 01
  150.     END ;SCN, 03/22//85
  151.  
  152. Listing Four
  153.  
  154. Qsqrt:     PROC            ;square root, bit-shifting version
  155. Znumb:  DOUBLE
  156.     VAR
  157.     BEGIN    <R4,R3,R1,> ;push registers used
  158. ;    BR.S    SQRTZ        ;for timing
  159.     MOV.D    Znumb,R0    ;number to R0
  160.     MOVQ.D    0,R1        ;estimate = 0
  161.     MOVQ.D  0,R6        ;trial root = 0
  162.     MOV.B    16,R4        ;loop count
  163. SQRTL:  ROT.D    2,R0        ;2 msb's to 2 lsb's of number
  164.     MOV.B    R0,R3        ;get shifted number in R3
  165.     AND.B    3,R3        ;isolate 2 lsb's of R3
  166.     ASH.D    2,R1        ;shift estimate
  167.     OR.B    R3,R1        ;OR 2 lsb's into estimate
  168.     ASH.D    1,R6        ;shift trial root
  169.     MOV.D    R6,R3        ;get trial root
  170.     ASH.D    1,R3        ;trial root * 2
  171.     CMP.D    R1,R3        ;compare to estimate
  172.     BLS.S    SQRT2        ;need a bit?
  173.     ADDQ.D    1,R6        ;add to trial root
  174.     ADDQ.D    1,R3        ;add to estimate
  175.     SUB.D    R3,R1        ;adjust estimate
  176. SQRT2:    ACB.S    -1,R4,SQRTL ;count down, loop
  177. SQRTZ:  ENDPROC            ;return root, in R6
  178.