On 11/06/2013 09:24 AM, Matthias Felleisen wrote:
On Nov 6, 2013, at 7:13 AM, Ben Duan <yfe...@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 ⊥
____________________
Racket Users list:
http://lists.racket-lang.org/users
