[racket] Implementation of Simpson's Rule (SICP Exercise 1.29)

On 11/06/2013 09:24 AM, Matthias Felleisen wrote:
>
> On Nov 6, 2013, at 7:13 AM, Ben Duan <yfefyf at gmail.com> wrote:
>
>> Thank you, Jens. I didn't know that the inexactness of floating point numbers could make such a big difference.
>
>
>  From HtDP/1e:
>
> (define JANUS
>    (list #i31
>          #i2e+34
>          #i-1.2345678901235e+80
>          #i2749
>          #i-2939234
>          #i-2e+33
>          #i3.2e+270
>          #i17
>          #i-2.4e+270
>          #i4.2344294738446e+170
>          #i1
>          #i-8e+269
>          #i0
>          #i99))
>
>
>
> ;; [List-of Number] -> Number
> ;; add numbers from left to right
> (check-expect (sumlr '(1 2 3)) 6)
> (define (sumlr l)
>    (foldl + 0 l))
>
> ;; [List-of Number] -> Number
> ;; add numbers from right to left
> (check-expect (sumrl '(1 2 3)) 6)
> (define (sumrl l) (foldr + 0 l))
>
> Then apply the two functions to JANUS. Enjoy -- Matthias

Nice example!

You could also (require math) and apply its `sum' or `flsum' to JANUS. 
Then *really* enjoy. :D

 > (sumlr JANUS)
99.0

 > (sumrl JANUS)
-1.2345678901235e+80

 > (sum JANUS)
4.2344294738446e+170

 > (exact->inexact (sumlr (map inexact->exact JANUS)))
4.2344294738446e+170

On my computer, using `sum' is about 20x faster than converting JANUS to 
exact numbers.

You can also sort by absolute value before summing, which is a little 
faster still but loses some precision. Do not trust Teh Internets on 
this one. Popular Q-and-A sites say to sort ascending, which makes 
intuitive sense: adding a big number to two small numbers in turn might 
do nothing, but adding a big number to their *sum* might result in 
something larger.

 > (expt 2 53.0)
9007199254740992.0

 > (sumlr (list (expt 2 53.0) 1.0 1.0))
9007199254740992.0

 > (sumlr (list 1.0 1.0 (expt 2 53.0)))
9007199254740994.0

But JANUS shows that sorting ascending doesn't work when summing huge 
numbers with alternating signs:

 > (sumlr (sort JANUS (λ (x y) (< (abs x) (abs y)))))
0.0

 > (sumlr (sort JANUS (λ (x y) (> (abs x) (abs y)))))
4.2344294738446e+170

All the research papers on summation by sorting sort descending, 
contrary to the wisdom of Teh Internets. So either do that, or use `sum' 
or `flsum' when you want an accurate sum of flonums.

Neil ⊥