Re: Division using FMAC, reciprocal estimates and Newton-Raphson - eg ia64, rs6000, SSE, ARM MaverickCrunch?

1 msg	[tuples] Merged with trunk @135126
4 msg	IRA performance testing on Fortran
14 msg	bit_size_type - a data type?
1 msg	About symbol and label
2 msg	[Windows] Fixing fprintf errors breaking bootst...
3 msg	inline assembly question (memory side-effects)
3 msg	How do I add target specific tests?
2 msg	Deprecation?!
1 msg	gcc-4.4-20080509 is now available
1 msg	RFC: Optimize caller-saved register
6 msg	How to handle loop iterator variable?

Division using FMAC, reciprocal estimates and N...
\ Hasjim Williams (9 May 2008)
. \ Paolo Bonzini (9 May 2008)
. . \ Martin Guy (10 May 2008)
. . . \ Hasjim Williams (12 May 2008)
. . \ Andrew Haley (10 May 2008)
. . . \ Andrew Haley (10 May 2008)
. . \ Andrew Haley (12 May 2008)

1 msg	Questions about attributes
2 msg	ssa_name issues
6 msg	RFH: Building and testing gimple-tuples-branch
1 msg	gcc-4.3-20080508 is now available
4 msg	How to implement the instruction in the back end
1 msg	gcc-4.2-20080507 is now available
5 msg	all-target-libstdc++-v3 broken again
22 msg	Bad code generation on HPPA platform

Subject:	Re: Division using FMAC, reciprocal estimates and Newton-Raphson - eg ia64, rs6000, SSE, ARM MaverickCrunch?
Group:	Gcc
From:	Martin Guy
Date:	10 May 2008

On 5/9/08, Paolo Bonzini <bonzini> wrote:
> The idea is to use integer arithmetic to compute the right exponent, and
> the lookup table to estimate the mantissa. I used something like this for
> square root:
>
> 1) shift the entire FP number by 1 to the right (logical right shift)
> 2) sum 0x20000000 so that the exponent is still offset by 64
> 3) extract the 8 bits from 14 to 22 and look them up in a 256-entry, 32-bit
> table
> 4) sum the value (as a 32-bit integer!) with the content of the table
> 5) perform 2 Newton-Raphson iterations as necessary

It normally turns out to be faster to use the magic integer sqrt
algorithm, even when you have multiplication and division in hardware

unsigned long
isqrt(x)
unsigned long x;
{
register unsigned long op, res, one;

op = x;
res = 0;

/* "one" starts at the highest power of four <= than the argument. */
one = 1 << 30; /* second-to-top bit set */
while (one > op) one >>= 2;

while (one != 0) {
if (op >= res + one) {
op = op - (res + one);
res = res + 2 * one;
}
res >>= 1;
one >>= 2;
}
return(res);
}

The current soft-fp routine in libm seems to use a variant of this,
but of course it may be faster if implemented using the Maverick's
64-bit add/sub/cmp.

M