Subject: [boost] Proposal for New Multiple-Precision/ Arbitrary-Precision Numbers Library
From: Reetesh Mukul (reetesh.mukul_at_[hidden])
Date: 2010-07-31 05:41:33
I know the purposes and necessities of a Multiple-Precision and
Arbitrary Precision Numbers Library in C++ have echoed many a times
in BOOST mail chain. Moreover in past and in present many such efforts
have been on to address these needs( Google SoC, XINT, and many others
). I too have a long, consistent interest in this area and so is this
proposal. I am putting some of the points in Q & A format.
Q. What does Numbers mean here ?
A. As a long standing definition, Numbers would mean a âSetâ.
However for most of the practical reasons, and in particular in
relation to Natural Numbers/Integers, it would mean a set with Peanoâs
Arithmetic or Principle Ideal Domain or Finite Field ( âorâ here is in
inclusive sense). In most of the cases these Sets will be generated
out of Rings. As an example, Natural Numbers can be created by
mapping Set of âunsigned intâs (which can be treated as Finite Field)
to an Indexed Family of âunsigned intâ. One such mapping is âradixâ
(a0 + a1*r + a2*r^2 + a3*r^3+ ...) based arithmetic. Clearly the
library has long term intention to provide support for such mappings
which has flavors of being generic.
Q. What does Multiple-Precision and Arbitrary precision means here ?
A. If the cardinality of indexing set (mentioned above) is finite and
known at compile time then it will be the case of multiple-precision
else it will be arbitrary precision. Both Arbitrary and Fixed
precision have a meaning that they are multiple of a unit
precision. We will use the term multiple-precision as an alias to
fixed precision, however I see chances of debate over this topic. In
its implementation paradigms, the current library has notions of
multiple-fixed-precision and multiple-unfixed-precision. In current
writing I am denoting multiple-fixed-precision as fixed/multiple
precision while multiple-unfixed-precision as arbitrary-precision.
That multiple-precision maps to cardinality of indexing set
additionally asserts that unit of computation will be Elements of
Rings of a given kind and bits/bytes will be of particular interest
only. To give additional meaning to finiteness of multiple-precision
arithmetic, like specifying it in terms of bits, bytes or range of
values that the generated number would have, will mean creating
compositions of mapping described in last question.
Q.What are some basic APIs that the library will expose?
A. This is yet to be finalized. However some design paradigms are
settled. I already described the core Mathematics in last two
questions. There will be a conception of âvarchâ(Virtual
Architecture). This would mean providing a set of functions like mov,
add, addto, or, xor, ... which underlying processor provides. Thus one
can do - addto(unsigned int* dest, unsigned int* src, unsigned int n),
which adds âsrcâ to âdestâ (like operator+=) assuming âunsigned intâ
is a âfinite fieldâ and the âpointersâ and ânâ means n-sized indexed
family of âunsigned intâ. Definitely there will be âaddtoâs
corresponding to each of the Ring and Mappings. The âarithmetic
conceptsâ corresponding to each âaddtoâ will be deduced based on types
involved, and in case âarithmetic conceptsâ thus deduced are
ill-formed or wrong or void, compile time errors will be
generated. These varch functions will be provide very low level
interface(with respect to intended library) and internally they will
be fine-tuned for underlying processor, system, compiler and
Numbers will be represented as an object via a kernel called
basic_mint (which in turn will use varchâs function):-
template<typename SignedType=varch::U, typename IntegerType=unsigned int,
std::size_t InitialSize=0, precision::value_type
typename Allocator=allocator<IntegerType> >
Further there will be conception of âgeneratorsâ which will handle
Algebra of underlying types.
Q. How much is done ?
A. Not much. However some of the above ideas have been implemented.
One can see pieces of codes here:-
http://sourceforge.net/p/spring-math/svn/. A very large portion of
code is to be implemented. I thought, before I go too far, too far
where design and implementation buckles, I should get âconcept-checkâ
by BOOST Gurus.
Q. Will it be wrapped around GMP ?
A. No, No and No. C++ has richer Algebraic content.
Q. Is there any final API where user can use it the way int/char/float
are used is specified.
A. Not yet. But at most it will be a thin compile time wrapper
Q. Why I came here?
A. For guidelines, help, ideas, warnings, disciplines, lectures,
volunteers and inherent desire to register initials of my work :).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk