Next: List Tutorial Exercise 14, Previous: List Tutorial Exercise 12, Up: Answers to Exercises [Contents][Index]

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`.