GMP with small numbers
Richard B. Kreckel
kreckel at ginac.de
Mon Jun 19 00:04:14 CEST 2006
>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 <http://www.ginac.de/CLN/> does
that for the user in a transparent way.
Richard B. Kreckel
More information about the gmp-discuss