RFC-70
by Darius Kazemi, March 11 2019
In 2019 I'm reading one RFC a day in chronological order starting from the very first one. More on this project here. There is a table of contents for all my RFC posts.
Padding math
RFC-70 is titled “A Note on Padding” and is authored by Steve Crocker of UCLA on October 15th, 1970.
The technical content
This is a continuation of notes on marking and padding, kicked off by Michel Elie's RFC-64, and also addressed in RFC-65 and RFC-67.
This is mostly a math/algorithms note. It is trying to solve the problem: given a series of bits (a “word”) where it's all 0 except for a single 1, but we don't know where the 1 is in the series, how do we efficiently and conveniently determine the position of the 1 bit?
The first and most obvious solution is to simply start counting from one end; on a computer this is accomplished by shifting the word to the right until the rightmost bit is a 1, counting each time we do a shift. This is apparently “unpleasant”, although I'm genuinely unsure if it's unpleasant meaning “difficult to program or inefficient to run on a contemporary computer” or if it's unpleasant meaning “brute force and therefore not aesthetically pleasing to those of us who enjoy mathematical elegance”.
Most of the paper is detailing the algorithms to discover the position of an isolated 1 bit. I won't summarize because (1) I will mess it up, (2) it's math so it's as terse as it's going to get and if you care you should read the RFC!
Analysis
I can imagine that having to do an O(n) search on every single message received over the network would suck, so I understand the impetus to come up with a better, more efficient way in this RFC.
I would also like to commend Guillaume Lahaye and John Hewes; they transcribed this RFC in June 1997 and they did an excellent job getting all the mathematical notation correct (I checked it against an original RFC in person).
Further reading
Crocker thanks Bob Kahn and Alex Hurwitz for their help on the RFC. Kahn is of course an ARPANET fixture we've spoken of before. But Hurwitz wasn't really an ARPANET guy. He is famous for using an IBM 7090 at UCLA in 1961 to discover the largest known Mersenne prime number. Fifteen minutes later he discovered an even larger largest known Mersenne prime number! According to this article the 7090 was actually an interface to SWAC, a giant special-purpose vacuum tube computer that was kind of the math processor for the whole thing! Anyway, having a guy like Hurwitz to check your math on a paper is like having Hemingway copy-edit your short story or something. Here are some cute photos from a meeting of prime number hunters in 1996 including Hurwitz.
How to follow this blog
You can subscribe to this blog's RSS feed or if you're on a federated ActivityPub social network like Mastodon or Pleroma you can search for the user “@365-rfcs@write.as” and follow it there.
About me
I'm Darius Kazemi. I'm a Mozilla Fellow and I do a lot of work on the decentralized web with both ActivityPub and the Dat Project.