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.

  1. It has been tested using 32 bit and 64 bit compiler gcc(MinGW, cygwin and TDM version) on Windows 10 Pro with memory 32GB.

  2. It is written by C++ and the operators +,-,*,/,%,<<,>>, etc. are overloaded. Then it is easy to make a program. See the comparison with GMP.

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

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

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

  6. Using the FFT multiplication a fast radix conversion (square coupling method) is provided for multi-precision number.

  7. The principle elementary mathematical functions are provided in which various fast algorithms are contrived.

  8. I begin to use the iostream and 64 bit version of C++ since version 2.30.

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