Question

I'm trying to adapt a bisection search, and for some reason I think I'm stuck in an infinite loop.

Any ideas what I'm doing wrong?
Here's the code I wrote:
http://pastebin.com/6cB5kXq3

Answer 1

First, did you try any prints to see what happens?

Answer 2

I have the print statement at the end, where it should be printing ans after the program terminates. I'm not entirely sure if that's what you mean by trying prints, though.

Answer 3

One good way to debug is to simply print out values. Then, if there is a loop, you can see why you are not meeting the exit requirement for the loop.

Answer 4

I just tried printing low, high, and ans inside of the loop that tests to see if the balance is within espilon. For some reason, it keeps attempting the exact same number over and over again.

Answer 5

OK, so the number is not changing. So whatever changes it is not happening, OR, it is being reset.

Answer 6

I think it should be changing to the halfway point between the low and high, which should be changing every time a new yearly balance is made. But for some reason I either can't speak python or math.

Answer 7

I haven't ruled out the possibility that the people who develop Python suspected someone like me would try and learn to program, and have designed mechanisms in the language to mock me for being so unsophisticated.

Answer 8

*** Remote Interpreter Reinitialized ***
>>>
hi: 87.6963778101 low: 83.3333333333
hi: 85.5148555717 low: 83.3333333333
hi: 85.5148555717 low: 84.4240944525
hi: 85.5148555717 low: 84.9694750121
hi: 85.5148555717 low: 85.2421652919
hi: 85.5148555717 low: 85.3785104318
hi: 85.5148555717 low: 85.4466830017
hi: 85.5148555717 low: 85.4807692867
hi: 85.5148555717 low: 85.4978124292
hi: 85.5148555717 low: 85.5063340005
hi: 85.5148555717 low: 85.5105947861

They rapidly become the same value, so... That seems to be the issue of it doing the same value over and over. It starts out with them being different, they meet, and stay there.

Answer 9

I had a feeling I was not actually doing a bisection search. I have no idea why my idea isn't panning out, though.

Answer 10

Hmmmm.... Well, I printed out a little more....


** Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win32. ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
hi: 87.6963778101 low: 83.3333333333bal: 1000.0 x: 92.0594222868
hi: 85.5148555717 low: 83.3333333333bal: 30.1703267959 x: 92.0594222868
hi: 85.5148555717 low: 84.4240944525bal: -1027.50715327 x: 92.0594222868
hi: 85.5148555717 low: 84.9694750121bal: -2202.79030319 x: 92.0594222868
hi: 85.5148555717 low: 85.2421652919bal: -3504.56746514 x: 92.0594222868
hi: 85.5148555717 low: 85.3785104318bal: -4944.37096097 x: 92.0594222868
hi: 85.5148555717 low: 85.4466830017bal: -6535.79732444 x: 92.0594222868
hi: 85.5148555717 low: 85.4807692867bal: -8294.29513757 x: 92.0594222868
hi: 85.5148555717 low: 85.4978124292bal: -10237.1448076 x: 92.0594222868
hi: 85.5148555717 low: 85.5063340005bal: -12383.5433045 x: 92.0594222868
hi: 85.5148555717 low: 85.5105947861bal: -14754.7513111 x: 92.0594222868
hi: 85.5148555717 low: 85.5127251789bal: -17374.2825513 x: 92.0594222868
hi: 85.5148555717 low: 85.5137903753bal: -20268.1263277 x: 92.0594222868
hi: 85.5148555717 low: 85.5143229735bal: -23465.000055 x: 92.0594222868
hi: 85.5148555717 low: 85.5145892726bal: -26996.6315827 x: 92.0594222868
hi: 85.5148555717 low: 85.5147224221bal: -30898.0727538 x: 92.0594222868
hi: 85.5148555717 low: 85.5147889969bal: -35208.046634 x: 92.0594222868
hi: 85.5148555717 low: 85.5148222843bal: -39969.3315181 x: 92.0594222868
hi: 85.5148555717 low: 85.514838928bal: -45229.1853564 x: 92.0594222868
hi: 85.5148555717 low: 85.5148472498bal: -51039.814729 x: 92.0594222868
hi: 85.5148555717 low: 85.5148514108bal: -57458.8929793 x: 92.0594222868
hi: 85.5148555717 low: 85.5148534912bal: -64550.1326294 x: 92.0594222868
hi: 85.5148555717 low: 85.5148545315bal: -72383.9177484 x: 92.0594222868
hi: 85.5148555717 low: 85.5148550516bal: -81038.0025433 x: 92.0594222868
hi: 85.5148555717 low: 85.5148553116bal: -90598.2831063 x: 92.0594222868
hi: 85.5148555717 low: 85.5148554417bal: -101159.649974 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555067bal: -112826.929964 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555392bal: -125715.926631 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555554bal: -139954.569675 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555636bal: -155684.184709 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555676bal: -173060.895982 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555697bal: -192257.175996 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555707bal: -213463.557372 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555712bal: -236890.523992 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555714bal: -262770.600148 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555716bal: -291360.658463 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555716bal: -322944.469484 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -357835.518237 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -396380.115732 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -438960.836263 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -486000.314656 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -537965.441121 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -595371.995379 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -658789.766025 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -728848.205965 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -806242.680051 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -891741.366922 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -986192.883557 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1090534.70822 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1205802.48541 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1333140.30513 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1473812.05855 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1629213.98277 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1800888.51917 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -1990539.62287 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -2200049.67539 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -2431498.16816 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -2687182.34257 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -2969639.99117 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -3281674.64659 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -3626383.40791 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -4007187.68102 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -4427867.13765 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -4892597.2306 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -5405990.63711 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -5973143.04202 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -6599683.71495 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -7291831.38363 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -8056455.95782 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -8901146.7166 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -9834287.63579 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -10865140.603 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -12003937.3464 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -13261980.9901 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -14651758.2426 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -16187063.3344 x: 92.0594222868
hi: 85.5148555717 low: 85.5148555717bal: -17883134.9317 x: 92.0594222868

