Question

Hi all, I have a question regarding lecture 2. Towards the end of the lecture the tutor talks about using algorithmic analysis to determine how many iterations it takes to find the square root. He states the formula to determine the number of iterations is:
x / epsilon**2
And he states the answer is 26.xxx
However with the values:
x = 12345.0
epsilon = 0.01
Iterations would equal 12345000

I'm very interested to know how you would determine the correct number of iterations. Can anyone help?

Answer 1

couple things. looking at the materials for the fall 2011 course and the 2015 videos on itunes U. I think the lecture you're referring to is lecture 3? I can't find any epsilons in the code for lesson 2. reviewing the transcript of that lecture, I don't see the relationship you've described. instead he says the number of iterations depends on the size of the steps you take to find a square root AND the epsilon which determines the square root.


here's the relevant code from the lecture

x = str(raw_input('enter a number to be square rooted')
epsilon = 0.01
numGuesses = 0
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans <= x:
ans += 0.00001
numGuesses += 1
print 'numGuesses =', numGuesses
if abs(ans**2 - x) >= epsilon:
print 'Failed on square root of', x
else:
print ans, '81is close to square root of', x

how does he determine the number of iterations? take note of the variable "numGuesses". it starts at 0, and every time the system takes a guess, it adds one to the value. this variable is what tracks the number of iterations

lastly, the reason why 12345 doesn't need 1234500 guesses (or rather 1234500000 based on the above code) is because the answer isn't supposed to get up to X. it needs to get up to the square root of x. or the cubed root of x. or whichever.

best of luck to you through the course!!!

Answer 2

Thanks for the response PrancingAbout - however I don't believe I explained the problem very well. Since then another student asked the same question and discovered the result. For all those interested the answer is here:
https://www.reddit.com/r/computerscience/comments/4aedzt/need_help_mit_600_course/