List Tutorial Exercise 13

First, we put the string on the stack as a vector of ASCII codes.

1:  [84, 101, 115, ..., 51]
    .

    "Testing, 1, 2, 3 RET

Note that the " key, like $, initiates algebraic entry so there was no need to type an apostrophe. Also, Calc didn’t mind that we omitted the closing ". (The same goes for all closing delimiters like ) and ] at the end of a formula.

We’ll show two different approaches here. In the first, we note that if the input vector is ‘[a, b, c, d]’, then the hash code is ‘3 (3 (3a + b) + c) + d = 27a + 9b + 3c + d’. In other words, it’s a sum of descending powers of three times the ASCII codes.

2:  [84, 101, 115, ..., 51]    2:  [84, 101, 115, ..., 51]
1:  16                         1:  [15, 14, 13, ..., 0]
    .                              .

    RET v l                        v x 16 RET -

2:  [84, 101, 115, ..., 51]    1:  1960915098    1:  121
1:  [14348907, ..., 1]             .                 .
    .

    3 TAB V M ^                    *                 511 %

Once again, * elegantly summarizes most of the computation. But there’s an even more elegant approach: Reduce the formula 3 $$ + $ across the vector. Recall that this represents a function of two arguments that computes its first argument times three plus its second argument.

1:  [84, 101, 115, ..., 51]    1:  1960915098
    .                              .

    "Testing, 1, 2, 3 RET          V R ' 3$$+$ RET

If you did the decimal arithmetic exercise, this will be familiar. Basically, we’re turning a base-3 vector of digits into an integer, except that our “digits” are much larger than real digits.

Instead of typing 511 % again to reduce the result, we can be cleverer still and notice that rather than computing a huge integer and taking the modulo at the end, we can take the modulo at each step without affecting the result. While this means there are more arithmetic operations, the numbers we operate on remain small so the operations are faster.

1:  [84, 101, 115, ..., 51]    1:  121
    .                              .

    "Testing, 1, 2, 3 RET          V R ' (3$$+$)%511 RET

Why does this work? Think about a two-step computation: ‘3 (3a + b) + c’. Taking a result modulo 511 basically means subtracting off enough 511’s to put the result in the desired range. So the result when we take the modulo after every step is,

3 (3 a + b - 511 m) + c - 511 n

for some suitable integers ‘m’ and ‘n’. Expanding out by the distributive law yields

9 a + 3 b + c - 511*3 m - 511 n

The ‘m’ term in the latter formula is redundant because any contribution it makes could just as easily be made by the ‘n’ term. So we can take it out to get an equivalent formula with ‘n' = 3m + n’,

9 a + 3 b + c - 511 n'

which is just the formula for taking the modulo only at the end of the calculation. Therefore the two methods are essentially the same.

Later in the tutorial we will encounter modulo forms, which basically automate the idea of reducing every intermediate result modulo some value m.