Re: [boost] Infinite precision integer draft

From: Beman Dawes (bdawes_at_[hidden])
Date: 2006-05-26 16:58:04

"Andras Erdei" <aerdei_at_[hidden]> wrote in message 
news:7fe28deb0605260808j7af82ba6k897d3dca5d5dd435_at_mail.gmail.com...
> On 5/24/06, Maarten Kronenburg <M.Kronenburg_at_[hidden]> wrote:
>>
>> In the boost vault
>> http://boost-consulting.com/vault/
>> under Math - Numerics the document
>> infintdraft.pdf contains the
>> Proposal for an Infinite Precision Integer
>> for Library Technical Report 2, Draft.
>> Any comments are welcome.
>>
>
> 1. My main concern is that both the interface and the specification seem 
> to
> be too implementation-driven.
>
> For example, i don't see any reason for specifying the time-complexity of
> the operations...

The LWG discussed this, and decided that the time-complexity should be 
specified tightly enough to require implementations that are broadly useful, 
but not so tightly as to require heroic efforts by implementors.

> 5. Summary
>
> It is high time to get an integer into the standard, but i would prefer a
> very minimal (strictly int-mimicking, no additional operations etc) one.

The LWG also discussed this, and would like a fairly minimal approach 
(incidently, it is for TR2, not the standard itself). However, certain 
additional functions are required for real-world applications, and are more 
efficient if part of the implementation.

> Of course, the boost _implementation_ can provide a lot more than
> this minimal integer, and when we have enough experience, then we
> can bloat the interface to support common use-cases.

Yes.

> Similarly, let's restrict implementations as less as possible: if someone
> ever comes up with a logarithmic integer class that provides O(N)
> multiplication  in exchange for addition being O(N*logN), then let them
> do so...

It might be possible to allow such an implementation by providing an escape 
clause. Perhaps something like: "Complexity requirements for certain 
functions may be relaxed if doing so allows improved complexity for other 
functions. Such complexity relaxations and improvements shall be documented 
by the implementation."

Is that a good idea? I don't know enough about the problem domain to have a 
strong opinion.

--Beman