Scientific researches, algebraic, cryptographic, engineering and physics applications are usually performed with big numbers which exceed typical data types of nowadays. So, arbitrary precision arithmetic is needed to do these tasks. Partitioning numbers into small parts and doing the calculation is the main principle. Divide and conquer philosophy lies behind it. In arbitrary precision arithmetic, just a classical addition operation takes lots of cycles. Multiplication and division operations have highest complexities.
Efficient arbitrary precision arithmetic calculation is the main purpose of this project and it is going to be one of the most important parts of Infelon Operating System.
Computation of large numbers, is a computationally time consuming task. For example, the classical multiplication algorithm (Schoolbook) takes O(n^2) time where n is the number of digits of the input operand. This complexity is negligible for small size operands. But, operation time depends upon the input size and tends to be larger because of the complexity.
(This picture is from the Internet / Anonymous)
There are some other algorithms which have lower time complexities for multiplication e.g. Karatsuba O(n^1.585), Toom-Cook O(n^1.465), FFT based Schönhage-Strassen, etc. On the other hand, such algorithms have more overheads in comparison to the Schoolbook algorithm. This leads to a trade-off between the proper selections of the multiplication algorithm along the computation. Lower complexity does not mean that it is better in every case. Overhead of the algorithm must be considered and input size determines the right method.
Also, there are another issues about memory management and exploiting hardware. Infelon Operating System will handle them and this library will provide a large set of mathematical functions for arbitrary precision arithmetic. It has lots of different efficient algorithms for various operations and optimization techniques and I got pretty good result from it.
It is mostly completed and I will integrate it after operating system project completion. Specialized operating system and calculation library relation part is the most important, unique and exciting part for me and it will determine the big project’s future. Regards...