
Boost : 
Subject: [boost] Proposal for New MultiplePrecision/ ArbitraryPrecision Numbers Library
From: Reetesh Mukul (reetesh.mukul_at_[hidden])
Date: 20100731 05:41:33
Hi,
I know the purposes and necessities of a MultiplePrecision 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 MultiplePrecision 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 multipleprecision
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 multipleprecision 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
multiplefixedprecision and multipleunfixedprecision. In current
writing I am denoting multiplefixedprecision as fixed/multiple
precision while multipleunfixedprecision as arbitraryprecision.
That multipleprecision 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 multipleprecision
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 nsized 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
illformed 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 finetuned for underlying processor, system, compiler and
algorithms.
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
P=default_precision<InitialSize>::value,
typename IntegerTraits=integer_traits<IntegerType>,
typename Allocator=allocator<IntegerType> >
struct basic_mint;
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/springmath/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 â€œconceptcheckâ€
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
around basic_mint.
Q. Why I came here?
A. For guidelines, help, ideas, warnings, disciplines, lectures,
volunteers and inherent desire to register initials of my work :).
With Regards,
Reetesh Mukul
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk