(No subject - faster division, multiplication and GCD)

[Torbjörn Granlund]

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!

-------------- next part --------------
A non-text attachment was scrubbed...
Name: foo.c
Type: application/octet-stream
Size: 24466 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-discuss/attachments/20220829/c99b0166/attachment-0001.obj>
-------------- next part --------------

:-)

-- 
Torbjörn
Please encrypt, key id 0xC8601622