I really, really wish that computer book authors would pay more attention to their work.

I know that I’ve mentioned the Montgomery reduction algorithm here before, and the sad state of nearly all of the few things that describe it. I finally got it to work properly a while back, thanks in part to the book Cryptography in C and C++, but it was slower than the standard raiseToPowerMod function I’d implemented. It was supposed to be significantly faster, so I started looking for tweaks I could do. There were several in that book, and implementing them one at a time helped, until I got down to the last piece.

The last piece was intended to quickly calculate the inverse of a number, and the heart of it was described as:

If x < ny mod x, set y ← y + x.

The only problem is, that statement is logically impossible. Regardless of the value of x, ny mod x will always be, at most, one less than x, so x can never be less than it. I puzzled over that line for many hours, trying to figure out what was wrong with it. It didn’t help that the German-to-English translator that they’d gotten for that book was either not a native English speaker, or didn’t understand the subject matter… reading it was easier than reading a machine translation, but the original German is still painfully obvious, obscuring many of the details. I finally dug into the example code for the book to figure it out.

It takes a lot of experience to write code that’s easy for another human to understand, which in large part is why reading code is considered significantly harder than writing it. (Book authors almost never have that level of experience, which is why I avoid their code whenever possible.) It took me nearly two decades of practice to reach the point that my code can be easily understood by anyone familiar with the language, rather than something that only the compiler could parse. It requires a clean design, carefully-chosen and descriptive variable and function names, and comments that explain why something is being done, possibly in addition to exactly what is being done if it’s not clear.

This guy doesn’t do any of that.

His code works, so far as I can see (and that alone is a major improvement over some computer books!), but he leans heavily toward old-school C — short and often cryptic variable and function names, and his comments are few and far between. The need for programming like that went out before 1200-baud modems arrived, but you’d think that he suffered the agonies of the damned over every byte that wasn’t absolutely necessary to compile the program.

On the plus side, every function that he provides does have a header comment that describes what it’s intended to do, and its syntax, inputs, outputs, and return value. And every macro has a one-line comment explaining (in terse but readably English) what it does. That goes a long way toward making the overall design understandable, even if the functions themselves take a lot of deciphering.

In any case, I discovered the problem. That line should read:

If x < ny mod 2^x, set y ← y + x.

It’s a small change, but it makes a huge difference.

My raiseToPowerMod function, using the Montgomery reduction, is now significantly faster than it was before. Timing is difficult, but it looks like it’s 25% to 50% faster than without the Montgomery stuff. 🙂 But getting to that point felt like walking barefoot over a bed of broken glass.

It’s really no wonder that good software developers can command such large salaries… anyone less stubborn persistent than I would have given up long before getting this to work, let alone making it work quickly.