Technical Difficulties from on Top of the Mountain
  Arriving at the answer as easily as possible
I was in a lot of competitions back in my school days. There really wasn't a lot else to do. I didn't really study, and the teachers figured they better keep me busy or I'd just cause more trouble that I was already doing. So I got sent off to win trophies. There were math competitions, orchestra competitions, physics competitions, engineering competitions, drafting competitions, science competitions, accounting competitions; I even got sent off to a spelling bee once (by mistake probably, I hate spelling). But one of my favor ates was the computer competitions.

The first reason I liked computer competitions was that the school, or some local business (back when local businesses sold computers), would loan me a computer for a couple of weeks to "get ready". Actually I'd spend every night writing and playing games on them. (Back then a computer cost more than a car, so my parents had not bought me a computer of my own.) My parents didn't know what I was doing on the thing, and maybe writing games could be considered "getting ready" in any case. The second reason I liked computer competitions the best was that I liked writing programs under pressure even better than normal, as I considered myself rather good at thinking under fire, and whipping out five or six solutions in a couple of hours by myself just left those other teams of three and four people in the dust.

Interestingly enough, I often missed problems or could not come up with a solution in the time allotted. Luckily, no body else could either, but I learned from those problems, especially in competitions where they handed out the answers afterwards.

On particular problem was called magic squares. Basically you had to generate all the possible permutations of valid magic squares for a grid of size N. I of course tried to write something that would automatically permeate the board through its valid values: put a 1 in the first square, then create a list of numbers remaining and use that to populate the adjacent nodes and so on and so on. A big complicated mess of permutation trees. And I was trying to do this in BASIC on a 6502 machine. In about 20 minutes. Needless to say, I didn't succeed.

The answer turned out to be far more simple. Create a square NxN filled with the number 1. Then start adding 1 to the first square, carrying forward when it wrapped beyond N. Sure this generates a lot of invalid answers, but you just test to see if its valid at the end of the day, and only print it if it is. Wow, let the computer do all the hard work generating thousands and thousands of wrong answers and only bother to say something if it happens to find one that's right. "Brilliant!" I thought.

Computer back then could handle millions of cycles per second and thousands of pieces of information with ease. Who cares if you send them down dead ends again and again. (Besides Marvin the paranoid android) This approach turns out to be even smarter when you want an answer that's good enough, but you don't care how good enough it is. I ran into just this situation a few years later.

We were living in California and the S&L crisis had just passed which meant there were a lot of banks around with the name "Federal" in them (as in the federal government had bailed the banks out and now basically owned them). I was banking at Fidelity Federal and had my checking account, business account and mortgage there. (Its convenient to apply for a mortgage from the same back where your checking account is--when they want to know your account balance and last six months history, you can tell them to go look it up themselves.) Anyways, out of boredom I had started reducing the fractions on my checks sometimes. Like 50/100 is the same as 1/2, and in fact back in sixth grade if you wrote down 4/8 for an answer instead of 1/2, you were likely to get marked off by the teacher--it wasn't proper. So I started writing amounts like 19/25 on my checks. Then I noticed something even stranger.

SIDENOTE (for those under 30) Once apon a time the world did not run on plastic & electrons. It ran on paper. Specifically little rectangular pieces of paper, a little smaller than money, called checks. They came from the printer in little books, and we'd carry one around with us everywhere and called them "checkbooks", and they had your name & address on them and a little number on the corner which went up on each successive page. The first one was 101, then 102, etc. Actually, a check with '101' on it made you look like a newbie, so if you were really hip, you ordered your first book of checks (for your checkbook) starting with 501 or something. Then you looked really cool. And then the really bizarre part was that after you wrote a check and gave it to the store, and then the store sent it to your bank to exchange for dollars, and the bank took the money out of your account; it saved up all these little scraps of paper and sent them back to your at the end of the month. I know, you're thinking crazy, but that's what they did.

