Factorization: Some Drawings

So here’s the very high level flowchart for the factorization program. The key insight here is that the things the program does are grouped together and put inside pretty inclusive boxes. The lower-level flowcharts will start to unpack these boxes. The really interesting thing about this is that for any box we don’t really know how to implement, we can just put in a stub that pretends to do the work. Like, “Oh, I don’t know how to do prime factorization so I’m just going to print the number 5 and move on.” Computer programming is all like this: break the problem down into smaller and smaller chunks until each chunk is something you know how to tell a computer to do.Continue reading “Factorization: Some Drawings”

Programming Assignment: Prime Factorization

Last night the Badb had to find the prime factorization of a number. Thrill moment! This is exactly the problem I once wrote a computer program to solve and wound up entering that program in the school science fair. That was pretty cool.

Back when I had to solve this problem, my computer had a pretty severe limitation within its BASIC interpreter: the highest integer value it could deal with was 65,535. The clock speed on the CPU was pretty darned slow, as well. These meant that any program I wrote had to be pretty efficient if I wanted to be able to interact with it — I could feel myself aging while I waited for the computer to count to 100 — and I didn’t have to worry about really huge data structures. When the biggest array was guaranteed to hold fewer than 100,000 items, FOR..NEXT loops were not very scary.

Okay, enough reminiscing. Here’s the assignment: write a BASIC program that will accept a user’s input of a positive integer greater than 1 and less than 65,536. The program will output the prime factors of the number. The program must guard against empty, non-numeric, and out-of-range values. If the user inputs a value that does not meet the acceptance criteria then the program must print out an error message and prompt once again for input. After writing out the prime factorization of the number, the program should ask the user whether to factor another number or to exit, and then behave appropriately.

Here are some hints:

  • a sieve of Eratosthenes would probably be a good place to start to get a bunch of prime numbers
  • Any factor of a number that is greater than the square root of that number is, by necessity, part of a pair of factors — and the other half of that pair is less than the square root of the number.
  • The modulus operator (mod) might be helpful.
  • Try using pencil and paper to draw a flowchart for how to solve the problem. Start with boxes that represent big steps (“get user input”, “compute prime numbers”, etc.) and then explode the boxes until each box represents a line of actual code. This can seem kind of extreme, but it totally works and it keeps you from having to remember everything at once.

I’m gonna make some time to try to write this program myself, but it’d be super cool if any of the three of you people reading this could beat me to it. I’d be really proud!

My New Commute

Highway 85 is, unless you’re a carpool, unusable during commute hours. I’ve been trying different ways to get to NASA for the past week and so far the best I’ve been able to come up with is 70 minutes. Without freeways, there are basically two routes: mountains north and a short run east across Palo Alto / Mountain View, or mountains northeast to Los Gatos and then surface streets to Mountain View. The second option seems to run about 70 minutes both ways, while the first is about 75 (there are three schools on Page Mill and traffic is a bit slower). Five minutes is pretty much a wash. The valley route, though, has a little bit less mountain twistiness and I can get slightly better mileage on the flats even in slow commute traffic. I can drive less aggressively and be all calm and stuff, but there’s just no way around gravity when you’re going uphill.

Now I’ll start keeping track of what stores I’m passing to see if I can combine any errands with my commute.

Bagpipe Tuning

There are several pages out there that go into great detail about tuning the Great Highland Bagpipes. The real trick, for me, is making sure that the chanter is in tune. I am not blessed with perfect pitch and it can be difficult to do this by ear. On top of that, my instructor doesn’t want to spend all lesson going over the tape on my chanter and fiddling with the reed. The whole band has been given a directive: show up to practice with your chanter in tune at band pitch so we spend a little time getting our drones set and can spend most of our time playing. We use a 449 A and tune to B-flat. Our scale is thus:

Chanter Note Tuner Note Variance
G G# flat by 31 cents
A B flat
B C flat by 1 cent
C D flat by 15 cents
D E flat flat by 1 cent
E F flat by 31 cents
F G flat by 5 cents
G G# flat by 31 cents
A B flat

Kids, Start Typing!

I have finished writing a BASIC implementation of a tic-tac-toe game. There are lots of ways it could be improved or modified, and the Badb has already told me she’d be interested in a tic-tac-toe program. I’ve printed it out on paper so she can type it in, herself. This is how I learned to program: by transcribing programs written by other people, with a mixture of good and bad habits. Things that were important became clear, and things that were not important also became clear. I’ve posted the program to this site so that if you, too, would like your kid (or heck, even you, yourself) to transcribe a program and play with it you can have the opportunity.

Here are some suggestions for changes, in no particular order of difficulty:

  • Instead of requiring the enter key for responses, use looping and inkey$() to get user responses
  • Instead of grid coordinates, map each cell to a single digit (play from the number keys)
  • Allow for two humans to take turns at the keyboard, using the computer as a very expensive paper and pencil
  • Have the program loop back to the beginning after a game is over so you don’t have to type “run” every time

