annotate src/video/e_sqrt.h @ 3932:cd5b5c52a37e SDL-1.2

Const correctness patch for SDL_MapRGB and SDL_MapRGBA. Fixes Bugzilla #421.
author Ryan C. Gordon <icculus@icculus.org>
date Wed, 04 Apr 2007 09:40:40 +0000
parents 7a610f25c12f
children 782fd950bd46 c121d94672cb
rev   line source
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
1 /* @(#)e_sqrt.c 5.1 93/09/24 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
2 /*
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
3 * ====================================================
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
4 * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
5 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
6 * Developed at SunPro, a Sun Microsystems, Inc. business.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
7 * Permission to use, copy, modify, and distribute this
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
8 * software is freely granted, provided that this notice
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
9 * is preserved.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
10 * ====================================================
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
11 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
12
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
13 #if defined(LIBM_SCCS) && !defined(lint)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
14 static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $";
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
15 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
16
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
17 /* __ieee754_sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
18 * Return correctly rounded sqrt.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
19 * ------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
20 * | Use the hardware sqrt if you have one |
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
21 * ------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
22 * Method:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
23 * Bit by bit method using integer arithmetic. (Slow, but portable)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
24 * 1. Normalization
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
25 * Scale x to y in [1,4) with even powers of 2:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
26 * find an integer k such that 1 <= (y=x*2^(2k)) < 4, then
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
27 * sqrt(x) = 2^k * sqrt(y)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
28 * 2. Bit by bit computation
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
29 * Let q = sqrt(y) truncated to i bit after binary point (q = 1),
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
30 * i 0
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
31 * i+1 2
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
32 * s = 2*q , and y = 2 * ( y - q ). (1)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
33 * i i i i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
34 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
35 * To compute q from q , one checks whether
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
36 * i+1 i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
37 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
38 * -(i+1) 2
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
39 * (q + 2 ) <= y. (2)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
40 * i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
41 * -(i+1)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
42 * If (2) is false, then q = q ; otherwise q = q + 2 .
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
43 * i+1 i i+1 i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
44 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
45 * With some algebric manipulation, it is not difficult to see
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
46 * that (2) is equivalent to
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
47 * -(i+1)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
48 * s + 2 <= y (3)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
49 * i i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
50 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
51 * The advantage of (3) is that s and y can be computed by
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
52 * i i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
53 * the following recurrence formula:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
54 * if (3) is false
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
55 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
56 * s = s , y = y ; (4)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
57 * i+1 i i+1 i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
58 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
59 * otherwise,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
60 * -i -(i+1)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
61 * s = s + 2 , y = y - s - 2 (5)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
62 * i+1 i i+1 i i
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
63 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
64 * One may easily use induction to prove (4) and (5).
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
65 * Note. Since the left hand side of (3) contain only i+2 bits,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
66 * it does not necessary to do a full (53-bit) comparison
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
67 * in (3).
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
68 * 3. Final rounding
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
69 * After generating the 53 bits result, we compute one more bit.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
70 * Together with the remainder, we can decide whether the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
71 * result is exact, bigger than 1/2ulp, or less than 1/2ulp
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
72 * (it will never equal to 1/2ulp).
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
73 * The rounding mode can be detected by checking whether
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
74 * huge + tiny is equal to huge, and whether huge - tiny is
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
75 * equal to huge for some floating point number "huge" and "tiny".
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
76 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
77 * Special cases:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
78 * sqrt(+-0) = +-0 ... exact
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
79 * sqrt(inf) = inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
80 * sqrt(-ve) = NaN ... with invalid signal
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
81 * sqrt(NaN) = NaN ... with invalid signal for signaling NaN
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
82 *
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
83 * Other methods : see the appended file at the end of the program below.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
84 *---------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
85 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
86
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
87 /*#include "math.h"*/
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
88 #include "math_private.h"
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
89
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
90 #ifdef __STDC__
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
91 double SDL_NAME(copysign)(double x, double y)
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
92 #else
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
93 double SDL_NAME(copysign)(x,y)
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
94 double x,y;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
95 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
96 {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
97 u_int32_t hx,hy;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
98 GET_HIGH_WORD(hx,x);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
99 GET_HIGH_WORD(hy,y);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
100 SET_HIGH_WORD(x,(hx&0x7fffffff)|(hy&0x80000000));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
101 return x;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
102 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
103
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
104 #ifdef __STDC__
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
105 double SDL_NAME(scalbn) (double x, int n)
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
106 #else
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
107 double SDL_NAME(scalbn) (x,n)
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
108 double x; int n;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
109 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
110 {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
111 int32_t k,hx,lx;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
112 EXTRACT_WORDS(hx,lx,x);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
113 k = (hx&0x7ff00000)>>20; /* extract exponent */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
114 if (k==0) { /* 0 or subnormal x */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
115 if ((lx|(hx&0x7fffffff))==0) return x; /* +-0 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
116 x *= two54;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
117 GET_HIGH_WORD(hx,x);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
118 k = ((hx&0x7ff00000)>>20) - 54;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
119 if (n< -50000) return tiny*x; /*underflow*/
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
120 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
121 if (k==0x7ff) return x+x; /* NaN or Inf */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
122 k = k+n;
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
123 if (k > 0x7fe) return huge*SDL_NAME(copysign)(huge,x); /* overflow */
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
124 if (k > 0) /* normal result */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
125 {SET_HIGH_WORD(x,(hx&0x800fffff)|(k<<20)); return x;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
126 if (k <= -54) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
127 if (n > 50000) /* in case integer overflow in n+k */
1424
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
128 return huge*SDL_NAME(copysign)(huge,x); /*overflow*/
7a610f25c12f Updated MacOS Classic MPW build
Sam Lantinga <slouken@libsdl.org>
parents: 1345
diff changeset
129 else return tiny*SDL_NAME(copysign)(tiny,x); /*underflow*/
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
130 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
131 k += 54; /* subnormal result */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
132 SET_HIGH_WORD(x,(hx&0x800fffff)|(k<<20));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
133 return x*twom54;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
134 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
135
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
136 #ifdef __STDC__
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
137 double __ieee754_sqrt(double x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
138 #else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
139 double __ieee754_sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
140 double x;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
141 #endif
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
142 {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
143 double z;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
144 int32_t sign = (int)0x80000000;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
145 int32_t ix0,s0,q,m,t,i;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
146 u_int32_t r,t1,s1,ix1,q1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
147
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
148 EXTRACT_WORDS(ix0,ix1,x);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
149
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
150 /* take care of Inf and NaN */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
151 if((ix0&0x7ff00000)==0x7ff00000) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
152 return x*x+x; /* sqrt(NaN)=NaN, sqrt(+inf)=+inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
153 sqrt(-inf)=sNaN */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
154 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
155 /* take care of zero */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
156 if(ix0<=0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
157 if(((ix0&(~sign))|ix1)==0) return x;/* sqrt(+-0) = +-0 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
158 else if(ix0<0)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
159 return (x-x)/(x-x); /* sqrt(-ve) = sNaN */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
160 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
161 /* normalize x */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
162 m = (ix0>>20);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
163 if(m==0) { /* subnormal x */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
164 while(ix0==0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
165 m -= 21;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
166 ix0 |= (ix1>>11); ix1 <<= 21;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
167 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
168 for(i=0;(ix0&0x00100000)==0;i++) ix0<<=1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
169 m -= i-1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
170 ix0 |= (ix1>>(32-i));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
171 ix1 <<= i;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
172 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
173 m -= 1023; /* unbias exponent */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
174 ix0 = (ix0&0x000fffff)|0x00100000;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
175 if(m&1){ /* odd m, double x to make it even */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
176 ix0 += ix0 + ((ix1&sign)>>31);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
177 ix1 += ix1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
178 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
179 m >>= 1; /* m = [m/2] */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
180
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
181 /* generate sqrt(x) bit by bit */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
182 ix0 += ix0 + ((ix1&sign)>>31);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
183 ix1 += ix1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
184 q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
185 r = 0x00200000; /* r = moving bit from right to left */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
186
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
187 while(r!=0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
188 t = s0+r;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
189 if(t<=ix0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
190 s0 = t+r;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
191 ix0 -= t;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
192 q += r;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
193 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
194 ix0 += ix0 + ((ix1&sign)>>31);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
195 ix1 += ix1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
196 r>>=1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
197 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
198
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
199 r = sign;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
200 while(r!=0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
201 t1 = s1+r;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
202 t = s0;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
203 if((t<ix0)||((t==ix0)&&(t1<=ix1))) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
204 s1 = t1+r;
1345
7f32b9bede06 Fixes for Visual C++ 6.0
Sam Lantinga <slouken@libsdl.org>
parents: 1330
diff changeset
205 if(((int32_t)(t1&sign)==sign)&&(s1&sign)==0) s0 += 1;
1330
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
206 ix0 -= t;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
207 if (ix1 < t1) ix0 -= 1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
208 ix1 -= t1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
209 q1 += r;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
210 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
211 ix0 += ix0 + ((ix1&sign)>>31);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
212 ix1 += ix1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
213 r>>=1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
214 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
215
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
216 /* use floating add to find out rounding direction */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
217 if((ix0|ix1)!=0) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
218 z = one-tiny; /* trigger inexact flag */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
219 if (z>=one) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
220 z = one+tiny;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
221 if (q1==(u_int32_t)0xffffffff) { q1=0; q += 1;}
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
222 else if (z>one) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
223 if (q1==(u_int32_t)0xfffffffe) q+=1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
224 q1+=2;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
225 } else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
226 q1 += (q1&1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
227 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
228 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
229 ix0 = (q>>1)+0x3fe00000;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
230 ix1 = q1>>1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
231 if ((q&1)==1) ix1 |= sign;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
232 ix0 += (m <<20);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
233 INSERT_WORDS(z,ix0,ix1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
234 return z;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
235 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
236
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
237 /*
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
238 Other methods (use floating-point arithmetic)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
239 -------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
240 (This is a copy of a drafted paper by Prof W. Kahan
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
241 and K.C. Ng, written in May, 1986)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
242
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
243 Two algorithms are given here to implement sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
244 (IEEE double precision arithmetic) in software.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
245 Both supply sqrt(x) correctly rounded. The first algorithm (in
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
246 Section A) uses newton iterations and involves four divisions.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
247 The second one uses reciproot iterations to avoid division, but
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
248 requires more multiplications. Both algorithms need the ability
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
249 to chop results of arithmetic operations instead of round them,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
250 and the INEXACT flag to indicate when an arithmetic operation
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
251 is executed exactly with no roundoff error, all part of the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
252 standard (IEEE 754-1985). The ability to perform shift, add,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
253 subtract and logical AND operations upon 32-bit words is needed
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
254 too, though not part of the standard.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
255
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
256 A. sqrt(x) by Newton Iteration
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
257
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
258 (1) Initial approximation
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
259
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
260 Let x0 and x1 be the leading and the trailing 32-bit words of
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
261 a floating point number x (in IEEE double format) respectively
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
262
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
263 1 11 52 ...widths
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
264 ------------------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
265 x: |s| e | f |
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
266 ------------------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
267 msb lsb msb lsb ...order
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
268
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
269
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
270 ------------------------ ------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
271 x0: |s| e | f1 | x1: | f2 |
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
272 ------------------------ ------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
273
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
274 By performing shifts and subtracts on x0 and x1 (both regarded
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
275 as integers), we obtain an 8-bit approximation of sqrt(x) as
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
276 follows.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
277
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
278 k := (x0>>1) + 0x1ff80000;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
279 y0 := k - T1[31&(k>>15)]. ... y ~ sqrt(x) to 8 bits
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
280 Here k is a 32-bit integer and T1[] is an integer array containing
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
281 correction terms. Now magically the floating value of y (y's
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
282 leading 32-bit word is y0, the value of its trailing word is 0)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
283 approximates sqrt(x) to almost 8-bit.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
284
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
285 Value of T1:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
286 static int T1[32]= {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
287 0, 1024, 3062, 5746, 9193, 13348, 18162, 23592,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
288 29598, 36145, 43202, 50740, 58733, 67158, 75992, 85215,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
289 83599, 71378, 60428, 50647, 41945, 34246, 27478, 21581,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
290 16499, 12183, 8588, 5674, 3403, 1742, 661, 130,};
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
291
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
292 (2) Iterative refinement
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
293
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
294 Apply Heron's rule three times to y, we have y approximates
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
295 sqrt(x) to within 1 ulp (Unit in the Last Place):
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
296
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
297 y := (y+x/y)/2 ... almost 17 sig. bits
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
298 y := (y+x/y)/2 ... almost 35 sig. bits
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
299 y := y-(y-x/y)/2 ... within 1 ulp
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
300
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
301
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
302 Remark 1.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
303 Another way to improve y to within 1 ulp is:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
304
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
305 y := (y+x/y) ... almost 17 sig. bits to 2*sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
306 y := y - 0x00100006 ... almost 18 sig. bits to sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
307
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
308 2
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
309 (x-y )*y
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
310 y := y + 2* ---------- ...within 1 ulp
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
311 2
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
312 3y + x
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
313
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
314
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
315 This formula has one division fewer than the one above; however,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
316 it requires more multiplications and additions. Also x must be
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
317 scaled in advance to avoid spurious overflow in evaluating the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
318 expression 3y*y+x. Hence it is not recommended uless division
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
319 is slow. If division is very slow, then one should use the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
320 reciproot algorithm given in section B.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
321
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
322 (3) Final adjustment
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
323
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
324 By twiddling y's last bit it is possible to force y to be
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
325 correctly rounded according to the prevailing rounding mode
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
326 as follows. Let r and i be copies of the rounding mode and
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
327 inexact flag before entering the square root program. Also we
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
328 use the expression y+-ulp for the next representable floating
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
329 numbers (up and down) of y. Note that y+-ulp = either fixed
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
330 point y+-1, or multiply y by nextafter(1,+-inf) in chopped
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
331 mode.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
332
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
333 I := FALSE; ... reset INEXACT flag I
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
334 R := RZ; ... set rounding mode to round-toward-zero
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
335 z := x/y; ... chopped quotient, possibly inexact
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
336 If(not I) then { ... if the quotient is exact
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
337 if(z=y) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
338 I := i; ... restore inexact flag
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
339 R := r; ... restore rounded mode
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
340 return sqrt(x):=y.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
341 } else {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
342 z := z - ulp; ... special rounding
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
343 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
344 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
345 i := TRUE; ... sqrt(x) is inexact
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
346 If (r=RN) then z=z+ulp ... rounded-to-nearest
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
347 If (r=RP) then { ... round-toward-+inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
348 y = y+ulp; z=z+ulp;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
349 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
350 y := y+z; ... chopped sum
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
351 y0:=y0-0x00100000; ... y := y/2 is correctly rounded.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
352 I := i; ... restore inexact flag
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
353 R := r; ... restore rounded mode
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
354 return sqrt(x):=y.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
355
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
356 (4) Special cases
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
357
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
358 Square root of +inf, +-0, or NaN is itself;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
359 Square root of a negative number is NaN with invalid signal.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
360
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
361
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
362 B. sqrt(x) by Reciproot Iteration
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
363
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
364 (1) Initial approximation
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
365
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
366 Let x0 and x1 be the leading and the trailing 32-bit words of
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
367 a floating point number x (in IEEE double format) respectively
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
368 (see section A). By performing shifs and subtracts on x0 and y0,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
369 we obtain a 7.8-bit approximation of 1/sqrt(x) as follows.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
370
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
371 k := 0x5fe80000 - (x0>>1);
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
372 y0:= k - T2[63&(k>>14)]. ... y ~ 1/sqrt(x) to 7.8 bits
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
373
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
374 Here k is a 32-bit integer and T2[] is an integer array
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
375 containing correction terms. Now magically the floating
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
376 value of y (y's leading 32-bit word is y0, the value of
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
377 its trailing word y1 is set to zero) approximates 1/sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
378 to almost 7.8-bit.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
379
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
380 Value of T2:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
381 static int T2[64]= {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
382 0x1500, 0x2ef8, 0x4d67, 0x6b02, 0x87be, 0xa395, 0xbe7a, 0xd866,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
383 0xf14a, 0x1091b,0x11fcd,0x13552,0x14999,0x15c98,0x16e34,0x17e5f,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
384 0x18d03,0x19a01,0x1a545,0x1ae8a,0x1b5c4,0x1bb01,0x1bfde,0x1c28d,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
385 0x1c2de,0x1c0db,0x1ba73,0x1b11c,0x1a4b5,0x1953d,0x18266,0x16be0,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
386 0x1683e,0x179d8,0x18a4d,0x19992,0x1a789,0x1b445,0x1bf61,0x1c989,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
387 0x1d16d,0x1d77b,0x1dddf,0x1e2ad,0x1e5bf,0x1e6e8,0x1e654,0x1e3cd,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
388 0x1df2a,0x1d635,0x1cb16,0x1be2c,0x1ae4e,0x19bde,0x1868e,0x16e2e,
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
389 0x1527f,0x1334a,0x11051,0xe951, 0xbe01, 0x8e0d, 0x5924, 0x1edd,};
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
390
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
391 (2) Iterative refinement
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
392
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
393 Apply Reciproot iteration three times to y and multiply the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
394 result by x to get an approximation z that matches sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
395 to about 1 ulp. To be exact, we will have
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
396 -1ulp < sqrt(x)-z<1.0625ulp.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
397
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
398 ... set rounding mode to Round-to-nearest
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
399 y := y*(1.5-0.5*x*y*y) ... almost 15 sig. bits to 1/sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
400 y := y*((1.5-2^-30)+0.5*x*y*y)... about 29 sig. bits to 1/sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
401 ... special arrangement for better accuracy
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
402 z := x*y ... 29 bits to sqrt(x), with z*y<1
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
403 z := z + 0.5*z*(1-z*y) ... about 1 ulp to sqrt(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
404
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
405 Remark 2. The constant 1.5-2^-30 is chosen to bias the error so that
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
406 (a) the term z*y in the final iteration is always less than 1;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
407 (b) the error in the final result is biased upward so that
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
408 -1 ulp < sqrt(x) - z < 1.0625 ulp
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
409 instead of |sqrt(x)-z|<1.03125ulp.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
410
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
411 (3) Final adjustment
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
412
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
413 By twiddling y's last bit it is possible to force y to be
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
414 correctly rounded according to the prevailing rounding mode
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
415 as follows. Let r and i be copies of the rounding mode and
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
416 inexact flag before entering the square root program. Also we
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
417 use the expression y+-ulp for the next representable floating
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
418 numbers (up and down) of y. Note that y+-ulp = either fixed
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
419 point y+-1, or multiply y by nextafter(1,+-inf) in chopped
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
420 mode.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
421
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
422 R := RZ; ... set rounding mode to round-toward-zero
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
423 switch(r) {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
424 case RN: ... round-to-nearest
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
425 if(x<= z*(z-ulp)...chopped) z = z - ulp; else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
426 if(x<= z*(z+ulp)...chopped) z = z; else z = z+ulp;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
427 break;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
428 case RZ:case RM: ... round-to-zero or round-to--inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
429 R:=RP; ... reset rounding mod to round-to-+inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
430 if(x<z*z ... rounded up) z = z - ulp; else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
431 if(x>=(z+ulp)*(z+ulp) ...rounded up) z = z+ulp;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
432 break;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
433 case RP: ... round-to-+inf
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
434 if(x>(z+ulp)*(z+ulp)...chopped) z = z+2*ulp; else
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
435 if(x>z*z ...chopped) z = z+ulp;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
436 break;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
437 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
438
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
439 Remark 3. The above comparisons can be done in fixed point. For
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
440 example, to compare x and w=z*z chopped, it suffices to compare
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
441 x1 and w1 (the trailing parts of x and w), regarding them as
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
442 two's complement integers.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
443
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
444 ...Is z an exact square root?
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
445 To determine whether z is an exact square root of x, let z1 be the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
446 trailing part of z, and also let x0 and x1 be the leading and
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
447 trailing parts of x.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
448
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
449 If ((z1&0x03ffffff)!=0) ... not exact if trailing 26 bits of z!=0
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
450 I := 1; ... Raise Inexact flag: z is not exact
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
451 else {
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
452 j := 1 - [(x0>>20)&1] ... j = logb(x) mod 2
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
453 k := z1 >> 26; ... get z's 25-th and 26-th
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
454 fraction bits
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
455 I := i or (k&j) or ((k&(j+j+1))!=(x1&3));
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
456 }
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
457 R:= r ... restore rounded mode
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
458 return sqrt(x):=z.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
459
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
460 If multiplication is cheaper then the foregoing red tape, the
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
461 Inexact flag can be evaluated by
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
462
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
463 I := i;
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
464 I := (z*z!=x) or I.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
465
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
466 Note that z*z can overwrite I; this value must be sensed if it is
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
467 True.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
468
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
469 Remark 4. If z*z = x exactly, then bit 25 to bit 0 of z1 must be
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
470 zero.
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
471
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
472 --------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
473 z1: | f2 |
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
474 --------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
475 bit 31 bit 0
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
476
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
477 Further more, bit 27 and 26 of z1, bit 0 and 1 of x1, and the odd
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
478 or even of logb(x) have the following relations:
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
479
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
480 -------------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
481 bit 27,26 of z1 bit 1,0 of x1 logb(x)
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
482 -------------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
483 00 00 odd and even
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
484 01 01 even
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
485 10 10 odd
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
486 10 00 even
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
487 11 01 even
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
488 -------------------------------------------------
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
489
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
490 (4) Special cases (see (4) of Section A).
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
491
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
492 */
450721ad5436 It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff changeset
493