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?
Euclids
algorithm
one of the
oldest algorithms
Euclids
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 Euclids 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?
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
Euclids
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
Euclids
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
Euclids
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