Fifty years ago, the world of programming languages was wildly different from today. Designers of programming languages were discovering ways of describing computations to computers. In that process, some amazing ideas were explored, resulting in interesting ways to program a computer. I love studying these languages and the ideas behind them.

Some of the wildest old programming languages is called SNOBOL, created in 1962. I am in love with this programming language because it is very different from modern programming languages. Some aspect of this language really show how old it is, while other aspects make it quite powerful, encouraging to think about programs in a new way.

In the 1960s and 1970s, if you went to university, you could take a SNOBOL course to learn how to do text manipulation. (SNOBOL4 is the most commonly used version; the source code is dated 1969.)

Studying this language helps you better understand the things we all take for granted. A few of the strange properties of SNOBOL are:

• Although this programming language is all about pattern matching, it doesn’t use the regular expressions that are used by almost every pattern matching tool today (Java, Python, awk, perl, your editor, and so on).
  In fact, its matching system is superior. Not only are patterns often easier to read, but you can even define recursive patterns!
• SNOBOL has tables that map arbitrary objects to other objects. This powerful feature is now common in modern languages: Lua has tables, Java has HashMaps and Python has dicts. It is hard to imagine that such a thing was already there decades before these languages were developed.
• SNOBOL allows for programmer defined data structures with fields. This was very uncommon at that time.
• SNOBOL allows for user-defined functions. The way you define them is quite strange (and awkward). The function definition header could occur in a location other than just before the code of the function. In fact, the code of the function is just a piece of code. You had to explicitly jump over it to prevent it from running prematurely.
  But still, you could use local names in a function, and recursion was allowed (both of which were uncommon at the time).
• User defined operators were also possible so you could define addition of complex number, for example.
• A terrifying feature is that it was possible to rewrite parts of the code of a running program. It sounds very powerful, and it is, but the resulting code is so hard to read that it is definitely not recommended.
• Like Fortran, lines were assumed to have 80 characters, of which the last eight characters were ignored. In that time, programs were typically stored on punched cards. So these last eight were a convenient place to put line numbers, so could sort your program again if you dropped your cards on the floor.
• The language is older than ASCII, so there were no square brackets [] . They used <> for indexing (“triangular parentheses”). It did include the ¬ sign however, which is hard to type today.
• SNOBOL4 did not have if/then/else or loop constructs at all. Instead you only had assembler-style labels and GOTOs. On the other hand, every sentence could specify a jump address, so you did not need explicit GOTO statements.
• The way spaces are treated in SNOBOL is confusing, to put it mildly. For example, if X=25 and Y=5, you get:
  X - Y equal to the number 20
  X -Y equal the string “25–5”
  X-Y is a syntax error
  A non-space character in the first column means a label, so
  A B = C means “set B to C” (with label A), while
  A B = C means “replace the part of string A matched by pattern B to string C”, and
  A = B C means “A is the concatenation of B and C”.
• From 1968 on, SNOBOL ran on a “virtual machine”, allowing implementations on different hardware.

Here a simple program that counts words. It gives you an idea of the craziness of the language. I’ll explain what it all means below.

*   Simple word counting program, WORDS.SNO.
*
*   A word is defined to be a contiguous run of letters,
*   digits, apostrophes and hyphens.  This definition of
*   legal letters in a word can be altered for specialized
*   text.
*
*   If the file to be counted is TEXT.IN, run this program
*   by typing:
*       SNOBOL4 WORDS /I=TEXT
*
        &TRIM  =  1
        WORD   =  "'-"  '0123456789' &UCASE &LCASE
        WPAT   =  BREAK(WORD) SPAN(WORD)
NEXTL   LINE   =  INPUT                      :F(DONE)
NEXTW   LINE WPAT =                          :F(NEXTL)
        N      =  N + 1                      :(NEXTW)

DONE    OUTPUT =  +N ' words'
END

Click here if you want to run this program right now, thanks to the power of Try It Online, where you can also try out 680 other programming languages, by the way.

There was a time when people used SNOBOL4 to write programs for many tasks. Hardcore fans of SNOBOL wear a t-shirt with this cool design:

I found an implementation of the language (SPITBOL 360 from 1971, released again in 2001), that still runs unmodified on current IBM mainframe machines (now that is what backwards compatibility!). It seems that there were relatively recent implementations for Macintosh, PC and some other machines. Until a few years ago these were all maintained by a company called Catspaw. The company seems to be gone, alas. When browsing around I stumbled on a mess of broken web links, many of them pointing to the now defunct snobol4.com that was owned by Catspaw. It was terrifying! Finally I managed to find a SNOBOL4 tutorial and a SNOBOL4 reference manual, archived on archive.org back in 2006. There are also a few collected SNOBOL resources at regressive.org, which may help you further investigate this language.

I recommend you to read the tutorial: it gives you a refreshing (and probably confusing) new view on text pattern matching!

As stated above, SNOBOL4 runs on a virtual machine. The reason was to make it easier to port the program to other computers. The virtual machine is called SIL (for SNOBOL Implementation Language) and it was written in assembler. This assembler code was specifically written to be easy to port.

This made SIL one of the very first virtual machines ever to be used for implementing a programming language. Today, this idea is quite frequently used, for example for Pascal, Java and Python. Indeed, the free downloadable version still uses SIL.

To get an idea of the working of SNOBOL, let me explain the example program above. Prepare to be confused.

Obviously, the lines starting with * are comments.

The lines that start all the way at the left are lines with labels; these can be jumped to.

The first line &TRIM = 1 sets a system variable (called “keyword” in SNOBOL lingo) to indicate that all spaces at the end of input lines are to be removed. This is useful, since SNOBOL assumes by default that input lines consists of all 80 characters on the punched card.

The second line WORD = "'-" '0123456789' &UCASE &LCASE defines a string called WORD containing the characters ’-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz..

