mpz_addmul_ui with ui = 1
Marc Glisse
marc.glisse at normalesup.org
Mon Feb 2 02:36:10 CET 2009
On Fri, 30 Jan 2009, Paul Zimmermann wrote:
>> At some point I was wondering whether the special representation of 0
>> (size==0) should be extended to represent instead small numbers that can
>> fit in an integer at most as long as _mp_d. Hard to tell.
>
> an alternate trick is to store in the mpz_t *pointer* a value of the form
> p=2k+1, where k is a small integer. Since pointers are usually even, you
> can easily distinguish between small integers and GMP integers,
> and you obtain the value k = p >> 1. It is also more memory-efficient since
> you don't allocate the mpz_t structure. A famous computer algebra system is
> using that trick together with GMP.
Indeed. Both approaches have the advantage that you don't need to call
malloc for small integers (save time and memory), and that you may be able
to inline the small_int case of some operations.
The version I mentionned has the nice property that, except for a small
increase in code size, it should not slow down anything except operations
involving 0 (precisely the case the original poster wanted to speed up
;-). However, I just noticed that it requires deallocating memory when you
set an existing number to 0 , which is wrong, or extend the meaning of
size 1 to include number 0, which causes its own trouble, or shift the
values of _mp_size to represent size+1, probably the best option. (There
are always more ways to do things, for instance always allocating even
sizes and using an odd _mp_alloc as meaning that the _mp_size is actually
a value, etc) Ok, I am dropping it.
The approach you mention uses even less memory for small integers (factor
2 or 3) and can be implemented on top of mpz_t. The drawbacks are fairly
small: it is not completely standard code, small integers have one less
bit, you need a small manipulation to get the true value of the integer
(>> 1 does not place the signbit at the right place, but that doesn't make
those numbers much harder to handle), there are more indirections, and you
need to malloc (or probably use a special allocator for this) the mpz_t.
The last two problems should mostly be noticable if you work a lot with
numbers that are just a few limbs long. Besides, this is successfully used
by two softwares (assuming that the "famous algebra system" is not CLN).
Ok, I am convinced, thank you for mentionning this,
--
Marc Glisse
More information about the gmp-discuss
mailing list