sdl-ios-xcode: src/video/e

annotate src/video/e_sqrt.h @ 4216:5b99971a27b4 SDL-1.2

Fixed bug #698 Hans de Goede 2009-02-13 01:10:52 PST Since the new "glitch free" version of pulseaudio (used in Fedora 10 amongst others), the sound of SDL using apps (like a simple playmus call) has been crackling. While looking in to fixing this I noticed that the current pulseaudio code in SDL uses pa_simple. However pa_simple uses a thread to pump pulseaudio events and ipc, given that SDL already has its own thread for audio handling this is clearly suboptimal, leading to unnecessary context switching IPC, etc. Also pa_simple does not allow one to implement the WaitAudio() callback for SDL audiodrivers properly. Given that my work is mostly a rewrite (although some original pieces remain) I'm attaching the new .c and .h file, as that is easier to review then the huge diff. Let me know if you also want the diff. This new version has the following features: -no longer use an additional thread next to the SDL sound thread -do not crackle with glitch free audio -when used with a newer pulse, which does glitch free audio, the total latency is the same as with the alsa driver -proper WaitAudio() implementation, saving another mixlen worth of latency -adds a WaitDone() implementation This patch has been written in consultancy with Lennart Poetering (the pulseaudio author) and has been reviewed by him for correct use of the pa API.

author	Sam Lantinga <slouken@libsdl.org>
date	Mon, 21 Sep 2009 09:27:08 +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 = 2q , 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 tinyx; /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 hugeSDL_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 hugeSDL_NAME(copysign)(huge,x); /overflow*/
7a610f25c12f Updated MacOS Classic MPW build Sam Lantinga <slouken@libsdl.org> parents: 1345 diff changeset	129 else return tinySDL_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 xx+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.5xyy) ... 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.5xyy)... 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 := xy ... 29 bits to sqrt(x), with zy<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.5z(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+2ulp; 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

Mercurial > sdl-ios-xcode

annotate src/video/e_sqrt.h @ 4216:5b99971a27b4 SDL-1.2