# VCR Controller Code: additional notes

The algorithm we published can be considerably simplified, and these are some incomprehensible rough notes on how to do this. You are not expected to understand this page.

Following an observation by J. Barrington that with the "key" 68150631, the difference between successive digits is 2345678, I realized that one can do away with multiplication, the key, and considerably simplify the algorithm by replacing the multiplications by addition of the differences.

That is, suppose "data" is the 8 digit input data and we want to compute the result of no-carry multiplication by 68150631. We can just do:

```diff = row = result = 0
for n = 0 to 7
diff += data  // i.e. diff = data * (n+1)
row += diff   // row will be data multiplied by successively 1,3,6,0,5,1,8,6
result += diff << n
end
```
In the above pseudocode, diff, row, total, data are all arrays, the addition is no-carry addition (i.e. mod 10), and "< Now, if they don't use multiplication for the key_mult, it's unlikely they'd use all the multiplication we have in the map_top function. But the same trick works here:
```f0 = f1 = f2 = f3 = 1
for n = 1 to year
f1 += f0 // additions mod 10
f2 += f1
f3 += f2
end
```
Then we will end up with f0=1, f1=y+1, f2=(y+1)(y+2)/2, f3=(y+1)(y+2)(y+3)/6 as required in map_top.

Now, there's a big trick where instead of summing 1's to get the fi's and then multiplying, we can just sum the values we're going to multiply:

```n3 = day
n2 = d2
n1 = d1
n0 = d0
for cnt = 1 to year
n2 += n3
n1 += n2
n0 += n1
end
```
Unless I've messed up the algebra, the above simple loop should do the digits=3 case of map_top.

For example: if you put 7462 into the above loop, you get the same result as no-carry multiplication of 7462x68150631

```diff=row=result=0
data=7462
n=0 pass through loop:
diff = 0+7462=7462
row = 0+7462=7462
result = 0+7462=7462
n=1 pass through loop:
diff = 7462+7462=4824 (no-carry addition)
row = 7462+4824=1286
result = 7462+12860=19222
n=2 pass through loop:
diff = 4824+7462=1286
row = 1286+1286=2462
result = 19222+246200=255422
n=3 pass through loop:
diff = 1286+7462=8648
row = 2462+8648=0000
result = 255422+0=0255422
n=4 pass through loop:
diff = 8648+7462=5000
row = 0000+5000=5000
result = 0255422+50000000=50255422
n=5 pass through loop:
diff = 5000+7462=2462
row = 5000+2462=7462
result = 50255422+746200000=796455422
n=6 pass through loop:
diff = 2462+7462=9824
row = 7462+9824=6286
result = 796455422+6286000000=6972455422
n=7 pass through loop:
diff = 9824+7462=6286
row = 6286+6286=2462
result = 6972455422+24620000000=20592455422
```
Compare with the long multiplication
```          7462
x     68150631
--------
7462
1286
2462      <- this is row in step 2, for instance
0000
5000
7462
6286
2462
-----------
20592455422
```
Note that at each step, row is a row of the partial sum and result is the sum of the terms so far. Thus, the pseudocode is another way of doing the multiplication by 68150631.

At each step, diff is (n+1)*data and row is incremented by data. Thus,

```n=0: diff=1*data, row=1*data
n=1: diff=2*data, row=3*data (3=1+2, 1 from previous row, 2 from current diff)
n=2: diff=3*data, row=6*data (6=3+3)
n=3: diff=4*data, row=0*data (0=6+4)
n=4: diff=5*data, row=5*data (5=0+5)
n=5: diff=6*data, row=1*data (1=5+6)
n=6: diff=7*data, row=8*data (8=1+7)
n=7: diff=8*data, row=6*data (6=8+8)
```
Now if you read the row multipliers, going up, you get 68150631, which is the number we were using as the key. So 68150631 isn't some secret key that they selected and we figured out, but just a consequence of their simple loop.

Ken Shirriff: shirriff@eng.sun.com