User Interface Rant

In the early days of the web, all hyperlinks were blue & underlined. Even images were outlined in blue. So all clickable links were easy to recognize. This was quickly fixed. These days, most pages have clickable images. These days, there are images that are clickable from icons that look like buttons to images you might want to see at a larger size. Seldom is there the slightest indication that they can be clicked. I ignore the boiler plate of most pages, since that's where much of the advertising or non-changing content resides. But some sites hide valuable content there - like the dates and times for events.
By default, links look like links. So web developers have to go out of their way to make this happen. Pretty strange, eh? An entire planet seemingly dedicated to user interface obfuscation.

Sudoko

I've now solved over 70 of the Project Euler site i mentioned a couple months ago. One of the problems i just solved was to generate solutions to 50 Sudoku puzzles. People solve these sorts of puzzles by hand all the time. I could have done it that way. I started by solving the first one by hand. It was pretty easy. I really only used one rule to make it happen. I thought about the rule for a bit, and decided it would be easy enough to code into a program, and that might be quicker than doing 50 by hand. And this first version solved some 29 of the 50. My program showed how far it had gotten. I used that to tackle the next unsolved puzzle by hand. And, indeed, i found an easy rule to code, and that version managed 39. From there, it might have been quicker to solve the last 11 by hand. Eventually, there were five ideas, and 46 problems were solved. One of the problems could be easily solved by hand from there if a guess was made of one of the two remaining possibilities for the cell. I decided to code in guesses. After making a guess, it would use it's previous system to see if it could get a solution. It continued to make a single guess until it either solved the puzzle, or it ran out of single guesses. All fifty puzzles were solved.

Total run time was difficult to get. What you'd like is the amount of time it takes to solve each puzzle. So, if you had a thousand puzzles to solve, you could multiply your time by a thousand and get a good estimate for how long that would take. But the total time was much less than a second. It's unlikely that the time would scale. It's quite possible that a thousand puzzles would also take less than a second.

Of notable interest is that nearly five thousand people have solved this problem. There are tons of programs that have been published that also solve this problem. So at least one person in a million, world wide, has written a Sudoku solver. That's a good deal more than i'd have expected.

Bike Log Day Four

I weighed myself just before day one. I guess that would be day zero. I'd lost five pounds compared to the previous time i'd weighed myself. That was a couple months ago. As i haven't been dieting, per se, i didn't expect to see a drop. I figured that since it was a fairly dramatic five pounds, i must have caught my weight at a low ebb. Historically, my weight has normally risen and fallen, pretty much at random, over a ten pound range, in the course of any random week. When i take a measurement, there's usually no way to take it at face value. I weigh myself approximately daily over a week, and my weight for the week is the lowest number. I figure it's easy to add weight - drinking a gallon of water is about eight pounds. But, i figure the bottom is the bottom.

A gallon of water is quite a bit. In 1986, i drank a gallon of water every day for six months, and half a gallon the other six months. It's great for your health. Now, you might think that my weight value from two months ago would also be subject to the ten pound range. But that was with several measurements. So it's likely that it really was the minimum back then.

On day two, i weighed myself again, and it was another three pounds down. So that's down eight pounds. Eight pounds is not something i lose in two months without serious effort. So this minor mystery is getting to be less minor.

Bike Log Day Three

In 1992, i rode to work every day for an entire summer. My speed started out at about 6 MPH, and ended at 21 MPH. I had a shower at work, so i could go as fast as i wanted. It was 9 miles each way, and so that first trip was an hour and a half. By the end, it was 27 minutes. Fastest transport across Boston.

Back in Boston, i started biking to work in the Spring. I really hadn't done any biking that season. Six miles per hour is the speed you can go on a bike if you're totally out of shape. Little kids who have just gotten over using training wheels can go this fast.

My first measured day this time around was a bit over ten miles per hour. It took a couple weeks to get to that speed back in '92.

Day three's first timing was 31:43, for an average speed of 11.91 MPH. That's more than 10.35 MPH. That's a 15% increase in speed in just one day. In 1992, a big speedup like this took a week. Things aren't exactly the same. One of the things that changed on this day was that instead of wearing a hooded sweat shirt, i just wore a sweat band over my ears. That means it was easier for my body to get rid of waste heat. Some of the early speed increases are going to be due to improvements in how things are done rather than in changes in physical health.

Bike Log Day Two

There is no bike log from day one. I wasn't going to log anything. After all, i probably won't bike to work for more than a few days this time. Don't worry. I won't post anything if i don't have anything to say.

The trip to work is 6.3 miles. My bike computer (odometer) said 10.11 km. I've not calibrated it to four significant digits. I haven't had this unit very long. I could have told this unit to read out in miles, but for no reason that i can discover, i told it to read out in km. So if i'm listening to jazz music on my mp3 player, i suppose it's Kilometers Davis.

It took 36 minutes and 25 seconds, according to the bike computer. My wrist watch said it took about 50 minutes. The bike computer keeps the time of day accurately. But if i stop for a street light, the bike computer stops too. There's no way that i was stopped for fourteen minutes. But i was stopped for perhaps five. I stopped my wristwatch stopwatch a bit later than when the bike computer would have stopped, so there's another two or three minutes. This anomaly is about six minutes. The man who has two clocks has no idea what time it is.

The average speed was 10.35 MPH. Again, this isn't calibrated to four significant digits. I'd read this as ten and a third MPH. The numbers probably have four significant digits of precision, but not accuracy. Precision has to do with repeatability. So you can think of the distance as a unit similar to miles, and compare day to day numbers with four digits. Unfortunately, though the bike computer has an Average Speed readout, and although the bike computer manual says that there's a trip timer, the only way to get trip statistics is to reset all values in the computer. So i lose the odometer setting. However, this value matches the bike computer's average speed readout, despite the fact that it also averaged a few previous trips. While what really matters is distance, what tracks progress is speed. I'll likely focus on average speed in the future.

interviews

I've been on both ends of the interview. I've seen that both ends pretty much suck. Interviewers ask pointless and stupid questions. Interviewees are in a half panic and act like they've lost 50 IQ points or more. It's not realistic on either side. It's mostly luck if it ends up with any kind of a match.

Despite getting resumes from recruiters, who were supposed to match requirements to experience, we seldom got the experience we were looking for. We soon discovered that only 1 in 3 candidates that we asked in for an interview actually showed up. So, we invited everyone. No big deal - i always had work to do to fill in. In one interview, the English was so bad that it wasn't clear if the candidate matched the resume or not. One guy showed up, we showed him the job in the morning. He went out for lunch and didn't return.

One of our best employees was transferred in from another department. She would never have made it through our interview. She had little actual relevant skills, but learned quickly. I spent about an hour with her about once a week in a code review. I tried not to critasize her working code too much. I'd simply make non-mandatory suggestions. Her code improved rapidly in quantity and quality. Everyone has a learning curve period. Hers was no worse than most. When she left, she tried to get me hired by her new employer. They turned me down.

These days, when i'm the interviewer, the question is "is this someone i'd like to hang out with?". It's not that i want someone to hang out with. It's just that these are the people who are the really sharp candidates. Very little else matters. I don't care if the candidate can't wake up in the morning, if they're obnoxious, if they're holding 3 other jobs. I only care if they'll get the job done.

I often get a contract with only one or a couple interviews. I often get offers for months after getting hired and i've stopped sending out resumes. How long do they think i'll wait?

I didn't send a resume or cover letter for my first interview. It was a summer job while i was in school. I'd made it through my freshmen year in Engineering, and that was enough. I didn't send a resume or cover letter for my first job after i graduated. I said i had an Engineering degree. They wanted to hire me for whatever. By the time i needed a resume, i had tons of experience on it. Many employers are looking for specific narrow skills these days, so i have to edit it down to what they want to see.

