Re: [boost] RFC: Multiprecision arithmetic library

Subject: Re: [boost] RFC: Multiprecision arithmetic library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2011-12-24 16:58:56

>
> As for priority, personally I think that the most important aspect is a
> Boost-license version of
> integer and floating-point (with rational a slightly lower priority).

I strongly agree with those priorities. Below is a brief overview of
features I would expect from boost multiprecision library.

1) Bigint class that supports both heap and stack memory allocation for its
storage.
I am implementing robust predicates for geometric algorithms (voronoi
diagrams)
that operate with input objects with coordinates from integer domain.
Naturally this requires big integer class implementation.
I started with using gmp classes at first. The drawback is slow object
creation (because memory is allocated from heap).
One of the solutions is to split all the formulas onto binary operations
and store all the temporaries and variables as struct/class members.
However splitting complex formulas makes code very nasty and less readable.
I ended up with my own stack allocated big integer
implementation. This approach suits me perfectly as I don't store big
integer objects but just use them to evaluate predicate result.
I found a bigint library under sandbox/SOC/2007/bigint. It implements both
stack and heap memory allocated storage for bigint classes.
Not sure of the reasons it is not part of the boost, but it might be a good
idea to wrap it with multiprecision interface.

2) Wrappers around integral floating-point types to support wider exponent
range.
Another problem that I faced is conversion from bigint to double. The
maximum double exponent is 1023, which is quite small to
handle intermediate values of the geometric predicates. I ended up with
implementing floating point type wrapper that extends
double exponent to int64 range and think it is quite useful feature for
problems that operate with big integers.

Andrii

On Fri, Dec 23, 2011 at 7:30 PM, Paul A. Bristow <pbristow_at_[hidden]>wrote:

> > -----Original Message-----
> > From: boost-bounces_at_[hidden] [mailto:
> boost-bounces_at_[hidden]] On Behalf Of John
> > Maddock
> > Sent: Thursday, December 22, 2011 1:41 PM
> > To: boost_at_[hidden]
> > Subject: [boost] RFC: Multiprecision arithmetic library
> >
> > Folks,
> >
> > I'd like to get some feedback on a multiprecision arithmetic library
> I've been preparing for
> possible Boost
> > inclusion.  The code is in the sandbox under the "big_number" directory.
>  Docs can be viewed
> online here:
> >
>
> http://svn.boost.org/svn/boost/sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/
> > intro.html
> >
> > The main features are:
> >
> > * A generic front-end that's capable of wrapping almost any type that's
> a "number".  The front end
> is
> > expression template enabled and handles all the expression optimization
> and code reduction.  For
> example
> > it's possible to evaluate a polynomial using Horner's rule without a
> single temporary variable
> being
> > created.
> > * A series of backends that need only provide a reduced interface and
> set of operations, implement
> the
> > actual arithmetic, currently supported backends
> > are:
> >
> > Integer Types
> > ~~~~~~~~~
> > 1/ GMP (MPZ).
> > 2/ libtommath.
> >
> > Rational Types
> > ~~~~~~~~~~
> > 1/ GMP (MPQ).
> > [ But note that the integer types can also be used as template aruments
> to Boost.Rational ]
> >
> > Floating Point Types
> > ~~~~~~~~~~~~~~
> > 1/ GMP (MPF)
> > 2/ MPFR
> > 3/ cpp_float - an all C++ Boost-licensed backend based on Christopher
> Kormanyos' e_float code.
> > [ Note these three types are fully compatible with Boost.Math Trunk - so
> you get full standard
> library plus
> > special function support ]
> >
> > There's still a bunch to do, but I'd like to see what folks think, and
> where the main priorities
> should be
> > before submission.
>
> This is a really important development, long overdue as a tool in the
> Boost kit box, made possible
> by Christopher Kormanyos  arbitrary precision floating point library which
> is free of licensing
> difficulties, so the whole setup *can* be Boost license.  (Those who can
> use other restricted
> licence packages like GMP can still do so and get a modest improvement in
> speed).
>
> It should allow user to move seamlessly (well fairly ;-) from the built-in
> types to much higher
> precision types.
>
> This will allow tasks which can only be done now by moving to arbitrary
> precision like MatLab or
> Mathmetica to be done in C++.
> Only those bits of code that need high precision need to use it, leaving
> most of the code in C++
> built-in types. Maximally accurate long double values can be computed and
> saved.
>
> The cunning expression template implementation that John has produced
> offers some useful speedups
> (but as he says in the docs, it doesn't give quite the speedup that the
> over-optimistic might
> expect).
>
> The other downside (as he also warns) is that not all existing code can
> use it without some code
> changes.  I fell straight into this pit by trying to use Boost.Test to
> check cpp_float IO exactly as
> I had with Christopher Kormanyos's multiprecision.  I had to use the Boost
> lightweight test version
> instead, not a big problem, and one that can probably be 'cured' by some
> changes within Boost.Test.
>
> So I see a need for *both* John's expression template enabled version
> *and* Christopher Kormanyos
> version.  So keep at it both of you!
>
> Checks using Boost.Test also show that IO (after some grrrring by both
> Chris and John - it's a
> really, really tiresome task) does as close as is reasonable to expect in
> matching the IO of
> built-ins like double.  This is highly desirable feature IMO.  Boost.Test
> shows a reassuring number
> of decimal digits when displaying failure messages!
>
> As for priority, personally I think that the most important aspect is a
> Boost-license version of
> integer and floating-point (with rational a slightly lower priority).  Of
> course, for others being
> able to use the 'gold-standard' GMP and MPFR may be more important.
>
> Paul
>
> ---
> Paul A. Bristow,
> Prizet Farmhouse, Kendal LA8 8AB  UK
> [phone]  07714330204
> pbristow_at_[hidden]
>
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>