mpz_addmul_ui with ui = 1

[Marc Glisse]

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