I don't say anywhere that "I have strong communications skills." My resume now has a reference to my TV show. It's a real attention grabber.

Mars attacks, every year

It's time for the Mars hoax email again. You may get email that says that Mars will appear as big as the full Moon, or even There will be two moons in the sky, and with a date, like August 27th. It comes from the 2003 Mars opposition announcement. In late August of 2003, Mars had a particularly close opposition, and in a telescope at 75x, Mars appeared as big as the Full Moon does with the unaided eye. Each summer, the email gets modified a bit more, and is pretty far from reality.

Mars doesn't get real close to the Earth every summer. Not even once a year. The next close approach is in March of 2012. Mars closest approaches that happen in Augst or September are the closest that they get. The March event won't be particularly good. But it will be worth a look.

At the moment (late July 2011), Mars is a morning object, and the visual diameter is 4.4 arc seconds. One must magnify Mars by about 400x to bring it to the visual size of the Full Moon. Fairly large back yard telescopes can achieve this. Perhaps an eight inch (200 mm) or ten inch (250 mm) diameter telescope would perform OK at this magnification. However, the atmosphere needs to be really steady to get a good view. One can expect a brief really still view about once every five minutes.

And then, you'd get a view with the kind of detail you can see on the Moon. That is, you'd see the largest areas of light and dark. No craters or mountains. For Mars, this may include a polar cap, and shades of orange. Waiting until March will give you views that are about 4 times larger in any given telescope.

The closest views of Mars at the moment can be downloaded over the Internet. They come from a rover that is on Mars - Opportunity. The twin cameras give a very human like stereo view, in color (multiple images are taken with red, green and blue filters, which combine to make color images). Further, there's a microscope, which can take images that can show detail to something like a 20th of a millimeter.

There is something about using your eyeball and a telescope and seeing it for yourself. It's different. There's still a month or so of Saturn's big show this summer. So get out to your local astronomy club's next event and take a look.

the possible future of cars

An article at Motortrend covers the proposed 56.2 MPG fuel standard by 2025. It's easy to be alarmed by the article, as evidenced by some of the comments left there. I'm not alarmed. I'm impatient. Here's why.

My 2000 Saturn (an American car) has a lifetime average of over 43 MPG, though it's still low mileage, at 290,000. A turbocharger should boost it's fuel economy by 20%. That would bring it to 52.4 MPG. A cruise control would boost highway economy by 5 MPG. That's been my experience with all my other cars. This car isn't a hybrid, or diesel, or indeed anything special. It's a cheap, reasonably peppy 4 door sedan, with air conditioning added for summer comfort and safety. Adding a cruise control would add less than $50. A turbocharger is a bit more, but not thousands. It'd be cheaper than A/C, and would pay for itself in gas. So, 56.2 MPG was achievable more than ten years ago at a reasonable price. Why wait?

I've said earlier that reducing highway speed from 70 MPH (in Michigan) to 62 MPH (100 km/hr) improves fuel economy by 17%. This hasn't changed. Not only do you save money, but your vehicle gets better range. Highway signs are cheap. They were changed to 55 MPH nationwide for a few years in the late 70's. We didn't get out of that fuel crisis because we obtained more fuel. We got out of it by improving fuel economy. One of the issues is that refinery capacity isn't growing. So gas availability is effectively capped. That's what the crisis was about.

The following was my response to the Motortrend article, including some of the comments at the time.

The BP oil spill in the Gulf has cost plenty to everyone. It's still costing us.

The American auto industry isn't at a disadvantage. My 11 year old American car has delivered over 43 MPG, lifetime average. Nearly 50 on the highway. It's just a cheap car, with A/C.

There's a saying that "There's no replacement for displacement" in the industry, meaning you have to have a big engine to have high power. But turbochargers have been in use since at least the 1940's, where they delivered higher power at lower weight, with less fuel, giving performance and range to aircraft. That's a 70 year lifetime for this particular nonsense.

This article claims that a breakthrough in battery technology is unexpected. But more than ten years ago, flywheel batteries were shown to have a 50:1 advantage in energy storage to weight ratio over lead-acid batteries. That's much better than Lithium. Everything in a flywheel is recyclable, and there are no toxic or rare chemicals.

Generic terms

One of the job titles that's pretty common is Systems Specialist. What does it mean? The word Systems is pretty generic. The solar system is a system. The one we live in has a star, some planets, asteroids, comets, and so on. So a Planetary Scientist is a Systems Specialist, right? But i work in Information Technology (IT), which is another overly generic title, but which is nearly always taken to have something to do with computers. So what is a Systems Specialist in terms of computers? Well, computers have parts too. There's the thing that actually processes data, the Central Processing Unit (CPU). There's at least one of them in every computer. But there's also specialized memory called cache, Random Access Memory (RAM), disk, networking, and various other devices. That's a computer system. Computer systems come in a number of varieties. Sometimes the same hardware can run very different software. For example, the exact same hardware might be able to run MS Windows, Linux or Apple Macintosh operating systems. So the same hardware might have very different personalities. And a Systems Specialist might not be a specialist in all of them. What kind of Systems is this person a Specialist in? Why not say Unix Systems Specialist, or whatever? Then examine the word Specialist.

When i'm asked what i do for a living, it is often the case that i'm talking to someone who doesn't do what i do. I assume they don't know the details of computers at first. So i don't launch into the details unless asked. I say, "I do something with computers". It's pretty generic. I've been asked what my job title is, and i tell them. But when they ask me what that means, and it's as generic as Systems Specialist, the only really good answer is "My job is so secret, not even i know what i'm doing".

euler

I bumped into a site that has mostly mathematical computer problems to solve. The site says that you can use any tools you want to come up with solutions. I use whatever i have at hand. That has included C, Perl, the shell, and my 25 year old HP-28C calculator. The problems are genearlly designed to require some computer programming. But some people have managed to solve some of the problems by hand(!). I have not, as yet, looked for hints elsewhere on the Internet, even though this is encouraged. The site suggests that computer programs can be written which take less than a minute to run.

At the time of this post, i've solved 36 of the over 300 puzzles. I don't attempt to limit computer time. If i get a solution, it's a solution. I expect that once i have a correct solution, it's code that will never run again, so there's not much point in optimizing the code. However, i like optimizing code...

Sometimes i make mistakes. But the system allows you to guess again if you get a wrong answer. One of the solutions i was writing had an estimated run time of a few hours. I ran it over night. But in the morning, it was still running. It turned out that there was an error, and it would never have finished. Opps. When i fixed it, i also noticed a way to speed it up, and the final version took about a minute. However, it took me a half hour to get the speed up working. I'm really just trying to get the total time spent down, except that i value my time over my computer's time.

