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