(No subject - faster division, multiplication and GCD)

[Anders Andersson]

On Mon, Aug 29, 2022 at 7:55 PM Torbjörn Granlund <tg at gmplib.org> wrote:
>
> Hans Petter Selasky <hps at selasky.org> writes:
>
>   After some struggle decoding your PDF attachment, it appears to me
>   that your optimization examples depends on lucky numbers for the
>   division and multiplication - right?
>
>   Did you run your algorithms on random numbers?
>
> Quoting from the paper:
>   The numbers used were n = 3^69581 − 2 of approximately 130000 bits and d
>   = 3^7989 − 2 of approximately 10000 bits. The results of the authors
>   algorithm compared with that of GMPLIB’s mpz tdiv qr() function. Only
>   limited testing of just a few numbers was carried out.
>
> You appear to be correct, this algorithm only performs well for very
> special numbers, and as it has not been tested nor proved, it might not
> even work for general numbers.
>
> But it is 81.92 times faster than GMP for the very numbers above.
>
> Incidentally, I wrote a division program which is 6553.6 times faster
> than Allan's program.  I've only tested it for (3^69581 − 2) / (3^7989 −
> 2), but it actually works just as well for any input which has the same
> quotient as the numbers above (i.e., it works for infinitely many
> inputs!).  Attached!
>
>
> :-)

Amazing, I just built it on my Amiga and it's blazing fast.