home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13599 < prev    next >
Encoding:
Text File  |  1993-01-09  |  2.0 KB  |  64 lines
  1. Path: sparky!uunet!caen!uflorida!gmt
  2. From: gmt@beach.cis.ufl.edu (Gary McTaggart)
  3. Newsgroups: comp.graphics
  4. Subject: RE: fixed-point square root
  5. Message-ID: <38189@uflorida.cis.ufl.edu>
  6. Date: 9 Jan 93 17:25:38 GMT
  7. Sender: news@uflorida.cis.ufl.edu
  8. Organization: Univ. of Florida CIS Dept.
  9. Lines: 52
  10. Nntp-Posting-Host: beach.cis.ufl.edu
  11.  
  12. murrayk@prism.CS.ORST.EDU (the Dodger) writes:
  13. >Well? Does anyone know of a quick and dirty way to get a reasonably accurate
  14. >square root of a fixed point integer number? My numbers are stored in a 16.16
  15. >bit format. I've heard of a few ways, but I'm open for ideas. I just want to
  16. >keep on avoiding floating point for ethical reasons. 8^)
  17.  
  18. I wrote a routine a while back to do an integer square-root using a lookup
  19. table.  This routine (below) could be modified to do a fixed-point sqrt by
  20. subtracting 16 (for you case of 16.16 fixed point numbers) from the final
  21. right shift.  If you have any problems or suggestions for improvement,
  22. please mail me.  
  23.  
  24. --Gary McTaggart
  25.  
  26. PS:
  27. I chose to use a relatively small sqrt table because accuracy was not
  28. important.  The table could be boosted up to a larger size for more accuracy.
  29.  
  30. ----------------------------------------------------------------------
  31.  
  32. #include <math.h>
  33.  
  34. /* Create a type for a 32 bit unsigned integer. */
  35. typedef unsigned long UINT32;
  36.  
  37. /* These hard-coded numbers are here because of a brain-dead compiler which 
  38.    would not resolve constant expressions at compile time. */
  39. #define ONE_SHL_31 2147483648UL
  40. #define ONE_SHL_30 1073741824UL
  41.  
  42. UINT32 sqrt_table[256];
  43.  
  44. void init_sqrt_table(void)
  45.   {
  46.     unsigned long int i;
  47.  
  48.     for (i = 0; i < 256; i++)
  49.         sqrt_table[i] = sqrt((double) ((UINT32)i << 24) );
  50.   }
  51.  
  52. /* --------------------------INTEGER SQUARE ROOT------------------------*/
  53. UINT32 int_sqrt(UINT32 in)
  54.   {
  55.     int lsh = 0;
  56.  
  57.     while (!( (in << lsh) & ( (UINT32) ONE_SHL_30 ) ) )
  58.         lsh++;
  59.     if (lsh % 2)
  60.         lsh++;
  61.  
  62.     return (sqrt_table[( (UINT32)in << lsh) >> 24]) >> ((lsh) / 2);
  63.   }
  64.