SRL Archive - Python/Perl Help and Tutorials

This code here keep going into an endless loop and I cannot figure out why


And yes I am aware of math.sqrt, I'm not alowd to use it

def sqr(n):
   guess = n/4
   print("Creating a guess, we will use: ")

   while abs(n-guess) >.00001:
       avgDeter = n/guess
       print("new avg determinant: " + str(avgDeter))
       guess = (guess + avgDeter)/2
       print ("Guess failed....retrying with: " + str(guess))
   return 0

Here's some debug

Guess failed....retrying with: 5.001524390243903Count = 1
new avg determinant: 4.998476074367571
Guess failed....retrying with: 5.000000232305737Count = 2
new avg determinant: 4.999999767694273
Guess failed....retrying with: 5.000000000000005Count = 3
new avg determinant: 4.999999999999995
Guess failed....retrying with: 5.0Count = 4
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 5
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 6
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 7
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 8
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 9
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 10
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 11
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 12
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 13
new avg determinant: 5.0
Guess failed....retrying with: 5.0Count = 14
new avg determinant: 5.0

edit: Made a stupid grammatical error.

EDIT:
see below

n shouldn't ever change that's the number I'm trying to find the sqrt of….

example sqr(25) should return 5 but it doesn't.


Unless I am not understanding your post.

guess = (guess + avgDeter)/2
it rounds off automatically

EDIT: think it's something like in PS, the numerator or denominator has to be a float for it to do float division
so u have to do either (guess + avgDeter)/2.0
or
(guess + avgDeter)/float(2)

Changed it to this

def sqr(n):
   guess = n/4.0
   print("Creating a guess, we will use: ")
   count = int(0)
   while abs(n-guess) >.00001:
       avgDeter = n/guess
       print("new avg determinant: " + str(avgDeter))
       guess = (guess + avgDeter)/2.0
       print ("Guess failed....retrying with: " + str(guess) + "Count = " + str(count))
       count = count + 1
   return 0

Still fails, same reason.

From: JPHamlett
This code here keep going into an endless loop and I cannot figure out why…

You are not allowed to use math.sqrt(), but you can use regular operators? If so, then can you do n**0.5 ?

If that is illegal then this should work for computing the square-root:

def sqrt(n,eps=0.00001):
  r = n;
  p = 1.;
  while abs(r - p) > eps:
    p = r;
    r -= (r*r - n) / (2. * r);
  return r

You left the IRC.. :P

Have you considered your loop's condition? It will never be reached..

Translated to pascal the above code is equivalent to:

function func(N: Integer): Single;
var
  guess: Single;
  avgDeter: Single;
begin
   guess := n / 4;
   writeln('Creating a guess, we will use: ');

   while (abs(n - guess) > 0.0001) do
   begin
       writeln('Condition: ', n - guess);
       avgDeter := n / guess;
       writeln('Average: ', avgDeter);
       guess = (guess + avgDeter) / 2;
       writeln('Guess: ', guess);
   end;
end;

begin
  func(144);
end.

It will print:

Condition: 108
Average: 4
Guess: 20
Condition: 124
Average: 7.199999809
Guess: 13.60000038
Condition: 130.3999939
Average: 10.5882349
Guess: 12.09411812
Condition: 131.9058838
Average: 11.9066143
Guess: 12.00036621
Condition: 131.9996338
Average: 11.99963379
Guess: 12
Condition: 132
Average: 12
Guess: 12

And finally it will hit an equilibrium.. such that the avgDeter = guess. The steps it takes are:

guess = 144 / 4 = 36

if ((abs(n - guess) = 144 - 36 = 108) > 0.001) continue.
108 > 0.001 = true.

avgDeter = n / guess = 144 / 36  = 4.
guess = (guess + avgDeter) / 2  =  (36 + 4) / 2  = 20.

--------------------------------------------------------

if ((abs(n - guess) = 144 - 20 = 124) > 0.001) continue.
124 > 0.0001 = true.

avgDeter = n / guess = 144 / 124 = 1.16129032258
guess = (guess + avgDeter) / 2 = (20 + 1.16129032258) / 2 = 10.5806451613

---------------------------------------------------------

if ((abs(n - guess) = 144 - 10.5806451613 = 133.419354839) > 0.001) continue.
133.419354839 > 0.001 = true.

avgDeter = n / guess = 144 / 10.5806451613 = 13.6097560975
guess = (guess + avgDeter) / 2 = (10.5806451613 + 13.6097560975) / 2 = 12.0952006294

---------------------------------------------------------------------------

if ((abs(n - guess) = 144 - 12.0952006294 = 131.904799371) > 0.001) continue.
131.904799371 > 0.001 = true.

avgDeter = n / guess = 144 / 12.0952006294 = 11.9055486893
guess = (guess + avgDeter) / 2 = (12.0952006294 + 11.9055486893) / 2 = 12.0003746594

---------------------------------------------------------------------------

if ((abs(n - guess) = 144 - 12.0003746594 = 131.999625341) > 0.001) continue.
131.999625341 > 0.001 = true.

And so on.. you can see that your condition is the problem and that the avgDeter & guess become very close; if not the exact same. With your condition, it will NEVER ever get anywhere close to 0.001 and so.. the infinite loop occurs.


Taking a stab based on the above numbers without messing up your algorithm, the following can be assumed to be the correct formula:

function func(N: Integer): Single;
var
  guess: Single;
  avgDeter: Single;
begin
   guess := n / 4;
   writeln('Creating a guess, we will use: ');

   while ((avgDeter - guess) <> 0) do //use epsilon instead of 0 when comparing floats.. but for the sake of simplicity here, I left it out..
   begin
       writeln('Condition: ', n - guess);
       avgDeter := n / guess;
       writeln('Average: ', avgDeter);
       guess := (guess + avgDeter) / 2;
       writeln('Guess: ', guess);
   end;

   result := guess;
end;

and you can see that for three of the test cases: 144, 25, 9 it prints: 12, 5, 3 respectively.


Translate it back to python, all you have to do.. is change the condition to:

while (compWithEpsilon(abs(avgDeter - guess))):

where compWithEpsilon should be a function that does proper floating point comparisons for you.


QED.

From: slacky
You are not allowed to use math.sqrt(), but you can use regular operators? If so, then can you do n**0.5 ?

If that is illegal then this should work:

def sqrt(n,eps=0.00001):
  r = n;
  p = 1.;
  while abs(r - p) > eps:
    p = r;
    r -= (r*r - n) / (2. * r);
  return r

You left the IRC.. :|

Sorry had network issues, and I'm so stupid. I forgot about n**.5!

From: JPHamlett
Sorry had network issues, and I'm so stupid. I forgot about n**.5!

if youre instructed to make a sqrt func, i doubt doing n**.5 would be want is wanted…

From: Turpinator
if youre instructed to make a sqrt func, i doubt doing n**.5 would be want is wanted…

The only requirement for the assignment was I couldn't use the math module.