Category Archive

I’m not a huge college basketball fan, but I am a sucker for statistics and random numbers. To predict my bracket for this year’s NCAA tournament, I wanted to improve upon the technique of a weighted coin prediction based on each team’s standing, so I used the log5 method (HT: Action Allen) to estimate a winning percentage of team A over team B, given each team’s record.

Instead of a single weighted coin flip, though, I ran a random number of trials between 0 and the percent chance of team A losing. For example, if team A has a 90% probability of defeating team B, then the predicted winner will succeed in the best of up to 10 trials, whereas a 50% chance would mean anywhere from 0 to 50 trials. (Python code for the algorithm appears below, where the inputs A and B are the season win percentages of two teams.)

This method is advantageous because it generally favors stronger teams while predicting likely candidates for upsets in the 50-60% range. My bracket predicts Tennessee, Kansas, Memphis, and UCLA in the final four, with Memphis taking it all. I probably won’t watch many of the games, but I’m curious to see how my predictions turn out.

import random

def gamePredict(A, B):
   Agamewin = (A - A*B) / (A + B - 2*A*B)
   Agamelose = 1 - Agamewin

   numgames = random.randint(0, round(Agamelose*100))
   Awincount = Alosecount = 0
   for i in range(0, numgames):
      game = random.random()
      if (Agamewin > game):
         Awincount = Awincount + 1
      else:
         Alosecount = Alosecount + 1

   if (Awincount > Alosecount):
      return True
   elif (Awincount < Alosecount):
      return False
   else:
      return gamePredict(A, B)  # Rematch!

Comprehending exponential timescales is one of the greater challenges of the human mind. As Brent pointed out:

You need a thorough understanding of the multiple levels of computing.  Programming requires understanding more levels of complexity than a mathematician, physicist, chemist, or structural engineer.

Cosmology and astrophysics as well require similar comprehension of scale from atomic fusion to stellar and galactic furnaces, and to a lesser extent geology depends on understanding the vast ages of the planet and universe.

Magnitudes such as these are difficult to understand fully, which I think contributes to the continuing challenges in the classroom over the theory of evolution. A majority of Americans do not fully accept the implications of common descent, preferring views which maintain a special status for humans, partially because it is difficult for most people to conceive of a time when there were no humans! Thinking about the world ten million years ago is daily work for a geologist, but it is nearly inconceivable for many others.

The falsificationist notion of scientific method states that no theory can be purported to be absolutely true, for science advances in knowledge by demonstrating theories to be false. Under this paradigm we cannot gain positive knowledge but instead learn through the falsification of ideas. This form of learning by trial and error (as opposed to induction) applies not only to science but also to any form of human knowledge.

When developing a computer program, for example, there is (almost) no way to prove the correctness of your code. Mathematical functions (and to a lesser extent, certain algorithms) can sometimes be proven equivalent to one another–for example, the functions f(x) = 2x and g(x) = 3x - 1x are equivalent–but the same procedure cannot be easily applied to code. Even if I write a simple procedure that takes as input any integer and returns an integer as output, I will never be able to prove the correctness of my program when compared to another method of calculating the same values. Instead, computer code improves by falsification: whenever your code behaves incorrectly you know that something must be wrong. Fixing the problem does not guarantee that the code is now perfect, but at least you can (hopefully) say the code is more correct (or less false) than the previous version.

(As a caveat to the above discussion, there are a small class of programs that can be shown to produce identical output when the limits of machine precision are taken into account. On any architecture there is a finite limit to the range of integers and real numbers, so for two procedures that output integers a case-by-case comparison could eventually determine agreement. This still does not prove correctness, though, as you can always get the right result for the wrong reason.)

Development of defect-free code, then, is a process, not a destination. Mediocre programmers think they’ve got things right, but good programmers have the ability to cleverly break their code in new ways and approach the limit of unattainable perfection.

I enabled display of avatars for “recent comments” in the left sidebar. The folks at WordPress.com enabled global support for Gravatars (globally recognized avatars), so now you can all show off your stylized personal images next to your comments.

