Re: [boost] Interest in an arbitrary precision library?

From: Daryle Walker (darylew_at_[hidden])
Date: 2005-09-05 18:38:12

On 9/5/05 2:43 PM, "Joel Eidsath" <jeidsath_at_[hidden]> wrote:

> I think that I need to define the mathematical concept of rational
> numbers here.  A rational number is any number that _can_ be written as
> a / b.  But a rational class does not have to be stored as a separate
> numerator and denominator.  In an arbitrary precision library, you
> definitely do not want to implement rational numbers as a struct with a
> numerator and denominator.

Then how would you implement them?

> Examples of basic rational number types in C++:  float, double, etc.
> 
> An arbitrary precision rational class will do the same thing as double,
> but to as many digits as you tell it to.  See NTL's "RR" class.
> 
> Irrational numbers can only be handled symbolically by a computer.
> There are no mathematical functions in C++ or TR1 that return irrational
> numbers.

You missed the point of my question.  Physically, your assertion is true
(since an irrational result would need infinite memory to hold it).
However, many of the standard functions conceptually return irrational
results.  We simply get an approximation returned.  The precision of the
approximation is automatically determined by the properties of the built-in
numeric type.  What would be the limitation on your version of these
functions?  Would you let a single result fill up as much memory as
possible?  If not, what's the cut-off?  Would the cut-off be fixed or
determined at run-time (noting that the latter could change the function
signature by requiring an extra parameter for the cut-off limit's data)?

> Daryle Walker wrote:
> 
>> 
>> I have an attempt at this in the Sandbox CVS.  It includes a
>> "numeric_limits" specialization.  Look for the math/big_whole library.
>> 
> I'll take a look at it.  It just provides support for arbitrary size
> integers?  What sort of algorithms are you using?
> 
>> Be careful.  Many functions return irrational (particularly transcendental)
>> results.  You have to define your cut-off philosophy.  You can optionally
>> make variants of the math functions that include a parameter for a cut-off
>> specification.
>> 
> See top.
> 
>>> 3)  As well as arbitrary precision, it should provide error range math:
>>> 2.00 * 2.00 is not generally the same thing as 2.0 * 2.0
>>> 
>> 
>> Will this be a separate class?  A pure computation class doesn't have to
>> make this kind of distinction.
>> 
> I imagine that there will be an option to disable it if you don't like
> the computation hit.

I don't think it can be a simple disabling-flag.  It changes the semantics
of the type and its functions.

>>> 4)  It should use fast algorithms for multiplication and division, but
>>> instead of trying to compete with other libraries in computation speed
>>> (GMP uses hand-coded assembly in places), it should concentrate on code
>>> portability and ease of extension.
>>> 5)  I do not envision any fancy memory management.  The "big int" class
>>> will probably use a std::vector<int> to store it's implementation data.
>>> 
>> 
>> What about std::deque?
>> 
> 
> Will I need to insert objects at the front at any time?

Maybe.  And remove from the front too.  These would be needed for
digit-shift operations (<< and >>).

>> Will access to the internals improve the implementation of GCD?  If not, we
>> already have GCD and LCM functions in Boost.
>> 
> Yeah, I knew about those.  I hadn't gotten around to checking them out
> yet.  If they use Euclid's algorithm rather than the binary algorithm,
> then I won't use them.

I think they're all Euclid-based.  (They can't assume that the numeric type
is binary-based.)

>>> 7)  It should work well with other Boost libraries where possible.
>>> 8)  Divide by zero errors for integers should be handled with an exception.
>>> 9)  Precision for rational numbers may be set as a static member
>>> variable or it may not.  In the second case, expressions involving
>>> rational numbers of different.
>>> 
>> 
>> Your rational numbers would be distinct from boost::rational<your::integer>?
>> What would be the advantage?
>> 
> See top.

But would it really be a cost savings?

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