Anyways, one day I was looking at the checks that came back from the bank (ok, must have been a really slow day), and I noticed that somebody had taken the check that I wrote for eighteen dollars and 19/25ths, and had entered 19/25ths into their adding machine to verify that it came out to 0.76 and had noted on the check that it was indeed 0.76 and they had initialed it. I couldn't think of one possible reason why you would do that, but for some reason I decided that it was my mission in life to keep that guy employed, by writing every check from that day on as an odd fraction. Now even numbers were easy enough to reduce, I could divide any number between 2 and 98 by 2 easily enough, but the odd numbers were a little trickier. You can't really reduce 33/100 exactly. But then I had a wild idea. Maybe I didn't need too. Maybe I only needed to get close (like say 0.005 close). 1/3 was 0.3333333, but it rounded down to 0.33. That ought to keep that poor accountant busy for hours. Now I just needed some way to come up with the right fraction that was close enough for any decimal amount.

The solution turned out to be simple. Let the computer try a hundred numbers that didn't work and then have it stop when it found one that did. I told it to start with 0 / 1, adding one to the top if it was too small and one to the bottom if it was too big. No finesse, no optimizations; just brute force. For 0.33 it would just try 0/1, 1/1, 1/2, and then hit 1/3. For something a little harder, like 0.37 it would try: 1/1, 1/2, 1/3, 2/3, 2/4, 2/5, 2/6, 3/6, 3/7, 3/8, 3/9, 4/9, 4/10, 4/11, 5/11, 5/12, 5/13, 5/14, 6/14, 6/15, 6/16, 6/17, 7/17, 7/18 and then finally get 7/19 (which is 0.368421). Notice how it runs over the same ground a lot, like 1/2 2/4 3/6 or 2/5 4/10, but who cares. The core routine is three lines long:

dtmp= 1. * ia / ib, delt= dtarget - dtmp ; if ((-0.005 < delt) && (delt < 0.005)) break ; /** found it */ if (delt < 0.) { ib ++ ; } else { ia ++ ; } /** work closer */
Eventually I souped it up a little, adding another test to capture the results within both 0.005 and 0.001 (just for some variety), and I also made a wrapper that would call that function for all values between 0.01 and 0.99 so that I could make a little cheat sheet to carry around in my checkbook and use when I was at the store and needed to pay with a check.

Don't get a chance to use that routine much anymore these days. Press a button, pay the bill. Occasionally you might see someone in the checkout line writ ting a small novel in order to pay for two gallons of milk and a bunch of bananas, but the check book is pretty much extinct. Too bad, I kind of miss that guy in accounting.

Comments: Post a Comment

<< Home
Life in the middle of nowhere, remote programming to try and support it, startups, children, and some tinkering when I get a chance.

January 2004 / February 2004 / March 2004 / April 2004 / May 2004 / June 2004 / July 2004 / August 2004 / September 2004 / October 2004 / November 2004 / December 2004 / January 2005 / February 2005 / March 2005 / April 2005 / May 2005 / June 2005 / July 2005 / August 2005 / September 2005 / October 2005 / November 2005 / December 2005 / January 2006 / February 2006 / March 2006 / April 2006 / May 2006 / June 2006 / July 2006 / August 2006 / September 2006 / October 2006 / November 2006 / December 2006 / January 2007 / February 2007 / March 2007 / April 2007 / June 2007 / July 2007 / August 2007 / September 2007 / October 2007 / November 2007 / December 2007 / January 2008 / May 2008 / June 2008 / August 2008 / February 2009 / August 2009 / February 2010 / February 2011 / March 2011 / October 2011 / March 2012 / July 2013 / August 2013 / September 2013 / October 2013 / November 2013 / December 2013 / December 2014 / February 2015 / March 2015 / July 2016 / September 2016 / December 2016 / April 2017 / June 2017 / July 2018 /

Paul Graham's Essays
You may not want to write in Lisp, but his advise on software, life and business is always worth listening to.
How to save the world
Dave Pollard working on changing the world .. one partially baked idea at a time.
Eric Snowdeal IV - born 15 weeks too soon, now living a normal baby life.
Land and Hold Short
The life of a pilot.

The best of?
Jan '04
The second best villain of all times.

Feb '04
Oops I dropped by satellite.
New Jets create excitement in the air.
The audience is not listening.

Mar '04
Neat chemicals you don't want to mess with.
The Lack of Practise Effect

Apr '04
Scramjets take to the air
Doing dangerous things in the fire.
The Real Way to get a job

May '04
Checking out cool tools (with the kids)
A master geek (Ink Tank flashback)
How to play with your kids

Powered by Blogger