Gravatars are linked to your email address, so whenever you enter a comment on a blog (any blog with Gravatar support) your avatar is automatically linked to your comment. Pretty sleek–get your Gravatar if you already haven’t!

Today’s guest entry comes to you courtesy of Brent Miller.

Who is the author of this essay?

Jacob asked me to write about my experiences learning how to write software and computer codes.  I got a B.S. in Computer Science from the University of Minnesota; managing to cram the “4 year” computer science part of the program in to 6 semesters.  I was 100% ignorant of how to program computers on the first day of college.  6.3 years later, a degree, 2 scientific programming internships (AHPCRC, and ARL), and 2.25 years of enterprise business software development, I’m 95% ignorant of how to program computers.  If it were up to me, anybody who’ll eventually program a computer should have at least 10 semesters worth of classes to take.

What is programming?

Read the Wikipedia article if you want to learn a definition without understanding it.  I’ll focus on scientific programming in this essay.  Your predecessors think programming is nothing but a tool to compute values.  They are correct.  Programming is a nothing but a tool to do work more efficiently.  This is not as simple as others make it sound.

Programming is not the language you use.  I repeat: the language you use does not matter at the highest level.  Please note I said level.  Programming is about levels of complexity and layers of abstraction.  Computing basic math is suitable in any language on modern hardware.  Computing huge simulations is not suitable in many languages.  The fundamental lesson to learn from these two statements is for programming to be a tool, you have to know what the right tool is for the current task.

How do I determine the right tools?

Answer: You need a thorough understanding of the multiple levels of computing.  Programming requires understanding more levels of complexity¹ than a mathematician, physicist, chemist, or structural engineer.

You took the required intro to programming course(s), right?  In my experience at UMN, these classes for non-Computer Science majors suck and the students retain nothing.  So, how do you regain that knowledge now that you have to write scientific codes for your primary research field?  What if the professor that taught it doesn’t even like programming and therefore didn’t teach you everything you should know?  What if you find yourself needing to read and write codes to do your graduate level work?

Well, you’re screwed if you don’t take the initiative to correct the mistakes of the current system.  I could discuss the inadequacies of the university system in another essay, but that won’t help us here.  universities do not teach students how to program well.  They simply use programming to help demonstrate computer related principles.  Computer Science is not the same as Software Engineering/Development.  Computer Scientists are not educated to be computer programmers; they are educated to be professional problem solvers with computers.

Let’s assume you are vaguely familiar with C++ or Java.  You know that programming requires a language (which consists of syntax and a grammar at minimum, but often has useful code libraries for repeated tasks).  You also know things have to be written in the right order to get the right results.  Great.  You can now write complex mathematical programs.  Wrong. 

What do I do now?

Do not buy a book that claims you can learn how to program well after reading it.  You cannot.  Programming well comes only from years of experience and the self motivation to continuously improve your craft.  Since programming is mostly art and partly math, individual skill determines the sustainability and quality of the codes you write.  Why should you care about the long term quality of codes?  Because it is more expensive to revise code later than to do it correctly from the start.  You must want to do things Right from the start.

Since you need to learn how to read and write code in a short amount of time, you’ll have to make sacrifices. 

You’ll need to learn the following concepts just so you can begin to understand scientific codes:

1. Computability theory
2. Data structures and how they influence the codes you write
3. Algorithms and their effects
4. Computers aren’t perfect
5. Computers do exactly what you tell them to do, unless physics affects the hardware level, or #4 shows up again from someone else’s code.
6. Abstraction
7. Reading computer codes is more important than writing computer codes.
8. Ugly code is often bad code.  Codes that look simple are often well written.
9. Stop thinking in Boolean terms.  Most things in computer science depend on other things, so yes/no or true/false logic often misses the big picture, even though computers function on Boolean logic.  Abstraction hides this from you.

