Divisionsalgoritme

[Bertel Lund Hansen]

Hej allesammen

Jeg er ved at programmere regning med uendeligt mange decimaler,
bl.a. for at kunne beregne diverse matematiske konstanter. I den
forbindelse har jeg brug for division.

Jeg har lavet plus med køretid O(n), og jeg har lavet gange med
køretid O(n^2). Minus er også nemt nok, men division er noget
drilagtig. Hvi jeg laver rutinen så den svarer til manuel
division, så får den lang køretid.

Findes der en nemmere algoritme?

Tallene oprettes som arrays af heltal hvor hvert element kun har
så mange cifre som der må være når der skal være plads til
overløb (1 ciffer ved plus, og dobbelt op ved gange).

Hvis man er i tvivl om hvad jeg mener, kan man kikke på denne her
side:

http://bertel.lundhansen.dk/?page=matematik/beregningsmetode

Og koden for beregning af e:

http://bertel.lundhansen.dk/matematik/show_phpcode.php

[Anders J. Munch]

Post by Bertel Lund Hansen
Hej allesammen
Jeg er ved at programmere regning med uendeligt mange decimaler,
bl.a. for at kunne beregne diverse matematiske konstanter. I den
forbindelse har jeg brug for division.
Jeg har lavet plus med køretid O(n), og jeg har lavet gange med
køretid O(n^2). Minus er også nemt nok, men division er noget
drilagtig. Hvi jeg laver rutinen så den svarer til manuel
division, så får den lang køretid.
Findes der en nemmere algoritme?

Nemmere? Nej. Hurtigere? Ja.
http://en.wikipedia.org/wiki/Division_algorithm#Fast_division_methods

Jeg vil foreslå at outsource problemet til GMP, hvis du ellers kan finde en måde
at kalde det fra PHP. Eller skift til Python, der er i hvert fald muligheder nok.

mvh. Anders