Ken Shirriff -> Papers -> VCRPlus -> VCRPlus Controller Further Notes |

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 endIn the above pseudocode, diff, row, total, data are all arrays, the addition is no-carry addition (i.e. mod 10), and "<

f0 = f1 = f2 = f3 = 1 for n = 1 to year f1 += f0 // additions mod 10 f2 += f1 f3 += f2 endThen 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 endUnless 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=20592455422Compare with the long multiplication

7462 x 68150631 -------- 7462 1286 2462 <- this is row in step 2, for instance 0000 5000 7462 6286 2462 ----------- 20592455422Note 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 This page: http://www.righto.com/papers/vcr1.html Copyright 1998 Ken Shirriff