Feel free to add your own suggestions in the comments.

Hook ’em Early

Yesterday I downloaded Chipmunk Basic and installed it on my laptop. I did code up a quick sieve of Eratosthenes with lots of comments and helpful PRINT statements, all without cheating and looking at the sieve program included in the readme. I guess I get a gold nerd for that. Anyway, this morning I told the Badb that if she did the programming — not me, mind, but she, herself — then I was perfectly okay with her using programs to do her homework. In two seconds she went from glazed and bored to hyperalert. I took her through the code and showed her how the program worked and I could see her starting to lose focus again. I’m trying to remember all the fooling around with programs I did as a kid before I was competent enough to write programs to cheat at doing homework.

We used to have a subscription to Byte magazine; some months there’d be a printed listing of a BASIC program and my dad would have me sit at the computer and type the listing in. The programs that I remember were games, some more interesting than others. One that I spent most time on was a sort of Zork imitation. There was just a text interface, of course, with the prompt being a printed description of the room your character stood in. You explored the maze, and I don’t remember if there was even a victory condition. Maybe you had to find an object and then bring it back out; I don’t remember. The thing that impresses me now is that the program was so long and complex that even though I knew that I was typing in a puzzle as I typed in the program, I didn’t know how to solve it. But I did see how to change the game — of course, the source was right there in front of me. First, I started by rewriting the descriptions of rooms. Then I figured out how to add a room and hook it in to the existing rooms. That took some doing, since the map was just a bunch of lines of DAT statements with line numbers as the data. Altering the program altered line numbers and wound up invalidating the lookup table. I think I must have spent several months fooling around with these programs before I ever undertook writing anything more complicated than, “Hello, world!” But all that fooling around taught me lots about the BASIC programming language, about how programs are structured, about the kinds of tricks you can do when you’re actually writing the software. Hmm. Maybe I’ll start out with a game that plays Hangman. Or tic-tac-toe. Or nim.

So now I wonder, having found an archive of scanned magazines, is this something my kid would be interested in? Can it really compete with web sites that let her dress up Barbie? Man, I sure hope so! I want her to think, if she’s unhappy with the array of accessories, “I know! I’ll write my own version that has the kind of bracelets I want!”

Those Were the Days

I think I just had a sports dad moment. This has always seemed a little alien to me: in the movies there’s always the middle aged dad who still remembers his glory days in high school and relives them vicariously through his children. I didn’t have glory days in high school, I had misery. Oh, there was fun, too, but the fantasy of going back in time and reliving high school holds negative attraction for me. I would pay money not to have to do it.

And yet, there we were. Badb was doing her math homework and I was helping her understand it and we got to the last problem: “Write down all the prime numbers less than 100.” I explained to her how to use pencil and paper to perform the sieve of Eratosthenes and she got started. The first problem was that in generating the list, she skipped a few numbers. I think maybe she got bored with the task and started thinking ahead of where the pencil was writing.

I told this story to Junglemonkey and she said I should try teaching Badb to program. Programming, after all, is all about attention to detail and planning, and it would really help the kid exercise mental discipline. I thought about it and I’m really unhappy with modern computers and programming languages. All the flashy, blinking, beeping, Internet-connected whiz-bang features combined with the really loose requirements for data typing, control flow, variable declaration, and so forth that you get with modern scripting languages really gets you a recipe for frustration. She hasn’t, up to this point, demonstrated any curiosity around programming. I figured it was something like, “Dad’s doing it so therefore it must not be cool,” but seriously, a little kid doesn’t care about object oriented highly scalable enterprise middleware; she just wants to solve this problem on her math homework.

When I was in the 6th grade, my dad brought home a computer because my mom didn’t want him writing the next revision of his textbook on a typewriter. I remember writing BASIC programs to do the drudgery of my math homework for me in later years (for example, computing Pythagorean triples). Suddenly, I’m all fired up to get BASIC on the Mac Mini and get Badb writing programs to do her homework. BASIC has lots of limitations, but that’s the beauty of it. It’s got huge advantages over Perl, PHP, Javascript, C, Python, Ruby, Groovy, Haskell, Scala, Lisp, or whatever other awesome language you’re about to suggest in the comments.

  • Line numbers. Having to go renumber your program by hand (and make sure that you’ve updated all the GOTO and GOSUB line references) is a major pain in the neck. Once you do that, you learn to leave yourself lots of room for future work. To an observer this might look like “planning ahead” but that’s too specific. One doesn’t know necessarily what changes one will make, nor where, nor even if one will make them. But learning to leave oneself the option…that’s a really valuable lesson.
  • Barely functional programming paradigm. Sure, you can declare subroutines, but it’s really all just labels and line numbers with no parameters. One needs to cultivate some ability to hold the whole set of instructions in mind at once. With no encapsulation, she’ll have to be able to remember what that variable means and which sections of code modify it.
  • Really primitive I/O. This is killer. She won’t get distracted from her dimensional analysis by trying to make the units feed in from some website and play an entertaining video when the answer’s spat out.
  • Cryptic error messages. Not, “Exception processing token <sieve> on line 2,” but merely, “Syntax error,” or perhaps, “Invalid character.” It’s like one of those I, Spy puzzles but instead of looking for a nail, a 4, and two butterflies you’re looking for the instruction that the computer can’t understand. You get really good at proofreading.

