Program Examples

Numbers

Prime Factorization

i = 2; m = n ! n is the number to be factorized

outer : do

if ( i*i > m) exit

inner : do

if ( modulo(m,i) /= 0) exit

m = m/i

print *, i

end do inner

i = i+1

end do outer

if ( m > 1)  print *, m

Prime Factorization

•     numbers printed are the prime factors of n with multiplicity

•     why?

•     intuitive idea

–   start with the smallest number 2

–   divide n by it as long as possible and each time print  2

–    after this n will be odd

–   do the same with 3 and so on

Loop Invariance

•     can we prove it formally?

•     prove it by induction

•     what is the induction hypothesis?

•     a loop invariant is a property relating the values of variables such that

–   if it is true before an iteration starts

–   then it is true at end of iteration

–   hence, if true before the first iteration it is true after the last

Prime Factorization

•     a loop invariant for outer loop

m is not divisible by any j ,  1 < j < i, and

product of all numbers printed and m is n

•     suppose this is true at start of iteration

–   let value of m = l and value of i = k

•     l is not divisible by any j, 1 < j < k

•     at end of iteration, value of i = k+1

Prime Factorization

•     to show, new value of m, say l’, is not divisible by any j,  1 < j < k+1

•     in the iteration l is divided by k as many times as possible

•     at end of iteration l’ is not divisible by k

•     l’ is not divisible by any j, 1 < j < k as any such j would also divide l

•     every time k is printed m is divided by k

•     loop invariant is true at end of iteration

Proof

•     any number printed must be prime

–   a number k is printed only if it divides m but no number < k divides m

–   at end of loop, value of m is either 1 or a prime

•     product of numbers printed is n

–   at end of loop, product of printed numbers and m is n

–   m is printed if it is > 1

 

Greatest Common Divisor

•     given two numbers n and m find their greatest common divisor

•     possible approach

–   find the common primes in the prime factorizations

–   not very efficient , why?

•     Euclid’s algorithm

–   one of the oldest algorithms

Euclid’s Algorithm

•     based on a simple observation

•     gcd(n,m) = gcd(n-m,m) and hence

•     gcd(n,m) = gcd(m, modulo(n,m))

•     use this property repeatedly

•     smaller number reduces at each step

–   assume n > m

•     stop when smaller number is 0

•     larger number is the gcd

Euclid’ Algorithm

do

! if n < m, first iteration will exchange them

if ( m == 0 ) exit

temp = modulo(n,m)

n = m

m = temp

end do

print *, “gcd is”, n

! original values of n and m are lost

! better to preserve them and use other variables

 

Binary GCD Algorithm

•     other algorithms possible for gcd

•     binary algorithm uses simple operations

•     n,m are even, gcd(n,m)=2gcd(n/2,m/2)

•     n odd, m even, gcd(n,m) = gcd(n,m/2)

•     n,m odd, gcd(n,m) = gcd(n-m,m) ( n > m)

•     multiplication and division by 2 is easy in binary (shifting)

•     simpler operations used

 

Binary GCD Algorithm

gcd = 1

do

if (n < m) then ! make n the larger value

temp = m

m = n

n = temp

endif

if ( m == 0) exit

n_1 = modulo(n,2)

n_2 = modulo(m,2)

if (n_1 == 0 .and. n_2 == 0) then

n = n/2; m = m/2; gcd = 2*gcd

elseif (n_1 == 0) then;  n = n/2

elseif (n_2 == 0) then; m = m/2

else ; n = n-m

endif ; end do

gcd = gcd * n

•      note : more than one statement can be put in one line separated by ;

•      this should however be avoided

Comparison of Algorithms

•     which algorithm is better?

•     basis of comparison?

•     usually based on time for finding the result

•     time measured in terms of number of arithmetic operations performed

•     time for a single operation is assumed to be a fixed constant

•     assumption is not always valid ( division by 2 is much simpler than arbitrary division)

Comparison of Algorithms

•     how many operations are performed in Euclid’s and binary gcd algorithms?

•     depend on values of n and m

•     count number of operations as a function of n and m

•     as values of n and m increase, time required also increases

•     how fast does it increase?

Euclid’s Algorithm

•     a fixed number of operations performed in each iteration

•     time depends on number of iterations

•     after every 2 iterations, value of m is reduced by at least half

–   if modulo(n,m) > m/2 then modulo(m,modulo(n,m)) < m/2

•     number of iterations is at most 2(log2m+1)

Binary Algorithm

•     fixed number of operations per iteration

•     number of iterations depends on n and m

•     after every 2 iterations  n*m is reduced by at least half

–   if either n or m is even it is halved

–   if both are odd, n-m is even and is halved in the next iteration

•     number of iterations <= 2(log2(n*m) +1)

Worst-case Bounds

•     bounds on number of iterations are called worst-case bounds

•     actual number of iterations for particular n and m may be lesser

•     worst-case bounds hold for all inputs n, m

•     Euclid’s algorithm is better than binary in the worst-case

•     operations in binary are simpler and can be implemented more efficiently at a lower level

Prime Factorization

•     how many operations are performed by the prime factorization algorithm

•     depends on value of n

•     if n = 2k, k = log2n iterations are done

•     if n is prime, sqrt(n) iterations are done

•     worst-case bound is sqrt(n)

•     time required is less if n has many small prime factors

 

Factorization Vs. GCD

•     consider two 100 decimal digit numbers

•     Euclid’s algorithm will take about 600 iterations in the worst case

–   done easily on modern computers

•     the factorization algorithm may require about 1050  iterations

–    not feasible even on the fastest computer

•     finding factors is more difficult than finding common factors

Summary

•     an algorithm for prime factorization

•     two algorithms for greatest common divisor

•     Euclid’s algorithm requires fewer iterations than binary algorithm

•     operations in binary algorithm are simpler

•     worst-case bounds on number of operations

•     factorization requires much more time than finding common factors