GMP with small numbers

Richard B. Kreckel kreckel at
Mon Jun 19 00:04:14 CEST 2006

Good evening!

Degski wrote:

>It seems to me your approach doesn't cut wood.An mpz number basically
>is a struct with a pointer to an array of limbs (i.e. digits in a base
>2^32 or 2^64) and a pointer to a lenght variable indicating the lenght
>for the forementioned array (and the sign of the number, negative
>length, indicates a negative number). so in case of numbers smaller
>than 2^32, a one limb number, there is no difference between an mpz
>operation and a "normal" operation apart for checking the length of

Really? Most advanced dynamic languages and computer algebra systems 
spare the user the brainpain of having to know exactly when their 
integers roll over to (surprise!) negative values. In many cases, they 
do the distinction between machine-representable and synthetic large 
numbers in a transparent way. Please consult your favorite search engine 
about "fixnums" versus "bignums".

>Your approach involves overloading (therfor everytime an operation
>gets called, there is a lookup of the appropriate function,
>overloading doesn't come for free, there's no such thing as a free

It appears to me that when you say that "there is a lookup of the 
appropiriate function" you are really having dynamic dispatch (a.k.a. 
virtual functions) in mind. But that is not what operator overloading is 
about. Per se, operator overloading is nothing more than a ordinary 
function call hidden behind some syntactic sugar. As with all function 
calls, if that function call is marked for inlining and the compiler 
finds that it's nothing more than an arithmetic operation on built-in 
types (which is exactly what we are talking about), then the compiler 
can and does usually generate ideal code.

In a sense, that *is* free lunch.

>and then you want to do an overflow check. That's two checks!!!
>Your perceived speed gain is by now long gone!

That's right, there's always an overflow check involved to make sure the 
result still fits a machine type. But not two. And I dare say that doing 
a machine-multiplication including this check can be made more efficient 
than the generic multiplication on small numbers.

>Just a general remark. Did you have a decent look at GMP, if you did,
>you would see the level of sophistication and the consideration of
>every possible speed improvement (implemented or to be implemented).
>I'm quite sure the issue you raise has already been extensively
>considered (in version 0.1 beta), decided upon and burried.

The discussion how efficient arithmetic over small numbers in GMP is, is 
a red herring. The reason is that the arithmetic may be blazingly fast, 
but the overhead that is incurred in *not* exploiting the fact that the 
number is small may kill your project. The overhead I'm talking about 
comes from mpz_init, mpz_clear, and friends, and from having the objects 
on the heap instead of on the stack.

In essence, the OP's idea of using GMP for big numbers and cutting 
corners for machine-representable numbers is both very legitimate and 
common practice. The CLN C++-library <> does 
that for the user in a transparent way.

Best wishes

Richard B. Kreckel

More information about the gmp-discuss mailing list