Now, your stop condition is:
```
while abs(balance) >= epsilon and ans <=x:
```

Ah, did not print ans, but I am printing high and low,which one or the other is coming from ans.

Answer 11

In a bisection, you do some math, see if you are where you need to be, if not, see if you are high or low. If you are high, you go half way back. If you are low, you go half way froward. But back to what and forward to what change.

That is the bisection part.

Answer 12

What's killing me: I just made it print the balance, and it's always negative, which means it should only be updating the lower bound. But for some reason it's updating both.

Answer 13

I think I'm thinking about the math wrong. I start out with my lower bound being way above zero, and then I update a low guess by setting the lower bound to a number below zero. Which means I wouldn't be getting any closer.

So maybe python is my friend, and it's just that math hates me.

Answer 14

Hmmm... Yes, having the low too hih would cause issues.

Answer 15

No wait. The low number would still be above the initial lower bound. Oh, this is killing my brain.

Answer 16

Hmmm.... yes, and it just causes the high to drop.

Answer 17

Ah, OK, so this is supposed to test each time until it gets rid of the ballance. But I see one flaw with that. It never resets the balance for the new test.

Answer 18

I'm almost positive where I messed up is what my stop condition should be. I've been trying to make it OH WOW YOU'RE RIGHT.

Answer 19

```
while abs(balance) >= epsilon and ans <=x:
if balance < 0:
low = ans
else:
high = ans
ans = (high + low)/2.0
months=1
print "hi: " + str(high) + " low: " + str(low) + " bal: " + str(balance) + " x: " + str(x)
balance=xbalance
while months<=12:
interest = moInt * balance
balance = (balance + interest) - ans
months+=1
```

There is still a problem.

*** Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win32. ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
hi: 87.6963778101 low: 83.3333333333 bal: 1000.0 x: 92.0594222868
hi: 85.5148555717 low: 83.3333333333 bal: 30.1703267959 x: 92.0594222868
hi: 84.4240944525 low: 83.3333333333 bal: 43.8763599121 x: 92.0594222868
hi: 83.8787138929 low: 83.3333333333 bal: 50.7293764702 x: 92.0594222868
hi: 83.6060236131 low: 83.3333333333 bal: 54.1558847493 x: 92.0594222868
hi: 83.4696784732 low: 83.3333333333 bal: 55.8691388888 x: 92.0594222868
hi: 83.4015059033 low: 83.3333333333 bal: 56.7257659586 x: 92.0594222868
hi: 83.3674196183 low: 83.3333333333 bal: 57.1540794934 x: 92.0594222868
hi: 83.3503764758 low: 83.3333333333 bal: 57.3682362609 x: 92.0594222868
hi: 83.3418549046 low: 83.3333333333 bal: 57.4753146446 x: 92.0594222868
hi: 83.337594119 low: 83.3333333333 bal: 57.5288538365 x: 92.0594222868
hi: 83.3354637261 low: 83.3333333333 bal: 57.5556234324 x: 92.0594222868
hi: 83.3343985297 low: 83.3333333333 bal: 57.5690082304 x: 92.0594222868
hi: 83.3338659315 low: 83.3333333333 bal: 57.5757006293 x: 92.0594222868
hi: 83.3335996324 low: 83.3333333333 bal: 57.5790468288 x: 92.0594222868
hi: 83.3334664829 low: 83.3333333333 bal: 57.5807199286 x: 92.0594222868
hi: 83.3333999081 low: 83.3333333333 bal: 57.5815564785 x: 92.0594222868
hi: 83.3333666207 low: 83.3333333333 bal: 57.5819747534 x: 92.0594222868
hi: 83.333349977 low: 83.3333333333 bal: 57.5821838909 x: 92.0594222868
hi: 83.3333416552 low: 83.3333333333 bal: 57.5822884596 x: 92.0594222868
hi: 83.3333374943 low: 83.3333333333 bal: 57.582340744 x: 92.0594222868
hi: 83.3333354138 low: 83.3333333333 bal: 57.5823668861 x: 92.0594222868
hi: 83.3333343736 low: 83.3333333333 bal: 57.5823799572 x: 92.0594222868
hi: 83.3333338534 low: 83.3333333333 bal: 57.5823864928 x: 92.0594222868
hi: 83.3333335934 low: 83.3333333333 bal: 57.5823897606 x: 92.0594222868
hi: 83.3333334634 low: 83.3333333333 bal: 57.5823913944 x: 92.0594222868
hi: 83.3333333983 low: 83.3333333333 bal: 57.5823922114 x: 92.0594222868
hi: 83.3333333658 low: 83.3333333333 bal: 57.5823926199 x: 92.0594222868
hi: 83.3333333496 low: 83.3333333333 bal: 57.5823928241 x: 92.0594222868
hi: 83.3333333415 low: 83.3333333333 bal: 57.5823929262 x: 92.0594222868
hi: 83.3333333374 low: 83.3333333333 bal: 57.5823929773 x: 92.0594222868
hi: 83.3333333354 low: 83.3333333333 bal: 57.5823930028 x: 92.0594222868
hi: 83.3333333343 low: 83.3333333333 bal: 57.5823930156 x: 92.0594222868
hi: 83.3333333338 low: 83.3333333333 bal: 57.5823930219 x: 92.0594222868
hi: 83.3333333336 low: 83.3333333333 bal: 57.5823930251 x: 92.0594222868
hi: 83.3333333335 low: 83.3333333333 bal: 57.5823930267 x: 92.0594222868
hi: 83.3333333334 low: 83.3333333333 bal: 57.5823930275 x: 92.0594222868
hi: 83.3333333334 low: 83.3333333333 bal: 57.5823930279 x: 92.0594222868
hi: 83.3333333333 low: 83.3333333333 bal: 57.5823930281 x: 92.0594222868
hi: 83.3333333333 low: 83.3333333333 bal: 57.5823930282 x: 92.0594222868
hi: 83.3333333333 low: 83.3333333333 bal: 57.5823930283 x: 92.0594222868
hi: 83.3333333333 low: 83.3333333333 bal: 57.5823930283 x: 92.0594222868

Answer 20

That last line then repeats.

