Complexity of GNU MP operations

[Torbjorn Granlund]

I have read and re-read your message, but I am still not sure what
information you are asking for.

Let me try some general answers:

GMP mainly performs integer arithmetic.  Rational and floating-point
routines are built on top of the integer routines.

The complexity of multiplicaton in GMP is O(n log(n) log(log(n))).  The
complexity of addition is O(n).

The actual time an operation takes is harder to tell.  You may get some
joy from the (poorly documented) program tune/speed.c.

I have attached a picture comparing addition and muliplication on a 3.2
GHz AMD Opteron processor.  The x-axis is the operand size in 64-bit
words, the y-axis is the time in seconds.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: foo.png
Type: image/png
Size: 4403 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-discuss/attachments/20100412/7a7493ed/attachment.png>
-------------- next part --------------

-- 
Torbj?rn