Henning Makholm wrote:
> Scripsit Jens Axel Søgaard <usenet@soegaard.net>
>
>>Henning Makholm wrote:
>>>Hvordan? Newton-iteration indeholder jo selv divisioner.
>>Har du et eksemplar af Knuth i nærheden?
> Kun bind 3.
Så skriver jeg lige af:
Algorithm R (High-precision reciprocal)
---------------------------------------
Let v have the binary representation
v=(0.v v v v ... ) where v = 1.
1 2 3 2 1
This algorithm computes an approximation z
to 1/v such that
-n
| z - 1/v | <= 2
R1. [Initial approximation]
Set
z <- 1/4 floor( 32 / ( 4v + 2v + v ) )
1 2 3
and k <- 0.
R2. [Newtonian iteration]
(At this point we have a number z of the binary
form (xx.xx...x) with 2^k + 1 places after the radix
2
point, and z<=2.)
2
Calculate z = (xxx.xx...x) exactly, using a high-speed
2 2
multiplication routine. Then calculate V z exactly,
k
where V = (0.v v ... v ) .
k 1 2 2^(k+1)+2 2
k+1
2 -2 - 1
Then set z <- 2z - V z + r , where 0<= r < 2 .
k
Finally, set k <- k +1.
R3. [Test for end]
k
If 2 < n go back to step R2; otherwise the algorithm
terminates.
Knuth fortsætter med at en variant af denne teknik er
blevet brugt i computerhardware (referencen er fra 1967).
Han viser at tidsforbruget er < T(8n) hvor T(n) er
tiden det tager at multiplicere to n-bit-tal.
>> - 1/v kan findes ved Newton-iteration:
>
>
>> x_n+1 = 2 x_n - v (x_n)^2
>
>
> Aha .. ved rodfinding i funktionen
>
> x |-> v-1/x
>
> går divisionerne ud mod hinanden. Smart.
Det er mest almindeligt at anvende teknikken, ved udregning
polynomiumsringe over en variabel. Hvor tingene er nemmere
at have med at gøre end når man regner på gemene tal.
> Men man skal sørge for at
> x0 er lille nok - hvis den er mere end 2 gange den ægte værdi af
> 1/v, divergerer iterationen mod -uendelig. Nå, det kan man forholdsvis
> nemt undgå ved at tælle bits.
Man kan se af R1 at det er nok at se på de første tre bits.
> Så vidt jeg kan se, vinder man imidlertid kun noget, hvis man kan
> multiplicere tal væsentlig hurtigere end den almindelige kvadraiske
> divisionsalgoritme. Det findes der vistnok algoritmer til, men de er
> så vidt jeg husker kun en gevinst hvis der er rigtig mange bits.
Ja - ovenstående har kun praktisk interesse, hvis man regner
på meget store tal.
> Og jeg har aldrig hørt om nogen der brugte dem til papirudregninger.
Heller ikke her, men Jonas og Bertel drejede jo også tråden
over til computerberegninger.
> Hvis nævneren holdes konstant, nytter iterationen ihvertfald ikke
> noget når antallet af uddatacifre går mod uendeligt - så kan
> papirmetoden producere n bits af resultatet i tid O(n), mens den
> iterative metode skal bruge O(n logn loglogn) eller mere blot til den
> sidste kvadrering i multiplikationen.
Det kan jeg ikke lige gennemskue.
>> > (f 7 1)
>>2 3930061525912861057173284004770585283429273822817848601487531
>> /3930061525912861057173624287137506221892737197425280369698987
> Det virker lidt som en omvej at udregne rationelle approksimationer
> til en eksakt brøk.
Heh. Det var mest fordi jeg blev så forbløffet over at få
tallene eksakt, at jeg syntes det var sjovt at tage dem med.
--
Jens Axel Søgaard