Garnet

Never saw the web magazine The Shallot before. Of particular note is the announcement of a new programming language: Garnet. This is the very first pure non-functional language. Garnet is related to Ruby, only not really.

Eight Queens part one

	Q
Q

If you get out a chess board, and put a queen in the lower left square, it's pretty clear that you can't put a second queen in the lowest row of the second column. That's the same row that the first queen is in. So there are really only seven choices available for the second queen. And the third queen only has six choices. It follows that there are 8 * 7 * 6 ... or 8! = 40,320 possible board positions to check for solutions. So combining the not-in-the-same-column rule with the not-in-the-same-row rule reduces the number of board positions to check by a factor of (8^8)/8! = 416.

There are algorithms that turn a counting integer into a unique permutation of a list. One could use this sort of thing. There are three reasons for not moving forward in this direction. First, the permutation algorithm is a bit complicated. It's nearly as long as the current program. Second, this permutation algorithm is fairly slow, though not anywhere near a factor of 416 slow. And its performance per call is proportional to the number of items to permute, in this case eight. Third, changing an exponential algorithm (8^8) into a factorial problem (8!) still gives you exponential time. If the board size is increased, the solution increases in time proportional to x^n of the board size. The permutation algorithm is handy. So perhaps it'll get a write up in some other series. This series has another direction. And if this code is converted to counting permutations, then it will be difficult or impossible to go where we're going.

		Q
	Q
	Q
Q	Q

Let's return to the chess board. Put the first queen in the lower left square. In the second column, you can't put a queen in the lowest square. If you put the second queen in the second row, then the two queens are also attacking each other, this time diagonally. In fact, with the second queen in either of these positions, there are no queen positions of the remaining six queens that are solutions to the Eight Queens problem. You may as well move the second column queen up one more square. If you skip checking the positions with the other six queens, you've skipped 2*8^6 = 524,288 positions (of 16 million). And, you've skipped all these board positions with a two checks. It's easy to show that if the first two queens are as shown, the third column queen must be at least at the fifth row. To get the third column queen that high, four more checks are made, eliminating 4*8^5 = 131,072 boards. Big chunks of the problem space are vanishing, though they're vanishing in smaller chunks as the queens farther to the right are placed and checked. But this is the general way that the student in 1979 came up with his nearly zero time solution. It's also what Dijkstra did in his 1972 article about Structured Programming. However, this article isn't about Structured Programming (that would be a completely different rant) so much as it's about the technique Dijkstra used called Backtracking.

To make use of Backtracking you need to be able to generate a first board, a next board (and know if there aren't any more), you need to be able to check the partial solution, and you need to be able to print or otherwise identify the solutions you found.

Let's see how it works. The first board routine needs to simply place the first queen. In the check board routine, there's only one queen, so there are no attacks. The next board code knows that there is a possible solution, so it puts a new queen on the board in the next column. From here on, it's only check board and next board. The check board function needs to know how many queens are on the board so it can check rows and diagonals for attacks. In this case there are two queens, and they're in the same row, attacking. The next board function needs to know if the check board found an attack or not. Since there's an attack, it needs to move the rightmost queen up a row. When it finds a queen is at the top already, then it is removed, and the previous queen needs to be moved up. This is Backtracking.

For the Eight Queens problem, the initial solution space was so large, that it seemed hopeless. But it turns out that Backtracking is an approach that can be used to attack many of these combinatorial problems. The downside for Backtracking seems to be that it isn't very easy to decide how good the performance will become without first trying it. In this case, as queens to the right of the board are considered, smaller chunks of the problem space are eliminated. With increasing board size, does the problem stay exponential? Or is it something else? Knuth wrote about this issue in 1975. From my perspective, it doesn't matter. That's because Knuth is primarily thinking about the problem as a mathematician. Mathematicians want to think about a problem and come up with a solution. Programmers have another tool. They can write yet another program and see how it works. If the program takes too long, the programmer can tell the computer to count something of interest to help the analysis. Often this shows the programmer where to attack the problem next.

Don't agree with me? Here's an analogy. My favorite sorting algorithm is Shell's Sort. How long it should take is an open question. One advantage that it has over other algorithms is that an in-place sort doesn't require extra memory. It usually performs similar to n*log(n). In practice, it's usually quicker than Quicksort which has a best case of n*log(n) time, but requires more space. It doesn't bother me that its computation time is an open question.

In any case, let's look at a modification to the 8^8 version of the Perl program that does Backtracking. It's instrumented to find out how many rows needed to be checked (which is the number of next boards, and the number of diagonals checked. One should note that the board checks are faster than the previous version. That's because instead of checking all eight queens against all eight queens, it only has to compare the most recent queen to other queens. The previous queens have already been checked, and none are attacking. Since only 15,720 boards were checked, that's less than one in a thousand compared to the 8^8 solution. Fewer than one in three thousand diagonals need be checked. What does that mean for the order of computation? Not much. This code is written for an 8x8 board. It could be generalized to nxn, and then run, and then we'd find out... something. Since the checks are proportional to the size of the board, we'd expect time to rise faster than board size. However, the chunks that would be eliminated would be a larger proportion for larger boards. So, who knows? I'd be willing to bet that someone has written this up somewhere.

#!/usr/bin/perl

# Eight queens - incremental backtracking version.
# Chess board where eight queens are not attacking each other.
# Can't have two queens in the same column, so represent row numbers in columns.
# There are 8^8 (1e7) positions to check.
# The check for one queen per row gives you unique digits.
# If there's an attack between queens to the left, there's no
# need to keep checking to the right.
# This reduces the problem further.
# 92 winning boards. 15720 rows checked, 5508 diags checked.
# 0 seconds - likely less than 0.05 seconds.

# main
my $col = 0; # current column under consideration
my $x;
my @b; # board, 0 - 7 are columns, values are positions, 0-7
my $cnt = 0;
my $chkh = 0; # horizontal checks
my $chkd = 0; # diagonal checks

# set board to queens at bottom.
for ($x = 0; $x < 8; $x++) {
 $b[$x] = 0;
}
while (1) { # The big loop, count to 8^8-1
 # check for a win
 if (&chkwin($col)) {
  if ($col != 7) {
   $col++; # Don't increment board, as new col is zero.
  } else {
   $cnt++;
#  print "win ";
   &prbrd();
   $col = &incbrd($col); # increment the board
   if ($col == -1) {
    print "$cnt winning boards.\n";
    exit(0);
   }
  }
 } else {
  $col = &incbrd($col); # Increment the board
  if ($col == -1) {
   print "$cnt winning boards. $chkh rows, $chkd diags.\n";
   exit(0);
  }
 }
}

sub incbrd { # Returns $col. -1 when done.
 my $col = shift;

 $b[$col]++;
 while ($b[$col] > 7) {
  if ($col != 0) {
   $b[$col] = 0;
   $col--;
   $b[$col]++;
  } else {
   return -1; # done
  }
 }
 return $col;
}

sub prbrd { # Print the board
 my $x;

 for ($x = 0; $x < 8; $x++) {
  print "$b[$x]";
 }
 print "\n";
 # sleep(1);
}

# Assumes partial incremental board.
# Only have to check the rightmost column.
sub chkwin {
 my $col = shift;
 my ($x, $y, $a);

 # Check for same row.
 $chkh++; # How many horizontal checks.
 for ($x = 0; $x < $col; $x++) {
  if ($b[$x] == $b[$col]) {
   return 0;
  }
 }
 # Check for diagonal.
 $chkd++; # How many diagonal checks.
 $a = 1;
 $y = $b[$col];
 for ($x = $col - 1; $x >= 0; $x--) {
  if (($y == $b[$x] - $a) ||
      ($y == $b[$x] + $a)) {
   return 0;
  }
  $a++;
 }
 return 1; # 1 is good, 0 is not a win.
}
0;

Could this code be made faster? Sure. For one thing, any solution that is up/down mirrored is also a solution. So the left most queen only needs to go from 1 through 4. The mirror solution can be created by subtracting the row number for each column from nine. So one becomes eight. It's an easy change. It would produce all the answers in a little over half the time. Perhaps tricks like that allowed someone to compute the number of distinct solutions for a 26x26 board. Time spent counting alone would take forever. One expects that they used a compiled language. That would improve performance by a factor of about three hundred. This code could be converted to C without changing much of the look. And it could be converted to run on multiple processors fairly easily.

The interested reader might note that the general algorithm for Backtracking is presented as recursive, and the Eight Queens code that Wirth presented is also recursive. My Perl solutions are not. My policy on recursion is to introduce it if it helps with dynamic storage. In this case, restoring the previous state is a simple matter of changing the value of the column under consideration ($col). A further issue is parallelization. Multiple core processors are now common. We should be considering parallel computations. It looks pretty easy to start with my code and modify it for multiple processors. For example, it could be modified to consider the case where the first queen is set once, and not moved. All of the other boards with this first queen would be considered. Eight instances would be run, possibly at the same time. Perhaps something similar could be done with a recursive version, but it may not be so easy. It's something for future investigation.

This code was timed with a resolution of one second. Why work hard to reduce a fifty second program you need to run once to nearly zero? The answer is that these techniques are worth learning. There are other problems where even modern machines are hopelessly slow. We'll get to one of those soon.

Eight Queens part zero

How many queens can be put on a chess board where none of them are attacking any others?

A chess board has eight by eight squares. A queen attacks all squares in the same row or the same column, or on either of the two diagonals.

If one considers putting queens on a chess board at random, the maximum number of board positions to consider is 64! That is, one puts a queen on the board, and there are 64 choices for where to put her. For the second position, there are only 63 open squares left. So for two queens, 64 * 63 positions need to be considered. There are 64 squares, so the maximum number of queens is 64. The number of positions to check is 64 * 63 * 62... or a total of 64!. That's about 10^89 positions. All the computers on Earth could not check that many board positions in the current age of the Universe. The overwhelming majority of these board positions can be shown to have at least two queens attacking each other. And there are some simple ideas to eliminate whole chunks of these at a time. For example, here's one idea.

Since a queen attacks all the squares in the same column, one can't have two queens in the same column. Since there are only eight columns on a chess board, it's not possible to have more than eight queens on a chess board without any attacking any others. It can be ruled out. That doesn't mean that there are any board positions with eight queens. It only means there aren't any with nine or more. This is apparently obvious enough that the problem is called the Eight Queens problem.

This not-in-the-same-column rule means that the queen in the first column can be in any of eight positions. For each of those, the queen in the second column can be in any of eight positions, for eight squared combinations. It follows that the total number of board positions to check is eight to the eigth power (8^8), or a bit over 16 million board positions. This is a speed increase over our original idea of a factor of about 10^81.

The Eight Queens problem, is an example of a combinatorial problem. It is said to be NP-complete. The solutions for these problems suggest that the entire solution space must be searched to find solutions. NP-complete problems strike fear in the hearts of computer science students. Having never been a computer science student, it's not much of a worry. However, my understanding of gravity is excellent, so acrophobia is available. It's always something.

While at school in 1979, i had a job sitting behind the I/O desk, answering student's computer questions. One day, an advanced computer science student asked me about the problem. The professor had likely read Dijkstra's 1972 article, and assigned it to a class. He prepared the class for the worst by implementing an 8^8 solution that attempted to get all solutions by brute force. After three days, it had covered a third of the solution space, and he killed it. The estimate was nine days for the full solution. This is on a PDP-10 designed in 1966 that performed at about a fifth of a MIPS.

Anyway, on a modern machine, 10^7 is not such a big number of things to do, so let's just plow into it. How should a computer program represent the board? It could have an eight by eight grid, with a one representing a queen, and a zero representing an open space. Since the numbers are either zero or one, the numbers don't have to be larger than one bit. 64 bits could be used.

A program with this representation needs code to generate a first board position, code to generate the next board position in any way that covers all possible board positions, code to check to see if a board position is a solution, and code to print or otherwise note a solution. One can imagine each of these routines. The first board position could be all eight queens at the bottoms of their columns. The next board position could move the rightmost queen up a row. But if that move the queen off the top of the board, it should move it down to the bottom of that column, and move the queen to the left up a row. When all the queens are at the top, it should report that all positions have been searched. The check for win must check each queen's row for other queens, and each queen's diagonals for other queens. A board position print might print a space where there are zeros and a queen where there are ones in an eight by eight square.

Here's another way to represent a board position. In each column, only one queen may be present. So each column can be represented by a single number. This number says what row that queen is in. There are only eight columns, so there are only eight numbers. Each column has eight rows. So each number can have one of eight values, so only three bits are needed. That's a total of 24 bits. In any case, you can think of each column as a digit in a number. As long as the digits are constrained to one of eight unique digits, you can count through all possible board positions. One of the nice features of this representation (compared with a bit per square) is that as you "count" through possible board positions, you don't have to check that two queens are in the same column. That is, the board representation can't violate this constraint, so there's no need to check.

The same routines are needed for the eight numbers as above. If each digit is one through eight, then the intial board could be all ones. The next board looks like counting by one. Checking for a queen in the same row is the same as checking the other queens for the same digit number. Checking diagonals is a bit more complicated. Two columns that are next to each other have a diagonal that are off by one row. If they're one row farther apart, then diagonals are two rows different. Finally, though a full board can be printed, it's easy enough to simply print the row numbers for each column.

This 8^8 Perl program takes 50 seconds to find all solutions. That's because a modern desktop machine is at least 15,000 times faster.

#!/usr/bin/perl
# Chess boards where 8 queens are not attacking each other.
# Can't have two queens in the same column.
# Represent row numbers in columns.
# There are 8^8 (1e7) positions to check.
# 50 seconds - 335544 board checks per second.

# main and global variables
my $col = 0; # current column under consideration
my $x;
my @b; # board, 0 - 7 are columns, values 0 - 7 are positions
my $cnt = 0;

# Set board to queens at bottom.
for ($x = 0; $x < 8; $x++) {
 $b[$x] = 0;
}
while (1) {
 if (&chkwin()) { # check for a win
  $cnt++;
  &prbrd();
 }
 if (&incbrd() == -1) { # increment the board
  print "Done $cnt winning boards.\n";
  exit(0);
 }
}

sub incbrd { # Increment board.
 my $col = 7;

 $b[$col]++;
 while ($b[$col] > 7) {
  if ($col != 0) {
   $b[$col] = 0;
   $col--;
   $b[$col]++;
  } else {
   return -1; # Puzzle is done
  }
 }
 return $col;
}

sub chkwin { # Check a board for a win.
 my ($x, $y, $a);

 for ($x = 0; $x < 8; $x++) { # Check row
  for ($y = $x + 1; $y < 8; $y++) {
   if ($b[$x] == $b[$y]) {
    return 0; # not win
   }
  }
 }
 for ($x = 0; $x < 8; $x++) { # Check diagonals
  $a = 1;
  for ($y = $x + 1; $y < 8; $y++) {
   if (($b[$y] - $a == $b[$x]) ||
       ($b[$y] + $a == $b[$x])) {
    return 0; # not win
   }
   $a++;
  }
 }
 return 1; # win
}

sub prbrd { # Show the board.
 my $x;

 for ($x = 0; $x < 8; $x++) {
  print "$b[$x]";
 }
 print "\n";
}
0;

The Eight Queens wiki page tells us that the first solutions were found in 1850, about 96 years before the first fully functional computer, depending on who you talk to, and what your definition of fully functional computer is. If any solutions can be found by hand, there must be better ways to approach this problem.

My help to the student was likely limited to some hand waving about reducing the problem space, without any real direction. A couple days later, he showed me that he'd reduced the time required to less than a second. He even removed the print statements showing that most of that time was spent printing the answers. There are only 92 of them.

In the next part, the problem is approached using a better technique. It may seem pointless, since the most time that can be saved is about fifty seconds. But the general technique can be used on many such problems. And many of these problems are considerably more complicated. It's best to practice on easier problems first.

Crimson

It was mostly clear last night. I thought it might be fun to see if i could find R Laporis, also called Hind's Crimson Star. Though visible from my back yard, which has better stray light blocking, it did not appear that i could get my telescope's computer aligned in a spot where i could see it. So, i brought the scope to the front sidewalk (the Mercury Vapor Observatory). The MVO has had a much wider sky view than the jungle in the back yard ever since the Emerald Ash Borer took down the front yard's twin gorgeous ash trees. I've never actually seen one of these beasts.

The constellation Lepus (the hare) is below the feet of Orion. This part of the sky looks entirely star free at first glance. 10x50 binoculars show the stars of the constellation easily. But after a few minutes, there seemed to be enough stars visible to the naked eye to sort of fill it in. At the MVO, there really isn't anything like dark adaptation for the eyes. It's more like scanning the area, paying attention, and using averted vision techniques to bring out the dimmer stars. I should note that the constellation looks more like LEPUS on the Orion wiki page than on the R Laporis wiki page.

The ten inch scope cooled down, and i performed an alignment using Rigel and Polaris. Rigel was chosen because it's near the target. Polaris was chosen because it was handy. The computer reports how good the alignment was, and it was excellent. R Laporis is less than a degree above NGC 1710. NGC 1710 is a galaxy that is absolutely invisible from the Mercury Vapor Observatory, since it's not one of the three brightest galaxies in the sky. The idea was to get into the neighborhood. It took about a minute of searching to find it. My wife also got a look at it briefly, before clouds blocked it. It looks like a seriously red LED light. Orion's Betelgeuse is also a red supergiant. And it's nearby in the sky, so i took a look at it for comparison. While Betelgeuse is somewhat orangish naked eye, it looked positively white in the scope, though not white like Rigel. The difference for R Laporis is that the star pushes carbon into its atmosphere. This carbon blocks blue light from the otherwise red giant, making it look much, much redder.

R Leporis is fairly faint, at about 10th magnitude. This is not a problem at the MVO. This ten inch (254 mm) scope has a collecting area (with the secondary mirror subtracted) of 47,553 square millimeters. My eyes dilate to 6.5 mm, which works out to 33 square millimeters. So the scope brings in 1,433 times more light into my eyes. That works out to a light grasp improvement of about 7.9 magnitudes. I was seeing 4th magnitude stars naked eye, so 12th magnitude should have been reachable with the scope. In addition to that, even low magnification (48x) tends to dim extended objects like galaxies and the sky glow, but not point like objects like stars. So the contrast is much, much better. A tenth magnitude star is fairly bright in the scope. Unfortunately, I didn't get a chance to see if R Laporis was visible in the 9x50 finder scope. It wasn't obvious in the 10x50 binoculars, but i didn't yet know exactly where to look.

R Laporis is a variable star with a period of about 432 days (14 months). It most recently peaked near magnitude 6 in November 2012. So it should be faintest in June 2013 near magnitude 11. Here's the current AAVSO light curve. To search for the star, use R LEP on the AAVSO web site. R Laporis should be at peak brightness again in January 2014 (about 40 times brighter). And, Orion, and therefore Lepus, will be well placed in the evening sky as well.

It was freezing cold, so i limited myself to a few other objects. Polaris and Rigel were alignment stars. Though i could have aligned using the finder scope's cross hairs, the main scope was used. Betelgeuse, Rigel and Sirius were used for comparison. Sirius was blinding. Jupiter was above the first quarter moon. The four Galilean moons were clearly visible in 10x50 binoculars. I didn't look at the Moon with optics, as the sky was very clear, and the moon filter was in the house.

Forth for Enlightenment, part thirteen of ten, Primes too

In part nine we had an introduction to testing if a number is prime. A function to check for primality was presented. It's short and to the point. And, since it checks by dividing the number by all integers up to the square root of the number, the execution time is proportional to the square root of the number. Is there something that can be done to speed it up? Absolutely.

For one thing, all numbers greater than two are divisible by two. So dividing by those numbers doesn't have to be done. One can test for even numbers by starting with three and skipping every other number. That's a quick and easy test. One can apply the same logic and skip numbers divisible by three after three. That's a little more complicated. The easiest approach appears to be to note that you can skip every other division by three, since those are divisible by two. That is, one can skip by six, and only check some of the numbers in each block. This code performs this sort of check. It searches two and three, then by sixes starting with five.

«
 0 0 → n s a «
  IF n 2 < THEN
   1 'a' STO
  ELSE
   IF n 3 > THEN
    IF n 2 MOD 0 == THEN
     2 'a' STO
    ELSE
     IF n 3 MOD 0 == THEN
      3 'a' STO
     ELSE
      IF n 7 > THEN
       n √ FLOOR 's' STO
       5 s FOR x
        IF n x MOD 0 == THEN
         x 'a' STO
         s 'x' STO
        END
        IF n x 2 + MOD 0 == THEN
         x 2 + 'a' STO
         s 'x' STO
        END 
       6 STEP
      END
     END
    END
   END
  END
  a
 »
» 'ISP2' STO

Here are some timings to show the speed up. On the left is the number that is tested. Then, the number of seconds for ISP and ISP2 to complete the check. Note that all numbers tested are, in fact, primes. So this is sort of the worst case. There was no run of 10000019 for ISP.

Number	ISP	ISP2
10007	5	2.3
100003	15	5.4
1000003	47.3	15.5
10000019	na	47.7

In any case, it's pretty clear that as the number goes up, so does the time. Of note is that ISP2 performs about as well as ISP does on numbers that are ten times larger. That's because both algorithms have time that goes up with the square root of the number. The ISP2 implementation is faster because instead of checking every number, it checks two numbers for every six. That's one third the number of divide checks. Since it does one third as much work, it should perform about as well on number 3 * 3 = 9 times larger. Nine is pretty similar to ten from a benchmark perspective.

This factor of three performance increase comes at a cost. For the HP-28c, this cost is size. While ISP only requires 82 bytes, ISP2 requires 443 bytes. Is that a big deal? Yes. For one thing, since this is a single big function, if you make a mistake and need to edit it, you get "No room to enter". You have to type the whole function in again from scratch.

Are there prime number test algorithms that do better than going up in time with the square root of the number? Yes. But they either require remembering stuff, or have more code, or both. The HP-28c simply doesn't have the memory to do a significant sieve or the code for the Miller-Rabin primality test.

Forth for Enlightenment, part twelve of ten, Four Digit Puzzle

This is another number based logic puzzle. It can be solved without a computer. It's not difficult. The mostly brute force coded solution is straight forward too. It's included because of the rewrites. Like the previous puzzle, individual digits need to be examined. An experiment for this code is to use strings to extract digits. First the problem statement.

What is the four digit number in which the first digit is one-third the second, the third is the sum of the first and second, and the last is three times the second?

First, just a minor bit of analysis. We're looking for a four digit number. One imagines that four digit numbers have a range from 1000 to 9999. I mean, what's the difference between 0000 and 00000? Is the later a five digit number? But 0000 is a solution, right? This program assumes 1000 to 9999, but to save time, it stops when it finds a solution. The code 9999 'X' STO sets the variable X to its final value, so that the FOR loop ends. Without this, the program takes well over an hour to execute, and finds only the one solution.

«
 1000 9999 FOR X
  X →STR 1 1 SUB STR→ 'A' STO
  X →STR 2 2 SUB STR→ 'B' STO
  X →STR 3 3 SUB STR→ 'C' STO
  X →STR 4 4 SUB STR→ 'D' STO
  IF A 3 * B ==
   A B + C == AND
   B 3 * D == AND THEN
   X
   9999 'X' STO
  END
 NEXT
 'A' PURGE 'B' PURGE 'C' PURGE 'D' PURGE
 440 .1 BEEP
» 'PUZ4' STO

This code requires 307 bytes of memory, and takes and 225 seconds for execution. It produces the right answer, 1349.

So, X →STR takes the number X, and converts it to a string. 1 1 SUB returns the substring that is the first character. Since more arithmetic needs to be done, STR→ converts it back to a number. Once each digit is isolated, it is assigned to a global variable. The number, X or ABCD, is a candidate solution. The IF statement figures out if ABCD is a solution or not.

The IF statement performs each of the tests. A 3 * B == multiplies A * 3, and compares it to B. A has to be an integer from 0 to 9. And so does B. One can multiply A by 3 or divide B by 3 and get the same result. The next bit, A B + C == AND adds A and B and compares the result to C. The AND bit combines the first two logic results. The result of the AND is true only if both of the conditions are true. Finally, B 3 * D == AND multiplies the second digit by 3 and compares that to the 4th digit. AND combines the result with the first two results.

The code 440 .1 BEEP makes the machine beep at the end. That makes it easier to time the execution with a stopwatch.

The next idea explored is saving X →STR on the stack, instead of recalling X and converting it to a string 4 times. The code X DUP DUP2 puts 4 copies of X converted to a string onto the stack. One copy is consumed in each of the following lines.

«
 1000 9999 FOR X
  X →STR DUP DUP2
  1 1 SUB STR→ 'A' STO
  2 2 SUB STR→ 'B' STO
  3 3 SUB STR→ 'C' STO
  4 4 SUB STR→ 'D' STO
  IF A 3 * B ==
   A B + C == AND
   B 3 * D == AND THEN
   X
   9999 'X' STO
  END
 NEXT
 'A' PURGE 'B' PURGE 'C' PURGE 'D' PURGE
 440 .1 BEEP
» 'PUZ4' STO

This version is smaller, using only 291 bytes. It's also faster, taking 190 seconds.

Using strings to extract digits was an experiment. We had a numeric digit extractor called G in our previous number puzzle. Here it is.

«
 DUP 10 / FLOOR SWAP 10 MOD 
» 'G' STO

The G function takes a number, and produces the number divided by ten, and the remainder. This peels off the least significant digit. So the right most digit, D is obtained first. G is then called with the new smaller number to peel off the next digit. It doesn't get called for the last digit, since we know that the number had four digits. The third call to G must produce the first two digits. The program that uses it looks like this:

«
 1000 9999 FOR X
  X G 'D' STO
  G 'C' STO
  G 'B' STO
  'A' STO
  IF A 3 * B ==
   A B + C == AND
   B 3 * D == AND THEN
   X
   9999 'X' STO
  END
 NEXT
 'A' PURGE 'B' PURGE 'C' PURGE 'D' PURGE
 440 .1 BEEP
» 'PUZ4' STO

It's slightly bigger than our optimized string version at 306 bytes of memory. But it's faster, taking only 103 seconds. The substring idea looked like it might be quicker, but it wasn't.

One thing of note is the PURGE commands towards the end. Global variables are convenient, but they've got to be cleaned up at the end, otherwise, they stay around for the user to clean up. This isn't much of a big deal on the HP-28c, but on the HP-28s, there's much more memory, and more than one program might be loaded at a time. These variables would add clutter everywhere. Local variables get cleaned up automatically. And we learned how to use them in a recent post. However, we need to change the G function to produce the digits on the stack all at once. That is, it leaves the shortened number on the stack where it can be used to produce the next digit. All the digits produced stay on the stack until converted to local variables.

«
 DUP 10 MOD SWAP 10 / FLOOR
» 'G' STO

Then the program follows.

«
 1000 9999 FOR X
  X G G G 
  → D C B A «
   IF A 3 * B ==
    A B + C == AND
    B 3 * D == AND THEN
    X
    9999 'X' STO
   END
  »
 NEXT
 440 .1 BEEP
» 'PUZ4' STO

This local variable version is shorter, using 266 bytes and faster, taking 69 seconds. I'd have thought this version would be slower, since variables are created and destroyed every loop. So, not only is this version smaller and faster, but it looks easier to read to me.

The code → D C B A « takes the four digits that are on the stack, assigns them to local variables D, C, B and A. Local variable blocks can go anywhere.

Curiously, in RPL, variables of any kind must be given an initial value. It's impossible to have a variable that isn't initialized. Using a variable that doesn't yet have a value is simply not a bug you can code in this language. Fortunately, there are lots of other kinds of bugs you can code, more than making up for this deficiency.

The next idea is to try nested IF statements. Nested IFs are logically the same as the AND statements. They should be quicker since the tests can stop as soon as one is false. The C language allows shortcut logicals where additional conditionals are not evaluated. RPL on the HP-28c does not.

«
 1000 9999 FOR X
  X G G G 
  → D C B A «
   IF A 3 * B == THEN
    IF A B + C == THEN
     IF B 3 * D == THEN
      X
      9999 'X' STO
     END
    END
   END
  »
 NEXT
 440 .1 BEEP
» 'PUZ4' STO

This version is larger at 296 bytes, but it's also faster at 54 seconds. Is it easier to read? Experimentation with the order of the IF statements did not yield a change in speed. One might expect that putting the condition that is false most often first would be faster, as less code is executed on average.

Finally, we'll inline the G function. The HP-28c's RPL encourages using and calling functions, but it takes time to call a function and return. The resulting code is bigger since the G function is 49 bytes by itself, and this version has three copies of it. It's not necessarily easier to read, but it is quicker.

«
 1000 9999 FOR X
  X
  DUP 10 MOD SWAP 10 / FLOOR
  DUP 10 MOD SWAP 10 / FLOOR
  DUP 10 MOD SWAP 10 / FLOOR
  → D C B A «
   IF A 3 * B == THEN
    IF A B + C == THEN
     IF B 3 * D == THEN
      X
      9999 'X' STO
     END
    END
   END
  »
 NEXT
 440 .1 BEEP
» 'PUZ4' STO

This version requires 334 bytes, but comes in at 47 seconds. That's about 4.8 times faster than the first version. Is that as fast as it can be done? Of course not. For one thing, the problem can be solved without a program, and it doesn't take very long. This exercise is about optimization. In this case, we didn't know the relative speeds of different functions before we started. So, a black box trial and error system was used to deduce what turns out to be fast or small. For RPL, this is what it takes. But it often takes something like it in other languages. You might think that instruction speed in assembly language would be well known. But most modern processors sometimes can perform instructions while waiting on external memory, or can even execute multiple instructions simultaneously. And often, one needs to sign a non-disclosure form to get the documentation. If that's not enough, various levels of cache miss or TLB thrashing can toss your best estimates out the window. Trial and error has the advantage of trial, which is sort of a final arbiter anyway. So make your best guess, and ask the universe if you're right.

Forth for Enlightenment, part eleven of ten, Number Problem Nine

I came across this logic problem. It uses numbers. I was able to solve it without the aid of any kind of computer. And there are computers that are way faster, and easier to use than my 1986 vintage HP-28c programmable calculator. But it looked as if a program to solve this just might fit on the beast, if barely. Also, it looked as if the run time to reach a solution might be less than hours. This machine isn't speedy. The processor has a cycle time of 640 KHz. Modern desktop processors are measured in GHz. There are 1000 KHz per MHz, and a 1000 GHz per MHz. Call it a challenge.

The following multiplication example uses all the digits from 0 to 9 once and once only (not counting the intermediate steps). Finish the problem. One digit has been filled in to get you started.

abc * d5 = efghi

Before we get started on the RPL program, let's do some minor analysis of the problem. The least significant digit produced by the 5 and c must either be 0 or 5. But if it's 5, then it's a duplicated digit. So digit "i" must be 0. That means that 'c' must be even. In fact, this program uses 'E' for Even instead of 'c'. The program doesn't have to guess either the 5 or the 0. Instead of a ten digit problem, it's an 8 digit problem.

ABE * D5 = STUV0

The program could cycle from 0 to 99999999. However, an empty loop that long takes about 8.8 days to execute. Since digits are non-repeating, and 0 isn't needed, the loop can start ABEDSTUV from 12346789 and go through 98764321. That brings it down to 7.6 days. The permutations of 8 digits that can only hold 8 distinct values is 8! = 40320. That's a loop that takes five minutes. But even there, it really only has to generate the permutations of the digits A, B, E and D from 1 through 9 excluding 5, multiply ABE * D5 and check to see if STUV also avoids 0, 5 and any of the digits A, B, E and D. And that's how this program does it.

Before you enter the program, you should know that i made numerous mistakes entering it into the machine. My first attempt had one huge function. When i finished entering it, i got "NO ROOM TO ENTER". This was on an empty HP-28c. It probably would have worked on an HP-28s, with its much larger RAM. But the HP-28c only has 2 KB of RAM, and only about 1700 bytes available when empty. It has to remember the whole function while compiling it into its internal form. This is effectively a show stopper for large functions. This version has two fairly large functions. Even here, when there's a mistake, you have to delete all the little functions to be able to edit either of the larger functions. So check your work. There's 498 bytes free on the HP28c after the run. This is one of the largest programs that can run on the HP-28c.

It would be nice to generate the permutations of ABED where A, B, and D can be 1, 2, 3, 4, 6, 7, 8, 9 and E can be 2, 4, 6, 8. But can it be done in a compact way? This program effectively counts digits, and skips inner loops when it comes to a digit that doesn't work. That leaves 8 * 8 * 4 * 8 = 2048 loops. This is well within the time constraints of the HP-28c. This program produces the correct answer 396 * 45 = 17820 in 270 seconds (four and a half minutes) and 800 seconds to search the entire problem space.

When i broke up the original function, i discovered that i needed global variables to get A, B, E and D into the inner loop. I considered passing them to the inner loop function as local variables, but then the helper functions couldn't access them. It's unfortunate in this case that the FOR loops create local variables, and helper functions can't access them. That's just the way it is.

This first function is the one you run when you've got everything entered. It doesn't take any arguments.

Check out the "2 8 FOR E" bit. The matching "2 STEP" makes it go from 2 to 4 to 6 to 8. In BASIC, the loop would be "FOR E=2 TO 8 STEP 2". The RPL version puts the STEP bit in a place that's not that easy to locate.

«
 1 9 FOR A
  A 'GA' STO
  IF A 5 ≠ THEN
   1 9 FOR B
    B 'GB' STO
    IF B CA THEN
     2 8 FOR E
      E 'GE' STO
      IF E CB THEN
       1 9 FOR D
        D 'GD' STO
        IF D CE THEN
         A 10 * B + 10 * E +
         D 10 * 5 +
         * 10 / LP
        END
       NEXT
      END
     2 STEP
    END
   NEXT
  END
 NEXT
» 'P9' STO

Then there's LP, the "loop part". It has one parameter, X. X is what you get when you multiply ABE * D5. X is then disassembled into STUV, with the 0 discarded. The G function does this disassembly. The argument is assigned to X using the right arrow (shift U on the HP-28c). This creates the local variable X.

«
 → X «
  IF X 999 > THEN
   X G 'V' STO
   G 'U' STO
   G 'T' STO
   G 'S' STO
   IF S CD THEN
    IF T CS THEN
     IF U CT THEN
      IF V CU THEN
       GA 10 * GB + 10 * GE + -> STR
       "*" + GD 10 * 5 + ->STR +
       "=" + X 10 * ->STR + "0" +
       DUP 0 DISP
      END
     END
    END
   END
  END
 »
» 'LP' STO

G gets the next least significant digit from a number. It's really divmod. It takes a number, divides it by ten, and gets both the quotient and the remainder. It returns both on the stack. This little ditty takes 49 bytes.

«
 DUP 10 / FLOOR SWAP 10 MOD 
» 'G' STO

Next come the helper functions that check to see if the given digit matches other digits. They return false (0) if any matches are found. Otherwise true. We could have a single function that checks all digits against all other digits. But it's better to check a single digit against what has been computed so far. That way, fewer total checks need to be done. The way this program achieves this is to cascade checks. The first function, CA, checks if the given digit matches A, the digit 0, or the digit 5. CB checks for a match of B, but then calls CA to check those. And so on, through CU, which checks against U, but then calls CT, which calls CS, and so on, calling all the functions to check all the digits. Checking E for 0 and 5 isn't needed, but it's done anyway, since that's done in CA. It's more or less harmless.

«
 DUP GA ≠ SWAP DUP 5 ≠ SWAP 0 ≠ AND AND
» 'CA' STO

These helper functions could have used IF/THEN, returning when false. This might be faster, but the code is bigger. The example below is not only much bigger (100 bytes vs 48 bytes), but it's slower on random input.

«
 IF DUP GA ≠ THEN
  IF DUP 5 ≠ THEN
   0 ≠
  ELSE
   DROP
   0
  END
 ELSE
  DROP
  0
 END
» 'CA' STO

CB checks the argument for ≠ B, then calls CA for A, 5, & 0.

«
 DUP GB ≠ SWAP CA AND
» 'CB' STO

CE checks the argument for ≠ E, then does CB. E stands for even, since this digit must be even.

«
 DUP GE ≠ SWAP CB AND
» 'CE' STO

CD checks the argument for D, then does CE.

«
 DUP GD ≠ SWAP CE AND
» 'CD' STO

CS checks the argument for S, then does CD.

«
 DUP S ≠ SWAP CD AND
» 'CS' STO

CT checks T, then does CS.

«
 DUP T ≠ SWAP CS AND
» 'CT' STO

CU checks U, then calls CT, which calls everything else.

«
 DUP U ≠ SWAP CT AND
» 'CU' STO

I liked this cascade style. It may not be the fastest (function calls are relatively expensive on the HP-28c, even though they're encouraged). It may not even be the smallest code. But it does work the way mathematicians think. That is, problems are attacked by solving small problems, then attacking a larger problems using the solutions to smaller problems that have already been solved. Languages like RPL and Forth have this in common with Lisp and variants like Scheme. One can design code this way for nearly any computer language. But i'm still a C and assembly language programmer at heart. I still like to shave off an instruction here and there which saves a few bytes (even if billions are available) and often a few nanoseconds or less. It should be noted that modern C compilers can do automatic function inlining. They can even note that a function can only possibly be called from one place, and not leave a callable copy. Using lots of little functions can still make such programs easier to maintain, without any penalties. In my experience, such techniques aren't limited to math and logic problems such as the above.

However, it's good to remember that superior algorithms often lead to the smallest, fastest code, and often by a large margin. For this test, one idea is to have an array of bits, one for each digit. Set the bits for 0 and 5. Then when each new digit is encountered, check if the new digit's bit is set, and if it isn't, set it. One routine clears the bits, and another does the check and set. I didn't code, test or time this idea.

That's all there is to it. Leave a comment if you manage to get it to work. Leave a comment if you attempted to get it to work and couldn't. Leave a comment if you improved it. The HP-28c is an ancient machine. But from time to time, i still see evidence that there are people who have one of these beasts. Maybe you have a younger model, like an HP-28s or an HP-48s. These programs should work with any of them.

Forth for Enlightenment, part ten of ten, local variables and loop exit

If you've been following this blog for a while, then you'll recall that i described a series of programs for a 1986 calculator, the HP-28c. There aren't any forward links in the series, though you can follow them easily enough in the blog's automatically generated links on the right side. They're more or less all together. Until now. I've decided to revisit the calculator, the language, and the descriptions.
Now that i think of it, there's an easy way to get access to all the previous articles in this series. Ten parts were planned, and labeled here zero through nine. Here are the links.
zero Count
one Factorial
two Logic problem pt 0
three Logic problem pt 1
four GCD
five Backwords pt 0
six Backwords pt 1
seven Backwords pt 2
eight Backwords pt 3
nine Primes
There are two features of the RPL language as implemented on the HP-28c that i really wanted, but didn't seem to be include. One is local variables. It turns out that RPL has local variables. And, they're documented in the manual. Worse, i'd written programs when the calculator was much younger that used them. There are a couple pages in the manual that describe it. Unfortunately, there aren't any examples of how to use them, but a little experimentation shows how they work. Above the "U" key, there's a right arrow. It's an operator that takes arguments to its left and right. To the right, you give it the new variable names. This list ends when a new block "«"(as a single character) is encountered. For each of the variables, that number of arguments are taken off the stack (to the left). A function with a local variable might look like this.

«
 1 2 → a b «
  a b 2 * +
 »
» 'FNAB' STO

This assigns 1 to 'a', 2 to 'b', recalls 'b' (2), multiplies it by 2, and adds 'a' (1). So 5 ends up on the stack. At the close of the block '«', the variables 'a' and 'b' vanish. You can assign new values to 'a' and 'b' at will in your program using 'STO'. Unfortunately, 'STO+' doesn't work with local variables. No idea why not. One can create a function that takes arguments on the stack, and has local variables like this:

«
 1 2 → a b c d «
  a b 2 * + c 3 * + d 4 * +
 «
« 'FNABCD' STO

This assigns two arguments from the stack to 'b', then 'a', then assigns 1 to 'c', and 2 to 'd'. So, if you call this function using 7 8 FNABCD, you get 'a' set to 7, 'b' set to 8, with an answer of 35.
The other feature that i'd like is some way to exit a loop early. The manuals extol the advantages of not having a functional GO TO. In my humble opinion, RPL (and Forth and Lisp) are not that easy to read. Perhaps GO TO would make it impossible. Or perhaps we should consider these read only languages. It is very likely that implementing an abusable GO TO would slow down these languages. And yet, it's common that you need to search a list for something, and you'd like to be able to stop searching when you've found it. You can use a WHILE loop, since there's a condition you can use to exit. But what do you do with a FOR loop? After all, the FOR loop creates a local variable, which gets automatically cleaned up when you're done with it. It's handy. Well, here's how you do it. You set the loop variable to the end value. This code puts A on the stack each loop. Run it, and 1 2 3 4 5 are on the stack. The number 6 doesn't go on the stack because when A is 5, it gets set to 10. The IF statement needs to be placed just before the NEXT. You can't use it to magically exit the loop from somewhere in the middle.

«
 1 10 FOR A
  A
  IF A 5 == THEN
   10 'A' STO
  END
 NEXT
« 'E' STO

The HP-28c has a printer, which prints to thermal paper. One way to save a program is to print it to the printer, then xerox the output. What happens is that the thermal paper fades with time. Making a copy can give you a high contrast print for longer. One thing that would be better is if you could print your program, but have another computer capture the output and store it to disk. Then you could make a CD, which would last quite a long time. However, the HP-28c has several non-ascii (non-standard) characters. You'd have to make sure that you also documented these. It turns out that the protocol that the HP-28c uses to talk to the printer is pretty straight forward. So building an IR receiver and capturing the data isn't that hard. I haven't done it yet. And this still leaves getting a program back into the calculator. The HP-28c does not have any kind of network input. The printer only accepts input. The HP-28c only emits output. If there's no printer, or it misses something or falls behind, well, too bad. And, i've discovered that you don't really know how to enter a program until you've entered it and made it work. So, once you have your killer application written, you need to copy it somewhere, delete it, and enter it from your notes. There's no way around this. Doing it sooner (when you still know the program) has the advantage that if you make a mistake, you probably still know enough about it to fix it. Doing it later than sooner has the advantage that if you can do it then, it's more likely anyone can.

What works in education - round up at Smithsonian

The Smithsonian has a series of articles on Finnish education. It starts by comparing Finnish education to 9/11. Really, it came without any apparent warning. I don't see much additional connection.

The meat of the series talks about why Finnish schools work despite costing 30% less than schools in the US. There are lots of reasons. No standardized tests means more time teaching students how to think. Did anyone think that teaching students how to take tests is a useful life skill? But there are surprises in the article. Some can also be read here at Business Insider, of all places.

Do (did) you like homework? I did. I work better when it's quiet. I can learn by reading a book. It's not harder for me than having someone else teach. So i got more done, more thoroughly and quicker at home. I expect that my experience is not the norm. My son's 4th grade teacher sent out math problems that most adults couldn't solve. Things like, "What is the sum of the integers from one thorugh one hundred?" Hey, i know that one: (100 * 101) / 2 = 5,050. Don't need a calculator, since 100 / 2 = 50, and 50 * 101 is easy. But WTF? Most adults can't do this without adding 99 numbers. Is homework good? Maybe - in moderation. Here's what the Smithsonian had to say.

My son went to a Montessori school from preschool through grade 5. But unlike this article, he managed to learn a technique for addition that resulted in the wrong answer 2 out of 3 times. You may have used a similar technique. To add 4 + 5..., you start with one number, say 4, on your fingers, and you add 5 fingers to it. Instead of correcting the mistake, i decided to make a complete break from it, and taught him addition and subtraction on an abacus. His math improved dramatically in a couple months. Regular readers of this blog will know that i'm not shy about using fingers for math. But it wasn't the school who taught it, despite the Montessori roots. I believe that's because the school didn't carry the method long enough. It wasn't a private school, but rather a charter school. That means that they got students pulled away from the public schools. These are students who have at least one parent who could fill out a 17 page application, and who actually did it. This is a big advantage for these students. The school doesn't have anywhere near the issues that public schools have. And yet, i also pushed my kid through to reading for enjoyment. I'm not against the Montessori method. But i don't like the way it's getting used here in the states very much. You can't talk about education seriously without Montessori.

My first thought was that all this guy wants to do is scientifically document stuff that good teachers already know. I mean, if you've got kids in front of you, then it's obvious. But he also wants more, and he gets what the serious issues are. He's got more to say here.

And yet, there is good stuff happening right here in the US. Salman Khan is doing good work, for example.

And, you've got to know what the Flynn effect is. My grandfather was an engineer. He'd have scored ridiculously good on modern IQ tests.

Bowling a Perfect Game

The gang at work did a team build thing. We went to a local bowling alley to shoot the breeze, eat pizza, and bowl a few games. I'd sprained my right wrist earlier in the month, and it was still a bit sore. I've bowled left handed in the past, but it's pretty dismal. Still, this is team building, not a real competition. My strategy was to try it right handed, and if it got too painful, i'd switch hands. The expectation was that each game would get worse. The sprain is by the pinky. The result was that i have no aim. It was sort of random, like Brownian pool. However, my scores were 85, 95, and 124.

The high point of the first game was that in frame six, i was tied for last place. That was the only time during the game that i wasn't alone in last place. In the ninth frame of the second game, i'd achieved 75. To equal my first game, i'd need to score 10. The only way to achieve that would be to bowl a spare and a gutter ball. See if you can figure out how i managed twenty in the tenth frame. That last game wasn't really better than the first two, except for three spares in a row, followed by a strike. I plugged the game scores into a spread sheet, and added a quadratic curve fitting trend line. The line goes right through the actual scores. It shows that by game six, i'm bowling 300 - a perfect game. Clearly, i should have played three more games. The math doesn't lie!

Curiously, the wrist felt much, much better (not worse) the next day. Who'd have guessed that?

Worst cars...

Bumped into this post at LA Times. Click on the box labeled 6 to get to the page "5. 2003 Saturn Ion". Now, i don't have an Ion, or anything as new as a 2003. But my 2000 Saturn SL has plastic fenders. And i love them. I have no idea what the LA times is talking about. Five years ago, the car was the recipient of a hit and run while parked. The left rear fender has, if you look real hard, a scuff mark, and a bit of green paint from the offending vehicle. There's no dent, because the plastic fender just bounced back. There's also no rust. Plastic doesn't do that. I've only recently discovered that the plastic isn't white all the way through. The plastic is, in fact, dark gray. It's painted, like any other car. But it's taken a very long time for enough of that paint to come off anywhere. And did i mention that it doesn't rust?

I love my Saturn. I kept careful track of gas mileage for several years. It was getting 43.7 MPG, overall. One 1,100 mile trip, the car got 49.5 MPG. Nothing special, a 1.9 liter 4 banger, with a 5 speed manual. Small engines rock on the highway. It has low mileage: only 307,000 miles. I see lots of younger cars with fewer miles blowing blue clouds out the back, but not my Saturn.

Maintenance has been low. I went through a series of brake rotors. But i bit the bullet and bought some good rotors, and the issue vanished. I also put some quality time and parts into the front end. So my front end alignment has held up on Michigan's crappy roads.

Click on the box labeled 8 to get to "3. 1987 Yugo". I had the '78 Dodge Omni. Four door hatchback. Small on the outside made it easy to park in downtown Boston. The hatchback made it huge on the inside. I wished the rear seats folded down flat, but it didn't matter much. I really wished it had a five speed manual, instead of a four speed. Or failing that, at least a highway gear. Lifetime fuel economy was a dismal 28 MPG. But i installed a cruise control, and it got 40 MPG on trips - at 50 MPH. Well, the national speed limit was 55. One of the very cool safety features was that in a level parking lot, i could push it backwards with one foot, and then pop start it in reverse. The engine always started. It got me where i needed to go. It was also oddly fun to drive. It was reliable right up to the end. At year eleven, everything broke except the engine. Door locks, the hatch latch, the hood latch, the electric fan for the radiator, the alternator, and so on. I gave it to a dealership. But the cost of ownership per year was low, and has only been improved on by my Saturn. I bet the Yugo had cost of ownership advantages over most vehicles.

Venus Transit 2012

I mentioned the Transit of Venus just before the event. That's where the planet Venus crosses in front of the Sun. Never seen at night. The lines to view the transit were continuous in every scope at the top of the Physics building at Wayne State University, in downtown Detroit. Both the primary and secondary had white light solar filters. The ten inch scope doesn't track the sky, so it has to be moved every minute or so. I used the finder to adjust the view, so that visitors would have more time to get a look through the primary.

When the Sun set on a building, I moved the scope to the top of a big metal box - part of the building. This extended viewing for maybe ten more minutes. I bring a kitchen stool so kids have something to hang onto other than the eyepiece. But with the scope raised, I'm standing on the upper step. I took the opportunity to get a picture with a cheap point and shoot camera held at the eyepiece. You can see clouds behind me, and they show up in the image.

It's pretty easy to spot a Transit of Venus once you've seen one. It's the round dot next to the word "Venus". A Transit doesn't look much like a Sun spot. Can't wait for the next Transit, in 2117.

Sales call

We've been getting sales calls at work. They want me to change my employer's long distance carrier. I have zero interest in it. I don't know what carrier is used, have no responsibility or authority over the long distance carrier. I figure that either these guys are paid on commission or by the hour. If' it's by the hour, well, i can kinda see it. But if there's any commission, then there are tens of thousands of numbers to call at my employer alone where the chance of success is absolute zero. Now that's a cold call.

One of my coworkers speculated on how long these people would stay on the line if put on hold. I wouldn't expect them to stay on hold for long. If you want to keep them on the line, you have to talk to them.

One time years ago, i got home from work, and got a magazine salesman. I told him that i had just let my last two magazine subscriptions lapse. He asked what kinds they were, and i talked to him for 45 minutes. At that point, i mentioned that, "well i just remembered, but i actually subscribe to over 50 monthly magazines". He was outraged, "How did you forget that you subscribe to over 50 magazines?" - I answered, "Oh, I collect comic books." He hung up on me.

That was total victory for me.

Old browsers

smashingmagazine.com

gmail (and other products) started complaining about my 10 month old version of Firefox at home. I have to dismiss the complaint every time I read mail. There is absolutely nothing wrong with my browser.  And though the newer version of Firefox has a Javascript engine that is 4 times faster, there are user interface issues that are simply unacceptable. I'm never going to upgrade until that's fixed.  Complaining that one year old browsers are holding back the internet is absurd.  End user load for upgrading software should be a consideration.  Should I also upgrade my video card every year to support epilepsy inducing eye candy? My primary home desktop is over ten years old. The video card can't be upgraded. And what about smart phones (and various tablets)... They run on batteries. They'll never be as fast. And their hardware can be upgraded by... oh right, they can be upgraded by outright replacement.

We should not have two internets - one for six month old high end desktops, and one for everything else. At work, I have no admin access to my computer. I can't install or update software. I get what I get. It currently has IE8. I don't have to like it. But if your site doesn't support my browser, i'm not going to use your site. The whole industry needs to get a grip.

In my opinion, we should all be using an open source browser that has zero corporate financial support. I'm not aware of one.  The browser experience should be entirely end user oriented - not advertiser oriented. One used to be able to stop all animations by pressing the escape key. These days, I kill the browser, and generally tell it to forget about any sessions when i bring it back up. Great user interface, guys.

A Dangerous Method

The Philosopher's Zone on Australian Radio had a discussion about the movie A Dangerous Method. The show generally has an interview between the host an another philosopher. And this show wasn't really different from that. They used a couple short audio clips from the movie. They attempted to go into some depth about what the characters were talking about. I came away from this show thinking that this is pretty much how i'd like movie reviews to be done. I'd rather not hear about the plot, if that can be helped. I'd rather not hear about how good the photography was, or how good the sets were, or what the special effects, if any, were. I don't even want to hear if the reviewer(s) liked it. What i'm interested in is if it's a movie i'd want to see. This review did that for me.

And it turns out that it was available at the local video store. The kids were away, so we rented it and saw it. I was quite pleased. But mind you, i'm not talking about the movie. I'm talking about the radio show as a review, and the movie as a combined experience.

My favorite movie of all time is still Brazil. It's a pretty odd movie. The review i followed was one of my friends who said, "We're going to a movie. Want to come?". This was an excellent review, since it said nothing about the movie, except suggesting that i might like it. The title doesn't give anything away. Later, i read the book, which includes the screenplay. I still haven't the foggiest idea how the movie name corresponds to the movie.

Eclipse and Transit

Every so often, a cool event gets upstaged.  This Monday, June 4th, at 6 am EST, there's a partial eclipse of the Moon.  The Moon will get partly covered by the shadow of the Earth.  It happens fairly frequently.  But it's pretty cool.  And, to the ancients, it was a way to state that the Earth is a sphere.  That's because the Earth's shadow on the Moon is always round, more or less.  If the Earth was flat, then even if it was a disk, the shadow would sometimes be a thin oval.

Check out Astronomy magazine's eclipse coverage.

The big event happens on Tuesday the 6th.  Here in Michigan, it starts around 6pm EST. Sky & Telescope magazine  says this. And the reason that it's such a big deal (though the effect is way smaller than the lunar eclipse) is that, if you miss it, your next opportunity might be in 2117.  I'd guess that kids born next year won't see one. Few live that long.

But it's not an either-or proposition.  Why not see both? Here in Michigan, there are lots of events set up for the transit:

Transit Events
 

Scylia and Charybdis

Bumped into this dinosaur comic. It reminded me that, every now and then, i hear a song that really rocks. It's evidence that someone has strapped themselves to the mast while sailing by the islands Scylia and Charybdis (that's how i'd heard it - not having read the book myself. Who knew that Scylia and Charybdis aren't the names of two islands that crash together if you attempt to go between them, but rather a six headed monster and a whirlpool? The book's on my reading list now.). Anyway, the Sirens really knew how to write and perform a tune. It'd be worth a little madness to hear something that good, right? The Sirens are still there, i hope.

Courage

Forget The Sorcer's Stone where Dumbledore gives Neville Longbottom points for standing up to his friends. Forget The Deathly Hallows where Neville chops off the snake's head. In the movie version of the Goblet of Fire, Neville steals something from Professor Snape. That takes courage. That's why he's in Gryffindor. Or was he smart enough to choose it?

Good news

A friend was recently in the hospital with a blocked artery and had angioplasty. This is not as absurd as open heart surgery. The later, though effective and highly successful, has been described as "overhauling an engine while it's running". However, even short hospital stays are not cheap.

The thing is, he recently changed jobs. And as of a few years ago, employers have started delaying health insurance for a month or three while you start the new contract. This is pretty evil. Getting health insurance on your own is ridiculously expensive. And if there's any kind of employment gap, it's ridiculously expensive when you have essentially zero income. So when this has happened to me, i've skipped health insurance for a month here and there. I take no medications, and rarely have anything serious happen, so it seems like a good bet. I've been lucky so far. When my gall bladder exploded, i was covered. It would have been something like $6k.

Anyway, the good news is that my friend's new insurance did indeed take effect before his hospitalization.

We seriously need to decouple health insurance from employment in the USA. Employers have way too much power over employees. And, employers have been shown time and again to make use of their power in unethical ways. For example, i know people who were threatened with termination who, once terminated, must then leave the country. That's because these people were invited to work here on a work visa. It's a major hassle to sell everything you have and fly home.

The thing is, companies, especially large companies that run a cyclical business, like to hire people on "at-will" contracts so that they can dump them when business slows. In the old days, they paid these people a bonus. Not so much anymore. There are some good reasons to be a contractor. First, you have a spouse with insurance, and you go with contracts so you can opt out of it. Second, you want absurd breadth of industry experience. Third, as an "at-will" contractor, you have the option of quitting without notice or explanation when you discover that your new boss is an asshole. The sword cuts both ways. But when jobs are scarce, you tend to take what's available. And that's when it becomes clear that this whole system sucks. We need an affordable national health plan.

OBFUSCATED COBOL

Today, i ran into a snippet of COBOL with a bug. It was of the form

 IF LONGWINDEDNAMEA = 3 OR 4
  AND LONGWINDEDNAMEB(1:1) = C
  MOVE...

but it should have been

 IF (LONGWINDEDNAMEA = 3 OR 4)
  AND LONGWINDEDNAMEB(1:1) = C
  MOVE...

because AND has higher precedence than OR. So what the first example does is, uhm, what the heck? Oh. COBOL has implied subjects and implied operators. If omitted, it uses the previous subject and/or operator. The first example expands to this:

 IF LONGWINDEDNAMEA = 3 OR LONGWINDEDNAMEA = 4
  AND LONGWINDEDNAMEB(1:1) = C
  MOVE...

so the compiler directs the computer to compute

 IF LONGWINDEDNAMEA = 3 OR (LONGWINDEDNAMEA = 4
  AND LONGWINDEDNAMEB(1:1) = C)
  MOVE...

Which is not at all what the author wanted.

When I was a good deal younger, the incredible verbosity that is COBOL was explained away like this. The language is designed so that business managers could read it. It's hard to imagine what business manager audience COBOL was aimed at. None that i've ever met could have told the difference between COBOL that does what it looks like and obfuscated COBOL.

IMO, a large fraction of computer bugs are actively encouraged by languages that think programmers don't know how to type. Computer languages also have absurdly complex precedence tables. Who could get that right every time? Only the guys who look it up every time, or use parenthesis every time. Why not just go with left to right everywhere? 1 + 2 * 3 = 9, instead of 7 (because you need to * before +).

Now, i suppose programmers don't, by and large, know how to type. I could type 22 words per minute by the end of high school. I could type 22 words per minute by the end of college (plenty of practice, but no additional instruction). Over the next 20 years, at a keyboard for 2000+ hours a year (40,000 hours), my typing speed doubled to about 40 words per minute. But about ten years ago, i got addicted to a typing game for a couple months, and my typing speed shot up to over 70 words per minute. What a wasted 20 years. With a little instruction, i could have save huge amounts of time typing.

Happy Pi Day

Go ahead, have a slice of pie. It's pi (π) day (3.14 or March 14th).

Wait a minute. I get '3' as the third month. But 0.14 of a month like March (31 days) is 4. So, shouldn't π Day be March 4th?

Or, if it's just the decimal representation, and you use the digits, what about other bases. Computer people use octal. The number pi, in octal, is 3.11. So two decimal digits of π is 14/100 (100 = 10 * 10). In octal, you're looking for a number that in decimal is x/64 (64 = 8 * 8). x = 64 * (14 / 100) = 8.96, or roughly 9. But 9 (decimal) in octal is 11, which is 8 * 1 + 1. All that to say, computer nerds can claim the 11th of March as pi day too.

Why stop there? Computer people also use hexadecimal. In hexadecimal, π is 3.24 or March 24th. This is particularly handy if you missed March 14th.

And, in Europe, dates are reversed from the USA. I have no idea if anyone really celebrates π day on the 22nd of July, which is 22/7.

If that's not enough, you can at least think about Tau day. Tau (τ) is π * 2 or 6.28 or June 28th. I don't know what you'd eat, maybe 2 pies? But you can show off as a real math geek.

There you go. You are eligible to eat your π on March 4, March 11, March 14, March 24, July 22 and June 28th. That should fill your pie hole.

If all else fails, March 14th is Einstein's birthday. And he doesn't look a day over 133. If you're not into π, you could have Einstein cake. You can have your cake and eat pi two (π * 2 = τ).

Opposition to Mars

Mars opposition this year was March 3rd. That's when Mars, the Earth and the Sun are lined up. It's when Mars is closest to the Earth for another year and a couple months. It's not a magic date where, if you miss Mars on that day, you missed it. It's just that Mars gets closer to the Earth up to that date, then farther. It happened to be cloudy on the 3rd for me. But on March 5th, i happened to have a 60 mm (2.4 inch) diameter refracting telescope out, and though there were some hazy clouds, and got to see the orange blob at 78x magnification.

It wasn't very impressive. However, i have ready access to a 254 mm (ten inch) diameter reflecting telescope. Since this is four and a quarter times the diameter, i should be able to see details four and a quarter times smaller. But also, it collects over thirteen times more light. That means the image should be brighter, and can stand more magnification before becoming grainy. Good enough to see some surface features at a glance, such as a polar ice cap. About once every five minutes, the atmosphere is still for a split second, and lots of surface details become clear. So the views are great for the patient.

The 2003 Mars opposition was the closest Mars would be to the Earth in something like 70,000 years. That's because it took place in late August. That's the time of year when the ellipse that is the Mars orbit is closest to the Sun. Six Earth months from late August is late February. So this very early March opposition can be described as nearly the farthest Mars opposition for quite some time.

It will be worth a look. Through my astronomy clubs, i have access to larger telescopes. And so do you. One club offers a public Open House every month, and another operates an observatory that seems to be open essentially every clear night. It's highly likely that you live near such a club.

Bacon

I haven't played in a movie, so i don't have a Bacon number. But in 1997, i was in the Mendelssohm Club, a chorus in Philadelphia. The Philadelphia Symphony Orchestra hired the chorus and also hired John de Lancie (you might know him as "Q" in Star Trek, among many other roles) as a narrator in a performance of Honegger’s King David. So, i performed on stage with John de Lancie. This is a fact which, i'm sure, he does not recall. There were over 80 of us in the chorus, and i never talked to him in any kind of one on one way. Well, i looked it up, and John has a Bacon number of 2. So, if my performance counts (no reason it should), then i have a Bacon number of 3.

I did have a curious concern. When i was a kid, i had all sorts of fantasies. Most of them were a bit stupid. And, almost all of them had come true. In fact, when some of the more outrageous fantasies actually happened, i started getting worried. One of the stupider fantasies had not yet happened. And it was sort of a recurring thing. I call it "Getting Stuck On An Elevator With A Celebrity". Since it recurred, i could sort of get an idea by what was meant by a celebrity. That's because it seemed to be a different celebrity each time. I avoided the elevator.

These days, i define celebrity as someone who has admirers that they've never met. And, since i volunteered, i now help produce a monthly TV show, Astronomy for Everyone. I'm in almost all the episodes. A few months after the show started, i was at Astronomy At The Beach, a really big public event that the Great Lakes Association of Astronomy Clubs sponsors. This is an organization that is made up of about eight area astronomy clubs. They bring somewhere between 70 and 100 telescopes to a park, and between 3,000 and 13,000 people show up over two nights. Anyway, at the event, one of my friends said that a member of the public admitted to knowing my name. It shouldn't have been a big surprise. My estimate is that about 10,000 people watch the show. I meet my definition of celebrity.

The really stupid bit about this "Getting Stuck On An Elevator With A Celebrity" fantasy is that it involves getting stuck on an elevator. At best, this is a nuisance. And now, i've actually gotten stuck on an elevator. It's not an at best experience. So, does this count? Or do i have to get stuck again, only with someone else? I take the stairs alot. If you think you might be a celebrity, try not to get on an elevator with me.

Windows Media Player v 9.00.00.4508 on XP review

I mostly listen to music, audio books and podcasts on an mp3 player. But sometimes when i'm at work, the battery is low. My mp3 player can be recharged by plugging it into a computer USB port. Unfortunately, i can't then use it to listen to whatever. It can only either operate or be charged, not both. However, if i plug it into a computer, the computer can mount the device. However, the computer doesn't know where the device was last in a track. And, when i want to use the device again, the device doesn't know where the computer was. I handle this mostly by listening to whole tracks on the computer, and different tracks than i used last on the device.

The sound quality for my computer at work is comparable to the sound quality on the device. In both cases, i'm using the same headphones, which appears to be the primary limit for quality.

I thought Media Player on Windows XP could play any mp3 track. However, in one case, Windows Explorer identified a track as mp3 that Media Player wouldn't play. It turned out to be 192 Kbps variable rate encoded. My mp3 device played it without complaint.

Media Player can be excused from not being able to play Ogg Vorbis files. This Media Player was released in 2002, which is also the first year that Ogg reference software was released. It took forever for portable audio devices to support it. I used to convert all tracks to mp3 format. But now that i own a device that can play Ogg files, i prefer it. I can't update Media Player to some newer version. I can't install real software. I don't own the computer, and my employer does not allow me to install anything on it.

Another glitch in Media Player is that it doesn't smoothly go from track to track. There's always a short pause. Every now and then, music is split into tracks, but the audio was originally played continuously. It can be an annoyance. It's not a performance issue. It's just buffering. Windows Media Player didn't bother to get the software right.

Sometimes, if you select a bunch of tracks at once in an Explorer window, and tell it to play, Windows Media Player plays them in some apparently random order. They appear sorted in the Explorer listing, but appear shuffled in Media Player. It looked like Media Player was playing in directory order, but the mp3 player actually plays in directory order by default. I put the files on the device so that directory order is sorted order. The play order can be changed on Media Player one at a time. I thought there was no sort function, because there isn't such an option in the menus. However, there's a playlist button, and a sort option appears there. Mostly, i play one track at a time on Media Player. Both Media Player and my mp3 player device have shuffle modes.

Media player can do a few things that my mp3 player can't. It can play from CD, stream from the Internet, play certain DRM material (not an issue for me), and it offers various distracting visualizations. Fortunately, there is a "no visualization" option. In short, there are no unique features here that i value.

What does the device offer that Media Player does not? It plays a variety of sound file types. It offers more information on how a file is encoded. It smoothly plays from one track to the next. It offers playback equalization. It shows file encoding information. It can play back either 20% fast or 20% slow. It remembers where it was when last playing every track. It plays adjacent tracks without a gap. In short, most of these features are valuable.

Internet Blackout

Tomorrow, Wednesday, January 18th, there will be no blog post here on Predelusional. This is to protest big entertainment companies, the Chamber of Commerce, and their lobbyists attempt to get their way by ramming Internet censorship legislation through the US Senate.

On Thursday, January 19th, there probably won't be any new content either, but you never know.

parent/teacher conferences

An algebra teacher has four hundred and twenty students. There are three hours for parent/teacher conferences. If each parent talks to the teacher for one minute, how many new gray hairs does the teacher have by the end of it?

a. 5
b. 100
c. 500
d. all of them.

teacher pay for performance

I'm an engineer and computer programmer. One of the things that bothers me is that my employers, and i'm talking about managers here, almost never have a clue about how good or otherwise my performance is. I'd have thought that one would get an idea based on productivity or problem solving, or problem anticipation, or something. It simply doesn't happen. Most managers have little or no technical competence of their own. They don't seem to have any way to judge the performance of any of their direct reports with respect to others. They mostly either like you personally, or they don't.

As a contractor, i've changed positions frequently, so i've gotten to participate in numerous interviews. These too, have been nearly without exception, awful. More than a few have subjected me to a "quiz". For no apparent reason, i generally have performed quite poorly on these quizzes. One exception revolved around a research question that would be worthy of a Master's Thesis. I'd never seen the problem before. Though i was not able to come to a solution in 20 minutes, my direction was at least tenable. So, my performance has historically been good on impossible questions, but poor otherwise.

In a few cases, i've gotten a new manager at an old job where the new manager subjected me to a quiz. These have also been awful gages of performance. Why have tests been so bad?

I've talked about the No Child Left Behind (NCLB) program that G. W. Bush pushed into law. The idea here seems to have been that 1) teacher's own test scores do not correspond with student competence, so 2) we'll test students, and reward teachers with improvements in student's scores. A logical problem with this approach is that student's scores on testing also does not correspond well with student competence.

I've just read the editorial in the AASA Journal of Scholarship & Practice, Summer 2011 edition. It lists a number of further points. These include the fact that NCLB was rolled out to the nation, but never tested. There are numerous statistical issues with what students are tested for what teachers, and how the response to the program is to "play the program", without concern for the education of students. For example, let's say that you are a Special Education teacher. All of your students have been given to you because they are behind. But there's no policy that protects you as a teacher. Even if you improve your student's test scores dramatically (though they're still below average), you'll be penalized. This editorial talks about how some students have been encouraged to drop out of school and pursue a GED, instead of staying in school, and lowering the average test scores for the school. This doesn't help the students. And so on. The details are important. I highly encourage everyone to read the above referenced article.

As an engineer, i don't have pay for performance unless i go into business for myself. And, even then, i only have pay for performance if i get all the business stuff right, and perhaps, am lucky. But now it appears that even if i'm an above average engineer (whatever that means), this is a good thing - judging by the teaching profession.

If we want our kids to do better in school, we have to be smarter than this. We need to use systems that work, proven in pilot programs. Our current system, forged in the general incompetence of politics, doesn't work.

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.