Re: correctly rounded sqrt

[Szabolcs Nagy <nsz@port70.net>]

[-- Attachment #1: Type: text/plain, Size: 111 bytes --]

* Szabolcs Nagy <nsz@port70.net> [2012-03-14 17:56:05 +0100]:
> ..and the code might be slow

forgot to attach

[-- Attachment #2: sqrt.c --]
[-- Type: text/x-csrc, Size: 5142 bytes --]

#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <float.h>

#include <mpfr.h>
#include <gmp.h>

/*
int read(double *x, double *y) {
	char buf[256];

	if (!fgets(buf, sizeof buf, stdin))
		return 0;
	if (sscanf(buf, "%la %la", x, y) != 2)
		return 0;
	return 1;
}
*/

struct {
	double x,y;
} testdata[] = {
//	#include "sqrt.data"
0x1.fffffffffffffp+1023, 0x1.fffffffffffffp+511,
0x1.ffffffffffffbp+1023, 0x1.ffffffffffffdp+511,
0x1.ffffffffffff7p+1023, 0x1.ffffffffffffbp+511,
0x1.ffffffffffff3p+1023, 0x1.ffffffffffff9p+511,
0x1.fffffffffffefp+1023, 0x1.ffffffffffff7p+511,
0x1.fffffffffffebp+1023, 0x1.ffffffffffff5p+511,
0x1.fffffffffffe7p+1023, 0x1.ffffffffffff3p+511,
0x1.fffffffffffe3p+1023, 0x1.ffffffffffff1p+511,
0x1.fffffffffffdfp+1023, 0x1.fffffffffffefp+511,
0x1.fffffffffffdbp+1023, 0x1.fffffffffffedp+511,
0x1.fffffffffffd7p+1023, 0x1.fffffffffffebp+511,
0x1.0000000000003p-1022, 0x1.0000000000001p-511,
0x1.0000000000007p-1022, 0x1.0000000000003p-511,
0x1.000000000000bp-1022, 0x1.0000000000005p-511,
0x1.000000000000fp-1022, 0x1.0000000000007p-511,
0x1.0000000000013p-1022, 0x1.0000000000009p-511,
0x1.0000000000017p-1022, 0x1.000000000000bp-511,
0x1.000000000001bp-1022, 0x1.000000000000dp-511,
0x1.000000000001fp-1022, 0x1.000000000000fp-511,
0x1.0000000000023p-1022, 0x1.0000000000011p-511,
0x1.0000000000027p-1022, 0x1.0000000000013p-511,
0x1.000000000002bp-1022, 0x1.0000000000015p-511,
0x1.000000000002fp-1022, 0x1.0000000000017p-511,
0x1.0000000000033p-1022, 0x1.0000000000019p-511,
0x1.0000000000037p-1022, 0x1.000000000001bp-511,
0x1.7167bc36eaa3bp+6, 0x1.3384c7db650cdp+3,
0x1.7570994273ad7p+6, 0x1.353186e89b8ffp+3,
0x1.7dae969442fe6p+6, 0x1.389640fb18b75p+3,
0x1.7f8444fcf67e5p+6, 0x1.395659e94669fp+3,
0x1.8364650e63a54p+6, 0x1.3aea9efe1a3d7p+3,
0x1.85bedd274edd8p+6, 0x1.3bdf20c867057p+3,
0x1.8609cf496ab77p+6, 0x1.3bfd7e14b5eabp+3,
0x1.873849c70a375p+6, 0x1.3c77ed341d27fp+3,
0x1.8919c962cbaaep+6, 0x1.3d3a7113ee82fp+3,
0x1.8de4493e22dc6p+6, 0x1.3f27d448220c3p+3,
0x1.924829a17a288p+6, 0x1.40e9552eec28fp+3,
0x1.92702cd992f12p+6, 0x1.40f94a6fdfddfp+3,
0x1.92b763a8311fdp+6, 0x1.4115af614695fp+3,
0x1.947da013c7293p+6, 0x1.41ca91102940fp+3,
0x1.9536091c494d2p+6, 0x1.4213e334c77adp+3,
0x1.61b04c6p-1019, 0x1.a98b88f18b46dp-510,
0x1.93789f1p-1018, 0x1.4162ae43d5821p-509,
0x1.a1989b4p-1018, 0x1.46f6736eb44bbp-509,
0x1.f93bc9p-1018, 0x1.67a36ec403bafp-509,
0x1.2f675e3p-1017, 0x1.8a22ab6dcfee1p-509,
0x1.a158508p-1017, 0x1.ce418a96cf589p-509,
0x1.cd31f078p-1017, 0x1.e5ef1c65dccebp-509,
0x1.33b43b08p-1016, 0x1.18a9f607e1701p-508,
0x1.6e66a858p-1016, 0x1.324402a00b45fp-508,
0x1.8661cbf8p-1016, 0x1.3c212046bfdffp-508,
0x1.bbb221b4p-1016, 0x1.510681b939931p-508,
0x1.c4942f3cp-1016, 0x1.5461e59227ab5p-508,
0x1.dbb258c8p-1016, 0x1.5cf7b0f78d3afp-508,
0x1.57103ea4p-1015, 0x1.a31ab946d340bp-508,
0x1.9b294f88p-1015, 0x1.cad197e28e85bp-508,
0x1.0000000000001p+0, 0x1p+0,
0x1.fffffffffffffp-1, 0x1.fffffffffffffp-1,
};

void sq1(double *hi, double *lo, double u)
{
	static const double c = 1.0 + 0x1p27;
	double cu, u1, u2, r;

	cu = c*u;
	u1 = u - cu;
	u1 += cu;
	u2 = u - u1;
	*hi = u*u;
	r = u1*u1;
	r -= *hi;
	r += u1*u2;
	r += u2*u1;
	r += u2*u2;
	*lo = r;
}

void sq2(double *hi, double *lo, double u)
{
	double u1;
	double u2;
	double c;

	c = scalbn(1, ilogb(u)+27);
	u1 = u + c;
	u1 -= c;
	u2 = u - u1;
	*hi = u1*u1;
	*lo = u1*u2 + u1*u2 + u2*u2;
}

void sq3(double *hi, double *lo, double u)
{
	float u1;
	double u2;

	u1 = u;
	u2 = u - u1;
	*hi = (double)u1*u1;
	*lo = u1*u2 + u1*u2 + u2*u2;
}

double d_sqrt(double x)
{
	double y;
	double hi, lo, r, y1, r1;
	union {double x; uint64_t u;} u = {x};
	int e = u.u >> 52;
	int k;

	/* +-inf or nan */
	if ((e&0x7ff) == 0x7ff)
		return x + INFINITY;
	/* +-0 */
	if ((u.u & (uint64_t)-1>>1) == 0)
		return 0;
	/* x < 0 */
	if (e&0x800)
		return (x-x)/(x-x);
	if (!e) {
		/* subnormal */
		x *= 0x1p1022;
		k = -511;
	} else {
		/* normal */
		k = (e - 0x3ff)/2;
		e -= 2*k;
		u.u = (uint64_t)e<<52 | (u.u & (uint64_t)-1>>12);
		x = u.x;
	}
	y = sqrt(x);
	sq1(&hi, &lo, y);
	r = x - hi;
	r -= lo;
	if (r == 0)
		return scalbn(y, k);
	if (r < 0) {
		y1 = nextafter(y, 0);
		r = -r;
	} else
		y1 = nextafter(y, DBL_MAX);
	sq1(&hi, &lo, y1);
	r1 = x - hi;
	r1 -= lo;
	if (r1 < 0)
		r1 = -r1;
	y1 = scalbn(y1, k);
	y = scalbn(y, k);
	if (r1 < r)
		return y1;
	if (r1 > r)
		return y;
	printf("tie x %a y %a %a\n", scalbn(x, 2*k), y, y1);
	return y1;
}

static mpfr_t mx, my;

void mp_init()
{
	mpfr_init2(mx, 256);
	mpfr_init2(my, 256);
}

double mp_sqrt(double x) {
	mpfr_set_d(mx, x, GMP_RNDN);
	mpfr_sqrt(my, mx, GMP_RNDN);
	return mpfr_get_d(my, GMP_RNDN);
}

int main()
{
	int i;
	int c;
	double x, my, dy;

	c = 0;
/*
	mp_init();
	x = 1.0;
	for (i = 0; i < 1000000; i++) {
		my = mp_sqrt(x);
		dy = d_sqrt(x);

		if (my != dy) {
			printf("fail %a %a %a\n", x, my, dy);
			c++;
		}

		x = nextafter(x, 0);
	}
*/

	for (i = 0; i < sizeof testdata / sizeof *testdata; i++) {
		x = testdata[i].x;
		my = testdata[i].y;
		dy = d_sqrt(x);
		if (my != dy) {
			printf("fail %a %a %a\n", x, my, dy);
			c++;
		}
	}

	printf("%d\n", c);
	return 0;
}