All Star

by James Classen

So I went looking for a few open source projects that I used to use, and found out that, not only were two of them long abandoned (3 years, no updates), but that third one (which was last updated in February) won’t run on my computer because I’ve got a 64-bit operating system. And I believe x64 has been relatively common for some time now. Therefore, I have added updates to these programs to my project list. Relating to one of these, I need to give myself a refresher course in finite field arithmetic, but that shouldn’t be a strain.

Some of you may know of my fondness for music. Perhaps better described as a hopeless addiction, though not one that naltrexone would affect. My tastes remain as eclectic as ever, but my choice of medium is shifting. I’m finally seeing the advantages of joining the Internet age when it comes to music. I have purchased my video games electronically for seven years. In that same period of time, I’ve purchased perhaps half a dozen songs on iTunes. My primary concern was always quality: iTunes’ AAC format versus a CD, I always considered the CD to be of higher quality. I have purchased a handful of albums with which a digital version (MP3, or, preferably, FLAC) was available in addition to the physical media, and most recently took advantage of the Humble Bundle when it went musical: again, all FLAC albums. But what’s the first thing I do with a CD? I rip it to VBR MP3 q=5 and play it from my phone through my car stereo. So what’s the advantage? Even if I did use the CD, would I ever notice a difference in the car? With that road noise? Not a chance. And despite what I consider to be a relatively discerning ear, I doubt I could tell a significant difference without a sound system far beyond my price range. Anyway, now that alternatives to iTunes exist, I may begin purchasing my music sans the physical media in the future. Unless, of course, I’m at a show. Purchased movies and television will remain hard-copies for the time being, however; if and when I resume my Netflix subscription, it’ll be the discs, not streaming.


There are several approaches to rounding. What I was taught in school is this: round to the appropriate number of significant figures (given such information). If the current number is halfway between two numbers, round away from zero. In other words, a result gives 22.5 N, but I only have 2 significant figures, the answer will be 23 N.

In programming, I learned about the “half-to-even” approach. For the same result, the answer would round to 22 N. Whichever integer (in this case; the last significant figure is the determining factor) is even, above or below, that is what the half gets rounded to.

Some other approaches are half-up, half-down, half away from zero, half-to-odd, stochastic, and alternating. I’m not going to go into detail about how each method works, but I would like to point out a few mathematical formulas that come in handy for rounding.

Say you’re writing a program to calculate the tip to leave your waiter or waitress. 18% is fairly standard. The program on my Android will, with the selection of a check box, round the tip amount to the nearest dollar, or the total to the nearest dollar. Sometimes, however, this method winds up cheating either you or the wait staff, especially relating to small sums. Let’s use a mathematical approach to round instead to the nearest denomination d where d\in(0.05,0.10,0.25,0.50). Honestly, you could round to any number you wish; a multiple of 17¢, but that’s inconvenient for American currency, so we’ll stick with the above set for examples.

Scenario: Your bill is $7.53 (maybe a slice of pie a la mode and a drink). But you were waited on, so the staff gets a tip, as is customary (the ethics of this are a discussion for another time). 18% of $7.53 is $1.3554. Rounding up to the nearest penny gives $1.36, which is roughly 18.06%; rounding down is about $17.93%. That certainly won’t cheat either party. But if you like your tip to come out to an even dollar amount, for ease of balancing your checkbook or because you prefer to leave cash on the table, rounding up is $2.00, or about 26.53%, while rounding down is about 13.28%. If, on the other hand, you want your total to come out to an even dollar amount, rounding up gives $1.47 while rounding down gives just 47¢: either 19.52% or 6.24%, the latter of which will certainly earn you a reputation of being a cheapskate.

Solution: choose a smaller denomination to round to, either the tip or the total, doesn’t matter. We’ll leave a discussion of tax out of it for now. Let’s call the tip multiplier s, typically 18%, but adjustable in our hypothetical program. The bill is a, so as=t, and a+t=a+as=a(1+s)=v. To round the tip t to the denomination d, d\lceil{{t}\over{d}}\rceil. Same formula for the total: d\lceil{{v}\over{d}}\rceil-a (subtracting the bill amount a to get the tip amount). So let’s round the tip to the nearest 25¢. 0.25\lceil{{1.3554}\over{0.25}}\rceil=1.50. Likewise with the total: $latex 0.25\lceil{{8.8854}\over{0.25}}\rceil-a=1.47$. These work out to 19.92% and 19.52% tips, respectively. Say your waitress was…less than adequate, but still deserving of something (simply because she makes $2/hr without tips, there’s tip sharing and others are busting their butts to cover her problems, she was trying her best and just having a bad day, or any number of other reasons). Replace the “ceiling” operator with “floor”. $latex 0.25\lfloor{{1.3554}\over{0.25}}\rfloor=1.25$ and $latex 0.25\lfloor{{8.8854}\over{0.25}}\rfloor-a=1.22$. This is much more subtle than a 47¢ or 1¢ tip, generating 16.60% and 16.20% amounts, respectively, and may not impact the staff’s performance or attitude, but you did only spend $7.53.

If you wish to allow calculations of the tip with and without tax, and the tax amount is x, your values will be skewed a bit: v=as+ax+a=a(s+x+1), yet you would still use v to calculate a rounded total. as would be the amount for a rounded tip without tax included in that total, and a(1+x)s would be the value of the tip calculated including tax.

A related issue is floating point binary representation. Say you’re working with a microprocessor, and have a mere 16-bits to define a number between 0 and 14, and you want the highest possible resolution. One solution is to call the entire field floating point and multiply the stored value by 14. Thus a value of 0x0001 equates to precisely 0.000213623046875, and 0xFFFF is 13.999786376953125 (we’ll pretend that’s close enough to 14 for our purposes). That’s all well and good. Now say we want to store the value 3.3 in the memory location. This cannot be represented exactly in multiples of {{14}\over{65536}}. So what can you store, exactly, if 3.3 is out? One way to solve this is essentially the same as the above formulae. Value to store v=3.3, scaling factor d={{14}\over{65536}}. Then t=d\lfloor{{v}\over{d}}\rfloor. Or ceiling, whichever is appropriate to the application. The result will tell you the actual value being stored. If you have an offset of at=d\lfloor{{v}\over{d}}\rfloor-a

There’s one more issue I’d like to touch. Say you want to programmatically round to n significant figures in base b, whatever the input v. What we’re doing here is finding d=b^{\lfloor{(\log_b{v})-(n-1)}\rfloor}. This plugs into the formula given for tip calculation—proving its value beyond that small application.