Saturday, September 15, 2007

Ligget se

I saw once more that inject:into: was being used to add consecutive integers. But wouldn't it be nice if you could do this instead?

anInteger sumTo: someOtherInteger by: someSkippage

Note this is not a matter of providing a nice interface to a raw sum of the contents of intervals. This is much more. Let's begin with someSkippage = 1, in which the case above reduces to

anInteger sumTo: someOtherInteger

Of course, we define the sum to be zero if anInteger > someOtherInteger. Then, what do we do to implement Integer>>sumTo:? Something like inject:into:?

No my friend, we remember what Gauss did at age 10 when we has asked to sum 1 to 100. He quickly realized the answer was 50 * 101 = 5050, and throwing his slate on his desk pronounced "Ligget se", or "There it is".

Ok, so that works when anInteger = 1. But if it is 10, then the trick doesn't immediately work. Well we can make it work though. If we need to sum all integers between i and j, then we will sum i, i+1, ... , j. Ok, but that is the same as summing 1, 2,... , j-i+1, and then adding (i-1)(j-i+1) (i-1 times the amount of sum terms). We also see that when i=1, the "shift" term evaluates to zero as it should. The sum from 1 to j-i+1 is, by Gauss' technique, (j-i+1)(j-i+2) // 2, so the result evaluates quickly: (j-i+1)(j-i+2) // 2 + (i-1)(j-i+1). Very nice.

Let's try 13 sumTo: 29. Our formula says the answer should be 17 * 18 // 2 + (12 * 17) = 357. A quick inject:into: check verifies this is correct.

What if we want sumTo:by: now? Well, instead of adding i, i+1,... , j, we are going to add i, i+m, i+2m,... , j // m * m. How many terms are in this sum? Clearly, if i <= j (the case when the sum is not already known to be zero), we must have j - i // m + 1 terms (Smalltalk notation). Let's call h = j - i // m + 1 for convenience. Also, the largest term in the sum will be j' = j // m * m.

We can downshift this sum from i, i+m etc to 1, 2 etc just like we did in the previous case. First, we subtract i from all the terms (and then we just add back hi to the result). So now we have 0, m, 2m etc. Now we can divide all of those by m and then we have 0, 1, 2, etc (so we multiply by m after we calculate the inner sum).

Ok, so to get the result, first we sum 0 to j'//m, which is the same as the sum from 1 to j'//m. We know how to sum that because of Gauss, and it is just (j'//m)(j'//m + 1) // 2. Then we need to multiply all that mess by m, so we get m(j'//m)(j'//m + 1) // 2. And finally, we need to add hi to all of that. Then the whole expression is just m(j'//m)(j'//m + 1) // 2 + hi.

Let's try adding 3 to: 45 by: 8. Then, we have i = 3, j = 45, m = 8, h = 45 - 1 // 8 + 1 = 6 and j'//m = 45//8*8//8 = 5. Our formula says the sum must be 8*5*6 // 2 + (3 * 6) = 138. A quick inject:into: check verifies this is correct too.

Ligget se --- no inject:into: necessary.

1 comment:

Andres said...

Hmmmm,

I found the derivation for sumTo:by: shown is not correct. The problem is left to the reader to find.

Thanks,
Andres.