Transcript PPT

More on Efficiency Issues
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
Euclids Algorithm
• based on simple observation (assume n > m)
gcd(n,m) = gcd(n-m,m) (and hence)
gcd(n,m) = gcd(m, modulo(n,m))
• uses this property to reduce the smaller
number repeatedly
• until the smaller number is 0
• larger number then is the gcd
Euclid Algorithm
program euclid
implicit none
integer * :: n,m,temp
read *, n,m
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
end euclid
Binary GCD Algorithm
• Other algorithms possible for gcd
• The binary algorithm uses the following derived properties:
– If n,m are even, gcd(n,m)=2gcd(n/2,m/2)
– If n odd, m even, gcd(n,m) = gcd(n,m/2)
– If n,m odd, gcd(n,m) = gcd(n-m,m) ( n > m)
• This involves simple operations - multiplication and
division by 2
• These operations easy to implement in binary
representation
– Multiplication by 2 is shifting to left
– Division by 2 is shifting to the right
Binary GCD Program
!declarations skipped
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
! more than one statement in one line separated by ;
! this should however be avoided
elseif (n_2 == 0) then; m = m/2
else; n = n-m
endif ; end do
gcd = gcd * n
Comparison of Algorithms
• Both the algorithms are correct (prove!)
• which algorithm is better?
• How do we compare?
– usually based on time for finding the result
• Time measured in terms of number of arithmetic
operations performed
• Time for a single operation assumed to be a fixed
constant
• assumption not always valid (division by 2 is much
simpler than arbitrary division)
Comparison of Algorithms
• How many operations performed in the two
programs?
– 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?
Euclids 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 better than binary in the worst-case
• Operations in binary simpler and can be implemented
more efficiently at a lower level
Prime Factorization
• Consider the algorithm given in the last class
• 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
– Euclids algorithm will take about 600 iterations in the
worst case
– done easily on modern computers
• Factorization algorithm may require about 1050 iterations
– not feasible even on the fastest computer
• Finding factors is more difficult than finding common
factors