You are currently browsing the category archive for the 'computing' category.
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.
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 complexity1 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:
- Computability theory
- Data structures and how they influence the codes you write
- Algorithms and their effects
- Computers aren’t perfect
- 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.
- Abstraction
- Reading computer codes is more important than writing computer codes.
- Ugly code is often bad code. Codes that look simple are often well written.
- 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:
- 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.
- Read as many of the classic computer science texts as you can.
- Read and participate in helpful programmer communities.
- Take as many undergraduate computer science courses as you can. Start with algorithms, numerical methods, or any other topic immediately relevant to your specialty.
- 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.
- 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.
- Try a new computer language. You’ll no longer see programming as a language. This is an important step in the growth process.
- 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.
1Famous 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 109! 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.”
Recent Comments