Answer 21

Interesting.... Balance is going up. So the payment is geting lower when it needs to get higher.

Answer 22

I changed the order and this shows more.

```
#try to set up a bisection test
while abs(balance) >= epsilon and ans <=x:
balance=xbalance
months=1
while months<=12:
interest = moInt * balance
balance = (balance + interest) - ans
months+=1
if balance < 0:
low = ans
else:
high = ans
ans = (high + low)/2.0
print "hi: " + str(high) + " low: " + str(low) + " bal: " + str(balance) + " x: " + str(x)
```

*** Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win32. ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
hi: 87.6963778101 low: 83.3333333333 bal: 2.7582605635 x: 92.0594222868
hi: 85.5148555717 low: 83.3333333333 bal: 30.1703267959 x: 92.0594222868
hi: 84.4240944525 low: 83.3333333333 bal: 43.8763599121 x: 92.0594222868
hi: 83.8787138929 low: 83.3333333333 bal: 50.7293764702 x: 92.0594222868

Answer 23

Hmm. I borrowed some of the code for the bisection search from a simple program that was supposed to find the square root of a number:

http://pastebin.com/dqMsU0Sw

I think I goofed when I substituted 'abs(ans**2 -x)' for 'abs(balance)'. I just figured that since I was looking for a balance of zero, that it could be plugged in. Or I could be very wrong, and it might have nothing to do with the problem I'm having.

Answer 24

Well, that looks for just epsilon, or the error factor.

Answer 25

Know the epsilon delta definition of a limit? If so, that is the epsilon they mean.

Answer 26

I barely have an idea of what a limit is, in the first place. :P

Answer 27

OH my god, I just stumped upon a possibly relevant wikipedia page on an epsilon delta definition of a limit, and this is frightening. Please don't tell me I need to understand how this works implicitly.

Answer 28

That's fine. In short, it is "close enough." As in you are not there, but you are close to there, and someone has said that epsilon is close enough so that delta will be close enough.

```
while abs(balance) >= epsilon and ans <=x:
balance=xbalance
months=1
while months<=12:
interest = moInt * balance
balance = (balance + interest) - ans
months+=1
if balance < 0.0:
low = ans
print "Shot low"
else:
high = ans
print "Shot high"
ans = (high + low)/2.0
#print "hi:" + str(high) + " lo:" + str(low) + " ba:" + str(balance) + " x:" + str(x)
```

*** Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win32. ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high
Shot high

So never seeing low. It has some issues still...

Answer 29

This is how print debugging works. It lets you see what parts of the code are being called. Then you can take another swing at it.

Answer 30

Every time it shoots high or low, it makes a remark. Pretty neat.

Answer 31

Yes. Makes the output spammy... but you get to see where the code went. Now I played some other games with your code, so it might not have the same answers as you would get, but I hope you at least see how to get a little more information out of the program for debugging.

Answer 32

I'm somewhat glad I'm not actually enrolled in this course. Something tells me getting this down is gonna take quite a bit of math research on my part.

Answer 33

Well, it is all about the computational thinking. Take a big problem and break it into little problems. Solve those. Then they solve the big one.

Answer 34

Oh, and the 2011 class was for more a more advanced group of students. The 2008 is a little more normal level for MIT. Which it is still MIT, so nothing simple there. Just less of the head on math.

Answer 35

Oh wow. I was under the impression that this was a gentle intro to computer science! Aw well, I might fall back to the 2008 course or stick with this done depending on how tough this gets.

I figured out what the bug was, by the way. I was setting the high and low bounds opposite of what they should be relative to the balance. I flipped a single greater-than around and it worked beautifully.

Thanks for the insight, by the way. I possibly would have given up if you didn't make me aware of print debugging.

Answer 36

Ah, if you are doing the "gentile intro" then that is 6.189, rather than 6.000. But they did not record any videos for that, so the MechMooc uses the 6.000 videos instead. Sort of a mixed blessing.

Answer 37

I'm almost sure it was a gentle intro, haha, maybe I got lost along the way. It is 6.00, so I'm thinking I probably just wandered into the advanced intro. :P