Once your brain stops spinning from dense computer science theory, read Steve McConnell’s superb book, Code Complete (2nd Edition) from cover to cover.  This book is geared towards business programming, but every bit of advice is completely applicable to scientific programming.  It’s that good of a book.  This book should teach you the majority of practical knowledge you’ll need for your scientific codes.

Now what?

If you now see that programming computers well is not as trivial as arrogant non-computer scientists think it is, then you’re on the right path.  To help prove this point, I wrote a series of small programs that all compute a single number.  The screenshot in that link shows 1 computation implemented 11 different ways.  A couple of them are trivially different, but result in huge performance differences.  I needed all 6.3 years of my computer science career to be able to write, measure, and understand the impact of naive codes.

Your intro to programming course(s) were probably a waste of time and taught you the wrong things.  Once you grasp the basics as I enumerated above, try some or all of the following help correct your mistake of not getting a B.S. in Computer Science and then deciding on a scientific specialty in which to conduct computational research:

1. Ask an experienced programmer for help and take everything s/he says with a grain of salt.  Most of us spew opinions masked as gospel.
2. Read as many of the classic computer science texts as you can.
3. Read and participate in helpful programmer communities.
4. Take as many undergraduate computer science courses as you can.  Start with algorithms, numerical methods, or any other topic immediately relevant to your specialty.
5. Write simple programs.  When I took a Math department cryptography course, I did my homework by hand then wrote small programs to do the exact same computations for me.  This teaches you two things at once.
6. Write more simple programs.  The more times you start over on a new program or a rewrite, you should find yourself making improvements.  If you don’t, you’re not learning or doing something wrong.  This is key.  If you don’t see your old code as crap, then you’re failing to improve. Failing to improve is what separates the horrid programmers from the good/great programmers.
7. Try a new computer language.  You’ll no longer see programming as a language.  This is an important step in the growth process.
8. Learn what not to do.

Closing thoughts

If you treat programming as a simple tool, then you’ll likely end up with Escherian codes.  Don’t write a line of code until you’ve mentally solved the problem.  If you write the same code over and over, you’re doing it wrong.  Remember abstraction.  Simplicity is often an indicator of correctness.  If you don’t know the best way of doing something, then ask someone else.  Asking questions in good programmer communities will often yield more knowledge than you originally requested.  We like to share experiences so we can advance the discipline.

I participate in the Ars OpenForum Programmer’s Symposium because I truly believe in helping others become better programmers.  To further prove this, any of Jacob’s students or peers are welcome to email me for help or advice.  I’ll do my best to give answers or point you in the right direction.  Please get my email address from Jacob.

A good programmer knows s/he will be better tomorrow.

¹Famous quote from an E.W. Dijkstra talk (italics mine):
“The town is made up from neighbourhoods, which are structured by streets, which contain buildings, which are made from walls and floors, that are built from bricks, etc. eventually down to the elementary particles. And we have all our specialists along the line, from the town planner, via the architect to the solid state physicist and further. Because, in a sense, the whole is “bigger” than its parts, the depth of a hierarchical decomposition is some sort of logarithm of the ratio of the “sizes” of the whole and the ultimate smallest parts. From a bit to a few hundred megabytes, from a microsecond to a half an hour of computing confronts us with completely baffling ratio of 10⁹! The programmer is in the unique position that his is the only discipline and profession in which such a gigantic ratio, which totally baffles our imagination, has to be bridged by a single technology. He has to be able to think in terms of conceptual hierarchies that are much deeper than a single mind ever needed to face before. Compared to that number of semantic levels, the average mathematical theory is almost flat. By evoking the need for deep conceptual hierarchies, the automatic computer confronts us with a radically new intellectual challenge that has no precedent in our history.”

From the afterward in The Calvin and Hobbes Lazy Sunday Book (1989):

Long ago the Sunday comics were printed the size of an entire newspaper page. Each comic was like a color poster. Not surprisingly, with all that space to fill, cartoonists produced works of incredible beauty and power that we just don’t see anymore, now that strips are a third or a quarter of their former size… All the things that make comics fun to read–the stories, the dialogue, the pictures–have gotten simpler and simpler in order to keep the work legible at smaller and smaller sizes. The art form has been in a process of retrograde evolution for decades. For those of us trying to return some of the childhood fun we had marveling at comic drawings, the opportunities today are discouraging.

I like to think that Bill Watterson is pleasantly surprised with the flourishing success of web-based comics. The economies of newspapers may have drained comics of their original unrestricted creativity, but the free expression of the Internet provides an outlet for even the most underrepresented comic artist to showcase the full extent of their work. The full-featured Sunday comics of Watterson’s youth may never make a resurgence, yet I think the movement toward online consumerism will revive the spirit of Watterson’s vision in a way almost unthinkable when he wrote those words nearly twenty years ago.

This place is magical.

The tremendous success of the Wikipedia project is familiar to regular Internet consumers, but the project is not without its critics. Though many people voice concern or dissatisfaction with the open content encyclopedia, the critics I tend to run into seem to be older and infrequent Internet users who raise two primary objections:

1) Why would anyone freely contribute without motivation?

2) Won’t the intent of malicious users detract from accuracy?

Thus far, the success of open content (as well as open source) projects stands in opposition to these objections. Granted, some degree of moderation occurs to prevent large-scale corruption, but as a whole open content seems to work. The objections above, at least for some people, may stem from particular assumptions about the typical behavior of human beings–whether religious values or secular perceptions–but widespread use of the Internet provides a different perspective regarding human nature. Regarding the concerns above:

1) Human beings are not exclusively motivated by greed. Other factors (the quest for knowledge, the desire to share) often achieve greater importance, even if these factors do not translate directly to an accumulation of wealth.

2) People are not inherently malicious. Though malicious individuals exist, they are the minority of a genuinely good population.

Of course, the sample space of open content users does not encompass the entirety of humanity; perhaps chaos would ensue if everyone on Earth were given Internet access and free reign. Nevertheless, I am optimistic that collaborative Internet initiatives will play an important role in shaping a culture previously defined largely by corporate and religious dogma.

The exception to the rule often draws the most attention. This extra attention, though, does not imply extra importance.

Our minds often fixate upon that which requires the most attention, clouding our vision of the grander scheme.

Mathematics: Begin with a sequence of numbers with maximum = MAX, minimum = MIN, and length = LEN. Given a random number generator with a range [MIN, MAX], find a seed that will generate the LEN numbers of the initial sequence. (I used this technique when developing the Stocalculator.)

Personal History: Begin with an interest, idea, interest, outlook, passion, belief, or philosophy you currently hold. Given the history of events that have transpired in your life, find the initial event (or seed) that generated the sequence of events leading to your present state.

Creating a personal history timeline is an interesting and insightful game to play. Some of these seed events can be easily identified , while others can only be confined to a range of a year or so–if at all; the complexity and inter-dependence of life’s experiences can make finding initial seeds a daunting task. But it’s still fun to try.

       PROGRAM GOTO_EXHORTATION
       GOTO 48
   29  PRINT *, "could one little GOTO statement do? The downside"
       GOTO 55
   13  PRINT *, "think of the children."
       STOP
   84  PRINT *, "have been left to die a quiet and forgotten death."
       GOTO 99
   66  PRINT *, "indented. A simple GOTO statement now may save a"
       GOTO 74
   47  PRINT *, "the problem to the next generation. Please,"
       GOTO 13
   18  PRINT *, "GOTO command. In this day and age, though, there are a"
       GOTO 39
   27  PRINT *, "revived by an unwary programmer--after all, what harm"
       GOTO 29
   55  PRINT *, "may not be immediately apparent, once other people"
       GOTO 11
   34  PRINT *, "nightmares will ensue. And depending on the field or"
       GOTO 98
   48  PRINT *, "Many years ago, it may have been reasonable to use the"
       GOTO 18
   39  PRINT *, "plethora of program flow structures that GOTO should"
       GOTO 84
   98  PRINT *, "industry, legacy code can persist for much longer than"
       GOTO 66
   99  PRINT *, "Nevertheless, this ancient command is occasionally"
       GOTO 27
   11  PRINT *, "become involved in reading and maintaining the code"
       GOTO 34
   74  PRINT *, "few minutes of time, but you're really just passing"
       GOTO 47
       END PROGRAM

Over a month ago, I entered the first Olympiad of Misguided Geeks, a programming contest where entrants designed simple four-function calculators in the most creative, complex, and contrived ways possible. The winning entries are quite entertaining and interesting, and the rest of the entries have some very clever and convoluted solutions as well. I didn’t win (nor did I expect to), but I had fun creating my entry and have posted it here for posterity.

By the contest rules, a calculator was considered fully functional if it passes the predetermined set of test cases in the correct order. I decided to take advantage of this, so my entry–the Stocalculator–is essentially a calibrated random number generator. If you input the test cases in the correct order during the month of May 2007, you will get the correct results; any other input produces random numbers. (Strictly speaking, all input produces random numbers, but it just so happens that the sequence of random output matches the test cases under a narrow set of conditions.)

The Stocalculator includes a gtk GUI and can be downloaded here. The significant parts of the code are below.

float DoAdd(float op1, float op2) {
   return (float) randseq(randigit());
}

float DoSub(float op1, float op2) {
   static int sign = -1;
   sign *= -1;
   return (float) (randseq(randigit()) * sign);
}

float DoMul(float op1, float op2) {
   return (float) randseq(digitlen((int)op1) + digitlen((int)op2));
}

float DoDiv(float op1, float op2, int *isErr) {
   int numlen;
   double divseq;
   if (op2 == 0) {
      *isErr = 1;
      return -17;
   }
   numlen = randigit();
   divseq = (float) randseq(numlen);
   if (digitlen((int)divseq) < numlen) {
      divseq *= 0.1;
   }
   return divseq;
}

int digitlen(int n) {
   if (n == 0) {
      return 1;
   }
   double len = floor (log10(n)) + 1;
   return (int) len;
}

int randigit(void) {
   static int stocounter = 0;
   static int seeder = 0;
   int seed;
   double seeded;
   if ((stocounter % 8) == 0) {
      seeder++;
      seeded = (seeder - 8.5) / 4.76095228569523;
      seed = (int) round( (round(time((time_t *) NULL) / 1e7)*1e7) * (9.906966206905*pow(seeded,15) + 5.168373047642*pow(seeded,14) - 73.418531365866*pow(seeded,13) - 37.443567190224*pow(seeded,12) + 209.539291108030*pow(seeded,11) + 103.292020775069*pow(seeded,10) - 291.407341342284*pow(seeded,9) - 136.571031185250*pow(seeded,8) + 204.837010407625
*pow(seeded,7) + 89.386899043508*pow(seeded,6) - 66.937774759431*pow(seeded,5) - 26.886181269472*pow(seeded,4) + 7.159451569824*pow(seeded,3) + 2.929885410459*pow(seeded,2) + 0.201212763525*seeded + 0.037897240236));
      srandom(abs(seed));
   }
   stocounter++;
   return (int) (10.0 * ((double)random() / (double)RAND_MAX));
}

int randseq(int len) {
   int i, num = 0;
   for (i=0; i<len; i++) {
      num += randigit() * (int) pow(10, len-i-1);
   }
   return num;
}

Many times it is necessary to transform the content of a written document into a presentation. Wouldn’t it be nice if this process could be automated? After all, most of the work already went into writing the document–why perform any unnecessary work? There are a few possible approaches to this. Here’s an outline of one process that assumes Microsoft Office:

1) Use the auto-summarize in MS Word to condense the content of a document
2) Write a macro to create bulleted Powerpoint slides from the summary
3) Write a macro to import figures (if any) from the original Word document
4) Give the presentation

Anyone out there who loves writing macros?

Passed the candidacy exam today! Perhaps I’ll find a way to use today’s post in a paper or presentation…