I love this idea. From now on, her math will be less and less about mastering basic operations and memorizing multiplication facts and become more and more about understanding and exploring relationships between numbers. Programming can totally help with that.

Look for the Union Label

I don’t remember what inspired this train of thought this morning. Maybe it was when I drove past the junk antique shop with the Republican signage, or maybe it was just thinking about how my labels have changed although I don’t actually think my core positions have. But anyway, I started thinking about politics and political party affiliation. Over the years I’ve been affiliated with several different parties, mostly because I’d be attracted by some policies but then later repelled by either the actions of the politicians or by the real platform of the party. It took a lot of disillusionment and protest to get me around to where I am today. But fundamentally, I think people are important, more so than are things. Property is nice, certainly, and I sure do like living indoors and having a computer, but I’m not prepared to enslave or kill anyone to make that happen.

I was in a job interview recently and one of the interviewers looked at my resume and asked, “So, your degree is in drama. How did you get to software engineering from there?” This question always comes up. Depending on how I feel at the time and what I think about the people I’m talking to, I tell the story differently. I never lie, but of course one can tell the same story different ways to emphasize different points. This time, I mentioned that if I’d wanted to keep on the track from my degree (I’d been focused on theater tech, particularly electrical) then I’d either have to go to grad school and join the union or I’d have to go find a shop to apprentice in and join the union. I’d worked with union stagehands and electricians when outside events came to campus and I hadn’t been terribly impressed. I recognize that unions exist because without them the workers would be exploited horribly. I think it’s terrible that they have to exist and I deplore the management practices that make them necessary. In fact, I refuse to work in an environment where unions are the only way workers can get treated with some decency.

This post is now all of three paragraphs long, and it has taken me half an hour to write it. Once upon a time, I would have spewed out several pages by this time, but I wouldn’t have believed half of what I wrote and nobody would have been interested in reading it. Unfortunately, I didn’t really have a clear idea of where this was going when I started out and now I’ve forgotten what point, if any, I was going to make. Something about people being important (did that, paragraph one) and the story about how I dislike unions but at the same time I recognize that they’re necessary (did that, paragraph two). Anyway, I have piping to get done and that’s all the profitless noodling I’m going to do for today.

Too Much Information

I saw this story this morning, that Sandia Labs has come up with a smart bullet. That is a pretty cool thing, for sure. But way down at the end of the story there’s this quote:

“Where we’re going is to a world where the individual soldier, Marine, sailor or airman lives in a bath of knowledge. The world would be surreal in the original sense of super real. When you look at something, you see what you need to see when you need to see it,” Firestone said. “They will have the ability to make decisions more accurately and that will have a significant impact.”

This reminds me of a passage in Starship Troopers where Heinlein is describing how the powered armor works:

If you load a mud foot down with a lot of gadgets that he has to watch, somebody a lot more simply equipped — say with a stone ax — will sneak up and bash his head in while he is trying to read a vernier.

I’ve just finished reading 23 Things They Don’t Tell You About Capitalism by Ha-Joon Chang and one of the points he makes about the global financial crisis of 2008 is that the problem was not that people didn’t have enough information but rather that people were unable to understand all the information they had already. Knowledge is power, when we compare having it to not having it, but there comes a moment in time when most of the knowledge available is irrelevant and one needs to act on the one or two facts that are pertinent right now. It is certainly true that part of good user interface design is figuring out what information to reveal and what information not to reveal. Too much information at once makes it hard to make a decision.

Get Excited!

Back in October, I wrote this:

So right now, what do I want? I want to be a good piper, I want to be a good husband, I want to be a good father, and I want to put good into the world. I’m still working on the actual implementation. I guess I need to come up with a new dream. I’m not that good at dreams; I’m better at nightmares. But I refuse to work on my nightmares. I’m just going to have to get better at dreaming.

Well, check it out! What you put out into the universe comes back to you. I’m playing the pipes better and looking forward to a good competition season with a new and very difficult 2/4 march finally coming to heel. I’m very excited about a job for which I’ve interviewed, as I’ve heard that an offer is imminent. And most exciting for anyone who is not me, TechRaising is coming up! Junglemonkey has a couple of really cool ideas which I think are very exciting. I’m sure there are lots of other people with great ideas, too. I’m busy learning Javascript so that I can bring more tools to the task of making someone’s great idea a working reality. I would love to see all my fellow software developers there, too. Let’s make some cool stuff happen!