1 of 14

COMPUTATIONAL THINKING

By

​

Dept. of CSE

​

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 14

  • Problem:
  • Given a number m devise an algorithm to compute its square root.
  • Algorithm development
  • We initially confronted with the problem of designing an algorithm to compute square roots, we may be at a loss as to just where to start.
  • In these circumstances we need to be really sure of what is meant by “the square root of a number”.
  • Taking some specific examples, we know that the square root of 4 is 2, the square root of 9 is 3, and the square root of 16 is 4 and so on.

​

Dept. of CSE

2025 - 26

FINDING THE SQUARE ROOT OF A NUMBER

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 14

Dept. of CSE

2025 - 26

From these examples we can conclude that in the general case the square root on n, of another number m must satisfy the equation

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 14

  • Suppose, for example, we do not know the square root of 36.
  • We might guess that 9 could be its square root.
  • Using equation (1) to check our guess we find that 9x9 = 81 which is greater than 36.
  • Our guess of 9 is too high so we might next try 8.
  • For example, 8x8 = 64 which is still greater than 36 but closer than our original guess.
  • The investigation we have made suggests that we could adopt the following systematic approach to solve the problem.

1. Choose a number n less than the number m we want the square root of.

2. square n and if it is greater than m decrease n by 1 and repeat step 2, else go to step 3.

3. When the square of our guess at the square root is less than m we can start increasing n by 0.1 until we again compute a guess greater than m. At this point, we start decreasing our guess by 0.01 and so on until we have computed the square root we require to the desired accuracy.

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 14

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 14

  • Studying our algorithm carefully, we observe that he number of iterations it requires depends critically on how good our initial guess is (e.g. if m is 10,000 and our initial guess n is 500 we will need over 400 iterations before we start to converge rapidly on the square root).
  • This observation raises the question, can we derive a quicker way of homing in on the square root that is not so critically dependent on our initial guess?
  • To try to make progress towards a better algorithm, let us again return to the problem of finding the square root of 36.
  • In choosing 9 as our initial guess, we found that

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 14

  • We know from equation (1) that the 9 should divide into 36 to give a quotient of 9 if it is truly the square root.
  • Instead 9 divides into 36 to give 4. Had we initially chosen 4 as our square root candidate, we would have found

​

  • From this we can see that we choose a square root candidate that is too large, we can readily derive from it another candidate that is too small.
  • The larger the guess is that is too large, the correspondingly smaller will be the guess that is too small.

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 14

  • In other words, the 9 and the 4 tend to cancel out each other by deviating from the square m in opposite directions. Thus

​

​

​

​

  • The square root of 36 must lie somewhere between 9, which is too big, and 4, which is too small.
  • Taking the average of 9 and 4:

​

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 14

​

​

​

​

​

  • We see that it again has a complementary value (i.e. 5.33) that is less than 36.
  • Thus,

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 14

  • We now have two estimates of the square root, one on either side, that are closer than our first two estimates.
  • We can proceed to get an even better estimate of the square root by averaging these two most recent guesses:

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 14

  • Our first task now is to clarify the averaging rule that we intend to use to generate successively better approximation to the desired square root.
  • As our initial guess g1 we chose 9.
  • We then proceeded to average this guess with its complementary value (36/9 = 4).

​

  • Our next step was to get an improved estimate of the square root, g2, by averaging g1 and its complementary value (i.e. (9+36/9)/2 = 6.5).
  • We can therefore write the expression for g2 in the general case as

​

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 14

  • In our example for finding the square root of 36, we began with g1 = 9 and established that g2 = 6.5.
  • We then repeated the averaging process.

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 14

  • Pseudo-code

begin

read m

set e

set g2:=m/2

do

begin

g1:=g2

g2:=(g1+g2/2)

while(abs(g1-g2)>=e)

end

writeout(g2)

end

​

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 14

Dept. of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques