Analyzing Roots

Computer Science Level 2

Below is a Python script that approximates the positive square root of positive integers. The algorithm makes guesses by continually averaging the upper and lower bound of a range of numbers that dynamically adjusts.

## Number we seek the sqrt of
n = input("Find sqrt of: ") ## input() gets input from the console

## Set the bounds
upperBound = n 
lowerBound = 0

## Acceptable variation in result
delta = 0.00001

## Current guess at sqrt of n
guess = (upperBound + lowerBound) / 2.0

## Checks if guess*guess is within +/- delta of n
while guess*guess < n - delta or guess*guess > n + delta:
    ## Resets bounds according to outcome
    if guess**2 < n - delta:
        lowerBound = guess
    else:
        upperBound = guess
    guess = (upperBound + lowerBound) / 2.0

test = int(guess + 0.5) ## int() casts other number types into integers
if test**2 == n:
    guess = test

print guess

Analyze the script and determine the error that exists in it from the choices below.

Cannot provide exact root of perfect squares Inputs between 0 and 1 cause an infinite loop Code assumes that bounds are adjusted each iteration Value of delta is too small for computable answer

4 solutions

Ryan Braam
Mar 15, 2014

In its current implementation, the script assumes that the positive square root of n is found within the range of 0 and n . However, this is not true when 0 < n < 1 because in this case the square root of n is actually greater than n . To correct this error, the initial setting of upperBound should be changed to this:

upperbound = n + 1

This change ensures that the initial range will be large enough to include the square root of n .

The problem says that the code is meant to find the square root of "positive integers". How can an input between 0 and 1 be a positive integer? Why can't such basic flaws in the problem statement be checked?

Vijay N Venkat Raghavan - 7 years, 2 months ago

Haha you've got a point :)

Paul Paul - 6 years, 10 months ago

u also need to add a condition to check if n is non negative

Aditya Pappula - 7 years, 2 months ago

Samuel Li
Apr 10, 2014

This problem says that the code "approximates the positive square root of positive integers". However, an input between 0 and 1 can never be a positive integer. So, the problem is flawed. However, it is true that inputs between 0 and 1 cause an infinite loop.

Sanjay Kamath
Apr 5, 2014

put in the values : min = 0 max = 1 avg = 1/2 . Hence square of this term is always less than w where w ~=1. Hence infinite loop executes. The loop never terminates.

This I think was the explanation the questioner wanted.

Arthur Conmy - 4 years ago

Felipe Almeida
Mar 27, 2014

Numbers between 0 and 1 have a square root which is smaller than themselves.

Analyzing Roots

4 solutions

0 pending reports