Multi-Precision Arithmetic by C++ with no use of assembler
SN library Copyright (C) 1999-2018 K.Tsuru
Preface
This SN library is distributed under the GNU Library General Public License Version 2.
The 'S' of "SN" means "Super" or "Special" and the 'N' means "Number". I have developed this library under the ANSI
C/C++. It can treat multi-precision numbers whose upper limit
is about several billion(=109) digits. The kinds of number are
integer number (D, B) floating point real number (D) fixed point real number
(B) fraction number (D) rational number (B) complex number (D).
Where D and B denotes the decimal radix(10,000) and binary(32,768) one, respectively.
For the real numbers you can freely set up the number of significant figures
less than the above. The default is about 240 digits. The multi-precision
matrix class is not provided yet. Please try to make it yourself.
Here I enumerate the peculiarities of this library.
- It has been tested using 32 bit and 64 bit compiler gcc(MinGW, cygwin and TDM version) on Windows 10 Pro with memory 32GB.
- It is written by C++ and the operators +,-,*,/,%,<<,>>, etc. are overloaded.
Then it is easy to make a program. See the comparison with GMP.
- Any assembler is not used at all. Then it will be easy to translate
to other platforms and possible to make an optimization peculiar to individual
CPU. However rather short number (about less than 1,000 digits) arithmetic
becomes faster by use of assembler. I did not do it and have no plan.
- The FFT multiplication is used by taking the work variable "double".
The division between real numbers is performed by the multiplication between dividend
and the reciprocal of divisor. To evaluate the reciprocal the Newton's method
with "doubling significant figures" algorithm is used.
For the division of integer the Knuth's method or the Newton's one is used. The former is fast
for short integer and the latter for long integer.
The multiplication of integer is applied to the real one. It is very useful
to test the integer arithmetic. Because we have few item assuring its correctness
to us. On the other hand we have many items for the testing real number
arithmetic, e.g. testing sqrt(2)^2 gives 2 or not, etc.
- It has two radixes, namely decimal and binary. Because for the real
number an ordinary value such as 0.1 has infinite digits in binary radix,
then for a multiplication 0.1*0.1 the slow multi-precision arithmetic must
be used. The speed of FFT multiplication does not depend on radix. The radix conversion takes much
time. Then it has no merit to use the binary radix for the long number
(over 1,000 digits) multiplication. Furthermore the fast radix conversion
needs decimal radix arithmetic. But it is faster to use the binary radix
for the multiplication and division between multi-precision number and
short one, e.g. the calculation of the base of natural logarithm by series
and for the programs in which many bit operations are used such as Lucas-Lehmer's
test (see a sample program "smplucas.cpp").
Using two radixes it is useful to test the correctness of arithmetic, namely
by checking that the same calculation gives the same result or not.
- Using the FFT multiplication a fast radix conversion (square coupling method) is
provided for multi-precision number.
- The principle elementary mathematical functions are provided in which
various fast algorithms are contrived.
- I begin to use the iostream and 64 bit version of C++ since version 2.30.
- I do not use the overloaded functions for mathematical ones sin, cos
etc. i.e. instead of them Sin, Cos, etc. are used to be able to write easy-to-follow programs. Then seeing a statement
y = Sin(x);
we can understand that an SDouble function is called without referring
the declaration of 'y' or 'x'.
As another merit it enables us to write y = Sin(2.0); instead of y = sin(SDouble(2.0)); .
Nevertheless, you want to use overloaded sin, cos etc., please prepare functions such
as
SDouble sin(const SDouble& x){ return Sin(x); }
yourself.