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