Question

Hey mates, I got stuck on the last part of the ps4. I wrote some code for the binary search, but it didn't work as I had intended. Any tips? Sorry for attach the code instead of pasting it in Codepad, Codepad isn't working properly for me on my netbook. Thanks in advance, mates :-).

Answer 1

Tips for the other parts of the code would be much appreciated also. Thanks again :)

Answer 2

Wrote a cleaner code and add comments. The codepad worked now :-) http://codepad.org/JWWvmfli

Answer 3

Damnit! wasn't logged in so it lost my long response...

Well, you are way overcomplicating your implementation of findMaxExpenses.

The only variables you need are:
-savings (use problem 2 to generate this list)
-high (last element in savings)
-low (0)
-iter (to keep track of how many iterations you run if you want)

Then, start your code with something like...
while abs(one of the above variables) > epsilon:
guess = (low + high)/2
blah blah...

I had a more detailed response but it is lost...if this doesn't help let me know and I'll try again.

Answer 4

concur.. lines 72, 85, 89
just before line 72 make two more variables - like high and low - then line 72 becomes estimate = (low+high)/2

if you get to line 82 you spent too much so you want to look below estimate, estimate becomes the top-end of the search and line 83 is becomes estimate = (low+high)/2

if you get to line 88 you aren't spending enuff so you want to look above estimate, it becomes the bottom of the search and line 89 is estimate = (low+high)/2

hope that's right, i always get the directions wrong in a binary search -

print more stuff to see what is going on: the output of my print statements look like this
http://pastebin.com/xVGBJh73

Answer 5

hmm that for loop probably isn't right , i also looped while my leftover savings (absolute) were greater than epsilon

Answer 6

Thanks for the help, mates. I rewrote the findMaxExpenses function to this: http://codepad.org/cz9wJLMJ but I found that not only my code runs infinitely, but it also converges quite strangely to 5266.26 . Any errors here, or should I double check postRetirement? It worked for the test file given to us.

Answer 7

is your comparison working? are you 'going-the-right-way' each time?

Answer 8

Actually, it isn't. It raises the expense, when it should've lowered it. I am reworking this code, while cursing enough ^^

Answer 9

Made it work, thanks guys. Gonna clean up a bit, then post it for some refinement ideas.

Answer 10

Have you ever looked at someone's binary search code and seen this line:

guess = low + (high - low) / 2

and thought why didn't they just do

guess = (low + high) / 2

There's a subtle reason why it's better. In languages where there are maximum int values the second one can overflow the limit and go negative (or some other unexpected outcome) if the values of low and high are enormous. The first line is guaranteed not to. It's not so important in python because python will automatically promote the int to a long if it gets too big. But just so you know.

Answer 11

@dmancine Interesting stuff to know, thanks :). Does languages that doesn't have that implicit conversion have that problem? Like C/C++. And does that problem exist even in higher abstractions like binary trees and so on? Thanks for the advice.

Answer 12

I think most (if not all) other languages I've seen don't do any sort of auto-promotion. C/C++, C#, Java all have strongly-typed variables, meaning you declare it with a specific type (like int) and it's always that type after that. Since Python plays fast and loose with types it can change the type of a variable at any time (more precisely, variables in python don't HAVE types). In strongly-typed languages overflow is a possibility.

Binary trees don't have this problem because you're not doing a binary search on a binary tree. A binary tree is just a tree structure where each node has two children (hence "BI"nary). But when you're adding two integers you should have this situation in the back of your mind. Except in python it's not a big deal.

Answer 13

@dmancine, Yeah, I get it now, thanks for the clarification. The problem with overflow resides more in strongly-typed languages because of the fact that memory allocation is done in compile time (preprocessor time?), rather than on run time? (I mean, static allocation, rather than dynamic or automatic). Python, as designed, can promote int types automatically, so it encounters this problem a lot less frequently?

Answer 14

In most languages an int is a "primitive" type (not implemented as a class or object). In python I think everything is an object. In other languages ints are 4 bytes (32 bits), which can only hold a certain range of values. They use 2's-complement representation to get negative values, so the range of values is -(2^31) to (2^31)-1. Negative numbers have a 1 bit in the leftmost (32nd) position. If you add two huge positive numbers you might have to carry a 1 into that 32nd position, which turns the number negative.

In strongly-typed languages there's no way to expand an int to hold a value that's overflowed its bounds. In python when an int is going to outgrow its bounds python can create a long (usually 8-byte value, but I think python just uses an infinite-precision integral data type at that point) that holds the exact value of the result, and point the variable at this new (object) value.

All primitive types are created at compile time. In Java and C# all object types are created dynamically at run time on the heap. In C/C++ some objects can be declared so that they're created on the stack.

The issue with strongly-typed languages is that once I've declared something to be an int, it's always an int, so it's always a 4-byte value. It can't point at any other type of value. If I do integer (4-byte) math that overflows the size of an integer, I lose that extra bit. If I do long (8-byte) math that overflows the size of an integer, that's fine, but if I try to store the value in an integer I'll necessarily have to throw part of it away.