Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Terje Mathisen <terje.mathisen@tmsw.no>
Newsgroups: comp.arch
Subject: Re: Continuations
Date: Tue, 23 Jul 2024 18:22:39 +0200
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <v7olcf$19cc0$1@dont-email.me>
References: <v6tbki$3g9rg$1@dont-email.me>
 <47689j5gbdg2runh3t7oq2thodmfkalno6@4ax.com> <v71vqu$gomv$9@dont-email.me>
 <116d9j5651mtjmq4bkjaheuf0pgpu6p0m8@4ax.com>
 <f8c6c5b5863ecfc1ad45bb415f0d2b49@www.novabbs.org>
 <7u7e9j5dthm94vb2vdsugngjf1cafhu2i4@4ax.com>
 <0f7b4deb1761f4c485d1dc3b21eb7cb3@www.novabbs.org>
 <v78soj$1tn73$1@dont-email.me> <v7dsf2$3139m$1@dont-email.me>
 <277c774f1eb48be79cd148dfc25c4367@www.novabbs.org>
 <v7ecrj$33vqv$1@dont-email.me> <20240722140115.000058cf@yahoo.com>
 <v7o828$16uk6$1@dont-email.me> <20240723162621.00005d95@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 23 Jul 2024 18:22:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ea07f0941b7d8c096c4251c6c9d75ad0";
	logging-data="1356160"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19sw2lnloZeFJJD/ytJFISKfm0Xm3YOp3jgmTcXxs6XlQ=="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:yNWBxdYrVCPZaYH/otk8mB6iMH0=
In-Reply-To: <20240723162621.00005d95@yahoo.com>
Bytes: 4237

Michael S wrote:
> On Tue, 23 Jul 2024 14:35:20 +0200
> Terje Mathisen <terje.mathisen@tmsw.no> wrote:
> 
>> Michael S wrote:
>>> On Fri, 19 Jul 2024 20:55:47 +0200
>>> Terje Mathisen <terje.mathisen@tmsw.no> wrote:
>>>    
>>>> MitchAlsup1 wrote:
>>>>> On Fri, 19 Jul 2024 14:16:01 +0000, Terje Mathisen wrote:
>>>>>> Back when I first looked at Invsqrt(), I did so because an
>>>>>> Computation Fluid Chemistry researcher from Sweden asked for help
>>>>>> speeding up his reciprocal calculations
>>>>>> (sqrt(1/(dx^2+dy^2+dz^2))), I found that by combining the 1/x and
>>>>>> the sqrt and doing three of them pipelind together (all the water
>>>>>> molecules having three atoms), his weeklong simulation runs ran
>>>>>> in half the time, on both PentiumPro and Alpha hardware.
>>>>>
>>>>> I, personally, have found many Newton-Raphson iterators that
>>>>> converge faster using 1/SQRT(x) than using the SQRT(x)
>>>>> equivalent.
>>>>
>>>> Yeah, that was eye-opening to me as well, to the level where I
>>>> consider the invsqrt() NR iteration as a mainstay, it can be useful
>>>> for both sqrt and 1/x as well. :-)
>>>>
>>>> Terje
>>>>   
>>>
>>> What is this "SQRT(x) equivalent" all of you are talking about?
>>> I am not aware of any "direct" (i.e. not via RSQRT) NR-like method
>>> for SQRT that consists only of multiplicationa and additions.
>>> If it exists, I will be very interested to know.
>>
>> sqrt(x) <= x/sqrt(x) <= x*rsqrt(x)
>>
>> I.e. calculate rsqrt(x) to the precision you need and then do a
>> single fmul?
>>
>> Terje
>>
> 
> That much I know.

I knew that! :-)
> 
> When precise rounding is not required, I even know slightly better
> "combined" method:
> 1. Do N-1 iterations for RSQRT delivering r0 with 2 or 3 more
> significant bits than n/2
> 2. Calculate SQRT estimate as y0 = x*r0
> 3. Do last iteration using both y0 and r0 as y = y0 + (x-y0*y0)*0.5*r0.
> That would give max. error of something like 0.51 ULP.
> A similar combined method could be useful for sw calculation of
> correctly rounded quad-precision sqrt as well. In this case it serves
> as 'conditionally last step' rather than 'absolutely last step'.
> 
> I was hoping that you'll tell me about NR formula for SQRT itself that
> can be applied recursively.
> The only formula that I know is y = (y*y + x)/(y*2). Obviously,  when
> speed matters this formula is not useful.

Sorry, no, I have not found anything approaching the rsqrt() NR for sqrt().

Terje


-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"