laziness, impatience, and hubris  
PerlMonks 
comment on 
( #3333=superdoc: print w/replies, xml )  Need Help?? 
Like everyone else, I have been reading the “10**21” threads with some academic interest – but also, I confess, some confusion when talk is made of “4 gigabyte lookuptables.” If the poor Romans actually had to do that, they’d never have been able to count anything. An algorithm for converting Roman numerals to decimal is trivially easy: just reverse the string (say ...) so that you intepret it from righttoleft instead of lefttoright.
When the string is viewed from lefttoright, parsing seems difficult because in a wellformed Roman string like MCCMLXXIV you don’t know what C means until you encounter M. However, that’s not the way the Romans did it. They probably also read the string from righttoleft, as was and is the standard for many human languages of the region. Now, the rule is one that any human could do in his head: “if the digit is as big or bigger than the biggest one you have seen sofar, reading from right to left, add it to the total; otherwise, subtract.” They did not use arbitrary combinations of letters, although the algorithm shown above would accept them. (As an example, I doubt that they actually used IM to represent 999.) In fact, the rules that they did use make the process similar to “making change” given various denominations of currency, and this can’t be accidental. So, while the talk of this being a “10**21 problem” is an interesting one, and the latest installment (#3) about whacking the TLB of the processor is even more so, it seems like an incredible amount of work to unleash on a problem that has a trivial algorithmic solution. I am certainly not “dissing” that thread for its informative discussion of how to deal with problems that would require massive search, but Roman Numerals does not seem to be a good example to use here, unless I am entirely missing the point. (Which possibility I do not deny.) The proper solution for Roman Numerals would be to “find a better algorithm,” then optimizethehell out of that algorithm. I cannot imagine that any solution would be faster, especially when the time required to populate those gigabytes of data is included, but I say this only because a nearly costfree algorithm to solve this problem readily exists, as just shown. For problems that lack such alternatives, the issues discussed in that thread are of course hugely relevant, and the solutions, very informative.      For the “true diehard golfers” among us, the same algorithm can be expressed, even without any conditional branches at all other than for the scanloop, as a finitestate machine (FSM) with twentysixelement tables containing numbers that are either positive or negative depending on the table. The machine’s state would, of course, represent the largest digit, if any, yet seen when scanning from right to left. For instance, in the table for state LARGEST_SEEN_IS_V (i.e. all tables except LARGEST_SEEN_IS_I and INITIAL_STATE), the entry for I would now be (1). A “real” Perl implementation would use a Clanguage subroutine. If an ERROR_STATE is provided, such an algorithm could also detect and reject “syntax error” inputs (as the algorithm shown above cannot do). Which is exactly why we build languageparsers and lexicalscanners this way . . .      Clearly, the intent of the main thread must be to present efficient solutions to problems that actually do consist of arbitrarystring inputs, for which all possible strings are equally probable, under conditions where arbitrarilylarge amounts of physical RAM are presumed to be available. Problems that, unlike Roman Numerals, do not present a trivial algorithmic solution. Problems for which an efficient solution in the Perl language (or at least, the Perl environment) is required.      (Postscript: I recently helped with a geocachinglike team building challenge for highlypaid “alphamale” executives, in which you had to use a GPS to find nearby things in an unfamiliar town and obtain clues. One of the things we took them to was a statue which had a date written in Roman Numerals. They just needed to get that date. No big deal, any thirdgrader could do that, right? Uh uh. I was speechless to watch several(!) of them busily searchingfor and downloading a “Roman Numerals app” to let them decipher the clue ... which they had utterly no idea how to do on their own. They could not read Roman Numerals! So they sat there, locating and downloading – in a couple of cases, buying – an app for their cellphones. “Oy vey!”)

