Time Estimation of Mathematical Operations
Time needed by a computer to perform a task can be evaluated by estimating a number of required operations on bits. One must analyse how many changes of bits is necessary to perform the calculations on the number, which is stored in computer memory by using binary notation.
Binary addition
Binary addition of two numbers (stored in Natural Binary System - NBS) may be presented as a simple columnar addition:
| 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 0 | 0 | ||
| + | 0 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 0 |
First, the vacant spaces in the shorter number are filled with zeros. As a result, both numbers are of the same length of k bits. After that, simple summation should be performed for each pair of digits. If the result of the summation is bigger than 1, then the result is set to 0 and the number 1 is carry to the next position.
The result of addition of two k-digit numbers contains k or k+1 digits. The whole operation of summation requires k operations on bits.
Binary multiplication
Analogously to addition one can perform multiplication of two binary numbers:
| 1 | 1 | 1 | 0 | 1 | ||||
| x | 0 | 1 | 1 | 1 | 1 | |||
| 1 | 1 | 1 | 0 | 1 | ||||
| 1 | 1 | 1 | 0 | 1 | 0 | |||
| + | 1 | 1 | 1 | 0 | 1 | |||
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
During multiplication of two binary numbers n and m of lengths of respectively k and j bits one can receive up to j rows (the number of rows is equal to the number of ones in the number m) which contain copies of the number n shifted to the left by the adequate number of positions. Multiplication can be presented as up to j-1 additions. Each addition requires k operations on bits.
The number of operations on bits during multiplication of two binary numbers is smaller than a product of their lengths. The result of multiplication has k+j or k+j-1 digits.
It should be added that there are known quite faster algorithms of multiplication of big numbers. Some of them allow to multiply two k-digit numbers using only k(ln k)(ln (ln k)) operations on bits.
Factorial
The factorial of a non-negative integer n (n!) is the product of all positive integers less than or equal to n.
The product of n numbers of length k is up to nk-bit long. Therefore, the number n! is also up to nk-bit long. To calculate n! one must perform n-2 multiplications of numbers of length of up to k bits and a number of length of up to nk bits.
Therefore, the total number of operations is equal to:
(n-2)nk2
The value can be presented by using only the number n:
(n-2)n([log2n]+1)2
Approximately:
n2(log2n)2
Polynomial time
According to Cobham's thesis, algorithms are considered to be fast and effective, if they run in polynomial time.
- Addition, subtraction, multiplication and division are algorithms running in polynomial time
- Base conversion algorithm runs in polynomial time
- The algorithm which calculate n! does not run in polynomial time
