Re: [boost] big_int, was Re: New file uploaded to boost

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-07-02 11:29:30

> --- In boost_at_y..., <boost_at_y...> wrote:

> .) What about the low-level boolean operations,
>    such as &,|,^:
> 
>    On the one hand, they are not really needed
>    since std::bitset and std::vector<bool>
>    already provide the respective functionality.
> 
>    Additionally, requiring these operators to be present
>    might restrict every implementation to have a radix
>    which is a power of 2; in particular,
>    a BCD implementation would be excluded.

I doubt it would prevent them, but it WOULD make implementing these 
operators rather inefficient in a non-base-2 radix.

Myself, I don't see the use for treating a big_int in a logical bitwise 
way, given bitset (I don't like vector<bool>), so that would argue 
against &, | and ^.

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. 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.

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.

> .) 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.

George Heintzelman
georgeh_at_[hidden]