Re: [boost] Infinite precision integer draft

From: Andras Erdei (aerdei_at_[hidden])
Date: 2006-05-27 17:37:28

On 5/26/06, Beman Dawes <bdawes_at_[hidden]> wrote:
>
> > 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.

i'm just worried that using guesswork it's pretty hard to come up with
the right set of "certain  additional functions"

my guess :O) would be that the additional functions in the current proposal
are not that final set:

- some of the functionality will move into a seriously revised & redesigned
numeric_limits replacement (e.g. checking for a zero value and finding out
the sign, together with constants for zero, one etc to allow generic
programming)

- some of the functionality will pretty fast become obsolete (e.g. i hope as
soon as there's a useable integer, and people start to use it, much more
efficient direct (non-integer based) modular artimetic classes will prop up,
and integer itself won't be used long for modular arithmetic computations)

IMHO stuff like sqr() in itself doesn't worth the risk of going beyond int

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

i think that's fine

an alternative could be to simply state that all basic operations (+-*/%)
should
have less than O(N^2) (amortized?) complexity

i personally wouldn't put restrictions on the rest of the interface: e.g.
IMHO the
complexity requirements on the constructors were made with positional
number-system based implementations in mind (assuming that the constructor
implementations consist of converting from one radix to another)

also, i'm not sure how the allocation times were taken into account (if they
were)

br,
andras