CMPS 2120 Lecture Notes - Algorithms on Integers

Positional representation of integers:

For b > 1 and n > 0, where b is the base and n is an integer, there is a maximum
k such that b^k <= n. Then there is a unique set of nonnegative integers
a_k, a_k-1,...a_0 < b such that

    n = a_k(b^k) + a_k-1(b^k-1) + ... + a_1(b^1) + a_0

   Ex. b = 10 , n = 2034

   2034 =  2(10^3) + 0(10^2) + 3(10^1) + 4

   The pattern is the same for any base b > 1.

Number base conversion.

Convert 1215 decimal to base 7.

   n    d    q    r
  1215  7    173  4
   173  7    24   5
    24  7    3    3
     3  7    0    3

ANS:  3354 base 7

Arithmetic operations are performed by the same method in any base. Ex.
base 16, where A=10 B=11 C=12 D=13 E=14 F=15

   1A34B  
+  25A15 
   -----
   3FD60  


   3FD60 
-  25A15 
  ------   
   1A34B

Base 2 division and multiplication are efficient given << left shift and >>
right shift bit operations (see ./Material/ch02/bits.c):

   1111 = 15
   * 10 = 2
  -----
   0000
  1111 
  11110 = 30

  Shifting a number to the left by one bit is a multiplication by 2:
  15 << 1 = 30

  Shifting 31 to the right is a divide by 2:
  30 >> 1 = 15 



Proposition:

  If d | m and d | n  then d | m-n  and  d | m+n.

Proof:

  If d | m then m = dp. If d | n then n = dq. Thus, m - n = dp - dq = d(p-q)
  and d is a factor of m - n. Further, m + n = dp + dq = d(p + q) and d is
  a factor of m + n. Thus, d | m-n and m+n.

/// Euclidean Algorithm.

Proposition:

     gcd(m,n) = gcd(m-n,n).

Proof:

    Let gcd(m,n) = d.

  If d is a common divisor of m and n then d also divides m-n (see proof above).
  Thus, gcd(m-n,n) is also a common divisor of m and n. 

  gcd(m,n) is less than or equal to gcd(m-n,n) and 
  gcd(m-n,n) is less than or equal to gcd(m,n).
  Thus, gcd(m,n) = gcd(m-n,n).

Corollary.

  gcd(m,n) = gcd(n, m mod n).  // since m mod n is m with multiples of n
                               // subtracted off

// pseudocode
   gcd(m,n) 
      if n = 0
         return m 
      else
         return gcd (n, m mod n)

   ex.
   gcd(210, 111) = gcd(111,210 mod 111) =
   gcd(111,99)   = gcd(99, 111 mod 99) =
   gcd(99,12)    = gcd(12, 99 mod 12) =
   gcd(12,3)     = gcd(3,12 mod 3) =
   gcd(3,0)      = 3



// Evaluation of monomials.

A monomial is a polynomial of a single term; e.g., 13^4

Calculate 13^n; 13^25

13*13*13*....*13   =  25 - 1  operations 

The efficiency of the brute force algorithm to compute x^n is big-Theta(n).

// Fast Exponentiation Algorithm

To compute 13^25, first convert 25 (the exponent) into binary:

25 = 11001

Factor 13^25 into a factor for every 1 in the binary number:
 
13^25 = (13^16)(13^8)(13^1)  

The largest exponent you need is 16. Compute that in 4 mult ops as follows:
13^2  = (13^1)(13^1)
13^4  = (13^2)(13^2)
13^8  = (13^4)(13^4)
13^16 = (13^8)(13^8)

The final computation is (13^16)(13^8)(13^1) which is 2 mult ops.

In general, to compute x^n, you make floor(lg n) preliminary mult operations.
You then make the number of bits flipped - 1 to compute the final result.
In the worst case for this step you make no more than lg(n) multiplications. 

The efficiency of the entire algorithm is thus
      lg(n) + lg(n) = 2lg(n) = O(lg n).

For 13^25, there are a total of 4+2 = 6 mult ops (quite a bit better than 24).

We can be even more precise. The number of ops varies by the length of the 
binary representation of the exponent. For example, the worst case for an
the exponent of length 4 is 15; e.g., 3^15 = (3^8)(3^4)(3^2)(3^1). This takes 
6 ops. The best case for an exponent of length 4 is 3^8, which requires 3 ops.
In general, the count of the mult ops to compute x^n is 

      floor(n)  <=  count <= 2 floor(n), where n is the exponent in x^n.

// Modular Exponentiation.

Find 123^13 mod 101. 

Since 13 = (1101)2, 123^13 can be expressed as the product of 123 raised to 
each appropriate power of 2:

   123^8 * 123^4 * 123^1 = 123^13.

By the Product Rule

     (n * m) mod p = ((n mod p) * (m mod p)) mod p   

we can find 123^n mod 101, where n is successive powers of 2:

123^1 mod 101 = 22
123^2 mod 101 = (123)(123) mod 101 
              = ( 123 mod 101 * 123 mod 101 ) mod 101
              = ( 22 * 22 ) mod 101
              = 484 mod 101 = 80  
123^4 mod 101 = 80^2 mod 101 = 6400 mod 101 = 37 
123^8 mod 101 = 37^2 mod 101 = 1369 mod 101 = 56

Multiply the terms of the powers of 2 you need (1,4,8). The final answer is 
mod 101 of that product. In this case, of 22, 37, 56:  
   22*37*56 = 45 584
   45 584 mod 101 = 33.