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

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-07-04 10:45:49

on 7/2/01 4:12 PM, Helmut at helmut.zeisel_at_[hidden] wrote:

> --- In boost_at_y..., <boost_at_y...> wrote:
>> You can access this file at the URL
>> http://groups.yahoo.com/group/boost/files/big_int/big_int_20010702.zip

> This is a first release of my unlimited integer class. It has been tested
> under NT (VC++ 6.0) and Linux (GCC 2.95). Observe that the heavy use of
> templates requires option /Zm210 under VCC and -ftemplate-depth-32 under GCC.
> With the exception of rational arithmetics, the tests and examples run on both
> platforms.

I guess you use some sort of extreme constructs, because my compiler
_crashed_ when I tried to make your examples/tests.  I had to use my
operating system's kill-program keystroke to take back control.

> As has already been said previously, the discussion should focus on the
> interface, not on the specific implementation. So I added several examples and
> tests to see whether the interface fits.
> 
> I did not yet test Daryle Walker's bignum class with my test programs, doing
> this might give some insights how far we agree w.r.t. the interface.

It'll also give my classes some tests.  -_^

For these tests and examples, you don't need to maintain separate *.hpp
files.  If there is only one file's worth of source, it's better to keep it
in one file, so it's self-contained.

> For the interface, it is clear that it should be as close as reasonable to
> built-in integral types, there are, however, many points which need
> discussion, e.g. the following:
> 
> .) 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 was thinking of treating the "bitwise" operators as "place-wise"
operators, and apply the operations to the specific radix.  I did something
similar for the modulo class I posted.

> On the other hand, if one wants to be as close as possible to built-in
> integral types, these operators are needed.
> 
> As I understand, GMP offers boolean operations, does someone know which other
> multiprecision libraries offer or don't offer boolean operations?

It probably depends on whether or not the library uses a binary internal
representation.

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

I had a class-static "div" member function that took in the dividend and
divisor and returned a std::pair representing the quotient and remainder.

> .) to_string() and the output operator definitely need some improvements, a
> stream input operator is currently not at all present.

I have something preliminary too.  I want to support all the integer I/O
options.  Since my main classes are concrete (non-template), other numeric
classes could define conversions to/from my classes and crib my
implementation for I/O.

> .) I am still looking for a good name for a floating point division of two
> unlimited integers. Observe that it might happen that two integers are too
> large to be representable as double, but there quotient can be represented.
> 
> Do you like double fdiv(const integer& p, const integer& q)?

Would this be a class-static member function?

> What should be the name of a float or a long double version?

Maybe you could have just a long double version.

> In file big_int.hpp there is a section of structs which, IMHO, should be part
> of operators.hpp. I would appreciate if David Abrahams and/or Jeremy Siek
> could check this section and offer similar functionality in operators.hpp.

I think I added a bunch of similar structs already.  I think there are a few
differences, though.

> Maybe Paul Moore will be happy to see that his rational class works with my
> unlimited integers. The bad news, however, is that these are the only parts
> where I did not succeed in getting a running program on NT/VC++. The examples
> fortunately work at least under Linux/gcc 2.95.
> 
> From the Lucas-Lehmer examples you can see that the implementation is by far
> not fast enough to win the EFF $100000 award for the first 10 million digit
> prime. Probably the award will be distributed before my implementation can
> even complete a single Lucas-Lehmer test of that size :-(
> 
> AFAIK, Hubert Holin is working on an FFT implementation for boost. Maybe I
> will implement fast O(n log n) multiplication/division when boost-FFT is
> available.

Speed is nice, but we shouldn't have to compete with the specialty C++ math
packages.  None of the other Boost math packages do.

> In the meanwhile it might be more important to get a wrapper for GMP or some
> other existing multiprecision library.
> 
> Is there already someone working on such a wrapper?

That could be done as a separate project.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com