Monday, September 05, 2005

Cycling for digits

There's a computer language called Nickle which grew out of something Keith Packard started working on two decades ago because he needed to do a little arbitrary-precision calculation. One of the entertaining features of the language, particularly if you're trying to teach people about compilers, is the treatment of rational numbers. Every rational number can be written as a decimal expansion that starts with some fixed digit string, and then has a repeating part, and this is the form Nickle uses for printing and (I assume) reading rational numbers. For example, the number 5/6 in Nickle would print as 0.8{3}, where the stuff between braces indicates the repeating part.

An entertaining exercise is to write a routine to read a Nickle number and convert it into the form p/q, where p and q are (relatively prime) integers.This turns out to be pretty simple to do in Lisp. Also entertaining is to write a routine that prints a Nickle number. If you find these entertaining, too, you can check out the class page in a couple weeks. I'm not going to post my solution until I've given the exercise for folks to think on between weeks three and four, but I will say that it fits in a page and a half of Lisp, including comments -- the front of the page for reading Nickle strings into Lisp, the back for generating Nickle strings from Lisp rationals.

I think it would be highly entertaining to work through the consequences of different internal representations of these numbers -- for example, if you represented Nickle numbers internally as strings like 0.{3}, then even something as simple as equality becomes nontrivial (since 0.{3} = 0.{33}, even though the two strings are different). You'd probably want to convert the strings into a unique minimal form for comparison, which boils down to a problem in state machine compression. But then you might want to do something different for actual arithmetic. Unfortunately, while I might find it entertaining, these sorts of issues are not likely to be of much interest to the class. So I won't say anything about it unless someone asks.

What I might ask about -- because it actually provides a very entertaining exercise in manipulating finite state machines -- is how you can recognize that a repeating decimal expansion can be written as p/q for some specified q. And what if I allow make the strings finite by allowing rounding? If I allow rounding, it's most natural to introduce nondeterministic finite automata (NFAs) and then convert them to deterministic equivalents (DFAs); this is also the usual chain of tools one uses in building tokenizers for programming languages. If you find such things amusing, I recommend the following two special cases: write a finite state machine to recognize decimal expansions of p/6 which are correctly rounded in the last digit, and another for p/7. You may be able to do the first case in your head, but the latter isn't so obvious. Or is it? I claim that, having done it once, I can now recognize by inspection a correctly-rounded decimal expansion of p/7 for any p. Your calculator probably displays enough digits that you can see the pattern just by playing around with it.

A similar sort of pattern holds in the case q = 17, actually, and in the case q = 47. But observing those patterns on a pocket calculator might be a little harder, unless your calculator displays more digits than does mine. And while I can now remember enough to pretty easily write down what the decimal expansion of p/7 looks like for any given p, remembering the same information for 17 or 47 is not so simple or useful.

But the washer just buzzed, which means that I should move my quilt over to the drier and get back to work.