Additional Problems
Smallest Divisor of an integer
Problem: Given an integer m, write a program that will find its smallest exact divisor other than 1.
•	Is the problem clear and well-defined?
•	what is a divisor?
–	For any number m, there are divisors
–	There are at least two divisors
–	All divisors of m can be totally ordered
–	Can m be 0?
–	Can it be negative?
–	What if m is prime?
•	Assume: m > 0
•	Assert: if m is prime, return 1 else the smallest divisor other than 1
Towards a strategy
•	All divisors of m are between 1 and m
•	Strategy 1:
–	Enumerate all divisors of m
–	choose the smallest one
•	Better Strategy:
–	Starting from 2, check one by one whether it is a divisor of m
–	If one is found before m is reached then return.
–	Otherwise, return 1.
•	How to check a divisor?
•	Can we do better?
Towards a Better Strategy
•	The above inspects (m-1) numbers, in the worst case
–	for even numbers, the answer is 2
–	for odd numbers, no need to check an even number
•	How to check whether a number is even or not?

•	Do we have go up to m?
The Algorithm
    Algorithm st_divisor
Input m
Assume: m > 0
Output d
Assert: if m is prime, d is 1; otherwise, 
                d is the smallest divisor other than 1

1. if ( even(m)) then d = 2
   else 
     1.1  d = 3
     1.2  do while ((m mod d /= 0 ) and (d < sqrt(m)))
                         1.2.1  d = d + 2
2. if (m mod d /= 0) then  d = 1

end algorithm
Observation
•	How to compute Square roots?
•	Better to remove the square root computation before the loop
–	Look for removing computations inside loops
•	Note m mod d can not be removed
•	Is the algorithm correct?
•	Does it terminate?
 Loop invariant
•	The invariant condition is:
m is odd, d is odd, 1 < d <= sqroot(m) + 1
for no x: 1 < x < d: x is a divisor of m

•	Bound Function:
                             (m – d)
Improvements
•	How many iterations?
–	In the worst case, the largest integer less than or equal to sqroot(m)/2
–	0, if m is even

•	Is there a better algorithm?
–	A lot of redundant checks are still made
–	Look for prime divisors
The square root problem
•	Problem: Write a program that computes the square root of a given number.
•	Is the problem definition clear?
–	If 25 is the input, then 5 is the output
–	If 81 is the input, then 9 is the output
–	If 42 is the input, then ?
•	For non perfect squares, the square root is a real number

•	So the output should be close to the real square root

•	How close? to a given accuracy 
A more precise specification
•	Problem: Write a program that given a number m outputs a real value r s.t. r*r differs from m by a given accuracy value e

•	More precisely, the program outputs r s.t.
                     |r*r - m| < e
Solution Strategy
Guess and Correct Strategy:
•	Choose an initial guess r less than m
•	If r*r > m then keep decreasing r by 1 until r*r is less than or equal to m.
•	If r*r < m then keep increasing r by 0.1, … until r*r exceeds or equals m
•	If r*r > m then decrease r by 0.01 until r*r exceeds or equals m.
        ...

•	Terminate the computation when  r*r equals m or differs from m by a given small number. 
Idea

•	Number of iteration depends upon the initial guess
•	If m is 10,00,000 and the initial guess is 300 then over 700 steps are needed
•	Can we have a better strategy?
Towards a better strategy
•	The basic idea of the strategy is to obtain a series of guesses that
–	falls on either side of the actual value
–	narrows down closer and closer
•	To make the guess fall on either side
–	increase/decrease the guess systematically
•	To narrow the guess
–	the amount of increase/decrease is reduced
•	Improving the strategy
–	faster ways of obtaining new guess from the old one
One Strategy
•	Given a guess a for square root of m
–	m/a falls on the opposite side
–	(a + m/a)/2, can be the next guess
•	This gives rise to the following solution
–	start with an arbitrary guess, r_0
–	generate new guesses r_1, r_2, etc by using the averaging formula.
•	When to terminate?
–	when the successive guesses differ by a given small number
The algorithm
Algorithm Sq_root
 Input m, e: real
 assume: m>0, 1 > e > 0
Output r1, r2: real
 assert:: |(r2 * r2 - m) | <= |(r1 * r1 - m)|, |r1 - r2| < e  
  
 1. r1 = m/2
 2. r2 = r1
 
 3.  Do while (|r1 - r2| > e) steps 3.1 and 3.2
            3.1   r1 = r2
            3.2   r2 = (r1+m/r1)/2
 end Algorithm
 
Analysis of the algorithm
•	Is it correct? Find the loop invariant and bound function

•	Can the algorithm be improved?

•	More general techniques available
–	Numerical analysis