I was going to post on INTERCAL today, but I’ll let you read about it on your own–INTERCAL amuses me less than it used to.

Instead, I stumbled across another interesting esoteric programming language: Fugue, created by Nikita Ayzikovsky in 2005. Fugue operates identically to the language Prelude, but it uses musical notation instead of ASCII text. For example, the following is the cat program (copy input to output) written in Fugue:

Prelude and Fugue are Turing-complete, but what really sold me was this statement: “it is trivial to compile BrainF*** into Prelude using just two voices”. Incredible! I must write some Fugue in the near future.

I created a database of my books using Books for MacOS X and have now exported this database to the web. My book collection is available online at library.gravityatwork.com.

The online version of the database does not show all the information contained in Books for MacOS X. In addition to keeping track of lending history, I can also give each book a rating on a 1-5 scale. This allows me to keep track of which books I have not read, since there are inevitably books that always seem to fall to the bottom of the pile. Currently, I have read 70.8% of the books in my collection. I’d like to get this number up to around 80%; I’ll post on my progress at significant milestones.

I was a bit surprised when I realized I had not yet done an entry on the BrainF*** programming language. The language itself is Turing complete, but it can cause a headache when coding. It’s a simple language to learn, though. The languages assumes a pointer that is free to move around an array of bytes, all initially set to zero. The pointer is initially at the beginning of the array, and eight characters can be used to create algorithms:

With this set of instructions (and a handy Ascii table reference), it is simple to write a line of code that prints out my first name:

+++++++++[>++++++++++.+++++++.++.++++.—–.

Isn’t it surprising that this language is not yet industry standard?

My Macbook Pro came with Comic Life pre-installed, so I decided to give it a try. What you see below is the product of this software, a built-in iSight camera, some plastic figurines, and about 20 minutes. I have not yet decided if there will be more.

A thousand monkeys may be able to randomly pound out the works of Shakespeare, but in all probability it would take longer than the age of the Universe. Creationists will often use this line of reasoning as a refutation of evolution, but the evolutionary process–although containing random elements–is not identical to the classic monkey paradox. Instead, it is more akin to a SuperMonkey, which I have coded below in Python for your amusement (and yes, I know the code could be more efficient). SmartMonkey pounds keys at random, but once a character has correctly been entered in its proper place, it is locked there. If you want to run this code, you also need to use this sample-with-replacement method.

A better monkey-model when making an evolutionary analogy, my SmartMonkey pounded out Hamlet in just 1215 iterations (~18 minutes on a dying PIII 750MHz laptop). Even for a slow SmartMonkey, this type of result could certainly be achieved well within an acceptable timeframe.

import random
import sys
import psyco
psyco.full()

if len(sys.argv) < 2:
   text = "My hovercraft is full of eels."
   desc = "Phrase: \"" + text + "\""
else:
   fid = open(sys.argv[1],’r')
   text = fid.read()
   desc = “File: ” + sys.argv[1]

charset = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P', \
'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i', \
'j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','1','2', \
'3','4','5','6','7','8','9','0','~','!','@','#','$','%','^','&','*','(',')', \
'-','_','+','=','[', '{',']‘,’}',’\\’,'|’,':’,';’,'\”‘,’\”,’,',”, \
‘/’,'?’,’ ‘,’\n’,'\r’]
test = range(1,len(text)+1)
itercnt = 0

print desc
print “SmartMonkey is pounding the keyboard…”
while sum(test) != 0:
   monkey = sample_wr(charset,len(text))
   for i in range(0,len(text)):
      if monkey[i] == text[i]:
         test[i] = 0
   itercnt = itercnt + 1
print “Number of iterations:”, itercnt

Here’s the output of a quick script I hacked together. Glancing at my keyboard, I created three sets of emoticon “eyes”, “noses”, and “mouths” to generate a set of smileys. No need to thank me.

06-29-06 Update: Added one set of eyes, one nose, and four mouths.

10-09-07: Instead of reformatting this entry for WordPress, I’m just going to keep a link to the original Livejournal entry.