Huh. It looks like they're also using Shewchuk's O(n*log(n))
average-case distillation algorithm. Like Racket's math library does. :D
Neil ⊥
On 11/07/2013 04:24 AM, Stephan Houben wrote:
The competition does it better, see Python's fsum:
import math
janus = [31.0, 2e+34, -1.2345678901235e+80, 2749.0, -2939234.0, -2e+33,
3.2e+270, 17.0, -2.4e+270, 4.2344294738446e+170, 1.0, -8e+269,
0.0, 99.0]
print(math.fsum(janus))
# 4.2344294738446e+170
The fsum algorithm is interesting, it essentially emulates
unlimited-precision FP
by using a list of limited-precision FP numbers.
Stephan
2013/11/7 Todd O'Bryan <toddobr...@gmail.com <mailto:toddobr...@gmail.com>>
I just found a lovely Java expression to emphasize the inexactness of
doubles to my AP students. The problem--which I think is from
HtDP/1e--is to find the value of a bag of coins given the number of
pennies, nickels, dimes, and quarters. In BlueJ's code pad (or similar
in DrJava, jGrasp, etc.)
> 0.01 + 0.05 + 0.10 + 0.25
0.410000000000000000003
(my number of zeroes may be off)
As one of my students said--"You can do that in your head. What's the
computer's problem?"
Todd
On Wed, Nov 6, 2013 at 1:30 PM, Neil Toronto <neil.toro...@gmail.com
<mailto:neil.toro...@gmail.com>> wrote:
> On 11/06/2013 09:24 AM, Matthias Felleisen wrote:
>>
>>
>> On Nov 6, 2013, at 7:13 AM, Ben Duan <yfe...@gmail.com
<mailto: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
____________________
Racket Users list:
http://lists.racket-lang.org/users
____________________
Racket Users list:
http://lists.racket-lang.org/users
