Dr. Dobb's Journal April 1998
I usually try, in this space, to touch on a variety of topics, including the theme of the issue (this month, it's algorithms) and the history of programming. Combining those two (algorithms and history) is not necessarily a good idea. Algorithms, unlike French wines, do not usually improve with age.
The Ylbvi-Nlliv algorithm, though, is of such interest that I just had to tell you about it. Even if it is 400 years old.
In other algorithmic news, Apple Computer would like us to believe that it is executing a smooth, fast, and efficient implementation of a powerful hill-climbing algorithm that will haul the company up out of the hole it's fallen into. Steve Jobs was coyly modest in announcing a $45 million profit for the quarter that ended just before the latest MacWorld Expo, but he and Apple's top management want the world to see this profitability as evidence that Apple has found the algorithm of its redemption.
I hope they have. A bad hill-climbing algorithm can lead you badly astray. Apple's recent profitable quarter could be the beginning of the end of the bad times, but it could also be just a local bump, surrounded by chasms on all sides. Does Apple have an algorithm that will let it find that sought-for long stretch of rising terrain?
They may, but if they do, they're keeping quiet about it. This year's MacWorld Expo showed off the latest release of the Macintosh operating system and the latest prerelease of Rhapsody, the operating system that is to the MacOS as NT is to Windows. It also showed off a more platform-neutral QuickTime and another product whose name you probably thought you'd heard the last of.
What we didn't hear much about at MacWorld Expo was, well, almost everything that could help to turn the company around. It's not that exciting new products aren't coming. It's just that Apple isn't talking about them. I listened to those who are talking about them, and I have a report.
But first this.
François Viete, who published under the Latinized name Franciscus Vieta, worked in the court of King Henry IV of France in the 16th century. He was a formidable mathematician, and he has been called the father of algebra. It was Vieta who first came up with the idea of using letters to represent unknowns and constants in equations.
Although he may be the father of algebra, he never would have referred to himself that way. He hated the word algebra, preferring the word analysis. That's why the use of algebraic methods to solve problems is today called analysis.
In the 1580s, Vieta did some clever work in a special kind of analysis -- cryptanalysis -- that was used for cracking the the Spanish monarchy's code. France and Spain were at war at the time, so this pleased Vieta's boss a lot. Just about as much as it annoyed Philip II of Spain, who went to the Pope to accuse the French of sorcery when the fortunes of war went against Spain.
Vieta fiddled around in various areas of mathematics and problem solving. In 1582 -- on October 10, 1582, to be exact -- he published what he claimed was a clever little searching procedure. He called it the "Ylbvi-Nlliv algorithm." The name Ylbvi-Nlliv is almost certainly some sort of cryptogram.
There are, as it happens, several mysteries surrounding this algorithm. For example, although he definitely published the algorithm on October 10, the publication bears a publication date of October 2, for some reason.
Even the algorithm itself, as published, seems to be some sort of cryptogram, but it is a cryptogram that has never been solved in over 400 years. Here, for what it's worth, is Franciscus Vieta's Ylbvi-Nlliv algorithm:
Apple in general and Steve Jobs in particular were uncharacteristically modest at January's MacWorld Expo in San Francisco. They just weren't talking about unreleased products or corporate strategy. It was such a thundering silence that one would have been justified in assuming that Jobs had laid down the law that such topics were verboten.
As was the case.
I think this is very smart, but the silence was so unsettling that a number of professional and amateur journalists began assuming, for example, that since Jobs hadn't mentioned Rhapsody in his keynote, the company must be abandoning it.
Such is not the case.
But if you wanted to hear about Rhapsody or about a variety of other subjects, you had to exert yourself a little.
The rumored Apple Network Computer was not mentioned formally at the show, and questions about it to Apple personnel were rebuffed. But Larry Ellison, who started the whole thing, was recently heard talking about it again. Apple will deliver NCs running the MacOS this year, perhaps focusing on the education market, if you believe the Acting CEO's best friend.
The Newton market was not mentioned, but the eMate continues to sell well in the education market. Apple is doing nothing to suggest that it isn't going to abandon the Newton line, with the exception of the eMate. In my opinion, the eMate has another six months to live, but that's predicated on the very risky assumption that Ellison isn't blowing smoke about the NCs.
The growing sub-$1000 PC market was not mentioned, but when pressed, Apple execs would go so far as to say they were aware of it. Rhapsody was not mentioned in Steve's keynote, but a new prerelease version was being demoed at Developer Central at the show, and everything I've seen and heard indicates that it's going to be solid and impressive when it hits the street this year.
The new CEO was not mentioned, and here I think that even the general press is reading it right. Nobody wants to take the job with Steve looking over his shoulder.
What Apple did mention was shipping products, or almost shipping. System 8.1, sure, fine. Macromedia Dreamweaver, a visual site-design tool that doesn't mess up the underlying HTML. And QuickTime 3.0, aha.
QuickTime is a technology that Apple has decided to give a lot of attention. The latest version uses compression technology from Sorenson Vision, specifically for streaming video and audio over the Internet and off CD-ROMs. There are other Internet-oriented advances, like excellent QuickTime VR compression that loads a low-res black-and-white image and fills in both resolution and color incrementally. Apple wants to make QuickTime the industry standard for digital media, and QT 3.0 is a big step in that direction. As they put it, "It brings the full power of QuickTime -- including the ability to capture, edit, compress, and playback digital media -- for the first time to all major personal computer platforms, including MacOS 8 and MacOS 7.x, Windows 95 and Windows NT 4."
Apple is so serious about QuickTime that they're finally going to charge for it. The basic version will remain free on all platforms, but an authoring version will cost $29.95.
And with the release of QT 3.0, HyperCard suddenly becomes relevant again to more than a few die-hard stackheads and the authors of Myst. The newly released (by-the-time-you-read-this) HyperCard 2.4 has the ability to read any QuickTime-readable file. It also has new scripting commands and properties for controlling QuickTime movies or other media. HyperCard 3.0 is expected to bring total HyperCard/QuickTime integration, so that HyperCard becomes a QuickTime development environment, and HyperCard stacks become QuickTime movies and then some. As a die-hard stackhead, I look forward to that eagerly.
It seems safe to say that scripting will be a feature of Rhapsody on all platforms.
TipTop's Objective-Framework System (http://www.TipTop.com/) integrates Tcl and Perl with compiled languages so you can do rapid prototyping when developing Rhapsody apps.
Apple people are saying privately that AppleScript or something much like it will be available for Yellow Box development. And a Tcl interpreter shipped with the Developer's Release. Meanwhile, Metrowerks has come through for Apple again, this time with Latitude, a code library that helps you to move Macintosh apps to Rhapsody. You recompile your source code under Rhapsody and link it against Latitude and you get a native Rhapsody app. Latitude should be completely endian neutral by the time you read this, which is an issue because of the various platforms Rhapsody will run on.
From Michael Tsai:
I enjoyed your column in [February]'s DDJ, but as customer of both MetaTools and Metrowerks I just can't let this line go: "MetaTools stepped in on that occasion and saved Apple from disaster."
Did I really say that? Darn. I meant "Metrowerks," of course.
Christopher Creutzig writes with a correction to another recent column:
In your latest column, you stated that "finding the prime factors of large composite numbers efficiently" lead to "cracking all existing cryptographic codes." This, however, is definitely not true. While there are a number of cryptographic algorithms whose security would be naught if factoring was found (or, in case of qc, engineered) to be feasible (RSA comes to mind as the prime example), there is a whole lot of widely used algorithms for which factoring is no threat, e.g., virtually all secret-key algorithms such as DES, IDEA, or Blowfish. Granted, quantum, computing would be a threat to almost all existing cryptosystems, but that's not due to the ability of factoring large numbers.
Corrections, links, and updates to my columns can be found on my web site at either http://www.swaine.com/ or http://www.cruzio.com/~mswaine.
When I ran my trivia quiz in December, I said that nobody would get all the answers. In fact, nobody got any of the answers. The response to this puzzle is the worst I've ever seen in a career of publishing puzzles. Okay, it's a hard puzzle (probably no more than a dozen people in the world know the answer to question 3, for example), but sheesh. On the assumption that you were just intimidated by its difficulty, I'm repeating it this month. You have one more chance. And the way things look now, if you get two questions right, you'll be the winner. Of course there is no prize, but with the build-up I've given this puzzle, think how proud you'll be to see your name in print as the one who solved it. Or even 20 percent of it. Send your answers to mswaine@cruzio.com.
Okay, here are a couple of hints. The answer to question 1 is not Steve Wozniak or Steve Jobs, Sue Cooper is an answer to one of the questions, the person in question 9 is really two different people with the same name, and don't waste your time on question 4 because nobody will ever get it.
Speaking of puzzles, I won't keep you in suspense about the Ylbvi-Nlliv algorithm.
For a cryptogram that has not been cracked for 400 years, this one is pretty easy. I suppose the reason that no code sleuth managed to crack it in all those years is that I just wrote it in 1998.
The code is a simple letter-substitution cypher, a <-- z, b <-- y, and so on. The nth letter of the alphabet becomes the nth from the end of the alphabet. "I" becomes "R". "R" becomes "I". "Nlliv" becomes "Moore".
The date October 10, 1582, was a nonexistent date in countries under the dominion of the Catholic Church in 1582 (like France). That was the year that Pope Gregory reformed the Julian calendar, removing ten days from the year at the stroke of a quill. NonCatholic countries changed over later, by which time they had to skip eleven days to catch up with the Catholics and the sun. There's a nice account of the history of the date in Andrew Binstock and John Rex's Practical Algorithms for Programmers (Addison-Wesley, 1995). Since October 10, 1582, is a bogus date, you may be harboring the suspicion that the story of Franciscus Vieta and his clever searching algorithm is also bogus. You would be correct. Why the bogus algorithm? It's a matter of dates again, which is why I worked October 2 into the story.
You see -- but I'll get to that in a moment.
Everything else said about Vieta is true. He did live in the time period indicated, he did work for the King of France, he is the father of algebra, he did hate the word, and he did crack the Spanish code for France. My source on Vieta is Asimov's Biographical Encyclopedia of Science and Technology (Doubleday, 1982). The algorithm, once it has been decoded, is also legitimate, being a brief, one might almost say cryptic, version of the Boyer-Moore algorithm that I borrowed from A.K. Dewdney's The Turing Omnibus (W.H. Freeman, 1989). There remains one date puzzle: Why did I say that the algorithm bore the publication date of October 2 when it was really published on October 10?
The answer is, October 2 is not a nonexistent date; Pope Gregory removed October 5 through October 14 from the calendar, but left October 2 alone. I wanted to use a nonexistent date to clue you that there was a trick involved, but I also wanted to work in the date October 2. Why did I want to get October 2 into the story?
Well, try applying the a < -- z letter-substitution cypher to the date. Only instead of counting off letters of the alphabet, count off days of the year. October 2 is the 275th day of a nonleap year (and 1582 was a nonleap year). Counting back from the end of the year, the 275th day from the end is...April 1.
This is the April issue.
DDJ