[math-fun] What kind of structure are IEEE 754 doubles?
Addition isn't even associative in floating point: http://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floati... so floating point numbers don't even form a monoid under addition. Is addition commutative? Is there some concise characterization of what kind of structure they do form, like "Addition and multiplication are magmas with an absorbing element NaN such that ..."? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
* Mike Stay <metaweta@gmail.com> [Apr 15. 2015 17:38]:
Addition isn't even associative in floating point: http://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floati... so floating point numbers don't even form a monoid under addition. Is addition commutative?
I don't think so: Take one value L so large that adding 1.0 does not change it at all. Also take very many 1.0's (indeed take L of them). Now 1.0 + 1.0 + 1.0 + ... + 1.0 + L ==> 2.0 * L but L + 1.0 + 1.0 + 1.0 + ... + 1.0 ==> L
Is there some concise characterization of what kind of structure they do form, like "Addition and multiplication are magmas with an absorbing element NaN such that ..."?
That's gonna be hard to answer (even when ignoring quiet vs. signaling NaNs, negative zero, and denormalized underflow). Suggest to check out (no idea how helpful as I never asked myself the question above): David Goldberg: What Every Computer Scientist Should Know about Floating-Point Arithmetic, ACM Computing Surveys, vol.23, no.1, pp.5-48, \bdate{March-1991} http://www.validlab.com/goldberg/paper.ps <--= edited reprint Jean-Michel Muller, Nicolas Brisebarre, Florent de Dinechin, Claude-Pierre Jeannerod, Vincent Lef\`{e}vre, Guillaume Melquiond, Nathalie Revol, Damien Stehl\'{e}, Serge Torres: Handbook of Floating-Point Arithmetic, Birkh\"{a}user, \bdate{2010} If I'd needed to know in a hurry, I'd ask Paul Zimmermann. If you find out, kindly tell us. Best regards, jj
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Apr 15, 2015 at 9:17 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Mike Stay <metaweta@gmail.com> [Apr 15. 2015 17:38]:
Addition isn't even associative in floating point: http://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floati... so floating point numbers don't even form a monoid under addition. Is addition commutative?
I don't think so: Take one value L so large that adding 1.0 does not change it at all. Also take very many 1.0's (indeed take L of them). Now 1.0 + 1.0 + 1.0 + ... + 1.0 + L ==> 2.0 * L but L + 1.0 + 1.0 + 1.0 + ... + 1.0 ==> L
So large floating point numbers behave rather like countably infinite ordinals in that sense: 1 + ω = ω ≠ ω + 1.
Suggest to check out (no idea how helpful as I never asked myself the question above):
Thank you! -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Joerg Arndt writes:
* Mike Stay <metaweta@gmail.com> [Apr 15. 2015 17:38]:
Addition isn't even associative in floating point: http://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floati... so floating point numbers don't even form a monoid under addition. Is addition commutative?
I don't think so: Take one value L so large that adding 1.0 does not change it at all. Also take very many 1.0's (indeed take L of them). Now 1.0 + 1.0 + 1.0 + ... + 1.0 + L ==> 2.0 * L but L + 1.0 + 1.0 + 1.0 + ... + 1.0 ==> L
You're both reassociating and commuting here. If you just commute, then you need to compare: (1.0 + 1.0 + 1.0 + ... + 1.0) + L vs. L + (1.0 + 1.0 + 1.0 + ... + 1.0) which one would hope are the same. But they might not be 2*L, since if L is sufficiently large, then at some point adding one to the sum may stop having and effect. In any case, I don't think this example addresses the question of commutativity. Tom
* Tom Karzes <karzes@sonic.net> [Apr 15. 2015 19:19]:
Joerg Arndt writes:
* Mike Stay <metaweta@gmail.com> [Apr 15. 2015 17:38]:
Addition isn't even associative in floating point: http://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floati... so floating point numbers don't even form a monoid under addition. Is addition commutative?
I don't think so: Take one value L so large that adding 1.0 does not change it at all. Also take very many 1.0's (indeed take L of them). Now 1.0 + 1.0 + 1.0 + ... + 1.0 + L ==> 2.0 * L but L + 1.0 + 1.0 + 1.0 + ... + 1.0 ==> L
You're both reassociating and commuting here. If you just commute, then you need to compare:
(1.0 + 1.0 + 1.0 + ... + 1.0) + L vs. L + (1.0 + 1.0 + 1.0 + ... + 1.0)
which one would hope are the same. But they might not be 2*L, since if L is sufficiently large, then at some point adding one to the sum may stop having and effect. In any case, I don't think this example addresses the question of commutativity.
Tom
I actually left the message hanging in my editor for a while pondering about whether I might be confusing associativity and commutativity. Thanks for pointing out! Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Joerg Arndt -
Mike Stay -
Tom Karzes