ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

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:

 111   
  11100
+ 01110
 101010

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:

    11101
  x 01111
    11101
  111010 
+11101   
101111001

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.

Definition An algorithm that performs operations on numbers n1, n2, ..., nr, of lengths of respectively k1, k2, ..., kr digits, runs in polynomial time, if there are integers d1, d2, ..., dr such as that the number of operations on bits necessary to perform this algorithm can be presented as O(k1d1  k2d2  ...  krdr).
  • 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