Re: [Tutor] while loop ends prematurly
Hi again, On 2 January 2012 06:28, Steven D'Aprano wrote: >> Another answer is to use Decimal class, which CAN represent decimal values >> exactly. > > > That only applies to decimal values which can be represented using a fixed > number of decimal places. So 1/5 is fine, and is 0.2 exactly, but 1/3 is > not, since it would require an infinite number of decimal places. It's occurred to me that I should've probably used the term "exact decimal" in my comment, so please read it as such. (The general class of decimals include 3 types of decimals: exact, recurring and non-recurring. Generally when people use the word decimal they tend to mean "exact decimals". Apologies for not being clearer.) Walter ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] while loop ends prematurly
(You accidentally forgot to include the list when you replied. The easiest way (for most people) to avoid that is to use Reply-all) On 01/02/2012 01:00 AM, Sarma Tangirala wrote: On 2 Jan 2012 08:56, "Dave Angel" wrote: Easiest answer is to use integers. Scale everything up by a factor of 100, and you won't need floats at all. Just convert when printing (and even then you may get into trouble). Just to add a bit here. I've seen a couple of people do it this way - subtract the two numbers and check if the result is above a particular threshold value, and if so they are not equal. That was also in that Fortran reference from '67. The trick on that is to subtract, and compare the absolute value to an epsilon value. if abs(a-b)< threshold: equals-logic goes here else: unequals-logic goes here It can get tricky to pick a good threshold. In this case, a thousandth of a penny is clearly enough. But for many programs the threshold also has to be calculated. In APL, this comparison logic is automated, via a concept called fuzz. You typically specify the fuzz value once, and the threshold is automatically calculated by something like multiplying fuzz by the larger (in absolute value) of the two numbers being compared. These approaches are also tricky, and when they fail, debugging them can be very difficult. Another answer is to use Decimal class, which CAN represent decimal values exactly. When I implemented the microcode math package for a processor (which predated microprocessors like the 8080 and 8086), it was all decimal. We had decimal logic in the hardware for adding two-digit integers, everything more complicated was a loop in the microcode. With that system, if you printed out a value, you saw an exact equivalent of what was stored internally. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] while loop ends prematurly
Hi Steven, On 2 January 2012 06:28, Steven D'Aprano wrote: > That only applies to decimal values which can be represented using a fixed > number of decimal places. So 1/5 is fine, and is 0.2 exactly, but 1/3 is > not, since it would require an infinite number of decimal places. Just a small nit pick with the above: 1/3 is however not a decimal number. The word decimal means "tenth part", decimal numbers are generally defined/understood as numbers that are expressible as decimal fractions, meaning numbers where the denominator is a power of 10 or is an exact "tenth part". Understood as such, decimal numbers are therefore obviously accurately representable by the Decimal class which is the whole point of calling the class "Decimal". To backtrack slightly, numbers like 1/3, 1/5 etc are in general called common or vulgar fractions, the only requirement being that they have an integer numerator and an integer non-zero denominator. The class of numbers representible like this is called rational numbers and the test for whether a number can be called rational is whether it can be written as such. The set of numbers we refer to as decimal numbers then, are a subset of rational numbers, the test for whether they can be called decimal being whether they can be written as a rational number with the additional requirement that the denominator be a power of ten. Addtionally, any rational number with a denominator of which the prime factors are 2 and 5 may therefore be rewritten as a decimal number, thus we know that 2/5 can also be accurately represented by a decimal number (since the prime factors of 5 is 5), as can 1/50 (since the prime factors of 50 are 2,5,5), but 1/3 can not, since 3 has only 3 as its prime factor (and not 2 or 5), and neither 1/24 (since the prime factors are 2,2,2,3). So an additional test for whether a given rational number can be accurately rewritten as a decimal (tenth part) number, is to inspect the prime factors of the denominator. If this consists solely of 2's and 5's it can be expressed as a decimal, if any other factors are present then it cannot be accurately expressed as a decimal. A happy and prosperous 2012 to all, Walter ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] while loop ends prematurly
Dave Angel wrote: Easiest answer is to use integers. Scale everything up by a factor of 100, and you won't need floats at all. Just convert when printing (and even then you may get into trouble). Another answer is to use Decimal class, which CAN represent decimal values exactly. That only applies to decimal values which can be represented using a fixed number of decimal places. So 1/5 is fine, and is 0.2 exactly, but 1/3 is not, since it would require an infinite number of decimal places. BTW, if this is supposed to represent US legal tender, you left out the fifty-cent piece as well as the two dollar bill. http://kowb1290.com/our-two-cents-on-the-two-dollar-bill/ -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] while loop ends prematurly
On Mon, Jan 2, 2012 at 3:48 AM, brian arb wrote: > Hello, > Can some please explain this to me? > My while loop should continue while "owed" is greater than or equal to "d" > > first time the function is called > the loop exits as expected > False: 0.00 >= 0.01 > the next time it does not > False: 0.01 >= 0.01 > > Below is the snippet of code, and the out put. > > Thanks! > > def make_change(arg): > denom = [100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 0.25, 0.10, 0.05, 0.01] > owed = float(arg) > payed = [] > for d in denom: > while owed >= d: > owed -= d > b = owed >= d > print '%s: %f >= %f' % (b, owed, d) > payed.append(d) > print sum(payed), payed > return sum(payed) > > if __name__ == '__main__': > values = [21.48, 487.69] #, 974.41, 920.87, 377.93, 885.12, 263.47, > 630.91, 433.23, 800.58] > for i in values: > make_change(i)) > > > False: 1.48 >= 20.00 > False: 0.48 >= 1.00 > False: 0.23 >= 0.25 > True: 0.13 >= 0.10 > False: 0.03 >= 0.10 > True: 0.02 >= 0.01 > True: 0.01 >= 0.01 > False: 0.00 >= 0.01 > 21.48 [20.0, 1.0, 0.25, 0.1, 0.1, 0.01, 0.01, 0.01] > True: 387.69 >= 100.00 > True: 287.69 >= 100.00 > True: 187.69 >= 100.00 > False: 87.69 >= 100.00 > False: 37.69 >= 50.00 > False: 17.69 >= 20.00 > False: 7.69 >= 10.00 > False: 2.69 >= 5.00 > True: 1.69 >= 1.00 > False: 0.69 >= 1.00 > True: 0.44 >= 0.25 > False: 0.19 >= 0.25 > False: 0.09 >= 0.10 > False: 0.04 >= 0.05 > True: 0.03 >= 0.01 > True: 0.02 >= 0.01 > False: 0.01 >= 0.01 > 487.68 [100.0, 100.0, 100.0, 100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 1.0, 0.25, > 0.25, 0.1, 0.05, 0.01, 0.01, 0.01] > What happened is that you ran into the weirdness that we call the IEEE 754-2008 standard, otherwise known as floating point numbers. in quite simple terms, the way the computer represents floating point numbers means that inaccuracies sneak in when performing math on them, and some numbers can't even be represented correctly, like 0.1. You can notice this in some of the simplest calculations: >>> 0.1 0.1 >>> # seems normal? Well, python is actually tricking you. Let's force it to >>> show us this number with some more accuracy: >>> "%.32f" % 0.1 # force it to show 32 digits after the period '0.1555111512312578' >>> # whoops! that's not quite 0.1 at all! let's try some more: >>> 9 * 0.1 0.9 >>> 0.9 0.9 >>> 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 0.8999 >>> "%.32f" % 0.9 '0.90002220446049250313' >>> # what?! those aren't even the same numbers!! >>> 0.1 + 0.2 0.30004 >>> # what the hell? Usually this doesn't really matter, because we don't really care about what happens after you get way far into the decimal spaces. But when you compare for equality, which is what you're doing here, this stuff can bite you in the ass real ugly. If you replace the %f with %.32f in that debugging statement, you'll see why the loop bails: False: 0.0077 >= 0.0100 That kinda sucks, doesn't it? floating point errors are hard to find, especially since python hides them from you sometimes. But there is a simple solution! Multiply all numbers by 100 inside that function and then simply work with integers, where you do get perfect accuracy. HTH, Hugo P.S.: this problem is not in inherent to python but to the IEEE standard. The sacrifice in accuracy was made deliberately to keep floating point numbers fast, so it's by design and not something that should be "fixed." Pretty much all languages that use floats or doubles have the same thing. If you really want decimal numbers, there is a Decimal class in Python that implements 100% accurate decimal numbers at the cost of performance. Look it up. P.P.S.: for more information you should read these. The first link is a simple explanation. The second is more complicated, but obligatory reading material for every programmer worth his salts: the floating point guide: http://floating-point-gui.de/ what every computer scientist should know about floating-point arithmetic: http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] while loop ends prematurly
On 01/01/2012 09:48 PM, brian arb wrote: Hello, Can some please explain this to me? My while loop should continue while "owed" is greater than or equal to "d" first time the function is called the loop exits as expected False: 0.00>= 0.01 the next time it does not False: 0.01>= 0.01 Below is the snippet of code, and the out put. Thanks! def make_change(arg): denom = [100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 0.25, 0.10, 0.05, 0.01] owed = float(arg) payed = [] for d in denom: while owed>= d: owed -= d b = owed>= d print '%s: %f>= %f' % (b, owed, d) payed.append(d) print sum(payed), payed return sum(payed) if __name__ == '__main__': values = [21.48, 487.69] #, 974.41, 920.87, 377.93, 885.12, 263.47, 630.91, 433.23, 800.58] for i in values: make_change(i)) False: 1.48>= 20.00 False: 0.48>= 1.00 False: 0.23>= 0.25 True: 0.13>= 0.10 False: 0.03>= 0.10 True: 0.02>= 0.01 True: 0.01>= 0.01 False: 0.00>= 0.01 21.48 [20.0, 1.0, 0.25, 0.1, 0.1, 0.01, 0.01, 0.01] True: 387.69>= 100.00 True: 287.69>= 100.00 True: 187.69>= 100.00 False: 87.69>= 100.00 False: 37.69>= 50.00 False: 17.69>= 20.00 False: 7.69>= 10.00 False: 2.69>= 5.00 True: 1.69>= 1.00 False: 0.69>= 1.00 True: 0.44>= 0.25 False: 0.19>= 0.25 False: 0.09>= 0.10 False: 0.04>= 0.05 True: 0.03>= 0.01 True: 0.02>= 0.01 False: 0.01>= 0.01 487.68 [100.0, 100.0, 100.0, 100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 1.0, 0.25, 0.25, 0.1, 0.05, 0.01, 0.01, 0.01] You're using float values and pretending that they can accurately represent dollars and cents. 0.19 (for example) cannot be exactly represented in a float, and when you start adding up multiple of these, sooner or later the error will become visible. This is a problem with binary floating point, and I first encountered it in 1967, when the textbook for Fortran made an important point about never comparing floating point values for equals, as small invisible errors are bound to bite you. Easiest answer is to use integers. Scale everything up by a factor of 100, and you won't need floats at all. Just convert when printing (and even then you may get into trouble). Another answer is to use Decimal class, which CAN represent decimal values exactly. BTW, if this is supposed to represent US legal tender, you left out the fifty-cent piece as well as the two dollar bill. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor