Yesterday, I was speaking with someone who was working with school kids to try to break the world record for the Most Delayed Palindromic Number. He had written a program for it in Smalltalk and they were trying to break the world record of 261.

First, a bit of background. A palindromic number is one where the digits are the same forward and backward. For example, 4328234 is a palindromic number. You can often make palindromic numbers by taking another number, reversing the digits and adding it to the original. For example, 1423 + 3241 = 4664 which is palindromic. This may not work all the time, but you can often continue the process. For example,

• 96 + 69 = 165
• 165 + 561 = 726
• 726 + 627 = 1353
• 1353 + 3531 = 4884

So, in 4 steps, we took 96 and created a palindrome. Now the challenge: What's the largest number of steps that produce a palindromic number using the reverse/add technique. The record is currently 261.

The implementation developed by my friend used printString on LargeIntegers, reversed it, then turned it back into a number to add and compare. I said I could make that faster for him, so I implemented a BCDNumber class using ByteArrays. It was surprisingly easy. Reversing the numbers was just a matter of reversing the bytes (I used one byte per digit). Comparing was easy and addition involved a //10 and \\10 calculation on each digit and handling the carry.

When I was finished, I started my program on 22 digit numbers and calculated the palindromic sequence length for a million numbers stopping if the sequence exceeds 300 steps. Overall, the system performed 33.6 million large additions, reversals and comparisons and ran in about 181 seconds. That means that each addition, reversal and comparison tool (of more than 22 digits) took 8 uS on average. I haven't broken any records yet, but it's a lot easier when the program funs faster.

I haven't compared to Java or C or anything else. I'm sure C could run faster (no bounds checking and no integer overflow checking). But I'd say that performing over 185,000 long Integer additions, reversals and comparisons per second is pretty darn good for a high level language like Smalltalk. Who ever said that Smalltalk is slow?