One of the puzzles asks how many months start on Sunday in the 20th century. I could have done some calendar arithmetic (i've done it before). I could have narrowed it down with some math. But Unix (and Linux) have a calendar function, and it produces text, so how hard could it be in a shell script?

#!/bin/sh
for y in `cnt 1901 2000`; do
 for m in `cnt 1 12`; do
  cal $m $y | grep "^ 1"
 done
done

I ran this script with the output into "wc -l". The "wc" program is the Unix word count program. The "-l" option makes it count lines. So here's how it works. The "for y" loop counts years from 1901 to 2000, inclusive. That's the 20th century. The 20th century is almost the 1900's. That's because the 1st century is the first hundred years, from year 1 through year 100, inclusive. The 2nd century is from 101 to 200. Anyway, the "for m" loop counts the 12 months. "cal" is the Unix calendar program. It can take two arguments, the month ($m) and year ($y). The "|" (vertical bar) symbol tells the shell to direct the output of "cal" into the next program. The "grep" bit is the Unix search program. It stands for "General Regular Expression and Print". The regular expression is the "^ 1" bit. This expressions tells grep to only pass lines that start with a space and the number 1. It turns out that the calendar format for a month has dates right justified. If a date is "10", then there's no space before it. The default calendars have Sunday at the far left. So this little script spits out a line like this:

 1  2  3  4  5  6  7

for each month that starts with a Sunday. I run the output of the script into the word count program, having it count lines. The number of lines is the number of months that start on Sunday.

There's just one more little thing to describe. In the line "for y in `cnt 1901 2000`; do" there's a bit of syntax and a program. The syntax is the back quotes - the first just before the word cnt. The stuff in between the back quotes is a program with it's options, in this case cnt. This program is expected to print out a list, and the variable y gets set to each value on each loop. But the program cnt is something i wrote in the 1980's. It knows how to count up or down, with skips, with leading zeroes or spaces, with small functions taking the initial integer for a start, and can output in roman numerals and other formats. There must be solutions like it for other people, but this is what i've used. I've not released it to the public, for various reasons. So, if you want to use my solution, you'll have to solve this bit of the puzzle yourself.

Anyway, this solution produced an answer really quickly. It took more time to write this post than to write and run this program.

The site has a forum for each problem. Early solvers often post hints on how to solve or optimize solutions. And, often, these hints help you solve later problems. For example, there are a bunch of problems involving prime numbers. Having a good prime number test can be really handy. I peruse these and see if there's anything of interest.

This whole site is about education. A million years ago, i looked at the book 101 BASIC Games. These were games, written in the computer language BASIC. Not all of them worked. There were lots of different variants of BASIC when it was written. The programs were submitted by lots of different people using most of those variants. I studied a bunch of them to see how they worked. But it wasn't really a curriculum. The interesting thing about Project Euler is that it's more like a curriculum. Each of the problems requires a new skill or skills. The result is inductive chain learning. This can be an efficient way to learn. And, it's free.

Stress

It's been suggested that college students should be graded on attendance.
http://www.wired.com/wiredscience/2011/06/do-you-get-better-grades-with-better-attendance/
First, a couple anecdotes, and then a better idea.

I had an engineering class called Stress, with a low pass rate. The prof did everything he could think of to get students to pass. Tons of office hour time, etc. 1st day, he passed out a syllabus noting the 3 open book exam dates and all homework. All homework counted the same as an exam. Of the 4 grades, the lowest was dropped. I started the 1st week's homework, but it was clear there was only time for half of it. I was careful to hit all types of problems. I passed it in, but, of course, 50% is not a passing grade. It became clear that the prof taught the material in the book. But i could read faster than he could talk, so i stopped going to class. I did OK on the first exam. One Friday, i came in for what i thought was the 2nd exam, but he passed out a quiz. At a glance, it covered next week's homework. I hadn't done that yet. I rechecked the syllabus, and it said that the 2nd exam was the following Monday - i hadn't missed it. I handed the quiz back. The prof told me that i'd likely fail the course. I looked him in the eye, but didn't tell him i'd do OK if i didn't miss any exams. The last exam was held at the start of the last week. It didn't cover the last week's homework. I did half of that anyway. And, i passed the course.

I would never have skipped half the homework if it weren't impossible to finish. I would never have skipped the classes if the pressure to optimize my time weren't so severe. Exams have high time pressure, and i already knew that my performance would be awful on them. It was just the only choice available. I liked the course material and the prof, but it still pisses me off that the course was set up that way. If i'd known in advance, i'd have dropped another course from my schedule, so i could devote twice the time to it. So the degree means what? These are the students who managed to get through by cheating, optimization, or by being unbelievably quick? Are these skills one needs in industry? Not as far as i can tell.

There was a brief break. Then Stress 2 was taught by the same prof. I figured he'd pass out a syllabus on the first day, so i didn't bring my books or calculator. He passed out an exam! I ran home, grabbed my stuff and ran back in 20 minutes. Panting, i asked for an exam. He found me a seat and an exam that didn't match my neighbors. At the 50 minute mark, i was done (!). I looked around and there was panic on 109 faces. I figured i must have done something wrong. All these kids are brilliant. I checked my answers. No errors. So at the 55 minute mark, i got up and handed it in.

Next day, the prof writes something like this on the board:

97:	1
60-70:	4
50-60:	7
40-50:	19
30-40:	37
20-30:	23
10-20:	13
0-10:	6

At first i wondered how i'd lost 3 points. But then i realized that i'd done the course right. One of the four questions was on that last week's homework, and i was the only one who'd done even half of it. In this course, there'd be 4 exams, homework with the lowest dropped. I did half the homework. Then it was announced that the lowest two grades would be dropped. But i took the 4th exam even though i'd already passed the course.

Years later i auditioned for a chorus. It involved sight singing and a bunch of music things i'd never done before. That morning, i ran 4 miles, showered, and took the train. The director gave me my starting tenor note and played the accompaniment. I dived in, but stumbled. But then i started getting where the piece was going, relaxed a bit and read ahead. At the start of the last line, i turned the page over (while singing), but it was blank. I looked up and finished the page, adding dynamics. The director was stunned. So was i. I'm simply not that good. But a 4 mile warm up does wonders. Phys Ed should be held for 20 minutes every morning for all students. They don't have to be awake for it.

STEM

One of the big pushes in education is to get students to do well in the STEM areas. That's Science, Technology, Engineering, and Math. From my perspective, SE would be enough. That is, if you've got Engineering, that's how you build or support technology. To do either Science or Engineering, you need math. Math turns out to be one of those tools which allows you to solve all sorts of problems. You really can't do without it. Not all students are good at it. In fact, nearly everyone has to struggle with it. Being good at math is, at least to some extent, a measure of how hard one has struggled with it compared to everyone else.

One of the reasons for students to go into science or engineering is that a technological society needs people to do these things to stay competitive with other countries. And if there is a need for a skill, then there are jobs. So, that's good for the student's future.

But just to mention a contrary concept, it turns out that when you go to bigger companies that want engineers, they're also looking for engineers with communications skills. So, it is not a good idea to ignore your natural language skills. That includes reading and writing, but also public speaking. These are good skills to have.

Forth for Enlightenment, part nine of ten, primes

Prime numbers are positive integers that can only be divided evenly by themselves and the number one. So there are no factors for prime numbers. Prime numbers are great for factoring, because if there are no prime factors, then there are no factors. The first few interesting prime numbers are 2, 3, 5, 7, 11, 13, 17, 19. If you're trying to factor a number, you only have to attempt to divide the number by prime numbers up to the square root of the number. An example should make it clear why. Let's say you're trying to tell if 25 is prime. You try 25 / 2, and get a 12 with a remainder of 1. You try 25 / 3, and get 8 with a remainder of 1. You try 25 / 5, and get 5 with a remainder of 0. So 25 is divisible by 5. But notice that you divided by 5 and got 5. The number 5 is the square root of 25. If you divide 25 by 6, you get 4 with a remainder of 1. But you already checked division by 4 (it's not a prime, but it's between 3 and 5, so we have effectively checked it). We don't want to check anything twice, so we only have to check up to the square root of the number. The short list of prime numbers given is good enough to check numbers up to 528. That's because the next prime after 19 is 23, which when squared id 529. So a small list of primes allows checking of large numbers. However, memory for storing prime numbers is in short supply on the HP-28C, so we'll check all numbers up to the square root, not just the primes.

The HP-28 RPL language has pretty much everything we need. There's a function to compute square root (√). There's a division function that returns the remainder called MOD. There are loops and conditionals. Yet my first version ran into a snag. It was convenient to use a FOR loop with a local variable. Having a local variable is handy because it doesn't clutter the stack, it doesn't need to be created before you start and purged when you're done with it. And local variables can be easily recalled. However, when a remainder of zero is found, indicating a factor has been found, the next thing to do is exit the loop and report the answer. It turns out that you can't exit a FOR loop in RPL. There's no "GOTO" in the language. The loops don't have any other "break" function, for example, as the C language has. There are two solutions. One is to let the loop finish. The other is to use a WHILE loop. In my first version, I continued with the FOR loop, but changed the problem to factoring a number. It got ugly. For example, if the number was 12, it divided by 2, but failed to check to see if it could continue dividing by 2. So it didn't always result in prime factors. A second version returns the focus to primes, using WHILE.

«
  DUP √ FLOOR WHILE DUP 2 ≥ REPEAT
    DUP2 MOD IF 0 == THEN
      DROP 1
    END
    1 -
  END
» 'ISP' STO

This function takes a number on the stack. It returns two numbers. The original number is left on the stack. But also a 0 is left if there is a factor, or a 1 is left on if the number is prime. Let's walk through this a bit to see how it does it. The first thing we want to do is get the square root of the number. But we'll need the original number later, so the first thing is to push a duplicate onto the stack. The square root function consumes that duplicate and pushes the square root of that number. The FLOOR function turns that into an integer, discarding any decimal fraction. So if the original number is seven, the square root is 2.64575..., FLOOR turns that into just two. The WHILE loop is started. The bit between WHILE and REPEAT is the loop condition. As long as the loop condition is true, the loop will execute. We'll need this square root, so DUP is used to make a stack copy. Then 2 ≥ compares it to 2 and the loop runs as long as the number is still at least 2. At this point we have the original number and the current number to check on the stack. We'll need both later, so DUP2 is called push a copy of both on the stack. MOD gets the remainder after division. I doubt that the IF does anything, but 0 == compares the remainder to zero. THEN executes the block to the matching END if the answer is true. If the remainder was zero, what we want to do is exit the loop, returning something that means the original value isn't prime. We have two items on the stack at this point. That's the original number and the current number to divide by. We DROP this number to divide by and push the constant 1 on the stack. After the IF THEN END, we have the current number to divide by on the top of the stack. We subtract one from it. If we had just pushed one on the stack, it becomes zero. If we just divided by two, which is the last number we check, it becomes one. In either of these cases, the loop stops. But if there are more numbers to check, they get checked in subsequent loops.

There are better ways to check for prime numbers. For example, a simple optimization is to first check if the number is divisible by 2. If it isn't even, then only the odd numbers up to the square root need to be checked. For large numbers, this could double the speed. There are other ideas as well. Some require lots of memory. Some are quite complicated. So we won't consider them now.

The main point of this exercise was to show how searching can be accomplished on this machine. Searching requires breaking from a loop that's in progress. A design decision in RPL was to not provide an explicit loop break mechanism. In fact, there is no GO-TO like function in the language. While anything you could want to implement can be implemented in this language, it isn't necessarily very easy. The loop structures available that work for this are WHILE-REPEAT-END and DO-UNTIL-END. My first thought was that these loops are equivalent and have their test at the start of the loop. But it turns out that the test can be placed anywhere in the loop. That is, any arbitrary commands can be placed between the WHILE and REPEAT clauses, and nothing need be placed between REPEAT and END. It turns out that one can not use WHILE-REPEAT-REPEAT-END to get the effect of two exits in one loop.

This bit about having to change the condition of the loop to break out of it is part of a wider issue. In 1968, Edsger W. Dijkstra published an often quoted paper entitled Go To Statement Considered Harmful. The paper starts with this line: For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of go to statements in the programs they produce. Note that he has a value judgment not on the programs written, but on the programmers who wrote them. Programs in languages like FORTran (at the time) absolutely required the use of go-to statements. And in such programs, it was easy to end up with spaghetti code that was very difficult to follow. And that is the gist of the paper. But the opening line suggests that the fewer go-to's in a program, the better the programmer. It had been proven that go-to statements were never necessary in languages that support if-then-else and loops or recursion. The logical conclusion is that programmers who never use go-to statements are as good as one can get. This conclusion isn't correct. Once the right languages appeared, the goal of zero go-to's became possible, but a new issue reared it's ugly head. The issue is breaking from a loop. There are two easy ways to do this in a language like C. First, one can jump out of the loop with a go-to. Second, one can create a state variable and set it so that when the loop test is executed, the loop exits. And what happened in the go-to's are evil era was that all such loops were exited using a state variable. There are at least two problems with this approach. First, extra instructions to set up a test must be executed. Often there are extra instructions in the test itself that are executed each loop. Second, compilers of the day had no idea how to optimize this sort of code. Third, state variables can be just as difficult to follow as go-to's are. For example, if there are four state variables, it's just as difficult to understand as four go-to's. Except that if all four go-to's are clearly loop exits, then they're very clear after all. The Internet didn't exist back in the '70s, so most people never read the original paper. They just latched onto that first statement, and used it as Gospel. These days, we have less of an excuse. It's an easy read. It's quite clear that the go-to's are always bad concept is an over-generalization. After all, Dijkstra makes an exception for machine language. Why make an exception there? Well, the flow control in machine language generally is all built on some form of go-to. There's no choice. And besides assembly language programmers are generally better than those who can't code in assembler. What i mean by this is that assembly language is not generally the first computer language that programmers are taught. By the time one is writing assembly language, they have considerably more experience. It turns out that there are other exceptions to go-to's being poor practice.

In any case, the designers of RPL decided not to include a go-to. And, the decision made it sometimes more difficult for the programmer to achieve certain goals. But nothing was made impossible. And, there may have been a performance reason for not including a go-to. Some of the Scheme language environments allow go-to, but performance for all structures suffers all the time because of it. That means that performance for the Scheme implementation suffers. It's a big deal.

There was one other observation of note during this project. I ran across a list of software errors for the HP-28 (they're at the bottom). I tried some of these on my unit, and they were all problems. So one issue with having a system strictly in hardware is that it can't be fixed. The software in something as complicated as the HP-28 series is way too large to have any hope of being bug-free. The bright side is that the language can't change out from under your program. I've been bitten by Light Year conversions getting inaccurate results.

Lots of applications written for the HP-28 series are available through this site.

Conclusion:The HP-28 is a highly capable machine. The RPL language is concise, making it a good match for limited machines. However, it can be difficult to estimate how much memory a structure or chunk of code might consume without actually trying it. The stack manipulation slows writing of functions, and can make reading functions difficult. Since tail recursion optimization is not supported, the system is not a particularly good place to experiment with recursion.

As always, any questions, leave a comment. I'll get it and respond, even if this post is ancient history by the time you read it.

Fear of Math

Fear of Math is real. If one adds 2 + 3 and gets 6, it's not close. It's wrong. All math requires careful approach, careful execution, and careful cross checking. For example, in 2 + 3, start with two fingers, and add three more. The answer is 6. But 2 is even and 3 is odd, and an even plus an odd is always odd, and 6 isn't odd. All this careful stuff requires a huge investment, and if there is a perception of likely failure, the return on investment calculation (which for some reason is easy for everyone as it is a right brain function though apparently with output directly to the amygdala) comes up negative. It's no wonder that no one wants to do it. Just for fun, anxiety shuts down short term memory. Proof positive that God isn't very smart - though one can sort of see the evolutionary advantages. The left brain style computations aren't as fast as the right brain reactions. So right brain reactions kept our ancestors from getting eaten more often.

My approach has been mostly to make the math work more reliable. For example, when my son was adding 2 + 3, he got 4, 1/3rd of the time, 5, 1/3rd of the time and 6, 1/3rd of the time. I had to watch him do this quite a bit before i figured out that he somehow was taught counting on his fingers in an unreliable manner. I introduced him to the Japanese abacus, and in twelve weeks his addition and subtraction was reliable. I then showed him that he could use his fingers like an abacus (for two digits), and his math scores went from behind the class to ahead. Also, every time we were in the car, i drilled him mercilessly on "what is seven plus eight", "what is eight plus seven", "what is fifteen minus seven", and "what is fifteen minus eight". He eventually relented and memorized the answers. He was, however, incredibly stubborn. For the record, his memory is astonishingly good. He can normally repeat anything i've said just once in the past year verbatim with minimal prompting.

But in 7th grade, i'd spend all weekend getting him caught up with his homework, and he refused to turn it in. The next weekend, i'd spend all weekend making him do it over. Old homework that was finished started appearing out of nowhere, but i still couldn't get him to turn it in.

I've just reviewed my own K-8 report cards. While i was always at least a little above average in math, in 8th grade all my grades jumped up permanantly. I recall nothing of the sort. My son seems to have had a maturity growth spurt at the end of 7th grade. I hope so.

Autism and the Hypocondriac

Steve Silberman from Wired magazine wrote a seminal paper in something like 1993 about autism. It's definitely worth a read. It's not the last word on the subject. He knows this, otherwise, he wouldn't be writing a book on the subject now.

You should know that i'm an Engineer, and furthermore, one who has pursued a career in computer programming. Since i've done both, i'm qualified to say that computer programming is like engineering, only much, much more difficult. My ex wife has accused me of having autism. OK, so being obsessive compulsive is something one needs to be a halfway decent computer programmer. And since the computer does exactly what you tell it to, no matter how stupid that might be, having the attention to detail to spot the most minor of flaws is something one needs. These skills, and others, can be viewed as symptoms of autism. One expects that all such people must have at least some bits of the autism spectrum. Still, i thought the idea was silly. These skills can be learned.

The article above has a link to an autism test. The test itself is not diagnostic. That is, it won't tell you if you definitely have or do not have autism. But a control group who took the test averaged 16.4 - and 80% of those diagnosed with autism or a related disorder scored 32 or higher. My score was eleven. One of the common symptoms of autism is an inability to tell lies. It's not that the autistic person avoids untruth. Telling an untruth isn't thinkable. It doesn't make any sense. So, either this is a lie or it's not. Either way suggests i'm not autistic.

Forth for Enlightenment, part eight of ten, Backwords 4

In part six, a full runnable program was presented. But the startup time, generating the random puzzle, takes forever. How to speed it up? One thing to try is to abandon strings, which aren't randomly writable, and use arrays, which are. Characters aren't allowed as a data type in arrays. Only numbers are allowed. All we need are 9 different numbers. But some numbers are easier to convert to characters than others. In particular, the ASCII values of characters can be directly converted. The code for lower case "a" is 97, with the alphabet following sequentially. An array is created with the highly imaginitive name "a". Here's the code:

« 97 105 FOR x x NEXT { 9 } →ARRY 'a' STO » 'MKARRR' STO

The 97 105 FOR x starts a loop from ASCII values 'a' through 'i'. The next x pushes that value onto the stack. NEXT ends the loop. At the end of the loop, 9 values are on the stack. The list { 9 } is pushed, which is used by →ARRY to create an array on the stack of length 9, using the numeric values just pushed. This array is stored in the variable a. The whole function is called MKARRR.

Given the array, we need a function to shuffle it. But such a function will probably need a helper function that swaps values at two positions. It's a bit more complex. Two positions from 1 to 9 are placed on the stack before called.

«
  DUP2 'a' SWAP 1 →LIST GET
  SWAP 'a' SWAP 1 →LIST GET
  ROT 1 →LIST 'a' SWAP ROT PUT
  'a' SWAP ROT 1 →LIST SWAP PUT
» 'SWAPA' STO

You can see that each line ends with GET or PUT. These are the functions that get or put values into an array. Both GET and PUT require a list for the array index. that's because arrays can be two dimensional, and making the coordinates a single list allows the same number of arguments for any array dimensions. A stack track should help see what's going on. The function is passed two array indexes to swap, which are called x and y below.

start	x	y
DUP2	x	y	x	y
'a'	x	y	x	y	'a'
SWAP	x	y	x	'a'	y
1	x	y	x	'a'	y	1
→LIST	x	y	x	'a'	{ y }
GET	x	y	x	yval
SWAP	x	y	yval	x
'a'	x	y	yval	x	'a'
SWAP	x	y	yval	'a'	x
1	x	y	yval	'a'	x	1
→LIST	x	y	yval	'a'	{ x }
GET	x	y	yval	xval
ROT	x	yval	xval	y
1	x	yval	xval	y	1
→LIST	x	yval	xval	{ y }
'a'	x	yval	xval	{ y }	'a'
SWAP	x	yval	xval	'a'	{ y }
ROT	x	yval	'a'	{ y }	xval
PUT	x	yval
'a'	x	yval	'a'
SWAP	x	'a'	yval
ROT	'a'	yval	x
1	'a'	yval	x	1
→LIST	'a'	yval	{ x }
SWAP	'a'	{ x }	yval
PUT

The stack is used for temporaries. It starts with DUP2, because both GET and PUT will consume an index for both coordinates. From there on out, it's all about goofing around with the stack until the arguments are in the right places. One can test this function by running MKARRR, entering two indexes on the stack, calling SWAPA, and looking at the a array for the results.

We need a new shuffle that uses this routine to create a puzzle.

«
  1 9 FOR x
    x x RAND * FLOOR 1 + SWAPA
  NEXT
» 'SHFLA' STO

Clearly, 1 9 FOR x starts a loop that runs 9 times.
Two x's are put on the stack. RAND returns a random number between zero and 1. It's multiplied by the current x, the integer part is extracted with FLOOR. Then one is added with 1 +. This produces a number from 1 to x. Finally, that first x on the stack and the computed random number between 1 and x are swapped with SWAPA. So each value can get swapped to any other position. This whole function takes about 6 seconds to run on the HP-28C. While there probably are ways to make this faster still, six seconds is fast enough.

We still need a function which turns the array into a puzzle string. It's quite simple. The CHR function turns an ASCII number into a single character string. The '+' operator concatenates strings.

«
  a ARRY→ DROP ""
  1 9 START
    SWAP CHR +
  NEXT
» 'A2S' STO

The entire a array is put on the stack as a single object. ARRY→ converts that into the individual values with the list { 9 } at the top of the stack, which is then DROPped. A zero length string is pushed onto the stack so that it can be appended to. The second line starts the loop. An ASCII value is SWAPped to the top of the stack, converted to a one character string, and appended to the running string answer. And that's all there is too it.

Finally, a modification of 'BACK' is needed that uses the new shuffle.

« CLLCD MKARRR SHFLA A2S
  1 'BMV' STO
  WHILE DUP "abcdefghi" ≠ REPEAT
    BMV 1 DISP 'BMV' 1 STO+ DUP 2 DISP
    DO UNTIL KEY END STR→ REV
  END
  2 DISP
  "You win" 3 DISP
  'BMV' PURGE
  'a' PURGE
» 'ABACK' STO

And that's it. This version is quite a bit larger, but also quite a bit faster. Usually, in space vs. time trade offs, the code size is ignored. In this case, the code size is nearly everything. Have a bit of fun with it.

Forth for Enlightenment, part seven of ten, Backwords 3

At this point, a diversion to playing the game is in order. If you examine the program, you might notice that when the program ends, it always says "You win!". You could quit before winning, but the game isn't that difficult. You always win. Compare that to a simple eye-hand coordination game like Tetris. There, you always lose. Always. With this positive reinforcement, one might expect that players would never stop playing.

There's a very simple algorithm for coming up with a solution to any problem. And, it turns out that 2 * n - 3 (on the HP-28, that's n 2 * 3 -) moves are required, as a maximum, and usually fewer. And when i learned this game so many ages ago, that's about all i knew about it. I had to figure out what the algorithm was. And it's pretty simple.

Note that if you get the last symbol, the "i" into the right most position, you should never have to move it again. So, if you build the string backwards one symbol at a time, you're done. What you do is search for "i", reverse it to the left most position. Then with "9", reverse it to the right most position. Then search for "h" and do the same. This seems to take two reverses per digit, so for a string with n symbols, you should have to perform 2 * n moves. But when you get to the first symbol, a in this case, it's already where you need it. So that's two moves you don't need, or 2 * n - 2. The remaining exercise is to figure out what other move you don't need. In any case, often, when you search for a symbol, it's already in the first position, so you don't need to get it there. Sometimes it's already in the position you need it to go to, so you save both moves. So the formula gets you a maximum number of moves. It may be fewer.

One might ask if there are optimum solutions that don't follow this algorithm. And there are. And in my opinion, that's where the real fun for this game lies. I've written optimal solution finders in C and Perl. And even the Perl version can find all optimal solutions for puzzles of length 9 in an hour on a modern computer. The C version can do it in under a second. How many puzzles of length 9 are there? Here's how to figure this out. If you're looking for a random puzzle, the first position can be any of 9 symbols. But having chosen one of these, there are only 8 symbols to choose from for the next symbol. So the first two symbols can be 9 * 8. Continue this way until the last symbol, from which there is only one left. The answer turns out to be 9! - that is 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880. I'd like to say that this was computed with my factorial program, but it had already been deleted. So the built in FACT function was used instead. Blame it on the low total memory area of the HP-28C.

Once one has an optimal solution generator, then one can compare the simply algorithm performance to the optimal solutions. In this table, Moves is that number of moves required. Optimal is the number of games with that many moves, and Auto is the number of games with that many moves using the simple algorithm. You can see that zero moves (starting with the solution) through two moves have the same number of games. That's because for those games, the optimal solution is the same as the easy solution. But there are no games where the optimal solutin requires more than ten moves. This table is for games of length nine.

Moves	Optimal	Auto
0	1	1
1	8	8
2	56	56
3	391	252
4	2278	980
5	10666	2968
6	38015	7798
7	93585	16836
8	132697	31396
9	79379	48636
10	5804	63868
11	0	68432
12	0	59233
13	0	39268
14	0	18108
15	0	5040

My evolution for puzzle solvers for this game over the years is interesting in it's own right. The first solvers were brute force with minor optimizations. They were written in C, but ran on machines that required hours of CPU time to solve a single puzzle. It would take years to generate all solutions of length 9. Modern computers are easily 10,000 times faster, so it would only be days now. But an idea came to me for solving all puzzles of length 9. One started with the solution. Each possible last move was generated, and that puzzle with the final solution move was recorded. Then, each of those puzzles was subjected to a single move as well. If the puzzle had already been recorded, the solution was ignored. Otherwise the puzzle and the move to get to a solved puzzle was recorded. This proceeded until all puzzles were recorded. In the early 1980's 362,880 puzzles would not fit into RAM except on large and expensive machines. For home machines the answers had to be stored on disk, and searched. By the late 1980's, everything could be kept in RAM even on home machines. But then my buddy Karl came up with an algorithm that could get an optimal solution to a single puzzle essentially instantly. It was so fast that it was quicker to generate puzzle solutions independently than all at once. And, no significant data needed to be stored. Further, with it's principals, one could solve any puzzle by hand, and quickly. Now that this has happened, i don't play the game very much. It's peculiar, but one of the goals of writting these puzzle solvers is to render the game less interesting. And this is done by attempting new techniques, and using the computer to prove that they are, in fact, essentially perfect. In this case, the computer didn't teach me the techniques, however. I have other, more complicated games, where the computer's brute force searching has lead to strategies that can be learned from study of the computer's play.

Forth for Enlightenment, part six of ten, Backwords too

One of the problems that had yet to be solved in the previous post is creating a new puzzle. And, the cat was let out of the bag, in that the HP-28 has no way to write into the middle of a string. However, we have already created a function, REV, that changes a string. Further, if the string starts out with no duplicate characters, it stays having no duplicates. So one idea is to call it a bunch of times with random reversals. The idea is to call the function often enough to randomize the string, but not so often as to take too long. After some experimentation, 30 calls was settled on.

« 1 30 START
    RAND 8 * 2 + FLOOR REV
  NEXT
» 'SHFL' STO

You can test this function by keying in the string "abcdefghi" and pushing the user defined key under 'SHFL'. This function takes about 18 seconds to run. It's too long. Most people can wait about 7 seconds before they start thinking about something else. At 18 seconds, they're thinking about getting a cup of coffee. I don't drink coffee.

Back in 1988, i had an 7.16 MHz 8088 based PC clone (switch selectable to 4.77 MHz). There were two C compilers. Microsoft C 5.0, and Borland's Turbo C. Turbo C seemed like it was infinitely faster. But timing tests showed that it was only three times faster at compiling programs. The expectation was that Borland must have been at least ten times faster. But here's what was really going on. Compiling a program that took 20 seconds in Microsoft's compiler would take about 7 seconds to compile with Borland's Turbo C. It turned out that typical C program files acted exactly this way. For larger projects, there were multiple files, and each turned out to take about 7 seconds to compile with Turbo C. When modifications were made to a program, typically only one file would be edited, and the compiler was smart enough to compile only the edited files. The developer experience was that Turbo C was always quick, while Microsoft C was always slow. It was worse than this, though. Turbo C really understood the new ANSI (now ISO) C standard, where Microsoft C 5.0 would only happily ignore the new syntax. And i encountered real working C code that would actually crash the Microsoft C compiler. Microsoft could refund me the more than three times higher cost any time now, and i wouldn't be quite so pissed off.

All this to say that while this solution is quick to write, it isn't very satisfactory. However, i went on to write the rest of the game.

« CLLCD
  "abcdefghi" SHFL
  1 'BMV' STO
  WHILE DUP "abcdefghi" ≠ REPEAT
    BMV 1 DISP 'BMV' 1 STO+ DUP 2 DISP
    DO UNTIL KEY END STR→ REV
  END
  2 DISP
  "You win" 3 DISP
  'BMV' PURGE
» 'BACK' STO

After you enter this program, you can run it by clicking on the user key labeled 'BACK'. It clears the screen first, and after what seems like forever, it puts up the new random puzzle. It then waits for single key presses. When it gets a digit between 1 and 9, it reverses that many letters, checks to see if you won, and if not, waits for the next key. You might notice that there is a symbol on the top of the screen that says that a program is running, even though it's waiting for you. When you finish the game (that is, when you win), it prints "You win". You can quit a game by pressing the "ON" button. It will probably leave the current puzzle string on the stack.

A closer look at the program shows that it starts with the solution and passes it to SHFL. It creates the variable BMV, with the value 1. This is the count of moves so far. It might have meant "Backwords MoVes". It then loops until the string is the solution string. It displays the current puzzle and the current move. The DO UNTIL KEY END is an idiom to get a character for input. The KEY function does not wait for a key press. There isn't a built-in function to wait for a character. So you must provide the wait loop yourself. The key comes back as a string. What was needed was a number. The STR→ function converts the string into a number. It wasn't my first guess for a function that might do that. It's passed to REV without any error checking. I mean, you could press anything. If you press the SOLV button, it turns out that STR→ can't convert that to anything. The machine beeps, prints "Bad Argument Type" on the screen and stops. There's lots of crap on the stack, too. Not very graceful. If you press the zero key, the first character is duplicated in the string. Pressing the '1' key reverses one character, which is to say that it does nothing. But it does increment your move count. So, confine your entries to 2 through 9. Back in the day, i might have performed better data entry checking. Call me lazy.

Next up is a diversion about playing this game.

Forth for Enlightenment, part five of ten, Backwords

How about a game that fits on this tiny machine that's fun to play? With 2 KB of RAM, this is tough. Fortunately, i have a copy of 101 BASIC Computer Games, which was written mostly using a PDP-11/70 (i got to log into the actual system, briefly, way back when). Anyway, there's a fairly simple game called REVERSE. I call it Backwords. Yes, it's misspelled. I've used the game for a couple purposes over the years. One is as an early program to write in a variety of languages. So, I have versions in C, Perl and OPL.

The game is pretty simple to play. In the original version, the digits from one through nine are used, but as ordered symbols. They start out in non-repeated random order. At each move, the user can reverse the first few digits. That is, the first two, or the first three, or, ... and on up to the first nine digits. The goal is to sort the digits from 1 to 9. Here's an example.

342156789 - Reverse 2 to get
432156789 - Reverse 4 to get
123456789 - you win.

A number of language capabilities have already been used in this series. For whatever reason, i've decided to use the letters 'a' through 'i' for this version. That lets me consider string manipulation.

The first obviously hard problem to solve is to take a string and reverse the first n symbols in it. Imagine a function named REV that takes two arguments, a string, and a number, and returns a string. First, my solution.

« DUP2
DUP 'ACNT' STO 1 SWAP START
  DUP 1 1 SUB
  SWAP 2 20 SUB
NEXT
DROP "" SWAP 1 ACNT START
  SWAP +
NEXT
SWAP DROP SWAP
ACNT 1 + 20 SUB +
'ACNT' PURGE
» 'REV' STO

By the way. I just got my 25 year old HP28 printer working. New batteries were installed. The darkness slider was pushed all the way to full dark. About a meter (three feet) of paper was unspooled. And, it started working. So the main issue is that 25 year old thermal printer paper is pretty marginal, and the most external bits of it didn't work at all. When a function is printed using the printer, it prints the name of the function first, rather than the way i've done it above. I'm giving you the command to save the function.

But back to this function. You feed it a string, like "abcdefghi", and a number, like 3, and it spits out "cbadefghi". A little study of the function reveals that 'ACNT' is a variable used to remember something. It is incremented in the 2nd loop. The value is used with SUB, which is a built in string function to get part of a string. This variable is deleted before the function exits. Beyond that, we really need some stack diagrams to see what's going on. Here, the function is called with a string, and is directed to reverse the first 3 symbols. The stack trace is transposed so that time goes down, and the top of the stack is to the right. That's because web pages are potentially infinitely long, but in this forum, narrow. Stacks are often quite shallow. I'd only seen stack traces horizontally, but i find that i like them vertically now. Note that the Start at the begining is just to show what's on the stack before this segment runs. The START at the end is the loop START function.

Start	"abcdefghi"	3
DUP2	"abcdefghi"	3	"abcdefghi"	3
DUP	"abcdefghi"	3	"abcdefghi"	3	3
'ACNT'	"abcdefghi"	3	"abcdefghi"	3	3	'ACNT'
STO	"abcdefghi"	3	"abcdefghi"	3
1	"abcdefghi"	3	"abcdefghi"	3	1
SWAP	"abcdefghi"	3	"abcdefghi"	1	3
START	"abcdefghi"	3	"abcdefghi"

The DUP2 saves both arguments for later. The DUP is used to make a stack copy of the numeric argument that gets consumed when 'STO' is used to put it into 'ACNT'. Then, the loop needs a start value (1) and an end value, the number to reverse. So in this case, the loop will execute 3 times. The 'START' loop command does not iterate a variable that you can access. So one of the features of the language is that there is often stack setup several commands before a function is called. While you read this setup, it's not at all clear what it's for. And that's why my listing is in little chunks. And it's probably easiest to read these backwards. Which is to say, start with the function, and try to figure out what the arguments are.

So, let's consider the loop. Here, the original arguments are not modified in the loop. So, they're not considered in the stack trace.

Start	"abcdefghi"
DUP	"abcdefghi"	"abcdefghi"
1	"abcdefghi"	"abcdefghi"	1
1	"abcdefghi"	"abcdefghi"	1	1
SUB	"abcdefghi"	"a"
SWAP	"a"	"abcdefhgi"
2	"a"	"abcdefghi"	2
20	"a"	"abcdefghi"	2	20
SUB	"a"	"bcdefghi"
NEXT	"a"	"bcdefghi"

This is just one trip through the loop. In the first loop, it starts with the full string on the stack. It gets copied in the DUP. That's probably because it will get consumed shortly. Two constants, 1, and 1 are put on the stack. Then, SUB is called, which consumes both constants and the copy of the string. SUB takes the string and a position and a length from the stack and returns a string starting at the position and as long as the length. So, in this case, it returns the first character. SWAP pushes that first character one deeper on the stack and exposes the original copy of the string. The constants 2 and 20 are put on the stack, and SUB is called again. A substring is returned, starting with the 2nd character. But the returned string isn't 20 characters long because the original string isn't that long. So, clearly, this SUB returns the string from the 2nd character to the end of the string. And that's it for one pass. Each subsequent run through the loop effectively pushes one more character of the string onto the stack. The loop runs for as many times as we want to reverse.

The next code segment pops each of these characters off the stack and builds a new string. Since they were pushed onto the stack in order "a", "b", "c", they are popped off of the stack in the order "c", "b", "a", which is the reversing that we want.

DROP "" SWAP 1 ACNT START
  SWAP +
NEXT

The DROP discards any remaining string on the stack from the first loop. This exposes the "a", "b", "c" list on the stack. A zero length string is then pushed. This is the start of the answer string being built. A loop from 1 to ACNT (the number to reverse) is started. In each loop, the string being built and the next single character are SWAPed on the stack. Then "+" concatenates the string being built with the single character. All the single characters are consumed by the end of the last run through the loop, leaving the built reversed string. If this isn't clear from the code, build a stack diagram to see how it works. After a while, you end up recognizing patterns like this. Or, you get to be able to visualize the stack processing in your head. Or, you get good enough at the logic to be able to predict what happens. This last is cool, because you've just demonstrated that the Halting Problem can be solved after all, even though Alan Turing proved it can't be. There may be hope for computer program correctness after all.

The last bit does some stack cleanup, gets the rest of the string from the original, and pastes the reversed part and the rest of the string together. There's no loop here, but you may have forgotten some of the stack from the start of the function. So, we'll do a stack trace.

SWAP DROP SWAP
ACNT 1 + 20 SUB +
'ACNT' PURGE

Start	"abcdefghi"	3	"cba"
SWAP	"abcdefghi"	"cba"	3
DROP	"abcdefghi"	"cba"
SWAP	"cba"	"abcdefghi"
ACNT	"cba"	"abcdefghi"	3
1	"cba"	"abcdefghi"	3	1
+	"cba"	"abcdefghi"	4
20	"cba"	"abcdefghi"	4	20
SUB	"cba"	"defghi"
+	"cbadefghi"
'ACNT'	"cbadefghi"	'ACNT'
PURGE	"cbadefghi"

The SWAP exposes the count to reverse, which is then DROPped. The next SWAP exposes the original string. Then ACNT is recalled and one is added to it. The constant 20 is pushed so that the SUB gets the string from position 4 to the end. The "+" concatenates the two strings, yielding the answer. The 'ACNT' PURGE simply deletes the temporary variable.

At this point, the Forth programmer is thinking, "Why was 3, which is the number of characters to reverse, remembered on the stack for all this time, just to DROP it? And indeed, code like "SWAP 1 + SWAP ROT ROT 20 SUB +" would work as a replacement for the above sequence. It's the same length and doesn't need the 'ACNT' variable. Since it is the same length, it is likely to run in about the same amount of time. Then, one could also rewrite the rest of the function to eliminate the 'ACNT' variable. And that rewrite might be slightly shorter or longer. It's highly likely that Forth programmers do this sort of thing all the time. But consider that the 'ACNT' variable is labeled, whereas none of the stack positions are labeled. It's kind of like Star Trek, where on the bridge, there are huge panels full of unlabeled buttons. Labeled variables are easy to read.

It must be admitted that it was my intent to rewrite the function to eliminate the variable. It was easiest to get the gist of the function working by using the variable. I thought of it as a crutch to get the function written. But having gotten it written, it seems to me that it's better the way it is. A down side of using a variable is that some other program might accidently use the same name. Since programs all use the same name space, this function could possibly delete a variable that is in use by some other program. Yet, i have total control over the calling program, so it's simply not going to be an issue. And, a naming convention, such has using the name of the function as a variable name suffix, would also make this a non-issue. On the HP-28C, there's only 2 KB of RAM. That's not much for code and data. On the HP-28S, there's 32 KB of RAM. But even there, only the calling program parts of this function need be considered. Only one program can run at a time.

This function is basically enough to play the game. Key in "abcdefghi", the enter button, and a number like 3. It runs pretty fast, and returns "cbadefghi". It's reasonably fast because the two loops combined have ten functions. If you reverse 9, that's 90 functions. There are another 10 odd functions, so the maximum is about 100 functions. That takes place in a hair over a second. One should see how it performs on unexpected input. Key in other numbers and make sure they return the right result. Does it work right if you try to reverse 1 character? How about something longer than the string, like 20? How about zero? How about -2? Frankly, i was satisfied with it's behavior with unexpected input. This can be controlled by calling code anyway.

One of the design notes that was skipped is interesting. The stack is used to effectively reverse characters in the string. But in a language like C or Perl, it's more likely that pairs of characters would be swapped, using a temporary variable. And that's because in those languages, one can subscript into a string and write whatever you want there. The HP-28 RPL language does not have a function to put a character into the middle of a string. So this simply isn't possible. In fact, i considered not using strings at all. I considered using an array for everything. Arrays can't hold characters or strings. So i'd have to either convert the result array to a string or come up with some other way to display it. It's very likely that using arrays on this calculator would require less code that executes faster on this machine, despite conversion.

This function isn't the whole game. It doesn't know if you've "won", and it doesn't create a randomized string for a starting problem. What is amazing is how much code is needed to turn this almost-game into a game. And that's in the next post.

Forth for Enlightenment, part four of ten, GCD

GCD implements an interesting way to compute Greatest Common Divisor. You remember fractions? Let's say you need to reduce the fraction

210
---
462

They're both even, so you can divide by 2.

210   105
--- = ---
462   231

Uhm... the digits of 105 add to 6, and the digits of 231 add to 6, so they're both divisible by 3.

210   105   35
--- = --- = --
462   231   77

Then, 35 is 5 * 7, and 77 is 7 * 11, so they're both divisible by 7.

210   105   35   5
--- = --- = -- = -
462   231   77   11

So, effectively, 210 / 42 = 5, and 462 / 42 = 11. 42 is the greatest common divisor between 210 and 464. The way this was solved was to attempt to find prime numbers that are factors. And it turned out that it wasn't that difficult. That's because we were able to divide big numbers by small numbers until all the numbers were pretty small. But you might have felt a looming fear that you'd have to do a bigger divide. There are lots of ways to get the greatest common divisor. Astonishingly, there is one that doesn't involve division. In C, it looks something like this:

int gcd(int a, int b) {
  if (a == b) return a;
  if (a > b) {
    return gcd(a - b, a);
  } else {
    return gcd(a, b - a);
  }
}

Let's use this to figure out the GCD of 210 and 462. Since b > a, the first step is to subtract 462 - 210 = 252, so it's gcd(210, 252). Then, b > a, so gcd(210, 252 - 210 = 42). Then gcd(168, 42). Then gcd(126, 42). Then gcd(84, 42). Then gcd(42, 42). Since 42 = 42, the answer is 42. OK, maybe this isn't so easy to do in your head. But there used to be computer processors like the 8080 that did not know how to divide directly. Such processors could use this sort of thing, and they were really relatively fast at it.

Anyway, the recursive version of this function on the HP-28 looks like this.

« DUP2 IF == THEN
      DROP ; return a
   ELSE
      DUP2 IF > THEN
         SWAP DUP ROT - SWAP GCD ; return gcd(a-b, a)
      ELSE
         SWAP DUP ROT SWAP - GCD ; return gcd(a, b-a)
      END
   END
» 'GCD' STO

This GCD function is called with two numbers, which i'll call a and b on the stack. The first thing the function does is make copies of the two arguments. They are then compared. If they are the same as each other, one of them is dropped from the stack. This is the return value of the function. If a and b aren't the same, the if a > b it returns the value from the recursive call of gcd(a - b, a). Let's look at this with a stack trace.

Level	Start	SWAP	DUP	ROT	-	SWAP
3			b	a
2	a	b	a	a	a	a - b
1	b	a	a	b	a - b	a

And then GCD is called. The stack trace for when b > a follows.

Level	Start	SWAP	DUP	ROT	SWAP	-
3			b	a	a
2	a	b	a	a	b	a
1	b	a	a	b	a	b - a

This program works. However, for large arguments it can run out of memory. That is, despite not putting much in the way of data on the stack, it runs out of recursive call depth. For example, it chokes on gcd(100, 101). I wanted to know exactly how deep it could go, and i tried various number pairs that are separated by 1. And gcd(100, 101) failed. So i wrote this little program to find out when it first fails. It starts at 50, and tries up to 200. It then calls gcd(x + 1, x). And, unexpectedly, it returned that gcd(180,179) works. That was really unexpected. It turns out that gcd(179,180) fails. The order of the arguments is important, for no apparent reason.

« 50 200 FOR x
      x
      x 1 + x GCD
      DROP DROP
   NEXT
» 'G' STO

Anyway, the fact that fairly small arguments lead to a stack crash is not good. The C version, using the full -O3 optimization of the gcc compiler, never runs out of memory. That's because this compiler optimizes the tail recursion, and it never generates much of a call stack. Likewise, the Scheme version never runs out of memory. The Scheme language requires that tail recursion optimization is implemented. Perl 6 is supposed to do some simple tail recursion optimization. All my code is in Perl 5, and it fails pretty quickly. It complains of Deep recursion with gcd(101, 100). By gcd(131, 130) it runs out of stack memory. But could the program be written without recursion? Sure. In fact, it's pretty easy. First we'll see what it might look like in C. Often to eliminate tail recursion, all you need is a jump back to the top.

int gcd(int a, int b) {
  while (a != b) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}

What this does is loop until a and b are the same. It changes it's own arguments each loop instead of calling itself. If this is done on the HP-28, then there's no recursion, and large numbers can be handled, given time. Note that the ≠ in the first line is a single HP-28 character, a shifted '='.

« DUP2 WHILE ≠ REPEAT
      DUP2 IF > THEN
         SWAP DUP ROT - SWAP ; repeat with gcd(a-b, a)
      ELSE
         SWAP DUP ROT SWAP - ; repeat with gcd(a, b-a)
      END
      DUP2 ; for the != in WHILE
   END
   DROP ; drop one of the equal a, b.
» 'GCD2' STO

This version is also a little quicker, because the while loop is quicker than a function call. At first, things seem to be moved around at random compared with the original version. The DROP that removed one of the identical values on the stack moved to after the while loop, just as the C version's return statement moved. Otherwise, the first IF became a WHILE.

Is the iterative version easier or harder to follow than the recursive version? This is an important maintenance question. And it isn't clear that either one are very easy. After all, even having stepped through an example, it's not clear how the subtractions end up giving you what amounts to division. And the begining of the answer is that repeated subtraction can be used in division. Think about how you have to guess the next digit in long division. You don't really have to guess. You can try the digit one, do a subtraction of the divisor, and repeat this (while incrementing the answer digit) until just before it goes negative. But that's just a hint. On the other hand, the nonrecursive version demonstrates that nothing needs to be remembered and that the only time something is returned is when a == b.