home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / graphics / 14240 < prev    next >
Encoding:
Text File  |  1993-01-27  |  3.2 KB  |  140 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.univie.ac.at!scsing.switch.ch!dxcern!marmac2.in2p3.fr!user
  3. From: Meessen@marvax.IN2P3.fr (Meessen Christophe)
  4. Subject: Re: Fixed point sqrt anyone?
  5. Message-ID: <Meessen-270193133948@marmac2.in2p3.fr>
  6. Followup-To: comp.os.os2.programmer,comp.graphics,comp.os.msdos.programmer,comp.sys.ibm.pc.programmer,comp.lang.c
  7. Sender: news@dxcern.cern.ch (USENET News System)
  8. Organization: Centre de Physique des Particules de Marseille
  9. References: <1idsq6INNced@flop.ENGR.ORST.EDU> <VJ.93Jan19115116@dlsi.dl.ac.uk>
  10. Date: Wed, 27 Jan 1993 14:02:48 GMT
  11. Lines: 127
  12.  
  13. In article <VJ.93Jan19115116@dlsi.dl.ac.uk>, vj@gserv1.dl.ac.uk (Dave
  14. Hines) wrote:
  15. > 
  16. > > Well? Does anyone know of a quick and dirty way to get a reasonably accurate
  17. > > square root of a fixed point integer number?
  18. > 
  19. > Hmmm - I have a long integer square root routine. 
  20.  
  21. Dave Hines proposed a sqrt function receiving an unsigned long (X) and
  22. returning
  23. an unsigned long. The remainder, an unsigned long, is accessible as
  24. 'result2'.
  25. The algorithm uses 4 unsigned long variables. 
  26. Thus it's a long -> long function.
  27.  
  28.  
  29. I suggest two algorithms using the same variables. The first one will
  30. compute a sqrt of a long, returning a fixed point value. The second will
  31. compute the sqrt of a fixed point value, returning a fixed point value.
  32. Thus it's a long -> fixed or fixed -> fixed function.
  33.  
  34. We will suppose a fixed is equivalent to a long, and longs are 32 bits
  35. wide.
  36.  
  37. /*
  38.  * fixed sqrtL2F( long X );
  39.  *
  40.  * Long to fixed point square roots. 
  41.  * RETURNS the fixed point square root of X (long).
  42.  * REQUIRES X is positive.
  43.  *
  44.  * Christophe MEESSEN, 1993.
  45.  */
  46.  
  47. fixed sqrtL2F( long X ) {
  48.  
  49.   unsigned long t, q, b, r;
  50.  
  51.   r = X;
  52.   b = 0x40000000;
  53.   q = 0;
  54.  
  55.   while( b > 0 ) {
  56.     t = q + b;
  57.     if( r >= t ) {
  58.       r = r - t;
  59.       q = t + b;
  60.     }
  61.     r = r * 2;     /* shift left  1 bit */
  62.     b = b / 2;     /* shift right 1 bit */
  63.   }
  64.   if( r >= q )
  65.     q = q + 1;
  66.  
  67.   return( q );
  68. }
  69.  
  70.  
  71. /*
  72.  * fixed sqrtF2F( fixed X );
  73.  *
  74.  * Fixed to fixed point square roots. 
  75.  * RETURNS the fixed point square root of X (fixed).
  76.  * REQUIRES X is positive.
  77.  *
  78.  * Christophe MEESSEN, 1993.
  79.  */
  80.  
  81. fixed sqrtF2F ( fixed X ) {
  82.  
  83.   unsigned long t, q, b, r;
  84.  
  85.   r = X;
  86.   b = 0x40000000;
  87.   q = 0;
  88.  
  89.   while( b >= 256 ) {
  90.     t = q + b;
  91.     if( r >= t ) {
  92.       r = r - t;
  93.       q = t + b;
  94.     }
  95.     r = r * 2;     /* shift left  1 bit */
  96.     b = b / 2;     /* shift right 1 bit */
  97.   }
  98.   q = q / 256;     /* shift right 8 bits */
  99.  
  100.   return( q );
  101. }
  102.  
  103. for memory I just rewrote the long to long sqrt function.
  104.  
  105. /*
  106.  * long sqrtL2L( long X );
  107.  *
  108.  * Long to long point square roots. 
  109.  * RETURNS the integer square root of X (long).
  110.  * REMAINDER is in the local variable r of type long on return.  
  111.  * REQUIRES X is positive.
  112.  *
  113.  * Christophe MEESSEN, 1993.
  114.  */
  115.  
  116. long sqrtL2L( long X ) {
  117.  
  118.   unsigned long t, q, b, r;
  119.  
  120.   r = X;
  121.   b = 0x40000000;
  122.   q = 0;
  123.  
  124.   while( b >= 256 ) {
  125.     t = q + b;
  126.     q = q / 2;     /* shift right 1 bit */
  127.     if( r >= t ) {
  128.       r = r - t;
  129.       q = q + b;
  130.     }
  131.     b = b / 4;     /* shift right 2 bits */
  132.   }
  133.  
  134.   return( q );
  135. }
  136.  
  137. This functions have been tested. But I'll be pleased to receive any
  138. comments.
  139. Please respond through mail: Meessen@marvax.in2p3.fr
  140.