Answer 38

I think the MIT gentle intro also reused some lectures of the 6.00. Lets see...
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-189-a-gentle-introduction-to-programming-using-python-january-iap-2011/index.htm

Hmm... Don't see any of the 6.00 vids linked there. But if you do it through the MechMooc, they mix them together.

Answer 39

Do you think it would be too redundant to start with 6.189, and then try my hand at 6.00? I kind of want a good understanding of the general concepts of programming, and I think I'm okay with struggling if I have to.

Answer 40

If you know any other language, 6.189 is just to get that stuff covered. What is a variable, etc.

6.00 is really for the computational thinking aspects. If you want to do computer science, that is critical.

If you wan more informatics, I know two other classes (one is really short) that blend well and aim at informatics.

Answer 41

To be honest, I'm just here out of a general interest. I decided on a whim that I was gonna learn python. And this looked like one of the further reaching courses, so I was attracted to it.

I actually don't even know the difference between informatics and computational thinking!

Answer 42

Computer Science is the whole thinking critically about the computer problem. Informatics is looking at information and using a computer to do it. So there is overlap. MIS, or Management Information Systems, is in the Informatics area, but tones of Computer Science has gone into refining that part of the field. This makes for highly developed MIS systems that help managers make decisions by tracking markets, employees, etc.

Answer 43

Some other comparisons:

Here is another informatics thing. Lets say you scrape all the baby name data from some web site. Then you search through for names that are uncommon, but not unpopular. Then you name your new kid one of these so that their name will be a little unique but not so odd they get hassled over it. That is very clearly in the informatics area.

A Computer Science problem might be say refining the sensors and evaluations in a train so that there are better timings to the service warnings. This allows the preventive maintenance on the train to happen on time, which reduces risks and wastes.

Both of these dealt with information. The informatics issue was almost all information handling. The science one was more refining the logic behind evaluating some more basic, automated information.

Computers are like that. There are thousands of sub-jobs for programming. Game design has a few dozen all alone. The more art parts use a physics engine to make things seem real when they program the game, but some other developer made that physics engine. So on and so forth.

Answer 44

They both seem like fascinating methods! I think eventually I'm going to investigate both, but maybe informatics is more suitable for a general interest?

Answer 45

Hard to say which is better. Give this a try:
http://www.pythonlearn.com/

It is a free book with lectures by the author. Oh, and he wrote some of the critical standards in computers, so he knows his stuff.

Then look at:
https://developers.google.com/edu/python/

It is a 2 day crash course on Python by Google, but aimed at existing programmers. Still, it is some great informatics info.

You can contrast this with the MIT 6.00 stuff and have a great idea of what sorts of things programming can do for you.

Answer 46

Thanks again. I'll look into both and see where it leads me.

Answer 47

In regards to the posted question; The loops is getting stuck because you're reaching an iteration where the high and low bounds are close enough together that adding them and dividing by 2 does not change the guess. Also, after you've run through your 12 months with a guess, you should reset the balance before starting the second loop again. You're very close to complete and you can definitely do this. Don't let the math scare you off, this isn't a math problem, it's a logic problem. You're already showing good habits with documentation and printing your values.

One thing I like to do when I run into an issue like this, is rather than going through the code for the billion and first time in the same head that created the logic, is to try to explain it to someone else who doesn't know the language or even understand the problem. When you have to explain every little bit, you forget to make the assumptions that are causing the failure and you'll spot ways to improve your code every single time.

People outside of your own head can ask the questions you're forgetting to ask yourself also; like "how much money is 92.0594222868" or "How is it ever going to be within .01 if you're working with ten digits of precision?" They probably won't ask that last one, but it was a sneaky way to remind you to round your values to hundredths precision at every step so your program can eventually hit its exit condition.

Answer 48

The loop is getting stuck, not loops... I swear English is my first language.

Answer 49

Great thread! I needed this to help me think through Bisection Search and PS1c.
And if anyone might help me out with a clarification question over here ( http://openstudy.com/updates/5376b19ce4b058cfb0dafd60) it would be greatly appreciated! I started a new thread before I found this old one...