[boost] Proposal for New Multiple-Precision/ Arbitrary-Precision Numbers Library

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

Hi,
 
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
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/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
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