Boost logo

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk