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