big_int, was Re: New file uploaded to boost

From: helmut.zeisel_at_[hidden]
Date: 2001-07-02 12:14:20

> 
> There are two problems I can think of, though. If it IS a base-2
radix, 
> one can almost certainly implement bitwise shifting operations used
to 
> multiply by powers of 2, MUCH more efficiently than normal bignum 
> arithmetic. 

I did not yet implement shift operators.
As you might have noticed,
in my implementation the radix is a template parameter,
which will not equal two
but usually be some power of two.

I do not see how for a base different from 2,
bitwise shifting can be implemented efficiently.

OTOH, if the shift operator meant
multiplication/division by a power of the radix,
this could be implemented efficiently.

I am not sure, however, whether this semantics
would be very good or a very bad idea.

> Given that the non-power-of-2 implementations can just 
> implement them as ordinary multiply/divides by 2, I think these
ought 
> to be supplied.
>

AFAIK, this is what GMP does.
I could implement this without problems.
 
> Second, I can definitely see that people will want to hash big_ints, 
> and bitwise XOR is frequently used in such functions. Some tools 
> useable for getting good hashes out of bignums are necessary, if the 
> bitwise ops are not supplied.

This is a very good point.
> 
> > .) What should be syntax and semantics of a "div" function
> >    that returns quotient and remainder at the same time?
> >    I implemented a member function div(d,q)
> >    which returns *this /= d and sets q to the remainder.
> >    There are, however, many other possibilities.
> 
> This seems obvious:
> 
> bignum.div(d)
> 
> returns pair<bignum,bignum> being the quotient and remainder.
> 

Doing like the int do
would mean something like

div_t div(int numer, int denom); 

defined in <stdlib.h>

I would prefer to see an additional version
which avoids copying temporary variables,
but I am not sure whether the copying takes much time
compared to the cost of the division.

Helmut