While watching lecture 2a at http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ (yes, for fun), a program was put forth to sum numbers from a to b. This, of course, reminded me of the famous Carl Gauss series summation formula (a+b)b/2. Quickly implementing both the naive summation and the Gaussian formula in the scheme programming language gave me the following:
(define (sum-i a b) (if (= a b) b (+ a (sum-i (+ 1 a) b)))) (define (fsum-i a b) (* 1/2 (+ a b) b))
The first line, sum-i, being the naive approach, and the second being the Gauss approach. That’s fine and dandy, but the naive approach is more capable at the expense of speed. So I got to thinking… Can the formulatic approach be developed until it is as capable? Of course!
Observing how the formula Mr Gauss operates on the sum from 1 to n while contemplating the set m to n, we see that a+b remains the same, as does the 1/2, so the last part remaining must be the effected component. We can observe that the sum of m to n is equal to the sum of 1 to n minus the sum of 1 to (m-1). So instead of multiplying by m, we should multiply by n-(m-1), or n-m+1 for a final formula of (a+b)(b-a+1)/2. Let’s throw that into scheme…
(define (fsum-i a b) (* 1/2 (+ a b) (+ (- b a) 1)))
Ok, now lets run some tests to see if we got the right observations and mechanics in place…
> (sum-i 1 100) 5050 > (fsum-i 1 100) 5050 > (sum-i 27 100) 4699 > (fsum-i 27 100) 4699 > (sum-i 47382 3487921) 6081675691810 > (fsum-i 47382 3487921) 6081675691810
yowza, that last sum-i really took some time to compute! The next obvious abstraction would be to introduce the concept of “stride”. But I think I’m done playing math games, and will amuse myself with those course videos 🙂
RSS Feed