big_int, was Re: New file uploaded to boost

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

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

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.

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.

   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?

.) 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.
 
.) to_string() and the output operator definitely need some
improvements,
   a stream input operator is currently not at all present.
 
.) 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)?
 
   What should be the name of a float or 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.
 
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.
 
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?
 
Looking forward to hear some reactions,
 
Helmut