The third line WPAT = BREAK(WORD) SPAN(WORD) constructs defines a pattern that consists of any number of characters not in WORD, followed by any number of characters in WORD. BREAK and SPAN are functions that produce patterns from a string (interpreted as a set). Patterns are a standard data type in SNOBOL, that can be combined in all kinds of interesting ways; here we just concatenate the patterns. Today we would WPATusing the regular expression [^-0–9A-Za-z]*[-'0–9A-Za]+ with the same meaning, but less readable.

The fourth line, NEXTL LINE = INPUT :F(DONE) is a bit confusing. It defines a label NEXTL that indicates the beginning of a loop. It reads a line of input into the variable LINE. And, if there is no input (end of file, that is), this “fails”. In that case (indicated by the F), we jump out of the loop to the end of the program. The idea that a statement can fail is now again a concept if one of the latest programming languages, called verse. I wonder if Simon Peyton-Jones was thinking of SNOBOL when he thought of this!

The next line is the inner loop of the program:NEXTW LINE WPAT = :F(NEXTL) . NEXTW is the label of the inner loop, since it is at the start of the line. The piece LINE WPAT = does all the work: it matches the pattern WPAT that finds the first word, and then replaces it by the empty string (that’s because there is nothing after the =). If there are no more words on the line, the pattern match fails. The :F(NEXTL) then jumps to the next line, forming the outer loop. Note that the concatenation LINE WPAT in this statement means “match a pattern”, while the concatenation BREAK(WORD) SPAN(WORD) two lines earlier means “concatenate two patterns”. The difference? Well, pattern matching is on the left of the equals sign, while concatenation is on the right. Duh.

Then N = N + 1 :(NEXTW) increments the word counter and jumps to NEXTW forming the inner loop. Initialization of N is implicit to 0.

Finally, the line OUTPUT = +N 'words' prints the result (the unary + makes sure N is interpreted as a number). The space concatenates the two strings (because it is on the right of the =).

Finally, the last line END tells SNOBOL to stop executing. Lines read after this point are input to the program. This line is required; an error occurs if you omit it. This strange feature meant you could put the punched cards with your program in the card reader together with your text, and in one go run the program with data.

There are many more strange and wonderful features in SNOBOL, such as the * operator that meant “compute this later when you use the value of this expression”, allowing to use values that you didn’t define yet. Thanks to that feature, you could define a recursive grammar with surprisingly little code (using lower case for legibility, because that is allowed today):

 atom = span(&lcase) | span(&digits) | '(' *sum ')'
 exp = atom ('**' *exp | null)
 prod = exp (any('*/') *prod | null)
 sum = ('-' | '') arbno(prod any('+-')) prod
 formula = pos(0) sum rpos(0)
* that's all. Now make sure we didn't make a mistake
 test = '-123+7*(2**3**a-5)'
 test formula . output :s(t2)
 output = "Test failed for " test
t2 test = '4+8 a'
 test formula . output :s(end)
 output = "Test failed for " test
end

Sorry that there is no statement coloring; Medium’s code box has no setting for SNOBOL4.

The grammar definition is beautiful, while the test code is terrible. You can try it out right now if you want. If you really want to understand the test code, I’ll explain the statement test formula . output :s(t2) :

test is the label; this is just used for readability. test formula . output matches the string test against the pattern formula. The “.” makes a copy of the matched pattern to the output if the pattern matches; this means the string test is printed (because assigning to output causes a string to print) if it matches. The s(t2) skips the next line on success; this means that the error message is printed if it fails.

I hope you liked my peek into the world of strange programming languages. There are way more of these languages, and who knows, I might study another one for you.

I was surprised by a few things in the news:

• Why is Utrecht University so heavily impacted?
• Why is this in the news for days on end?
• Why are people protesting against data centers in relation to this?
• This time, the data center simply stopped operating. Why didn’t anyone warn that things could be worse, where both computers and data could be lost?
• [Update] I hear that the data center wasn’t impacted, and the power connection was still available. The whole reason the data center went down was because the fire brigade ordered to shut it down because of safety. In effect, the backup power was the cause of the shutdown instead of protecting against it.

Let me explain my surprise.

Data centers have been there for a long time. Worldline has used data centers for three decades. When I started working there (back when it was Interpay), there were five centers across the Netherlands that handled payment processing. The data centers where owned and operated by our company. There are good reasons to run a data center:

• Computers need good power, good connections and good cooling, and it makes sense to have specific buildings (or rooms in buildings) that provide this.

There’s also a very good reason to run multiple data centers:

• Computers aren’t very reliable.
  Not only do they fail if power, connections or cooling are unavailable, but they can fail due to hardware faults, cyber attacks or just poor programming.

Of course, having more than one data center doesn’t solve that problem; you also need to build everything to that keeps functioning when things go wrong. This is a surprisingly hard problem. A nice example is how AT&T long-distance service failed because of a single line of code.

But it can be solved. Thirty years ago, the services of Interpay did not go down. I remember power outages, cables being severed by digging machines and misconfigurations that did not result in clients even noticing something went wrong.

Today, the services of data centers are called “cloud computing”. You can rent these services in many different ways, from just renting the computers directly, to renting computer programs, databases, email servers, and so on. The data centers can provide automatic backups of your data, but also redundancy, and provide all kinds of other security services such as automatic updates and detection of security problems.

So there I come to the first of my surprises.

Why is Utrecht University so heavily impacted?

Utrecht University has a IT department. They know about cloud services and data centers. They know how to make services redundant (they teach that). They could have set up everything so that they were not dependent on any single data center. Considering this, I have a few questions for their IT department:

• Did you decide that making a redundant system was too complicated, or too expensive?
• If not, did you consider that something could go wrong?
• This time, the data storage was not impacted. Please check your data backup for next time.

Of course other companies were impacted, but they appeared to be prepared, at least a little bit. Transdev had reduced services (but apparently everything still worked). The ferry to Texel could check the tickets (but they had a manual backup). That sounds like a good way to run a business: if something terrible happens, make sure you can keep running.

Why is this in the news for days on end?

So it is a big fire, and it took days to stop. But that isn’t exceptional. A data center stopped functioning. That’s also not very exceptional. A few companies had reduced services: that happens all the time.

It’s probably me: I don’t understand what gets in the news, and what doesn’t. To be honest, I don’t follow the news daily anymore: highly recommend to reduce your stress level!

Why are people people protesting against data centers in relation to this?

A few days later there was a demonstration against “data centers” and “big tech”.

What these protesters are upset about is the energy and water used to run AI models and cryptocurrency mining. Both of these are resource wasters driven by the greed of a few rich individuals who want to get richer. At least, I hope that’s what they were really protesting.

Are you using it as a warning for yourself?

I like to learn from my mistakes. What we can learn from this fire is to think a bit about “risk management”. Many good books have been written about this subject. This is not only useful for companies, but you can do it for your own life as well. I’ll take an example: my phone.

A risk analysis consists of a few steps.

First you ask yourself the question: “what are you afraid of”? In other words, try to predict the unexpected things that can happen, and find out what you worry about. In the example, I am afraid to lose my phone of course. But it I think about it, the real thing I worry about is the data that is in the phone. I use my phone for all kinds of things, but there is a lot of information in there: addresses and phone numbers of of friends, for example. Also, I would like this data to be available if I cannot access it myself.

The next question is: what are you doing about it now? In my case, I have a backup in Google of all my data, and another backup by another cloud provider.

After these questions, you can ask the two essential questions that can be use to compare the risk against other risks:

• How likely is it that it happens? (Likelihood)
• How terrible is it? (Impact)

If you have done this for multiple risks that you are afraid of, you can compare the different risks that you have in your life. This allows you to make decisions about your life, and what you can fix. In my case, I could just write down (or print) all these names and addresses on a piece of paper, and store it somewhere. A very simple solution that addresses the risk almost completely.

Final thought

There is an ISO standard on risk management: ISO 31000. Interestingly, this standard also includes “positive risks” where an unexpected event has a more positive outcome. It is quite interesting to see that some countries oppose this view, while other sees this as interesting. It is part of the current version of ISO 31000. Alas, this text is not public, but many good books have been written about the subject.

To my surprise, the discussion isn’t over, and few countries insist that the standard is changed back to the “pessimistic” view on risk management. I have not seen this before in my ISO work that a standard is “moved backwards”. The new version is currently being written, and the progress is painfully slow because of this. Only time will tell how this ends.

I did the research because I couldn’t stop. I never planned about writing an article about it. But when I spent more than a week doing the research, going in many different directions, I though I might as well share the story with you!

[Read on Substack]

As most you know, I am a cryptographer. Cryptography is part of mathematics, so I started studying mathematics at the Eindhoven university of technology (in 1988, this was still called the THE). Of course I needed a calculator. I decided to spend a considerable amount of money on an HP-15C, which turned out to be a good investment; it is a wonderful calculator that could do everything I needed, and more. (For a story specifically on the HP-15C, you can read this article by Peter Sels.) If you want to play with it on your Android phone, I recommend the free JRPN simulator. (Note: specifically its integration command differs from the original HP-15C, which was a bit inconvenient while writing this article.) There is also an very faithful official emulator, that gives you the exact same behavior as the original one.

The HP-15C can do all kinds of fancy math. This article is about my favorite command: numerical integration. This is calculating the area under a curve. The curve is given by a function you program into the calculator. The calculator calls your function a couple of times, and computes the area.

The idea doesn’t sound to hard, but if you want an accurate answer this way, you would have to call the function hundreds of times. There are much better ways of doing this; if you are interested in this branch of mathematics, look up “numerical quadrature”. I wanted to know the exact method used by this calculator, because I remember from my college days it was pretty good, and I wanted to understand how and why, so I could write is for myself on a current computer. That’s where the story starts.

In search of the mythical algorithm

The calculator was not only great because of the construction and functionality, but also for the documentation; I have used the “advanced functions handbook” (now available for free as a recreated high quality PDF!) as an addendum to my study books. This book helps you with working with the integration command, and explains a few things about the algorithm, but not everything. William Kahan wrote a detailed article in their HP journal, with is quite an interesting read; there I found that the HP-15C wasn’t the first calculator with that function: it was the much less well known predecessor, the HP-34C.

From the descriptions in the handbook, I knew the following:

• The calculator computes the functions at a fixed set of points in the interval.
• It doesn’t use the endpoints, to enable you to integrate functions that cannot be computed at one of these points (which occurs quite often)
• It uses more and more points, until the integral is accurate enough.
• It doesn’t use uniform samples, but computes the function more often near the ends of the interval than in the middle. According to the description, this is for integrating functions with oscillations, but I found out that there is a much more important reason. This is an important result that I will explain in detail below.

And then there are the obvious restrictions because this was a very small single chip lower power calculator:

• The calculations could only use a small amount of memory space (less than 100 bytes).
• The algorithm could also not use much ROM memory, so no big tables of constants cannot be used.
• The function should be called only a few times, because otherwise the computation would take days instead of minutes.
• If the calculation is extended with more points, the earlier results should be reused to save time.

In my first attempts to understand it, I found that all of the numerical integration methods in the literature failed on one or more of these points. Many use a lot of memory (that increases with the number of points) or long tables, and most methods start with calling the function at the endpoints.

The advanced functions handbook gave two hints to start my investigation: it used “Romberg” integration, and it gave the exact formula that it used to compute the points where it called the function. The HP journal article also gave a link to a very big mathematical textbook that supposedly contained the relevant information.

I studied the textbook. Most of that is in the Wikipedia page on Romberg integration as well. But the book doesn’t explain enough: nothing about non-uniform sampling points, and nothing about computations that do not use the endpoints. Even worse: the formulas didn’t work! I tried to repeat the calculations, and I got very inaccurate results, much worse than the calculator. And to make matters worse, this method uses a variable amount of memory. And I still didn’t want to believe in magic: there must be a way this tiny calculator did this.

After a long search, I found a program that did a calculation that looked a lot like what I was looking for. The the PPC ROM plug-in module for the HP-41C calculator contained an integration routine. This PPC ROM contains an enormous amount of extremely well written routines, and each of these routine is well documented and also contain a program listing. The routine is question was the “IG” program. In the documentation it stated that it used “a Romberg method” just like the HP-15C. Also, the way the points are computed was identical to what the HP-15C used. So I was finally getting close to an answer!

Since this program was for the HP-41C, I needed an emulator. Fortunately, there is Thomas Okken’s highly recommended Free42 emulator for the HP-42, which could run the same program. So I entered the program and ran it. (Note: again, the built-in integration routine of the Free42 is different from the original HP routine. It calls the endpoints of the function and therefore doesn’t work the way I wanted.)

Yes! the routine produced the same results as my trusty HP-15C. Now I could reproduce the HP-15C integration with a routine that I could see for myself. I was getting closer to my goal of understanding how it worked. All I needed to do is figure out how this program worked. I thought I was close, but there was another hurdle.

The geniuses that wrote this program used so many techniques for making the program faster and shorter that it was impossible to figure out how it worked, even with the explanations that were provided. Several times, I stared at the code to see what it was doing, but it looked more like a programming bug than something else. The only thing that was clear was that the right results came out!

There is a loop in this program calculates the Romberg approximation, and also calculates the weights of the non-uniform sampling points. After lots of trail and error I saw how this code cleverly combined all computations into one. I had an idea how the calculation worked, and I could program it into a spreadsheet.

Now there was only one thing left to figure out, and that was how the HP-15C could do this with only a fixed amount of memory, while this program used a variable number of registers. That puzzle is only solved all the way at the end of the story, however. First I had to see how well this algorithm worked in practice.

In order to do that, I had to try out the calculations with a few functions of myself. I could do that with the spreadsheet I made; feel free to have a look. Let’s start with an example. For easy comparison, all functions I pick are integrated between 0 and 1.

Here’s x*exp(–3*x). The function is drawn in red, the area to integrate is in blue. (The integral is (1–4/e³)/9 = 0,08898352517: you can use Wolfram Alpha to calculate that for you.)

Of course, the calculator only samples a few points, and never sees the function like this. For example it could use the following 31 points. (The number of points automatically depend on the accuracy that you specify.) The fact that the points get closer near the endpoints is visible in this picture:

The set of points used by the calculator is fixed for every integral; adjusted for the endpoints. In this article, all integral are between 0 and 1 for simplicity. The calculator use iterations of increasing number of points, doubling every time:

• First it computes the middle point only (0.5).
• Of the two halves of the interval, it picks two “middle” points, slightly closer to the end of the interval.
• Now the interval is split in four quarters, and it picks a point in each one.
• Now it pick eight points, and so on, until the result is accurate enough.

After having calculated the 31 points shown above, it estimates the integral to be 0,08898349319, which is six significant digits of precision!

In order to understand better how accurate this approximation is, I tried a few more functions. The example above is a “tame” function without very jumps or steep parts. I tried a few more functions, from “tame” to “wild”.

Here are the functions I used for my investigation.

The following table shows the accuracy of the computations in digits. To have a good comparison, I didn’t just count the accurate digits, but used an exact formula. If you want to know: I calculated -log10(abs(computed-exact)) for each result. Note that the table goes beyond the 10 digits that the HP-15C provides.

Accuracy in digits of Romberg integration
Function     15pts 31pts 63pts      63(4) 127(4)
x*exp(-3x)     5.1   7.5  12.1      10.5   14.6
floor(x+π)     2.2   2.4   2.0       2.0    3.3
1/(0.1+x)      3.2   4.5   6.9       7.0    9.3
√1-x²          6.7   9.2  12.4      12.6   15.7
sin(25x²)      1.0   2.1   3.9       3.9    6.5
sin(10x²)      2.1   3.9   6.4       6.5    9.9
sin(πx)        4.5   6.9  10.0      10.5   13.5
exp(-3x²)      5.0   7.7  10.1      10.0   13.9

More points give more accuracy, as expected. And “smooth” functions are very precisely calculated, even with only 31 points. The “wild” functions are harder. In particular, the function with a single jump in it is very imprecise: that’s why the user manual suggests to compute such integrals in separate parts around the jump. It is not hard to understand why this is imprecise, by the way: you can’t find the exact position of the jump by observing only the sample points.

Finally, the explanation of limited memory

The last two columns of the table are allow to understand how to use a fixed amount of memory. To understand them, I have to explain a little bit about what Romberg integration does. To put it simply, it looks at the integration estimates after 1, 3, 7, 15, 31, etc. points and looks “where it is going”. In theory from the textbook is explained that each estimate is about four times as accurate as the last one. If you know that in advance, you can predict the “final” step with a simple computation. If “est4” is four times as accurate as “est1”, then the ultimate outcome is (4*est4-est1)/3. By computing this final step for all iterations, you get a new row of estimates, which is much more precise. You can do this again assuming that each estimate is 16 times more precise, then 64 times, and so on. This is the Romberg method.

In the table, the first three columns repeat the Romberg process until the end: three times for 15 samples, four times for 31 samples and five times for 63 samples. The last two columns stop at four repetitions. To my surprise, stopping prematurely is not always bad: in some cases it is even more precise. You can see this in the table for sin(πx). And since more points gives much more precision.

Each iteration of the prediction process uses an extra register for keeping intermediate results. So what the HP-15C apparently does is to only do four Romberg iterations, which gives plenty of precision for a 10 digit calculator, unless your function is very wild.

How useful is non-uniform sampling?

The next question is there use of non-uniform sampling. According to the “advanced functions handbook” (where they call this “substitution”:

Besides suppressing resonance, the substitution has two more benefits. First, no sample need be drawn from either end of the interval of integration […] Second, [∫] can integrate functions […] whose slope is infinite at an endpoint.

So, in order to find out how this worked, I first had to write an alternate version with uniform sampling. Because of the super optimized implementation, that wasn’t so easy. When I finally managed, I discovered the Romberg prediction process didn’t work at all! The reason is that the iterations are not getting four times as precise per iteration, but only two times. After adjusting the formulas, I finally could see how many digits of accuracy we get, and compare with the original non-uniform version.

Loss of precision in digits when using uniform sampling
Function     15pts 31pts 63pts      63(4) 127(4)
x*exp(-3x)     0.3   0.7   3.5       2.4    5.0
floor(x+π)     1.2  -0.4   0.6       0.6    1.4
1/(0.1+x)      0.9   1.2   2.9       3.0    4.1
√1-x²          3.7   5.7   8.5       8.6   11.3  !!!
sin(25x²)     -0.8   0.6   1.6       1.5    1.7
sin(10x²)      1.1   1.9   3.0       2.6    4.1
sin(πx)        0.3   0.9   1.9       2.9    4.4
exp(-3x²)      0.3   0.7   3.5       2.4    5.0

So substitution doesn’t only improve the result “for some oscillatory functions” as claimed in the manual: it gives a solid improvement everywhere! The effect is stunning for the “quarter circle” function: this is exactly what the advanced function handbook predicted. You can see this because the samples near the end nicely follow the function:

In the table you see it doesn’t work for the function sin(25x²) sampled at 15 points. This is easy to explain with a picture:

Conclusion

The integration function of the HP-15C is amazing: I already knew that. Now I finally have a solid understanding of why it is designed the way it is. It clearly is absolutely necessary to do non-uniform sampling it is an essential part of the integration process. This is also exemplified by most modern algorithms for integration, which all use non-uniform sampling. The choice for the sampling function allowed them to use a clever algorithm for computing the iterations.

There’s only one thing I would like to know: how does the calculator compute it error estimate? If you know, drop me a line!

Some extra findings during the quest

• One frequently used modern numerical integration method uses a very simple sampling function, that is described in completely unreadable terminology. They talk about “the extreme values of the Chebyshev polynomial”, while they just mean regular points around a semicircle, dropped down onto the x-axis.

• The sampling function used by the HP-15C is (3x-x³)/2. I tried to find its inverse with Wolfram Alpha, and it gave me this unusable expression:

• This expression useless, because all the square and cube roots involve complex numbers, giving you multiple solutions: 36 combinations, three of which are real, and only one the one I need. Instead, it should have told me that for real numbers, the inverse is just 2sin(asin(x)/3).
  I could not find a way for Wolfram Alpha to confirm this, so I used the good old pencil and paper method.
  And then, with this inverse function in hand, I could check that the sampling points where indeed as claimed by the advanced functions handbook.
• A very disturbing thing I found was that Excel and Google spreadsheets think that -3² is 9. To be precise, it always applies the minus before the square! I discovered this in the middle of a computation, and it took be a long time to realize that the problem is that the spreadsheets break a simple basic assumption of mathematics, in contrast to every programming language I know.
• And finally, here is the listing for the great program for the HP42 that does the integration for you, only slightly modified from the PPC version. Inputs: name of function in alpha register, lower and upper bound in Y and X. Set flag 10 if you want to see intermediate results.

00 { 159-Byte Prgm }
01▸LBL "Romberg"
02 ASTO "FN"
03 STO 17
04 X<>Y
05 -
06 4
07 ÷
08 STO 16
09 STO- 17
10 STO- 17
11 CLX
12 STO 15
13 STO 11
14 STO 18
15 SF 09
16▸LBL 01
17 1
18 ENTER
19 2
20 STO 14
21 RCL 11
22 +/-
23 Y↑X
24 STO× 14
25 1
26 -
27▸LBL 02
28 STO 12
29 X↑2
30 -
31 STO 13
32 2
33 +
34 RCL× 12
35 RCL× 16
36 RCL+ 17
37 XEQ IND "FN"
38 RCL× 13
39 STO+ 15
40 1
41 RCL 12
42 RCL+ 14
43 X<Y?
44 GTO 02
45 RCL 11
46 STO 13
47 18
48 STO 12
49 1
50 STO+ 11
51 RCL 15
52 RCL 16
53 1,5
54 ×
55 ×
56 RCL× 14
57▸LBL 03
58 R↑
59 4
60 ×
61 ENTER
62 DSE ST Y
63 X<> ST Z
64 ENTER
65 X<> IND 12
66 STO- ST Y
67 RND
68 X<> ST Z
69 ÷
70 RCL+ IND 12
71 ISG 12
72 STOP
73 DSE 13
74 GTO 03
75 STO IND 12
76 NN→S
77 FS? 10
78 XVIEW
79 CLX
80 LASTX
81 FS? 10
82 PSE
83 FS?C 09
84 GTO 01
85 RND
86 X≠Y?
87 GTO 01
88 LASTX
89 RTN

When you are in a waiting line, you have plenty of time to think. My thoughts wandered to the question what kind of patterns you could make with these poles. Could you make a maze, for example?

After a bit of thought I found out that the answer is yes. Even stronger, you can make any maze that fits in the grid! (For some reasonable meaning of the word maze, at least.)

So we are going to talk about mazes today. I’ll restrict myself to the mazes you can draw on the lines of a piece of graphing paper (or, as I will show, from airport barriers), with one entry, one exit, and one possible path between the two. Here are two examples, using my advanced “ballpoint pen on graph paper” technology:

Around 1974, when I was ten years old, I spent days on end drawing mazes on graphing paper together with a friend of mine (hi Geert!). When ready, we swapped papers and solved each other’s mazes.

Then the computer came (for me, that was somewhere around 1980). One of the first computer programs I ever wrote generated mazes consisting of +, - and | characters on screen. I was so lucky to get access a cool Philips P860 minicomputer, and programmed it in BASIC. In these days, I was carrying a cigar box with punched tapes with my programs on them. This is approximately what a program looked like:

I found the original program in a magazine (yes, in these times code was published on paper!) and quickly realized the program wasn’t very good, so I started fiddling with it. I had access to a flatbed plotter: probably the most satisfying way to output a maze. Also it was interesting (and hard!) to try to optimize the number of pen movements to draw the maze.

That was the start of a years long search for a better program to generate mazes.

A few years later, maze generators became popular, and you saw them everywhere. Some examples from that era:

• David Matuszek wrote an article on maze generation in BYTE magazine of December 1981.
• The XscreenSaver maze generator that I always used on my Sun Sparcstation 4 (back in 1990 this was considered a pretty cool computer):

• The “3D” maze displaying screen saver of Windows 95.
• This beautiful program from the “obfuscated C code contest”, that prints unlimited length mazes, with a finite amount of memory:

• The “origin shift” maze generator that is used in a Minecraft maze. This algorithm modifies an existing maze, and manages to continuously modifiy the maze with you in it.
• And during research for writing this article, I found that Wikipedia addresses many maze generation algorithms, but it is incomplete (at least until someone puts the algorithm below in it).
• Today, there is a maze generation web site that generates all kinds and shapes of mazes for you. There is no information on the generation algorithm, however.

The “wall maze”

Let’s do some maze mathematics. If you look at the walls of the maze, and interpret them as paths, you will notice that they are just like a maze themselves. If your original maze has one entry, one exit, and no loops, the walls will form two mazes, that are separated by the solution path of the maze. For example:

I the terms of mathematics, the maze is a tree graph, and the walls form two tree graphs themselves.

Proof that you can make any maze in the airport

With the property that the walls of a maze make two trees, there is an easy way to show that you can make a maze out of airport barriers.

For each of the two walls, pick one of the poles in the piece as a “starting pole”, marked with S in the picture below. Then, for every other pole, you extend a ribbon in the direction of the starting pole. This will always work, since in a tree there is a unique path towards the starting point.

Making a maze into another maze

If you connect the two wall tree graphs, there is no path anymore in the original maze, but it gives you a new maze from the walls. This suggest a way to make a new maze out of an old one.

First, you shift the maze, so that the corner points are in the middle of the squares on you graph paper. Make an extra connection (dotted in this picture):

Then, you carefully draw lines where two boxes are not separated by lines. I added two openings for the new entry and exit. Note that the dotted line for the extra connection now turns sideways:

The final result, a slightly bigger maze:

If you look a the wall mazes of this new maze, they look a lot like the original maze we started from (with a few extra lines, of course). Therefore, the wall mazes could be called the “dual maze”. In math, the term “dual” stands for “something that goes back to the original if you do it twice”. It is well known that the walls form a maze by themselves, but I could not find the concept of a “dual maze” in the math literature (contact me if you find a paper about this, please). I would be interested to see if there are more interesting properties on dual mazes.

By the way, this dual maze different from the dual of a planar graph: since a maze is also a planar graph, you could apply this to a maze, but it results in a graph that is not a maze of any kind.

Generating mazes in any order

Generating mazes is more fun than solving them, even on paper. The maze drawing algorithms I showed above all first generate a maze, and then draw it. The exception is the obfuscated C version, which used a variant of the algorith I will describe now. This algorithm allows you to draw a maze in any order, without having to regret earlier decisions.

The algorithm below applies to many different kinds of mazes, but let’s start simple. Take a blank sheet of drawing paper (or an array in computer memory). Start with the outside of the maze, with two openings for entry and exit.

Now you look at the line piece on the graphing paper (between two crossings). Each line piece on the paper has to become a wall or an opening. When you draw the maze, you have to make a decision for each line piece. In many cases, only one of the choices is allowed because the maze would become invalid otherwise:

• If the two ends of the line piece are already connected by walls, you’re not allowed to put a wall this would create an “island” in the maze that cannot be reached.
• If the two cells on either end of the line piece are already connected by a path in the maze, you have to put a wall because otherwise you would create a loop in the maze.
• In other cases, you have free choice, but you have to remember what you did. That means, if you decide not to draw a wall, you have to remember that there is a path between the two sides now.

In the beginning of drawing process, there aren’t many walls or paths, so there is plenty of choice. But later, partial paths and wall are beginning to appear, and you must be careful to make the right decision. The means that during the drawing process, you need to have a quick way to find out if there is a wall path between two points or path between two cells. Let’s just assume for the moment that we can do this easily and quickly.

That would suggest the following program:

# get all potential walls, that we call openings
openings = list(enumerate_openings())
# choose a pretty drawing order
openings.sort(key=interesting_order)
for location in openings:
    # make the right decision
    if must_be_wall(location):
        is_wall = True
    elif must_be_open(location):
        is_wall = False
    else:
        is_wall = random() < 0.5
    # draw a wall or opening at this location
    draw(location, is_wall)

This outline makes use of the following functions:

• enumerate_openings(): generate all places where a wall or an opening could be. For our easy graph paper case, this is an easy function that describes the horizontal and vertical lines in the grid.
• interesting_order(): a function that determines the order of drawing. You can vary this to generate the maze in any interesting order (I really like to draw my mazed from the middle outwards, for example).
• must_be_wall(): determine if there is a path between the two sides of the opening.
• must_be_open(): determine if there is a wall connecting the endpoints of the opening.

The two functions must_be_wall() and must_be_open() are the clever parts of the algorithm. And (some readers may have seen this coming!) here’s where the duality of mazes comes in: they are essentially the same function! I’ll describe the must_be_open() function first.

Let’s have a good look at what it is supposed to do:

• At the beginning, all corner points disconnected, except for the outside boundary, where there are two paths (the “right” and “left” halves of the outside wall).
• When a wall is created, the groups of walls on either end of the opening become connected.
• The function must_be_open() has to detect if the wall on either end are in the same group.

The function must_be_wall() does the same thing, but then for cells instead of corners. And the initialization is easier, because nothing is connected at the start.

These functions depend on a so called disjoint set data structure. This thing is known since 1964 (that makes it the same age as myself, maybe that’s why I like it so much). There are surprisingly many different ways to make such a data structure, and most of them are pretty efficient. The study of implementing these pretty interesting by itself; the Wikipedia link above gives a decent overview of you are interested.

Drawing a maze

Now we come to the reason this column is delayed so much. I promised to write it months ago. I decided to make a Python program that draws makes in all kinds of shapes and forms, in many different orders, and public that with the article.

Apparently, my English is better than my Python, because I kept getting stuck on many silly errors. The basic program is ready, but there are so many problems with it that I don’t dare to show it to you guys.

If you are a reader of this and like to see my partial program, or even like to help me update it, just react; I am looking forward to the cooperation. I might just publish the half finished program and let you guys have fun with it. Personally, I am just frustrated that the layout isn’t perfect and that the drawing and solving function don’t work properly for all different mazes.

But the real fun of the program for me is the idea that the wall and paths are using the same data structure, and that is the beauty of looking at mazes from a mathematical point of view.

A bit of security history and a bit of related fun math

Let me show you how naive decisions by programmers in the ’70s influenced the security of all our bank accounts. Originally, I wasn’t allowed to talk about it, but today information is public, so I can share it with you. After explaining the issue, I’ll describe a few algorithms that could have solved the problem, including a particularly beautiful one. The connection between those subjects is that both came up during my work on the new ISO 9564–5 standard under development.

Let’s start at the beginning. In the 1970s, your PIN was solely used to get cash money out of a machine, that you then used to pay your groceries. These machines are called ATMs (Automated Teller Machines). You insert your bank card and enter you Personal Identification Number (PIN). This is of course a misnomer, since the number is used for authentication, not identification: the card does the identification. When you enter the right value, the money becomes available to you instantly. It felt amazing at the time. Note that Point-of-Sale (PoS) devices came later.

Of course, the system was designed with security in mind. If a machine gives cash to people, there are always others willing to try if they can get cash for free. Clearly, the one important aspect was to prevent PINs against eavesdropping. The main dangers envisioned when designing this system were:

• someone looking over your shoulder when typing;
• bank employees providing your PIN and then could abuse it later;
• hackers reading the magnetic stripe on the card to figure out how the PIN was encoded.

Famously, shortly after the first ATMs were installed in the 80’s, a journalist showed on Dutch television that cards could be copied onto some video tape stuck on a piece of cardboard, and then used to withdraw money. (I couldn’t find a reference to this video in the archives; contact me if you find one!)

The banks were right in their reaction: they emphasized that you should protect your PIN, and if you did that, they would take care of the rest. And that is still true: it is still pretty hard to steal money if all you have is a magnetic stripe bank card (unless the merchant accepts signature payments, and yes, these still exist).

A few years later, the Dutch Hack-Tic even jokingly provided a service to copy bank cards (in Dutch). Don’t worry: today’s chip-based systems do not allow attacks like this anymore.

Back when I was in college, not yet a cryptographer, I wondered how the PIN codes were stored. Today I can explain it. The Dutch bank cards at the time used a clever system with the following intriguing security properties:

• There was no way to recover the PIN, even if you could read the magnetic data on the card;
• for verification of the PIN, a cryptographic key was needed that was only available to the card issuer;
• even with this key, the information stored at the bank’s systems was insufficient to get the PIN value, because the magnetic stripe was also needed.

This method is called the offset method (or IBM 3624), after the first IBM ATMs that used it. Simplified, PIN verification worked as follows:

• If you entered your PIN on the ATM, it was encrypted and sent to the issuer along with the magnetic stripe value.
• The issuer performed a cryptographic calculation using values from the magnetic stripe such as account number and expiry date.
• This value was converted into a four digit “intermediate PIN”: that’s what this whole article is about.
• The four digit “offset” value from the magnetic strip was added to this value giving is the “reference” PIN.
• The value you entered is decrypted at the issuer and compared with the reference PIN to see if you entered the correct value.

All PIN calculations on the issuer side were done inside an Hardware Security Module (HSM). This made sure the actual PIN was not visible to anyone, even staff. It was pretty secure.

In the picture below, triple DES is used. In the 80’s, the era of 8 bit microprocessors, that was secure enough. For a comparison of 56-bit DES versus 112-bit triple DES, see my previous article.

PIN change

Originally, your PIN was assigned by the bank. Because it is much easier to remember your PIN if you picked it yourself, it later became possible to change your PIN. The offset system allows for that as follows:

• You go to your ATM, and enter your new PIN (after entering your old PIN for authentication of course);
• the bank’s computer would compute a new offset to match the new PIN;
• the ATM would update the magnetic stripe with the new offset.

Again, the offset value would not be stored on the bank’s computers, so that the above security properties still hold.

Even today, it is unclear if self selected PINs improve security. Sure, people don’t write their PIN on their card anymore, but on the other hand they tend to select pretty easy to guess PINs, as shown in this beautiful article.

Decimalization: the weak point of the system

Back to the main point of my story. In the above picture there’s a box called “digit replacement”. Its input is an encrypted block (64 binary bits) and its output is a “intermediate PIN” of four digits. Unfortunately, the following algorithm was used for that:

• Take the first 16 bits of the cryptographic number.
• Interpret these as four digits in hexadecimal (seen as values from 0 to 15).
• Look each digit up in the “decimalization table”.
• This was the value added to the offset.

In most cases, the decimalization table was as follows:

That doesn’t sound so terrible, does it? Well, the problem is that the digits 0 through 5 occur twice as often as the digits 6 through 9. This means that the intermediate PIN was more likely to have the lower digits. The mathematical term for this is “bias”.

Later they tried random, secret decimalization tables, in an attempt to hide the bias, but it was almost never used because of implementation problems. So the “random, secret table” was still the table shown above.

This bias makes your PIN easier to guess. A thief that stole your card could get the offset from the magnetic stripe. Thanks to the bias in the intermediate PIN, he would have an advantage guessing the PIN. In effect, it was as if there fewer than the 10000 values to guess from.

It gets worse. The networks weren’t as reliable in these days, so the network that routed from the ATMs to the banks was able to do “stand-in”: if the bank’s computer didn’t respond quickly enough, the network would do it in the bank’s place. The network didn’t have the bank’s keys, but had three keys of its own: the “pool keys”. For each of these pool keys, the offset was also stored in the magnetic stripe! Each of these four offsets leaked some information about the PIN. Together, the PIN could be guess with much more chance than designed.

All this got published in an article with the title “the unbearable lightness of PIN cracking”, which had quite an impact.
The Dutch banks reacted instantly, removing the pool key offsets from the bank cards. It was a fun project to work on; we managed to do the change before someone realized the attack from the article also applied in the Netherlands. Since the original offset was still on the card, the problem was still there, but the danger was reduced a lot.

The real problem is that using a decimalization table is a terrible way to make a four digit value from a binary block. Even though there is no offset on the magnetic stripe anymore, decimalization still works this way, alas.

What happened to the offset

If you are interested in how to fix the mathematical problem of making random decimal values from binary data, skip this section and read on below. If you want to know how the story ends, read on, but I’ll be a bit vague because there are still some company secrets around this process.

As usual, history progresses in unexpected ways. It was discovered that the magnetic stripes were easily erased by accidentally holding your purse close to a magnet. That meant that your suddenly couldn’t get to your money anymore. This was fixed using “high coercivity” magnetic stripes that were much sturdier. As a result, it was much harder for ATMs to change the offset on the magnetic stripe, so that changing PIN went wrong frequently! This was then solved by keeping the offset in the issuer’s system. Unfortunately, that defeats one of the design principles of the offset system, but to my surprise, nobody appeared to worry about that. The issuers even didn’t bother to encrypt the values in their systems “because they weren’t encrypted on the card as well”.

Other PIN verification systems are also in use. One of the systems stores the PIN itself at the issuer side (in encrypted form, of course) and compares that against the value typed in by the customer. I don’t really like this method because it relies a lot more on the way the HSMs are used, making design mistakes more likely. Another system stores a PIN Verification Value on the magnetic stripe, instead of the offset. It’s security properties are comparable to the offset method.

Today the magnetic stripes are used almost nowhere, and replaced by the much more secure chip cards. The chips on these cards encrypt the relevant data, so doesn’t help to steal information. It took some iterations to get to this point, probably because business features where chosen above security functions. This is all explained in glorious detail here.

A beautiful algorithm for decimalization

Back to the math aspect of decimalization and bias. This part may be too academic to your liking; in this case feel free to read some of my less mathematical ramblings. We are talking more about nice algorithms than about banking here.

Let’s zoom in on the question: how do I convert a 64 bits binary random value into a few decimal digits, with as little bias as possible? This is a pure math puzzle. We emphasize ways that could have worked on the early microprocessors in the 80’s, like the Ordinator that I built and programmed with some friends in the time.

Mathematically, the bias is the variability in probabilities of the decimalized values if you start with a random binary value. The table above converted 4 bits values to a digit, where 0 through 5 had a probability of 12.5% and 6 through 7 had 6.25%. For a 4 digit PIN, you got the following combined probabilities:

This table shows the probability of each PIN value, the number of PINs with that combination of digits, and the combined probability so you can check that it adds up. The probabilities are wildly different: 1234 occurs 16 times as often as 6789, for example. In the ideal case, all probabilities are exactly 0,010%, by the way.

Unfortunately, it is not possible to create perfectly unbiased decimal numbers from a random binary number, but we can get close. A very simple way to create better probabilities is to take these 16 bits, treat them as a number from 0 to 65535, and take the last four digits. Now the probabilities vary between 0,0091% and 0,0107%: much closer but not perfect. Another problem is that this method requires a division by 10000, which is almost impossible for an 8 bit processor that cannot even multiply two digit numbers.

The original method used just the first 16 of the 64 bit block. To further reduce bias, we need to use more of the bits. A much better way to generate random decimal digits is sometimes called “ANSI-Scan”:

• treat the whole 64 bits block as 16 hexadecimal characters (0–9 and A-F);
• take the first four that happen to be digits, skipping A through F;
• in the (unlikely) case there aren’t enough digits in the block, convert the letters into digits (for example, A to 0, B to 1, etc). Use these letters to produce the remaining digits.

This method, which is quite simple to do, has negligible bias, (unless you want many more than four digits. The probabilities will be 0,0100% for all number. In the new 9564–5 standard, this method is applied to 128 bit blocks, giving even less bias. It allows to generate up to 10 digits with almost no bias.

The pretty method

But there is a much more beautiful method that I want to show you. It can generate more digits from the 64 available bits with less bias. It came up in the standardization committee discussions about ISO 9564–5, but it’s not in the standard. Since I think it deserves to be published, I’ll do it here.

Instead of interpreting the block as hexadecimal digits, this algorithm looks at the individual bits. Each bit can be seen as a random coin flip (where the coin has a 0 on one side and a 1 on the other).

During the calculation, a random number is remembered; the range of this number varies, but it is always bias free in this range. The number is called rsn, the “random source number”, and its range is from 0 to m, inclusive. All values from 0 to m are equally likely during every step of the algorithm:

• Start with rsn equal to zero, and the maximum value is 0 of course.
• For every decimal digit that you need to produce, check if your maximum is at least 9. If it isn’t, do a “doubling step” as follows: get a new random bit b, set rsn to 2*rsn+b and set the maximum value to 2*maximum‒1.
• After a few doubling steps, the maximum will be 9 or more.
• Now if rsn is somewhere from 0 to 9, you can output this as bias free random digit and start over for the next value.
• Otherwise, rsn is 10 or more. We don’t just throw the number away, but keep the bias free randomness (in the range 10 through m). Subtract 10 from rsn and from the maximum; now rsn is again a bias-free number in the proper range. You go to the second step to do one or more doublings again for the next digit.

Or, If you like pseudocode:

rsn, m = 0, 0
repeat:
   while m < 9:
      rsn := rsn * 2 + next_random_bit
      m := m * 2 + 1
   if rsn < 10:
      return rsn
   else:
      rsn := rsm - 10
      m := m - 10

In the form I first saw the algorithm, the line rsn := rsn — 10 was replaced by the bizarre calculation rsn = rsn ^ m (yes, that’s an exclusive OR). It took me several days to figure out that this worked as well. However, the algorithm is much clearer with subtraction.

Here an example run of the algorithm:

Random bit  rsn   max  Comment
            0     0    Start
1           1     1
0           2     3
1           5     7    add bits until max >= 9
1          11    15    Too big; reuse values 10-15 as 0-5 by subtracting 10
            1     5
0           3    11    Output -> 3
            1     0    Start over
0           0     1
1           1     3
1           3     7
0           6    15    In range: Output -> 6

The method produces perfectly bias free random decimal digits, using up a variable number of bits (4 to 8 in most cases). With 64 bits, you can produce 8 digits without running out of bits with a probability of 99.9998%. And in the extreme case that you do run out of bits, you can just add zeroes at the end, with negligible effect to the bias.

The following table shows how many digits are produced from 64 bits. If you don’t mind a few users having a PIN ending in a some zeroes, you can go to 10 digits, still with very good bias.

Using 64 bits.

At least 12 digits:  97.2544% of the time
At least 11 digits:  99.6125% of the time
At least 10 digits:  99.9597% of the time
At least  9 digits:  99.9969% of the time
At least  8 digits:  99.9998% of the time
At least  7 digits: 100.0000% of the time

The algorithm is easy to write, easy to prove to be bias free and used only values under 20 that fit in 8 bits. No divisions are needed, nor hard multiplications, so it is perfect for a small microprocessor.

If you want, you can modify it for other number bases, like dice rolls.

If you are seriously implementing the algorithm, I recommend to use m+1 as a variable; this will simplify the code a lot.

But alas, this beautiful algorithm may be obsolete already since our current 64 bit processors can do divisions with ease. However, if you like nice and obsolete ideas, I wrote two earlier blogs on these:

• An inventive solution to a centuries old problem
• Another brilliant solution to an obsolete problem

On 2 and 3 December 2025, there was a big conference on Post Quantum Cryptography. (Here’s the aftermovie from TNO.) I was there.

I learnt many new things on this conference, more than I expected. Here’s a quick summary:

• PQC is a transition process that is important for every company, and coordination is needed within and between countries. If we restrict ourselves to goverment level advice, there is a European roadmap, UK roadmap, ANSSI roadmap, 17 country roadmap, the PQC handbook, the NIS roadmap, the Canada roadmap, the CISA roadmap, the GSA roadmap, the Australian roadmap, and this may be a bit too much.
• Development of new PQC algorithms and quantum computer algorithms is specialist work that provides input in this process, but it’s not the hard part.
• And I learnt, completely outside the subject of cryptography or quantum computers, about formal methods that can increase the quality of any kind of software that is important to you.

Organization and scope

From the organizing parties, you could already see that there was more at stake than mathematics — it was about data security. The real concern is the security of our infrastructure. The consortium organizing the conference:

• ANSSI (the French Cybersecurity Agency)
• BSI (the German Federal Office for Information Security)
• MinBZK (the Ministry of the Interior & Kingdom Relations of The Netherlands)
• CWI (National Research Institute for Mathematics and Computer Science in The Netherlands)
• TNO (Netherlands Organization for Applied Scientific Research)

Why another conference?

Honestly, I wasn’t sure what this conference was for. There was an earlier conference on the subject, where the second edition of the PQC handbook was published. Here’s my report. This handbook is still relevant, and if you didn’t have a look at it, you can read it here. The message is clear: you have to do something if you are a company.

When I was there, I realized the real goal of the conference was much bigger: this has to be taken up to a higher level. There were a lot of people, from all over the world. Everybody wanted to make sure we are all aligned on what to do now, both nationally and internationally. One reason this needs to be aligned is to make sure work isn’t repeated: there are already quite a few documents on quantum computers and on the PQC algorithms, and it is important to coordinate. Another important reason is to standardize solutions.

The British delegation summarized it nicely: “the biggest problem with PQC is that it has to be solved in about 10 years, which is longer than a government period”. And that’s why it is important that everybody involved is aware of the transition.

Of course, this process can be seen as part of the European DORA regulations (for financial industries) and NIS2 regulation (for everyone) that expect you to be up to date with your cryptography.

What I learned about PQC

As a mathematician, I see PQC as a very interesting research area. I even contributed a bit myself in the development of HQC. But for a company, it is a transition process. If you are in a company, you should ask yourself if your company is already busy with PQC. If the answer is no, I would recommend the following “simple model” as described by Anita Wehmann, from MinBZK, with her permission:

What I liked so much about this picture is that it clearly shows that for most people, it is not at all about the technical details. For me as a cryptography nerd, that was very refreshing.

In order to get to the end of the process, the most important thing to do is to make someone responsible for the PQC transition. This person could start by reading the PQC handbook. This handbook recommends a risk based approach, where you start with mitigating the high risks, and work your way through until you reach a point where you’re satisfied with the level of risk. Here’s a picture from the handbook:

What I learned about the quantum computer

I came in the conference with a negative attitude, I have to admit. I am not at all convinced that there will be quantum computers within the next 30 years. That might be because these machines are too expensive to be worth the cost. But it maybe even because there is a physical reason why they are impossible to build. I am not alone in this, see for example Gil Kalai, Peter Gutmann and Stephan Neuhaus. And then there are articles by EMV on breaking 2048 bit RSA and ETSI on breaking symmetric cryptography that argue it is going to take a very long time before quantum computers become a threat for current cryptography.

My opinions on the matter didn’t stop me from going to the conference, however: I know how important it is to listen to people who disagree with you. And I wasn’t disappointed.

To my surprise I found that the question if and when there will be a quantum computer is almost irrelevant. The question wasn’t mentioned at all (at least in the lectures that I attended). The point is that the cryptography we need to protect our assets is trustable. And in order to be trustable, it has to be protected against any kind of attack, realistic or not. So we need PQC because of the quantum computer threat, not the quantum computer itself.

There weren’t many details about the status of quantum computer research. In a way, it was out of scope of the conference. If you want to know about the status, I wish you luck. The problem is that most publications on this subject are more hype than news.

Surprising QKD posture

I have written before on Quantum Key Distribution: it is a way to share a common cryptographic key between two parties. This key can then be used to do secure communication. The security depends on physics, not mathematics, which means it is unbreakable regardless of how powerful you computer is.

Cryptographers agree that QKD is an expensive way to solve a very simple problem: when you clicked on a link to read this article, your phone or computer exchanged a key with the Medium server. This was very secure and took only a fraction of a second. QKD can do this too, but only for small networks and at the cost of an expensive box containing specialized hardware that can generate extremely short pulses of light (because single photons cannot be produced). For big networks, you need a trusted network switch.

When asked about their posture on QKD, two parties did not immediately dismiss the idea, because they actually had experience:

• Singapore said that “they could implement QKD for key exchange because there are small enough”. This addressed the problem of scalability.
• Korea said that they had extensive experience because they already used it for about a decade, and concluded that it was too expensive, except maybe for specialized applications.

You may disagree with me, but I think this is underlines that QKD is not worth the effort: not only in theory, but also in practice.

Formally verified implementations

The most interesting presentations I heard were about how new protocols are designed. In the last decade, big changes have happened in the design of cryptographic protocols.

The process of designing a protocol is summarized by the following picture of the implementation process:

Originally, up until a decade or so ago, cryptographers wrote the design of the protocol. They worked really hard to make sure it couldn’t be broken. This is quite hard, because it is hard to find things have have overlooked in the design. And indeed for many protocols, attacks were discovered after a specification was published. But the problems don’t end there. Mistakes are possible in each steps of the process. Especially recently, many protocols are broken because the implementation leaked information about the keys via so called “side channel attacks”. To make things worse, even perfectly fine code with built-in protection against side channel attacks can be converted into code with weaknesses by the compiler’s optimizations.

As protocol specifications grow more complex, this problem is getting larger. Fortunately, there is a solution: make a mathematical proof that the binary implements the specification exactly. This sounds hard, and it is. But today the tools exists that can help you do this. Two examples I saw are the protocols for TLS 1.3 and Signal: the implementation you use on your device has probably been proven as secure as designed!

Cryptographers already know it: you cannot publish a cryptographic protocol unless you can prove you have a secure implementation. And indeed, all new PQC protocols have this.

But there are more specifications than cryptographic ones. If you are old enough, you may remember that Windows before Windows 7 could just crash without any obvious cause. Most of these were caused by bugs in driver software. For Windows 7, Microsoft started systematically using formal methods on their drivers to prove that they didn’t crash. And indeed, today random crashes are much less frequent.

Of course, with formal methods you can do more than prove your driver doesn’t crash. And with modern tools, this is no longer so hard. So a thought entered my brain that refuses to leave: this must be done with all code that you want to be correct. And indeed, for example Siemens already wrote about this in their blog.

So, completely out of scope of this conference, I learned that the future of code design lies in formally verifying you’re doing things right, and that bug-free code is achievable.

Watching the training I could not stop thinking of energy wasting practices in my area of expertise: cryptography. It it is not getting better; quite the contrary, in fact. Let me show a few ways in which cryptography is very wasteful, but before I do that, let’s help your intuition a bit.

Arjen Lenstra was so friendly to convert several levels of security into energy use, which was an important source for this article. The $30 figure comes from crack.sh, which breaks DES for $30 per key. The money amounts of a million, billion and trillion are mine. Note that all these numbers are inaccurate; you use more that $30 of electricity per year, probably.

Things to note from this picture:

• Keys longer than 128 bits make no sense at all. Keys over 100 bits can be considered “unbreakable” against any attack, even state actors. If the NSA builds a Dyson sphere around the sun, you may want to use a few bits more.
• Not shown are hash functions and elliptic curve security strength. As a rule of thumb, you can double the “bits of security” for these. This means SHA256 is secure enough, as is Curve25519.
• Keys of 90 bits are enough for personal and small business applications, since it is just not worth breaking them.
• PIN security is much stronger than expected; this is because of additional security measures around PIN entry.
• The RSA numbers in this picture are probably too low. Otherwise the 862 bit RSA challenge would have been broken already by now.
• Moore’s law moves the “bits of security” points slowly down relative to the cost and energy numbers. This corresponds to about one bit every 1½ to 2 year.

How secure should my cryptosystem be?

If you are the user or designer of a cryptosystem, there are a few factors to take into account. Of the factors shown here, the first two argue to use less bits of security, while the last one argues to use more.

• Cost of implementing the system, which should be affordable.
• Environmental impact (energy use, pollution, etc.).
• Cost of attacking the system, which should be more than the expected “benefits” for the attacker.
• Compliancy with regulations.

I am talking about the entire cryptosystem, including the encryption method used inside this system. As I will show below, in most systems the encryption method is not the weak point.

Reasons for choosing longer keys

When studying cryptographic methods that are used in practice, I noticed a trend to use overly long keys. For example, nobody dares to use an RSA 1024 bit key for anything. Still, I would be happy to use RSA-1024 for protecting all my possessions, since I do not own anything that is worth so much that an attacker would be interested.

There are several reasons to choose a cryptographic method that is stronger than needed:

• For long term security, you have to take into account that systems with short keys will be broken.
  Since the GNFS factoring method was invented around 2000, many people were afraid this would happen to RSA. That’s why RSA is perceived to be weaker that it is in practice. But RSA-1024 still is not broken, even though GNFS has been improving steadily since then.
• Using a stronger encryption method is cheap. Using AES-256 is almost the same as using AES-128, except your key is 32 bytes instead of 16 bytes, and computation is 40% more work. But as you can see in the picture, you do not gain any extra security.
  By the way, using very long RSA keys is not that cheap; 3000 bits RSA is about 25 times as much work as 1000 bits.
• Compliancy rules force parties to choose encryption methods. For example, ETSI TS 119 312 and the SOG-IS Agreed Cryptographic Mechanisms specify that we must use at least 3000 bits RSA.
• Marketing. Every since DES was replaced by triple DES (with twice the key length) there is a feeling that key sizes need to be doubled for extra security.
• Related to that point: perceived security (because people don’t want to use a system they don’t trust).

Note that even though these are valid reasons for choosing a long key, there is no use to choose key lengths that fall of the scale of the picture. No attacker, whatever their capacity, is going to break 2048 bits RSA or AES-128; there aren’t enough resources on earth to do this.

But I heard that <some reference> is broken recently!

Yes, cryptosystems get broken. But believe me, this is not because the encryption system inside is broken. The only exceptions to this rule is if the encryption system is used in the wrong way. That’s why cryptography is so hard.

If you really look into the details of an attacked system, you’ll find that the attack used well know weak points that are not cryptography:

• Human mistakes, where users of the system don’t understand the result of their actions
• Social engineering, where users of the system are manipulated by attackers
• Design flaws in the system
• Attacks on the operating system or software application

I don’t thinks references are needed here, there are plenty of examples of each of these.

Bad reasons for choosing long keys

The reasons for choosing longer keys that I listed above are not always good reasons, but there are also really bad reasons for choosing long keys. Here a few.

• Homebrew encryption. Some parties invent their own encryption system that uses very long keys. You can safely assume these are not secure, or at least not more secure than a well designed system with short keys.
• Misunderstanding systems. For example, HMAC is a “Message Authentication Code” that uses an underlying hash function. But that hash function is used in a way that does not depend on the so called “collision property” which means that you don’t need a full strength function like SHA-256. In fact, HMAC SHA-128 is perfectly secure, and even HMAC MD5 is unbreakable, even today, because it has a security level of 160 bits.
• Forgetting about context. For example, in the payment industry, payment transactions are valid for about a month; after that, there is no way to revert the payment. This means that almost all payments could be protected with a 3DES key, without any risk.
• Quantum computer scare. Publications have claimed that you would need to double the key length of your encryption to protect against quantum threats. This is almost certainly not true, as this ETSI report explains.
  Additionally, breaking RSA on a quantum computer is also still pretty far away, as EMV seems to agree, but that’s not the point of this article.

More wasteful cryptography

As if using long keys wasn’t bad enough, there are more ways in which cryptography is wasteful.

Key rotation is the requirement to change you keys regularly. The idea behind key rotation is that if someone somehow finds your key, they can only use it during the period you use the key. Historically, this made sense: if the Germans didn’t change their Enigma keys every day, the war would have been a lot shorter.
Another related point is the laughable way in which passwords were protected (and sometimes still are). This allowed attackers to find many passwords in a matter of days. Forcing users to change their (long) passwords frequently doesn’t solve the problem; what you need is better password protection. If you don’t believe me, explain why your PIN is still secure, even though is it weaker than a weak password and rarely changes.

But today, every way in which you can find a key (by using side channel attacks, for example), finds the key in a few hours at most, often much faster than that. There is no amount of key rotation that is going to help against these attacks. In my career of about four decades in cryptography, I have not heard of a key that was compromised as a result of a cryptographic attack (not counting systematic attacks and errors, of course).

To be fair, there is a surprising reason to require key rotation: familiarity. As I said, key compromise is very unlikely, but possible. And if it happens, you need to be ready to change your keys immediately. So if you practice doing key changes regularly, this helps. Key rotation can play a role here.

Encryption uncompressed data is another way to waste resources. Encrypted data is completely random (by definition; if it isn’t, you are certainly using the wrong encryption). So if your data can be compressed, do it before you encrypt it, otherwise it is too late.

(Side note: the “compressible encryption” that Microsoft Outlook used until a few years ago for email storage was the laughing stock of cryptographers.)

HMAC key length

The strength of HMAC depends on the underlying hash function. In effect, HMAC is as secure as the full length of the hash function, not half of it as it is in the general case. The recommended length of HMAC keys is explained in a NIST document SP800–107r1. This document explains that SHA-1 is completely fine to use with HMAC. It also contains the phrase “In general, there is no benefit in generating K [key length] with more than 2C [twice the size of the hash] bits of security.”

Many, if not most application don’t dare to use SHA-1, because it is “broken”, so they use HMAC-SHA256. Furthermore, they conclude frrom the citation that the must choose the key length to be twice the hash size. The result is that many applications now use an HMAC with a 512 bits key “just to be safe”. Even if we could convert all of the matter in the universe to energy (with E=MC², remember?), you can just barely break HMAC with a key of 256 bits, so I think it is safe to call this “overkill”.

(If you have more examples, let me know; I may add them.)

Can this be fixed?

I would really like to contribute to reducing wasting of resources. Unfortunately, much of the damage has already been done:

• The Bitcoin network, which has an unbelievable energy use and managed to make a few people very rich at the cost of everyone else, cannot be stopped as long as there are people interested.
• News stories about “broken encryption” keep giving the wrong impression. For example the attack on the Thai smart cards in combination with the later attack on Latvia cards, both caused by bad prime random number generators, reduced trust in RSA because the news said that RSA keys were broken.
• Mark Stevens invented the concept of counter-cryptanalysis: this method allows to detect attempts to cause a collision of SHA-1 by just looking at one of the two messages in the collision. You can do this while calculating the hash value, effectively making SHA-1 secure again with a strength of 160 bits.
  Unfortunately, SHA-1 did not survive the scare caused by the false CA certificate attack of MD5 and the later SHA-1 collision. And, as Mark told me himself, almost everywhere where SHA1 is used today, counter-cryptanalysis is already implemented!
• Institutions are not likely to reduce their compliancy requirements, because they don’t want to lose their credibility.

So, alas, no happy ending. This article shows that people don’t make decisions based on security or efficiency, but on their “gut feeling” that is often based on lack of knowledge. We knew this already, of course.

If you want one advice out of all this: make sure you can change your cryptography by using “crypto agility” methods. This will protect you against future attacks by allowing you to switch on time. As a plus, this allows to prepare for the quantum computer.

Quickly computers were programmed by making a program in the form of a file (in these days, that was a string of paper tape with holes) that described the instructions to be executed. These programs consisted of unreadable strings of letters and numbers, and were specific for the computer. Writing these programs involved directly constructed the instructions for the computer.

The programmers realized that the computer itself was the ideal tool to make those programs. The first programming languages appeared, beginning with assembler languages: helper programs that made it easier to type in the machine instructions.

In the decades that followed, lots of programming languages appeared in quick succession. And still, seven decades later, assembler is still used, in a few situations.

The programming process

Let’s have a look at the whole process of how a computer program comes to be. You want to compute something, and you have an idea in your head how this should be done. Then you write a program in C, Python or Java, it gets translated (somehow) into machine code instructions for ARM or x86, the processor executes the instructions, and the internals of the chip perform the additions, loads, stores and other actions needed for your computation.

In summary, the steps are:

• You write out your idea in the form of a program;
• the compiler (or interpreter) converts the program into instructions for the processor;
• the processor executes the instructions;
• the Arithmetic and Logical Unit (ALU) inside the processor performs the actual computations.

Each of these steps has evolved since the construction of early computers, and these have influenced each other.

Programs

The idea of “programming” was pioneered by Edsger W. Dijkstra. I am proud to have met him and discuss his ideas on programming with him. He used a very systematic way of constructing programs. Thanks to his systematic methods, most of his notes are available on line.

He taught programming for many years. His method appears simple: start with turning the requirements of the program into mathematical notation, and then work systematically with these expressions towards expressions in the target programming language. If you do this right, you program has no errors at all. As a student of this method, I found it hard to apply to realistic programs, where the requirements are non-mathematical.

In reality, most programmers used a more interactive mode of programming, where you write parts of the program, and then test these, building up towards the whole. For this, you need a programming language that allows to write down your thoughts in a recognizable way.

Processor instructions

The next step is converting programs into executable instructions. The simplest of programming language is an assembler that used a special word (“mnemonic”) for every instruction of the processor. There is some support for thing like calculating addresses of instructions or defining memory areas.

The first programming languages made certain things easier. In the name of the early programming language FORTRAN (for FORMula TRANslation) shows this clearly: you could just type a formula. Later, programming languages started to help you with organizing your thought, allowing to split a program into pieces, define data structures, and so on.

These programming languages made it easier for the programmer, for example by hiding details about the computer your program ran on. This made it hard or even impossible to use some of the functions of the microprocessor. These functions are put there because the processor manufacturer knows they are easy to implement, and very important for certain computations. But you can’t express these in many languages.

A famous example is the “carry bit”: each time you add two integer numbers on a processor, it automatically registers for you if the result fits in a register. This bit makes it very easy to add numbers that use multiple registers. But there is almost no programming language that allows you to use the carry bit in a program. If you want to do computations with long numbers in C or Java, you have to use all kind of tricks to do this in an efficient way.

Other examples of things that are hard in many programming languages, but are supported by almost all processors:

• rotating bits (that’s like shifting, but the bits than come out go in on the other end);
• multiplication of two numbers with the result in two registers;
• manipulation of bits in numbers;
• moving of blocks of memory;
• addition of numbers in BCD (that is, with two decimal digits per byte).

In modern processors, there are now hundreds of very specific advanced instructions that have no simple description in most programming languages: vector instructions, cryptography, multiplication without carries (!), counting bits, and so on.

The most advanced compilers today can use some of these functions (such as vector computations). In many (but not all) cases this can make programs much faster. The compilation time becomes slower, because the compiler has to carefully analyze which combination of instructions has the same effect as what the program is trying to do.

The other way around, the processor manufactures also added lots of features to help the compiler convert programs into instructions, such as:

• index registers (for stack access);
• efficient ways to put registers on stack (for local variables);
• instructions for array bound checking.

Performing computations

The last step of the programming process is often overlooked: converting instructions into computations for the ALU. This process is dictated by which instructions are available: the “Instruction Set Architecture” or ISA of the processor. There have been many ISAs in the past, but only a few have left. The device you use to read this probably has a ARM or x86 processor in it. Popular ISAs used at the moment are:

• x86, supported by Intel and AMD processors, mainly used by Windows;
• ARM, mainly used by iOS, Android and Apple computers;
• Power PC, used by many (older) Apple computers;
• the IBM ISA for z processors, used by AIX;
• Risc-V, an open standard that is coming up, and redesigned an ISA from the ground up.

The number of ISAs has dropped steadily over the last few decades because it is hard to make an ISA. Each ISA has its own set of tools: compilers, libraries, and application programs have to be adapted. If you use an existing ISA, you can reuse all these tools, so that you can quickly sell processor chips without having to remake the tools. Even forty years ago, the z80 and 8086 ISA were designed to be compatible with the 8080 ISA to allow existing tools to be used.

In the early days of microprocessors, there were lots of different processors on the market. For example, in the period 1974–1980, there were the 8080, 6800, 1802, 2650, 6502, F8, Z80, 6805, 8085, 6809, 68000, 8051, each with a completely different instruction set. Further back in history, the earliest computers were limited by their hardware, resulting sometimes in very strange ISAs, such as the ZEBRA.

Later, where the number of ISAs reduced because of market pressure, there still were quite a few experimental ISAs that tried to improve efficiency of computation by all kinds of means:

• Intel’s Itanium processor, allowing to write multiple actions in a single instruction, requiring a sophisticated compiler;
• the Transputer, specifically designed for parallel processing;
• WebAssembly and LLVM, these are ISAs without processors. Instead, their instructions are designed to be easy to convert to other ISAs;
• ARM’s Jazelle processor that directly runs Java bytecode;
• coprocessors such as the 8087 that added extra (floating point, in this case) instructions to the main processor;
• a special place in this list is the Field Programmable Graphics Array (FPGA): you could see these as processors with an extreme ISA where you describe the computation in extreme detail, down to the operation on bits. The corresponding programming language is called VHDL FPGAs allow for extreme efficient calculations, at the price of a very hard to write program.

Why people still program in assembler

For some applications, it is necessary to use all the functionality of the processor in order to efficiently use the computing power available. And although compilers have come a long way in making efficient code, it is often worth the effort to write part of the computation in assembler: this gives you complete control over the instructions that are executed and allows to produce code that takes less space and runs faster. This takes much more effort, of course.

Fortunately, many programming languages allow to use a bit of assembler inside a program to speed up the crucial computations.

In my own experience, compilers are getting much better. But using assembly keeps helping in making sure your program is as fast as possible.

• in 1994, I wrote an implementation of DES for a Z80 microprocessor. I used only assembler. The resulting code was 300 times as fast as the C program.
• around 2005, I wrote a program that performed approximate matching of internet domain names to detect typosquatting (that is: buying of domain names that look like real domain names).
  This program spent 97% of its time in about fifty lines of assembler code. Almost the entire program was written in Python, allowing for easy programming.
• a few years ago, I wrote a piece of code for the HQC project. There I optimized a bit of code to decode a binary code using the using vector instructions. Here I made use of “intrinsics” which appear as functions in the C source code, but they are converted into single instructions for the processor. The code was almost completely C, and the compiler did a great job: I could not get more than 15% off the computation time of the pure C version.

So even though most programmers seldomly see machine code anymore, it is still used in places where speed is more important that easy to write code:

• cloud computing;
• “high performance computing” or HPC for example for scientific modeling (the weather forecast, for example);
• searching for giant prime numbers, or factors of special large numbers;
• trying to break cryptographic codes: for example, in 2008 false Internet certificate was made with a computer entirely built of PlayStation game computers;
• last but not least, writing cryptographic software in such a way that the secrets are not leaked by timing of the code (for details, see Dan Bernstein’s article for example).

Some historic notes

Back in the early computing age, the last two steps were not as fixed as they are today. The designers of computers did you yet have a clear idea of what a processor looked like, and the designers of programming languages wanted to make life easier for programmers by hiding the details of the processor. On the other hand, computers weren’t that fast, so compilers couldn’t do too much.

The result of this growth process resulted in a few interesting programming languages, that do not look at all like the ones we are using today; they had no idea what was needed from a good programming language. Also, the computer designers had no idea what was needed for making an efficient processor, so the processor designs (ISAs) where more different than today.

Let me pick out a few interesting languages for you. I highly recommend to study some of these languages (if you didn’t already) to see how different programming can be. Each of these languages had an interesting story. And realize that each of these languages was meant seriously, and people used them for solving their programming problems. So we are not talking about “esoteric programming languages” that are used for the fun of make life harder for yourself.

In order of appearance:

• FORTRAN (1956), the first “high level language”. Originally, it had quite a few restrictions: for example, it did not support recursion because it didn’t use a stack.
• COBOL (1959), famous for its verbose programs. It was designed for “businesses”, and clearly shows it was written for the IBM computers of the time.
• LISP (1960), the first language that could process its own programs. It is still used for all kinds of purposes!
• ALGOL60 (1960), the first “structured” language with a recursive grammar. Very popular language for more than a decade.
• APL (1962), where programs are completely unreadable because there were too many symbols and no official syntax. Lines are literally processed in reverse.
• SNOBOL (1962), a language that had extremely powerful pattern matching, but no compound statements. It has been used quite a bit in language analysis.
• TRAC (1964), a language that only used the special characters colon, parentheses and comma, and very strange semantics. It could be seen as “advanced find and replace”.
• Forth (1970), a language which effectively had no grammar at all, except for the space character. Still used because you can write a running Forth implementation on a bare processor, directly in machine instructions, without operating systems, libraries or compiler.
• Algol68 (1973), the language which is the basis of almost all current programming languages. Infamous because of the “two level grammar” used in its formal definition.
• ABC (1987), the language that lead to the development of Python. It used upper and lower case in an interesting way. (My PhD thesis contains some ABC programs.)

There are many interesting things to say about these languages, but this article is too long already. I got surprised several times when doing research for this article. Therefore, I will write blog entries about some of these; follow this channel to see them.

So I was sending a WhatsApp message with a time in it: 15:30 (or 3:30 PM, if you like). For clarity, I added a clock emoji to it: 🕞. (I have no idea what it looks on your screen; we’ll come to that later.) Because this emoji looked quite small on the screen, I didn’t notice at first what was wrong with it, but enlarged it looked like this:

Notice anything? Let’s compare it to a real clock:

That hour hand is a little off, isn’t it? I assume that most people understand that if the minute hand is at the bottom, the hour hand is between digits.

Now WhatsApp, and other big companies, make their own emojis to match their company style. For example, let’s have a look at a very common emoji: the “grinning face”.

The differences are quite obvious. Some of these appear to have a different meaning and could confuse communication. But I digress; much has been written about this subject.

Net’s have a look at the three-thirty emoji over the platforms (at the time of this writing; optimistically, this could change before you read this):

It’s worse than I thought. Every platform, except two, has it wrong! Telegram doesn’t have it yet, apparently. If you read this at Telegram, here’s your change to make things right!

I was so frustrated, couldn’t resist writing about this.

What’s going on here? I have been wrecking my brain for the last weeks, but I can’t figure it out. I learned to read a clock with a toy like this:

(Calculation of the number of teeth in the gears is surprisingly complicated, but that’s a whole different story).

This toy automatically makes sure that the hour hand moves with the minute hand, so you learn to understand that the hour hand is between digits if the minute hand is at the bottom. Once you understand that, you can read a clock. Modern kids probably watch a YouTube video to learn this, or use an online lesson.

So apparently there are almost no designers living today that have learned to read a clock when they were small. I don’t know what to think of this. A few theories:

• These kind of clocks are only used by old people (I’m from 1964, remember). And designers are young, and use digital clocks.
• Google’s designers are older than other designers.
• The designers don’t use their brain when designing, but just mindlessly tweak someone else’s design.
• To many designers mistakenly believe that you can turn a clock upside down without messing up the relationship between the hands.
• It’s a glitch. But that isn’t true, just copy this into you messaging app and check for yourself. They’re probably all wrong: 🕜🕝🕞🕟🕠🕡🕢🕣🕤🕥🕦🕧.

So, if you are (or know) an emoji designer, and you have the opportunity, please fix this, so I can clearly show my friends when to meet.

Update: I just sent an issue to openmoji’s GitHub, and I got confirmation that it will be fixed in their next release! I wonder if the other providers will do this as well.

We learn that a lot of the math we know comes from ancient Greece, but there is an even earlier civilization that knew a lot about mathematics: the Babylonians.

Because this was a very long time ago, there isn’t much left of these times. Let’s start with a look at this piece of clay, dated about 3700 years ago, with the underwhelming name YBC 7289:

The proud owner of this is the Yale Peabody Museum, formerly the Yale Babylonian Collection. If you go to that link, you can find a very modest description of it, but also a very high resolution image if you want a really good look.

This battered piece of clay with triangular impressions contains some pretty sophisticated math, from before the Greek and Roman empires. To understand the mathematics in it, knowledge about both math and history is required; this is probably why these tables when not deciphered until less than a century ago.

What you see here, it a picture of a square, with its size given: ½. You probably remember from school that the size of the diagonal of a square is √2 times the size of the square. That means the length of the diagonal is ½ • √2; which is written next to the diagonal, together with the value of √2.

The numbers are written using the notation of the day: cuneiform numbers. They were written with a stick with a specially shaped point, pressed in the clay to make a triangular dent.

Since this notation is in sexagesimal (i.e. base 60), it is a bit hard to read. Converted to our decimal notation, you get:

• √2 is given as 1.41421
• the length of the diagonal is given as 0.70711

(If you want to know all the details, it is all explained on the Wikipedia page.)

So thanks to this tablet, we know that the Babylonians knew the value of the square root of 2 to a precision of six digits! The value given is the best approximation with four sexagesimal digits. We don’t know if the student making this piece copied the value from somewhere else or computed it herself/himself. But it must be clear that they had a way to calculate it; this was probably a very early variant of what we now call “Newton’s method”.

There’s a whole article about this tablet in the journal Historica Mathematica: Square root approximations in Old Babylonian Mathematics.

There’s more

Although there aren’t very many, there are more of these wonderful artifacts from the Babylonian era, for example:

This text named IM 67118 gives the complete solution of a math problem where the area and diagonal of a rectangle are given, comparable to the kind of homework you’d get today. It even includes a proof of correctness of the result.

Si.427 is a detailed land survey plan, including application of the theorem of Pythagoras, a thousand years before Pythagoras was even born. Youtube video.

The famous Plimpton 322 is a table of sides and hypotenuse of right triangles, sorted by angle. Nobody alive today knows what it was for: it could be a surveyor’s instrument, a number theory investigation, or a list of homework problems. To make it more interesting, there are believed to be a number of mistakes in this table.

Finally, this tablet, found in Kish among lots of others, contains a homework problem with a wrong solution. It is believed to be made by a student, who probably didn’t get a good grade for it.

I love how such simple artifact give a peek into a rich culture, where mathematics obviously was well studied and used. It must have been a great feeling to finally discover what the inscriptions meant!

For readers who can read Dutch, I can recommend this article by Jan van de Craats about Plimpton 322 and YBC 7289. Hi Jan!

Update: I just saw a video on Wrath of Math about AO 6770 which contains a problem in compound interest: how long (down to the day) does is take to double your money if you have 20% annual interest? Today, we would see this as a logarithm problem, but logarithms weren’t invented for three millennia. Their solution uses a linear approximation to the exponential function.

By the way: Babylon was situated in the current country of Iraq. I am really worried about the preservation of these unique artifacts.