Re: [boost] New Boost.XInt Library, request preliminary review
Chad Nelson wrote:
This disables the copy-on-write optimization that the library uses by default [...]
I'm not convinced that integers should be COW. What situations do you forsee where COW would be helpful but move semantics wouldn't suffice?
As described on the rationale page of the documentation, the primary reason I'm using copy-on-write is that move semantics aren't widely available yet. Portability is one of my primary goals, and while I've seen references to a move-semantics-emulator in Boost, I've also seen suggestions that it relies on the compiler to somehow recognize it. That doesn't sound fully portable to me.
No offense, but I'm not confident that COW semantics for the integer class is a wise design choice. I assume you have tested the performance with and without COW semantics, as well tested the performance for thread safe operations with and without COW semantics, before making that decision. Care to disclose the numbers? I guess that you have read the COW string article (http://www.gotw.ca/gotw/045.htm) by Herb Sutter, and his conclusions. Optimizations on other parts should perhaps have been made before converting to COW semantics. Using COW semantics could also complicate the complexity requirements for most functions, as they may be "amortized O(something)" instead of just "O(something)". Another concern I have is that NaN is "signaling" as most operations on a NaN integer will throw an exception. I think it would be more sound if operations on NaN integers would result in NaN integers, compare with float NaN. Don't take these comments the wrong way, I'm very glad to see development of an arbitrary precision integer boost licensed library. Best regards, Anders Dalvander
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
No offense, but I'm not confident that COW semantics for the integer class is a wise design choice.
I assume you have tested the performance with and without COW semantics, as well tested the performance for thread safe operations with and without COW semantics, before making that decision.
Yes to everything except for the "thread safe operations with and without COW semantics." The only way to provide fully thread-safe operation with copy-on-write enabled is by putting locking functions in the xint::integer class itself. I experimented with that, but in the end I decided that it just wasn't that class's place to do that sort of thing. As such, copy-on-write is only used when the library is compiled in single-thread mode.
Care to disclose the numbers?
In single-thread mode, running my test suite presently takes an average of 1.30 seconds. Still in single-thread mode, but with copy-on-write disabled, it's 2.42 seconds. (For the sake of completeness, full thread-safe mode also takes 2.42 seconds. The main difference is a mutex protecting the random number generator as well.)
I guess that you have read the COW string article (http://www.gotw.ca/gotw/045.htm) by Herb Sutter, and his conclusions.
Of course.
Optimizations on other parts should perhaps have been made before converting to COW semantics.
There were, a large number of them. They were insufficient.
Using COW semantics could also complicate the complexity requirements for most functions, as they may be "amortized O(something)" instead of just "O(something)".
Wouldn't you rather have "amortized O(something)" than just "O(something)", when the first O is about half the value of the second? ;-)
Another concern I have is that NaN is "signaling" as most operations on a NaN integer will throw an exception. I think it would be more sound if operations on NaN integers would result in NaN integers, compare with float NaN.
I actually implemented it that way first. But after long consideration, I decided that a signaling NaN was better. With the non-signaling one, you could go through hours of calculations, only to find that NaN returned at the beginning of them rendered all that work useless.
Don't take these comments the wrong way, I'm very glad to see development of an arbitrary precision integer boost licensed library.
And I appreciate your comments, and your politeness in delivering them. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuuqTYACgkQp9x9jeZ9/wR4QQCglIIunbj56RuifAw6n8w6DkFi FHwAn34554rZI70/kMaLOdCrRV/va9Ce =bCzG -----END PGP SIGNATURE-----
On 27 March 2010 20:56, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
I actually implemented it that way first. But after long consideration, I decided that a signaling NaN was better. With the non-signaling one, you could go through hours of calculations, only to find that NaN returned at the beginning of them rendered all that work useless.
Of course, the same argument works for quiet NaNs: I actually implemented it that way first. But after long consideration, I decided that a non-signaling NaN was better. With the signaling one, you could go through hours of calculations, only to find that the NaN returned near the end of them lost all the still-useful work. Why not just support both? One more bit for signalling or quiet isn't a space problem, since it'd only be defined when the current NaN bit is already set. Then in the code you already have to check NaN would look at the bit to decide how to respond. It would probably mean that the NaN-checking prefix in the functions would end up being a macro instead of an ordinary function call, but I think it'd be worth it. When deciding to allow NaNs, did you consider allowing infinities as well? That's idle curiosity, though; I don't have a use case in mind.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
I actually implemented it that way first. But after long consideration, I decided that a signaling NaN was better. With the non-signaling one, you could go through hours of calculations, only to find that NaN returned at the beginning of them rendered all that work useless.
Of course, the same argument works for quiet NaNs:
I actually implemented it that way first. But after long consideration, I decided that a non-signaling NaN was better. With the signaling one, you could go through hours of calculations, only to find that the NaN returned near the end of them lost all the still-useful work.
Touché. But I still have to disagree. You can prevent signaling NaNs from signaling by testing for them before trying to use them. There are only a tiny number of functions that will return one, after all, and most of those will only do so under specific and user-controlled circumstances. But you can't prevent non-signaling ones from non-signaling. :-)
Why not just support both? One more bit for signalling or quiet isn't a space problem, since it'd only be defined when the current NaN bit is already set. Then in the code you already have to check NaN would look at the bit to decide how to respond.
The problem wouldn't be with space, but with interface -- you'd have to have a way to tell the library which type of NaN to return, from the functions that can normally return one. I can think of several ways around that, but all of them feel... ugly. They would require too many logical inconsistencies and too much special-case coding, both in the library and for users of the library. For example, the best way I can see so far would be to simply allow the not-a-number exception to be blocked. But then what do you return for functions like even() or odd()? getbit()? How should comparisons be handled -- is a NaN greater than or less than any specific number? Neither true nor false is a valid answer, because the question itself is nonsensical. In most cases, throwing an exception is the only response that isn't obviously and horribly wrong.
It would probably mean that the NaN-checking prefix in the functions would end up being a macro instead of an ordinary function call, but I think it'd be worth it.
I'm not sure that it would. There's a concept among theoretical mathematicians, that when an equation feels ugly, it's probably incomplete or incorrect. Similarly, I've found that when a decision leads to an interface that feels ugly, then it's probably the wrong decision.
When deciding to allow NaNs, did you consider allowing infinities as well? That's idle curiosity, though; I don't have a use case in mind.
I don't see any reason to. Infinity is not-a-number (literally), and can be validly represented as such in the few places where it might be needed, like division by zero when exceptions are blocked. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuu400ACgkQp9x9jeZ9/wQ8jACfckKKdg+Tyj/HXqccfAGLWwfK /S8AnAnQl2ZqFel+BjkjyfkTNEvnvblZ =wBC7 -----END PGP SIGNATURE-----
Chad Nelson wrote:
I actually implemented it that way first. But after long consideration, I decided that a signaling NaN was better. With the non-signaling one, you could go through hours of calculations, only to find that NaN returned at the beginning of them rendered all that work useless. Of course, the same argument works for quiet NaNs:
I actually implemented it that way first. But after long consideration, I decided that a non-signaling NaN was better. With the signaling one, you could go through hours of calculations, only to find that the NaN returned near the end of them lost all the still-useful work.
Touché. But I still have to disagree. You can prevent signaling NaNs from signaling by testing for them before trying to use them. There are only a tiny number of functions that will return one, after all, and most of those will only do so under specific and user-controlled circumstances. But you can't prevent non-signaling ones from non-signaling. :-)
Any way this could be a compile-time policy and/or runtime configurable?
For example, the best way I can see so far would be to simply allow the not-a-number exception to be blocked. But then what do you return for functions like even() or odd()? getbit()? How should comparisons be handled -- is a NaN greater than or less than any specific number? Neither true nor false is a valid answer, because the question itself is nonsensical. In most cases, throwing an exception is the only response that isn't obviously and horribly wrong.
Can't you return the same result specified by IEEE floating point? Do those operations have standardized results when using NaNs?
When deciding to allow NaNs, did you consider allowing infinities as well? That's idle curiosity, though; I don't have a use case in mind.
I don't see any reason to. Infinity is not-a-number (literally), and can be validly represented as such in the few places where it might be needed, like division by zero when exceptions are blocked. - -- Chad Nelson Oak Circle Software, Inc.
(Aside: Division by zero should only produce an infinity if you make a distinction between +0 and -0.) Keep in mind that +/-infinity *is* different than an NaN. It has a sign and a well-defined ordering wrt to "regular" numbers and themselves. If you are going to represent NaNs, you might as well represent +/-infinity and +/-0. I think the principle of least surprise says to follow the semantics of IEEE floating point. But the best short term solution might be to just throw an exception and not worry about NaN's or infinities for now. - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 03:56 AM, Jeffrey Lee Hellrung, Jr. wrote:
Touché. But I still have to disagree. You can prevent signaling NaNs from signaling by testing for them before trying to use them. There are only a tiny number of functions that will return one, after all, and most of those will only do so under specific and user-controlled circumstances. But you can't prevent non-signaling ones from non-signaling. :-)
Any way this could be a compile-time policy and/or runtime configurable?
Certainly, but I'll need a compelling use-case for it. I'd rather not spend the time putting such a feature in if no one needs it or is going to use it.
For example, the best way I can see so far would be to simply allow the not-a-number exception to be blocked. But then what do you return for functions like even() or odd()? getbit()? How should comparisons be handled -- is a NaN greater than or less than any specific number? Neither true nor false is a valid answer, because the question itself is nonsensical. In most cases, throwing an exception is the only response that isn't obviously and horribly wrong.
Can't you return the same result specified by IEEE floating point? Do those operations have standardized results when using NaNs?
In the IEEE system, comparisons involving NaNs always return false. That's consistent, but not logically correct -- a NaN is not "not less than" or "not greater than" a number. I don't think there are any IEEE functions for even or odd (that requires an exact representation) or getbit (that wouldn't be meaningful on floating-point numbers), or most of the other problematic XInt functions.
When deciding to allow NaNs, did you consider allowing infinities as well? That's idle curiosity, though; I don't have a use case in mind.
I don't see any reason to. Infinity is not-a-number (literally), and can be validly represented as such in the few places where it might be needed, like division by zero when exceptions are blocked.
(Aside: Division by zero should only produce an infinity if you make a distinction between +0 and -0.)
I can't tell whether you've never realized the logic behind zero and infinities, or whether you're so far beyond me that I just can't follow you. Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero. You can see why dividing a non-zero number by zero produces infinity with a simple thought experiment. Imagine a pie divided into four slices, another into three slices, and another into two. Each time you decrease the number of slices by one, the size of each slice not only gets larger, but does so at an exponentially-increasing rate. (Again, my terminology may be off, but that's the basic idea.) By the time you get to one "slice," you get the whole pie with no cuts at all. Extending that to fractions (which is physically impossible, but logically definable), if you cut it into 0.5 "slices," you get two whole pies. 0.1 slices gives you ten whole pies. 0.01 gives you 100, and it just keeps going up at the same exponential rate. If you try to reduce it to *zero* slices, you get an infinite number of pies -- not just a inexpressably and unimaginably large number, but an *impossible* number. If the entire universe were pies, it still wouldn't accurately express the result of dividing a pie by zero. It occurred to me as I was writing the above that you're probably approaching the problem from the domain of computer science and floating-point representations of numbers, rather than pure mathematics. A floating-point number is an inexact representation of a true number, so it follows slightly different rules. The XInt library only represents integers, and unbounded ones, so it follows the mathematical rules of numbers, rather than those of inexact representations. The floating-point library that will inevitably be written on top of XInt, if it's accepted into Boost, will need to deal with that stuff, but XInt itself doesn't.
Keep in mind that +/-infinity *is* different than an NaN. It has a sign and a well-defined ordering wrt to "regular" numbers and themselves.
Certainly, in both computer science and mathematics. But by the mathematical definition, infinity isn't a number, it's a representation of an impossible number. So logically, representing it with the not-a-number value is correct.
If you are going to represent NaNs, you might as well represent +/-infinity and +/-0. I think the principle of least surprise says to follow the semantics of IEEE floating point.
Sorry, but I disagree. XInt is integers, not floating point numbers. It *would* surprise me if an integer library slavishly followed floating-point semantics. NaN has a well-defined meaning for integers. The rest does not.
But the best short term solution might be to just throw an exception and not worry about NaN's or infinities for now.
There we can agree. :-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuvfOoACgkQp9x9jeZ9/wTOewCfTZk/4tE14ShV3E3tUG2QObbQ UxsAoKitvHNlapzFcKDXbVvXtel3KXSp =imWc -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/28/2010 03:56 AM, Jeffrey Lee Hellrung, Jr. wrote:
Touché. But I still have to disagree. You can prevent signaling NaNs from signaling by testing for them before trying to use them. There are only a tiny number of functions that will return one, after all, and most of those will only do so under specific and user-controlled circumstances. But you can't prevent non-signaling ones from non-signaling. :-) Any way this could be a compile-time policy and/or runtime configurable?
Certainly, but I'll need a compelling use-case for it. I'd rather not spend the time putting such a feature in if no one needs it or is going to use it.
Sure.
For example, the best way I can see so far would be to simply allow the not-a-number exception to be blocked. But then what do you return for functions like even() or odd()? getbit()? How should comparisons be handled -- is a NaN greater than or less than any specific number? Neither true nor false is a valid answer, because the question itself is nonsensical. In most cases, throwing an exception is the only response that isn't obviously and horribly wrong. Can't you return the same result specified by IEEE floating point? Do those operations have standardized results when using NaNs?
In the IEEE system, comparisons involving NaNs always return false. That's consistent, but not logically correct -- a NaN is not "not less than" or "not greater than" a number.
Sure, informally.
I don't think there are any IEEE functions for even or odd (that requires an exact representation) or getbit (that wouldn't be meaningful on floating-point numbers), or most of the other problematic XInt functions.
Sure.
When deciding to allow NaNs, did you consider allowing infinities as well? That's idle curiosity, though; I don't have a use case in mind. I don't see any reason to. Infinity is not-a-number (literally), and can be validly represented as such in the few places where it might be needed, like division by zero when exceptions are blocked. (Aside: Division by zero should only produce an infinity if you make a distinction between +0 and -0.)
I can't tell whether you've never realized the logic behind zero and infinities, or whether you're so far beyond me that I just can't follow you.
Well, neither; just following, again, the IEEE floating point standard: 1/+0 = +infinity 1/-0 = -infinity and also 1/+infinity = +0 1/-infinity = -0 I guess I implicitly assumed that, if one were to represent "infinity", it would be desirable to distinguish between +infinity and -infinity, which compels one to further distinguish between +0 and -0. I guess you can have a single infinity (and, correspondingly, a single 0).
Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero.
+/-0 would carry the same meaning they do for IEEE floating point. They behave exactly identically except for a few exceptional operations (e.g., when you divide by them). [...slicing pies...]
The XInt library only represents integers, and unbounded ones, so it follows the mathematical rules of numbers, rather than those of inexact representations. The floating-point library that will inevitably be written on top of XInt, if it's accepted into Boost, will need to deal with that stuff, but XInt itself doesn't.
That's fine. Then I don't think it's this library's job to represent NaNs, signed zeros and infinities aside. I guess I dislike the change in semantics of NaN from what it is for floating point. NaNs might have a valid use case to simply represent indeterminates, but it also might be convenient to guarantee that every xint::integer object actually represents an actual integer. Seems simpler (semantics, implementation) to just forego any NaN representation, and throw on operations that produce indeterminate, complex, or infinite results. [...more discussion on +/-0 and +/-infinity...] - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 02:37 PM, Jeffrey Lee Hellrung, Jr. wrote:
(Aside: Division by zero should only produce an infinity if you make a distinction between +0 and -0.)
I can't tell whether you've never realized the logic behind zero and infinities, or whether you're so far beyond me that I just can't follow you.
Well, neither; just following, again, the IEEE floating point standard:
1/+0 = +infinity 1/-0 = -infinity
and also
1/+infinity = +0 1/-infinity = -0
Those make perfect sense, but only if you assume that +0 and -0 represent numbers that are very close to zero, but not *exactly* zero. Since this is explicitly an integer library, they aren't needed here. By the same token, specific infinity values aren't needed either. The library will represent, exactly, any value that it can access enough memory for, and will throw an exception on any value with a greater magnitude than that.
I guess I implicitly assumed that, if one were to represent "infinity", it would be desirable to distinguish between +infinity and -infinity,
Certainly, the two are distinct values with the same magnitude.
which compels one to further distinguish between +0 and -0. I guess you can have a single infinity (and, correspondingly, a single 0).
With a single (integer) zero, n / 0 = infinity, and -n / 0 = -infinity. No specific need for a signed zero value for that.
Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero.
+/-0 would carry the same meaning they do for IEEE floating point. [...]
An integer library has no need for that meaning. There is only one value between -1 and +1, and that's exactly zero -- it has no need to represent infinitely small fractions between zero and the first integral number in either direction, the way a floating-point library does.
The XInt library only represents integers, and unbounded ones, so it follows the mathematical rules of numbers, rather than those of inexact representations. The floating-point library that will inevitably be written on top of XInt, if it's accepted into Boost, will need to deal with that stuff, but XInt itself doesn't.
That's fine. Then I don't think it's this library's job to represent NaNs, signed zeros and infinities aside. I guess I dislike the change in semantics of NaN from what it is for floating point.
I'm trying to understand exactly what you're objecting to, but so far I'm failing. I called that value a Not-a-Number because it represents the same concept as the floating-point library's Not-a-Number value, namely something that isn't a valid number. That's the only relationship the two have to each other.
NaNs might have a valid use case to simply represent indeterminates, but it also might be convenient to guarantee that every xint::integer object actually represents an actual integer. Seems simpler (semantics, implementation) to just forego any NaN representation, and throw on operations that produce indeterminate, complex, or infinite results.
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuvyt4ACgkQp9x9jeZ9/wSY6wCcDKsV1vCHIMshBSz4wT1+33aH N6QAoI1/+6RuL+w8BgTxhgjEYVkUkfDj =6gcG -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/28/2010 02:37 PM, Jeffrey Lee Hellrung, Jr. wrote:
[...]
NaNs might have a valid use case to simply represent indeterminates, but it also might be convenient to guarantee that every xint::integer object actually represents an actual integer. Seems simpler (semantics, implementation) to just forego any NaN representation, and throw on operations that produce indeterminate, complex, or infinite results.
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-)
If that's the purpose of your NaN, why limit your set of "special" values to just { NaN }, when under some circumstances returning some representation of infinity (or +infinity or -infinity if you make such a distinction) would be more informative? For example, you can make n/0 for n != 0 result in infinity, and 0/0 result in NaN.
By the same token, specific infinity values aren't needed either. The library will represent, exactly, any value that it can access enough memory for, and will throw an exception on any value with a greater magnitude than that.
What if "exceptions are blocked" in this case? Do you return an NaN here as well? - Jeff
Jeffrey Lee Hellrung, Jr. wrote:
By the same token, specific infinity values aren't needed either. The library will represent, exactly, any value that it can access enough memory for, and will throw an exception on any value with a greater magnitude than that.
What if "exceptions are blocked" in this case? Do you return an NaN here as well?
Chad, I see you've answered this already, thanks. - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-)
If that's the purpose of your NaN, why limit your set of "special" values to just { NaN }, when under some circumstances returning some representation of infinity (or +infinity or -infinity if you make such a distinction) would be more informative? For example, you can make n/0 for n != 0 result in infinity,
I could, but why? Who needs to know that n/0 is specifically infinity, rather than simply NaN? If you can point out a case where it would help someone more than returning a NaN would, I'll be happy to add it.
and 0/0 result in NaN.
Technically, 0/0 should be allowed, with a result of 1. I don't know any computer implementation that bothers checking for that and allowing it though. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwDPgACgkQp9x9jeZ9/wS6ygCfayt7AnkjcDN4nnLCr6NFZFRS /IkAn2adaeWga7tnCsCBmVlZXdC3vYdE =3ov3 -----END PGP SIGNATURE-----
On 28 March 2010 22:14, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Technically, 0/0 should be allowed, with a result of 1. I don't know any computer implementation that bothers checking for that and allowing it though.
Please no. As x -> 0, 0/x says it should be 0, x/x says it should be 1, sqrt(x)/x says it should be +infinity. 0/0 is the one that really has to be NaN. Ask your friendly neighbourhood high school calculus teacher for further elaboration.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Technically, 0/0 should be allowed, with a result of 1. I don't know any computer implementation that bothers checking for that and allowing it though.
Please no. As x -> 0, 0/x says it should be 0, x/x says it should be 1, sqrt(x)/x says it should be +infinity. 0/0 is the one that really has to be NaN.
Ask your friendly neighbourhood high school calculus teacher for further elaboration.
Oops, you're right. Sorry, as I said, I'm only an armchair mathematician. :-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwJW0ACgkQp9x9jeZ9/wQSzwCgw88N9nFUaBDP6zGb/X4sN+JY M20An12LEUBwh5zSMckCmAW3GpkIGDcI =1Tg1 -----END PGP SIGNATURE-----
Chad Nelson wrote:
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-) If that's the purpose of your NaN, why limit your set of "special" values to just { NaN }, when under some circumstances returning some representation of infinity (or +infinity or -infinity if you make such a distinction) would be more informative? For example, you can make n/0 for n != 0 result in infinity,
I could, but why? Who needs to know that n/0 is specifically infinity, rather than simply NaN? If you can point out a case where it would help someone more than returning a NaN would, I'll be happy to add it.
An xint::integer which is +infinity or -infinity is more meaningful than one which is NaN. At the very least, you can make more refined calculations and comparisons with +/-infinity (compared to NaN), constructing intervals where either or both endpoints are +/-infinity, etc. You might feel that an infinity value belongs in a wrapper class around xint::integer, and I would tend to agree. But I would also put the NaN representation in this wrapper class as well, along with the entire exception blocking framework. It seems to me to be orthogonal to the rest of the interface, and if one never uses blocking exceptions, it seems like a waste. Also, why does invmod always return an NaN on an invalid inverse, and not throw a blockable exception? - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 01:11 AM, Jeffrey Lee Hellrung, Jr. wrote:
If that's the purpose of your NaN, why limit your set of "special" values to just { NaN }, when under some circumstances returning some representation of infinity (or +infinity or -infinity if you make such a distinction) would be more informative? For example, you can make n/0 for n != 0 result in infinity,
I could, but why? Who needs to know that n/0 is specifically infinity, rather than simply NaN? If you can point out a case where it would help someone more than returning a NaN would, I'll be happy to add it.
An xint::integer which is +infinity or -infinity is more meaningful than one which is NaN.
Agreed -- but only slightly. It carries one additional bit's worth of meaning, the sign.
At the very least, you can make more refined calculations and comparisons with +/-infinity (compared to NaN),
Do you have an example where this would make any noticeable difference in XInt?
constructing intervals where either or both endpoints are +/-infinity, etc.
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
You might feel that an infinity value belongs in a wrapper class around xint::integer, and I would tend to agree.
I don't see a need for an infinity value at all. It provides no value to any function presently in the library, or any function I can imagine, that isn't already provided by Not-a-Number.
But I would also put the NaN representation in this wrapper class as well, along with the entire exception blocking framework. It seems to me to be orthogonal to the rest of the interface, and if one never uses blocking exceptions, it seems like a waste.
Not completely. There *are* the two functions that return Not-a-Number as part of their normal operation, not counting the string- and stream-reading functions. As I said on the rationales page of the documentation, I tried using Boost.Optional for those, but it made the library harder for people not already familiar with Boost.Optional to understand. An error code is an idiom that every C or C++ developer already understands well and knows how to deal with. I could move the Not-a-Number value and the exception-blocking system to a wrapper, and go back to using Boost.Optional for those two functions, neophyte users be damned. Or have them throw exceptions, though the idea is distasteful to me. But I'm not yet convinced that there's sufficient reason to do so... though I must admit, the idea is appealing from a design perspective, as it would make the interface noticeably more elegant. Scott McMurray's point about the existence of Not-a-Number forcing the library to check for it in all functions is an argument in its favor as well. Keep going, one more valid argument might be enough to change my mind. :-)
Also, why does invmod always return an NaN on an invalid inverse, and not throw a blockable exception?
Because exceptions should, to my mind, be reserved for exceptional behavior -- things that should never happen under normal circumstances, and which demand special handling. Unless the specified modulus is prime, which cannot be trivially determined, invmod is *expected* to discover that some numbers have no inverse for it. That's neither unexpected nor exceptional, and depending on the application, doesn't automatically require special handling. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwSY8ACgkQp9x9jeZ9/wQVZwCgwWUcW9WyQOM0ciMSpKD3FZAw Jr4AoMansGdn95HXYaMTUHPkDJHMND/x =Z7xK -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/29/2010 01:11 AM, Jeffrey Lee Hellrung, Jr. wrote:
If that's the purpose of your NaN, why limit your set of "special" values to just { NaN }, when under some circumstances returning some representation of infinity (or +infinity or -infinity if you make such a distinction) would be more informative? For example, you can make n/0 for n != 0 result in infinity, I could, but why? Who needs to know that n/0 is specifically infinity, rather than simply NaN? If you can point out a case where it would help someone more than returning a NaN would, I'll be happy to add it. An xint::integer which is +infinity or -infinity is more meaningful than one which is NaN.
Agreed -- but only slightly. It carries one additional bit's worth of meaning, the sign.
Even if you identify +infinity and -infinity as a single infinity, it should *still* mean something different from an NaN. You might group infinity into the class of NaNs, but that doesn't mean that every operation which results in an NaN may as well result in an infinity (signed or unsigned). 0/0 and sqrt(-1) should evaluate to an NaN (or throw); it would be unsettling to evaluate these as infinity.
At the very least, you can make more refined calculations and comparisons with +/-infinity (compared to NaN),
Do you have an example where this would make any noticeable difference in XInt?
Noticeable in what sense? 1/NaN is NaN; 1/+infinity is +0 (or 1/infinity is 0 if you don't want signed infinities and zeros). Assuming, of course, you allow calculations with NaNs.
constructing intervals where either or both endpoints are +/-infinity, etc.
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
Since NaN compares false to anything else, good luck getting your intervals with NaN endpoints to work in any kind of generic setting ;)
You might feel that an infinity value belongs in a wrapper class around xint::integer, and I would tend to agree.
I don't see a need for an infinity value at all. It provides no value to any function presently in the library, or any function I can imagine, that isn't already provided by Not-a-Number.
Yes, this is true. I keep thinking that your NaN should be quiet, but the current state of affairs (non-blockable throwing when you do just about anything with an NaN) presents fewer use cases for infinities.
But I would also put the NaN representation in this wrapper class as well, along with the entire exception blocking framework. It seems to me to be orthogonal to the rest of the interface, and if one never uses blocking exceptions, it seems like a waste.
Not completely. There *are* the two functions that return Not-a-Number as part of their normal operation, not counting the string- and stream-reading functions. As I said on the rationales page of the documentation, I tried using Boost.Optional for those, but it made the library harder for people not already familiar with Boost.Optional to understand. An error code is an idiom that every C or C++ developer already understands well and knows how to deal with.
Which 2 functions? invmod and random_prime? These hardly seem like fundamental operations that necessitate this "invasion" into an otherwise pure big-integer interface ;) Returning optional values is precisely the raison d'etre of Boost.Optional, and you're ending up just building its functionality directly into the xint::integer class, so instead of xint::integer, we really have a boost::optional< xint::integer >. I don't like that :/ What did you find about Boost.Optional that was difficult for users to understand?
I could move the Not-a-Number value and the exception-blocking system to a wrapper, and go back to using Boost.Optional for those two functions, neophyte users be damned. Or have them throw exceptions, though the idea is distasteful to me. But I'm not yet convinced that there's sufficient
Returning a Boost.Optional seems perfectly reasonable.
reason to do so... though I must admit, the idea is appealing from a design perspective, as it would make the interface noticeably more elegant. Scott McMurray's point about the existence of Not-a-Number forcing the library to check for it in all functions is an argument in its favor as well.
Keep going, one more valid argument might be enough to change my mind. :-)
The interface to invmod and random_prime should be built around the interface of xint::integer, not the other way around.
Also, why does invmod always return an NaN on an invalid inverse, and not throw a blockable exception?
Because exceptions should, to my mind, be reserved for exceptional behavior -- things that should never happen under normal circumstances, and which demand special handling. Unless the specified modulus is prime, which cannot be trivially determined, invmod is *expected* to discover that some numbers have no inverse for it. That's neither unexpected nor exceptional, and depending on the application, doesn't automatically require special handling.
I sympathize with this reasoning. Generally speaking, if the user cannot trivially check the preconditions, it could make sense to return some kind of error condition rather than throwing. - Jeff
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeffrey Lee Hellrung, Jr. Sent: Monday, March 29, 2010 8:23 AM To: boost@lists.boost.org Subject: Re: [boost] New Boost.XInt Library, request preliminary review
Chad Nelson wrote:
On 03/29/2010 01:11 AM, Jeffrey Lee Hellrung, Jr. wrote:
You guys are obviously having a lot of fun with this thread, but I'd just like to point out that the *users* wishes can sensibly be granted here using policies as John Maddock implemented in the Boost.Math library (see the docs if you need reminding how this works - and you probably do need reminding because the sensible default policies mean that you probably will ignore policies unless the library doesn't do what you want). While there are things that are mathematically right or wrong, the application or user may not consider this important. Policies allow the user to get exceptions thrown when something 'nasty' happens (like divide by minus zero say), or not. Existing code may rely on getting a NaN, or may rely on *not* getting a NaN. Policies allow users to decide. I was going to strongly suggest policies to Chad - but there are much more important things to sort out first (adding policies really clutters the code, so policies are best added last). My original point was that existing code may rely on std::numeric_limits, so it is important to specialise it, even the meaning may not be perfect. Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 05:26 AM, Paul A. Bristow wrote:
You guys are obviously having a lot of fun with this thread, but I'd just like to point out that the *users* wishes can sensibly be granted here using policies as John Maddock implemented in the Boost.Math library (see the docs if you need reminding how this works - and you probably do need reminding because the sensible default policies mean that you probably will ignore policies unless the library doesn't do what you want).
As I'd only delved into the math toolkit a couple times, I wasn't aware of them. Thanks for pointing them out.
While there are things that are mathematically right or wrong, the application or user may not consider this important.
I'm trying to set up the library so that, if the user knows what to expect mathematically, he isn't surprised at any XInt behavior.
Policies allow the user to get exceptions thrown when something 'nasty' happens (like divide by minus zero say), or not.
Existing code may rely on getting a NaN, or may rely on *not* getting a NaN. Policies allow users to decide.
Exactly what I was intending with the exception-blocking mechanism. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxP9kACgkQp9x9jeZ9/wSsZgCeKam5c3niaB1Kp88udO9zNXqO 6L8AnjgSK6R90v82q3kFy4wlndNGtc+b =jfLy -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/29/2010 05:26 AM, Paul A. Bristow wrote:
While there are things that are mathematically right or wrong, the application or user may not consider this important.
I'm trying to set up the library so that, if the user knows what to expect mathematically, he isn't surprised at any XInt behavior.
Doing so can make the library less approachable to those without the mathematical expectations. Be careful about purity in this sense.
Policies allow the user to get exceptions thrown when something 'nasty' happens (like divide by minus zero say), or not.
Existing code may rely on getting a NaN, or may rely on *not* getting a NaN. Policies allow users to decide.
Exactly what I was intending with the exception-blocking mechanism.
Your approach involves runtime cost, I think. Policies allow altering the implementation, at compile time. How does one mix code wanting exceptions with code not wanting them? With policies, the two types differ, but can be designed for interoperability. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Stewart, Robert wrote:
How does one mix code wanting exceptions with code not wanting them?
Pretty easy (bad_alloc aside (*)), since the only way to get an exception when doing integer operations is to divide by zero (**). So code not wanting exceptions needs only not divide by zero - problem solved. This of course assumes that the exceptions are not delayed via a signaling NaN with the express purpose of making your life difficult by turning unary op+/- into a throwing operation. (*) And by the way, out of memory is not overflow. It's possible to run out of memory while computing an integer that is smaller than another integer that already has been computed. This is not what overflow means. (**) OK, sqrt(-1) throws as well.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 08:23 AM, Peter Dimov wrote:
How does one mix code wanting exceptions with code not wanting them?
Pretty easy (bad_alloc aside (*)), since the only way to get an exception when doing integer operations is to divide by zero (**). So code not wanting exceptions needs only not divide by zero - problem solved. This of course assumes that the exceptions are not delayed via a signaling NaN with the express purpose of making your life difficult by turning unary op+/- into a throwing operation.
Which is only a problem if you're doing something that produces a NaN. In XInt, that's rare, and all such cases are very carefully documented.
(*) And by the way, out of memory is not overflow. It's possible to run out of memory while computing an integer that is smaller than another integer that already has been computed. This is not what overflow means.
If that was aimed at XInt, note its purpose: it's intended to allow calculation with numbers of arbitrary length, up to the memory size of the system. If the system can't provide enough memory for it at some point, that *is* an overflow -- the number is too large to represent. That definition is already used in Boost as well, in the Boost.Math library: "Overflow Error: Occurs when the result is either infinite, or too large to represent in the numeric type being returned by the function." - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyCXYACgkQp9x9jeZ9/wQwDQCg+Gjt+ZCMetMd/2OgZCIhNpBK pNUAoOohZZfJyo3+/gCkduC6yNAqMeK6 =sZPu -----END PGP SIGNATURE-----
On 30 March 2010 10:23, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
If that was aimed at XInt, note its purpose: it's intended to allow calculation with numbers of arbitrary length, up to the memory size of the system. If the system can't provide enough memory for it at some point, that *is* an overflow -- the number is too large to represent.
That definition is already used in Boost as well, in the Boost.Math library: "Overflow Error: Occurs when the result is either infinite, or too large to represent in the numeric type being returned by the function."
I disagree. Consider, for instance, [lib.basic.string]/4a in C++03: For any string operation, if as a result of the operation, size() would exceed max_size() then the operation throws length_error. That, in my opinion, is the equivalent of an overflow. The type is fundamentally *incapable* of representing such a large string/number. Note that it's a distinct exception from bad_alloc, which states that the type *could* represent the value requested, if only the memory allocator would give it what it asked for.
Chad Nelson wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 03/30/2010 08:23 AM, Peter Dimov wrote:
How does one mix code wanting exceptions with code not wanting them?
Pretty easy (bad_alloc aside (*)), since the only way to get an exception when doing integer operations is to divide by zero (**). So code not wanting exceptions needs only not divide by zero - problem solved. This of course assumes that the exceptions are not delayed via a signaling NaN with the express purpose of making your life difficult by turning unary op+/- into a throwing operation.
Which is only a problem if you're doing something that produces a NaN. In XInt, that's rare, and all such cases are very carefully documented.
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing?
(*) And by the way, out of memory is not overflow. It's possible to run out of memory while computing an integer that is smaller than another integer that already has been computed. This is not what overflow means.
If that was aimed at XInt, note its purpose: it's intended to allow calculation with numbers of arbitrary length, up to the memory size of the system. If the system can't provide enough memory for it at some point, that *is* an overflow -- the number is too large to represent.
No, it isn't an overflow. An overflow doesn't occur at random, depending on some external resource. Overflows are deterministic and depend on the fixed range of the number. A 32 bit signed integer always overflows at 2^31. If a calculation produces a number X without overflowing, that same calculation, when performed again, will still produce X without overflowing. This is not true for out of memory conditions. Arguing that making a copy of a number can overflow is stranger still.
on 30.03.2010 at 19:45 Peter Dimov wrote :
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing? if you don't want to deal with specific exceptions
xint::integer foo(); //... xint::integer i = foo(); MY_ASSERT(i!=NaN);
No, it isn't an overflow. An overflow doesn't occur at random, depending on some external resource. Overflows are deterministic and depend on the fixed range of the number. A 32 bit signed integer always overflows at 2^31. If a calculation produces a number X without overflowing, that same calculation, when performed again, will still produce X without overflowing. This is not true for out of memory conditions. Arguing that making a copy of a number can overflow is stranger still. agree bad_alloc and the like suit better i would leave bad_alloc actually (no re-throwing needed)
-- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
"DE" wrote:
on 30.03.2010 at 19:45 Peter Dimov wrote :
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing? if you don't want to deal with specific exceptions
xint::integer foo(); //... xint::integer i = foo(); MY_ASSERT(i!=NaN);
So, in other words, if you don't want to deal with exceptions, you abort the program on the assert (in debug mode) or throw at the next use of i (in release mode). This doesn't strike me as very useful.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 11:45 AM, Peter Dimov wrote:
Which is only a problem if you're doing something that produces a NaN. In XInt, that's rare, and all such cases are very carefully documented.
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing?
If you ignore NaN results from functions that return them, then yes, that is the result. If you use them properly, and check for NaN as soon as a function that can return it returns, you will know the exact line that it came from. In what scenario is this a bad thing?
(*) And by the way, out of memory is not overflow. It's possible to run out of memory while computing an integer that is smaller than another integer that already has been computed. This is not what overflow means.
If that was aimed at XInt, note its purpose: it's intended to allow calculation with numbers of arbitrary length, up to the memory size of the system. If the system can't provide enough memory for it at some point, that *is* an overflow -- the number is too large to represent.
No, it isn't an overflow. An overflow doesn't occur at random, depending on some external resource. Overflows are deterministic and depend on the fixed range of the number. A 32 bit signed integer always overflows at 2^31. If a calculation produces a number X without overflowing, that same calculation, when performed again, will still produce X without overflowing. This is not true for out of memory conditions. Arguing that making a copy of a number can overflow is stranger still.
I'm sorry you don't see the logic behind it. I do, and n1744 (the "standardese" for the large-integer library proposal) specifies it, on page two: "all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory. Such errors are reported as overflow_error exceptions (as available memory defines the range of the integer class)." As such, I'll need a much stronger reason than that to change it. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyYKMACgkQp9x9jeZ9/wR1+gCePQwHET1YkVjsZ6O83WRnP4Ty 6TgAnA4kN0ghFxfzIBURGVCNR9KXF4xo =J5H+ -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 30 March 2010, Chad Nelson wrote:
I'm sorry you don't see the logic behind it. I do, and n1744 (the "standardese" for the large-integer library proposal) specifies it, on page two: "all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory. Such errors are reported as overflow_error exceptions (as available memory defines the range of the integer class)."
Just to put my 2 cents in (on what is probably a minor issue after all), I find it conceptually silly for an "unlimited range integer" to throw an overflow_error. Maybe it should be renamed "dynamicly unspecified range integer". Boost isn't under any obligation to respect a design decision just because it's in a standard proposal. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkuyaTQACgkQ5vihyNWuA4U0FwCcC+w9F9JJTOTqFbmucCBmcdEI sroAn0iisOZ7U9y6bmjaILYvpDnKyuan =m+o2 -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 05:12 PM, Frank Mori Hess wrote:
I'm sorry you don't see the logic behind it. I do, and n1744 (the "standardese" for the large-integer library proposal) specifies it, on page two: "all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory. Such errors are reported as overflow_error exceptions (as available memory defines the range of the integer class)."
Just to put my 2 cents in (on what is probably a minor issue after all), I find it conceptually silly for an "unlimited range integer" to throw an overflow_error. Maybe it should be renamed "dynamicly unspecified range integer".
Well, it's not called an "infinite range integer," after all. :-) Just an unlimited one, because the library does not place any limits on it. Only available memory, and the time needed to operate on something that large, do.
Boost isn't under any obligation to respect a design decision just because it's in a standard proposal.
Certainly. But that (and n1692) are what XInt's interface is modeled after, so it does. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyb8MACgkQp9x9jeZ9/wQz0gCgypR0HE5SDzZ8f8QxUceYNEPM sVUAn3dtT1v2qBWfNNJqPeYsm1oZrAQc =Ghra -----END PGP SIGNATURE-----
On 30 March 2010 17:40, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Well, it's not called an "infinite range integer," after all. :-) Just an unlimited one, because the library does not place any limits on it. Only available memory, and the time needed to operate on something that large, do.
The library *does* impose a limit: It has to allocate space, so there's necessarily the limit implied by the size of the type passed to the allocator to request the space. Take, for instance: pow(xint(-1u), xint(-1u)) That should probably throw an overflow error from checking ahead of time that the amount of memory requested is infeasible in the same way as std::vector<int>(-1) will throw a std::length_error. (Yes, I agree that it's not a limit anyone should ever be hitting in useful programs, but...)
On 30 Mar 2010, at 22:47, Scott McMurray wrote:
On 30 March 2010 17:40, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Well, it's not called an "infinite range integer," after all. :-) Just an unlimited one, because the library does not place any limits on it. Only available memory, and the time needed to operate on something that large, do.
The library *does* impose a limit: It has to allocate space, so there's necessarily the limit implied by the size of the type passed to the allocator to request the space.
Take, for instance:
pow(xint(-1u), xint(-1u))
That should probably throw an overflow error from checking ahead of time that the amount of memory requested is infeasible in the same way as std::vector<int>(-1) will throw a std::length_error.
By the same argument, should we changed the hashed containers to "dynamically unspecified size hashed containers"? Chris
On 30 March 2010 17:49, Christopher Jefferson <chris@bubblescope.net> wrote:
On 30 Mar 2010, at 22:47, Scott McMurray wrote:
The library *does* impose a limit: It has to allocate space, so there's necessarily the limit implied by the size of the type passed to the allocator to request the space.
By the same argument, should we changed the hashed containers to "dynamically unspecified size hashed containers"?
Can you elaborate? Your question makes me think of the "unordered_" prefix, which I can't mentally link to the discussion of boundedness.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 05:47 PM, Scott McMurray wrote:
Well, it's not called an "infinite range integer," after all. :-) Just an unlimited one, because the library does not place any limits on it. Only available memory, and the time needed to operate on something that large, do.
The library *does* impose a limit: It has to allocate space, so there's necessarily the limit implied by the size of the type passed to the allocator to request the space.
That's size_t, which is defined as an unsigned 32-bit integer on my 32-bit machines. Unless I've got my sums wrong, such an integer can hold 4GB, which not coincidentally, is the maximum amount of address space that a program on a 32-bit machine can address. Ditto 64-bit size_t on a 64-bit system. So it's not really a limit.
Take, for instance:
pow(xint(-1u), xint(-1u))
That should probably throw an overflow error from checking ahead of time that the amount of memory requested is infeasible in the same way as std::vector<int>(-1) will throw a std::length_error.
Probably so, but I don't think checking it before starting calculations is feasible. For one thing, what would you compare it to, to see whether it's too big? There's no standard C++ call (so far as I know) to get the amount of free memory on the system. And if there were, the system wouldn't necessarily be able to provide all of it.
(Yes, I agree that it's not a limit anyone should ever be hitting in useful programs, but...)
But bugs happen, and people might specify it by accident, even if they're intending only to use numbers that would easily fit into memory. (Yeah, I've made that kind of mistake before myself.) ;-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuydzkACgkQp9x9jeZ9/wQO3QCg2xN+zwGTBU7nVWXjhPOnXc1j J7IAoKSSuYy0kFE5iWSxXumOCquqOyBF =SFfV -----END PGP SIGNATURE-----
Chad Nelson wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 03/30/2010 11:45 AM, Peter Dimov wrote:
Which is only a problem if you're doing something that produces a NaN. In XInt, that's rare, and all such cases are very carefully documented.
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing?
If you ignore NaN results from functions that return them, then yes, that is the result. If you use them properly, and check for NaN as soon as a function that can return it returns, you will know the exact line that it came from.
So, in other words, the purpose of the NaN is to be a "throwing error code". You are supposed to always check for it, and if you omit a check, it throws when someone looks at it.
In what scenario is this a bad thing?
In general, but this leads us into the generic exceptions vs error codes debate. Error handling philosophies aside, in this specific case, I don't see how checking the result of every op/ for NaN is in any way better, more readable or more expressive than checking the denominator for being zero beforehand, but to each his own.
I'm sorry you don't see the logic behind it. I do, and n1744 (the "standardese" for the large-integer library proposal) specifies it, on page two: "all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory. Such errors are reported as overflow_error exceptions (as available memory defines the range of the integer class)."
I see the logic, I just don't agree with it. Term abuse aside, the correct response to std::bad_alloc (making more memory available, if possible) typically differs from the correct response to std::overflow_error. If you insist on masking std::bad_alloc, it would be better to choose a distinct type so that people can treat it as a bad_alloc.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 05:17 PM, Peter Dimov wrote:
Which is only a problem if you're doing something that produces a NaN. In XInt, that's rare, and all such cases are very carefully documented.
Right. What is the purpose of the NaN? Its function is to delay the exception until the first use of the result, making the point of the erroneous calculation harder to trace. In what scenario is this a good thing?
If you ignore NaN results from functions that return them, then yes, that is the result. If you use them properly, and check for NaN as soon as a function that can return it returns, you will know the exact line that it came from.
So, in other words, the purpose of the NaN is to be a "throwing error code". You are supposed to always check for it, and if you omit a check, it throws when someone looks at it.
As I said above, it's extremely rare that a function will return a NaN. There are only two functions in the library that do so under normal circumstances, both carefully documented. If the user is blocking exceptions, there are a handful of others, also carefully documented. Where am I explaining things wrong, that everyone seems to think that any function can randomly return a NaN, and is complaining about it on the basis of that misconception?
I'm sorry you don't see the logic behind it. I do, and n1744 (the "standardese" for the large-integer library proposal) specifies it, on page two: "all integer operations which return an (temporary) integer and many member operators may fail due to insufficient memory. Such errors are reported as overflow_error exceptions (as available memory defines the range of the integer class)."
I see the logic, I just don't agree with it. Term abuse aside, the correct response to std::bad_alloc (making more memory available, if possible) typically differs from the correct response to std::overflow_error. If you insist on masking std::bad_alloc, it would be better to choose a distinct type so that people can treat it as a bad_alloc.
That's a good reason, and your suggested solution is easy to implement. I'll do so for the next iteration. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuycZQACgkQp9x9jeZ9/wT1sACeOCDoPoKc3bzAeznilP2OMXWX WL4An2UUoDxiupaYk5bCodQbiV4qPJv5 =CQ3q -----END PGP SIGNATURE-----
Chad Nelson wrote:
Where am I explaining things wrong, that everyone seems to think that any function can randomly return a NaN, and is complaining about it on the basis of that misconception?
You stopped reading too soon. In my the next sentence, I said (quoting from memory): "I don't see how checking the result of every operator/ for NaN is better, more readable or more expressive than checking the denominator for being zero beforehand" which, as you can see, acknowledges both the rarity of functions returning NaN and the fact that they do so under circumstances that are well defined and easily checked for. Besides, the problem introduced by the NaN, that every function taking a xint must be prepared to receive it, is not affected by the number of functions that produce NaNs.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 07:42 PM, Peter Dimov wrote:
Where am I explaining things wrong, that everyone seems to think that any function can randomly return a NaN, and is complaining about it on the basis of that misconception?
You stopped reading too soon. In my the next sentence, I said (quoting from memory):
"I don't see how checking the result of every operator/ for NaN is better, more readable or more expressive than checking the denominator for being zero beforehand"
Ah, I see... you had abbreviated operator/ to op/, and I misread it for a typo of "operation". Sorry.
which, as you can see, acknowledges both the rarity of functions returning NaN and the fact that they do so under circumstances that are well defined and easily checked for.
But not quite accurately, because operator/ throws an xint::divide_by_zero under those circumstances, unless you're deliberately blocking exceptions.
Besides, the problem introduced by the NaN, that every function taking a xint must be prepared to receive it, is not affected by the number of functions that produce NaNs.
Why is that a problem? It's only library functions that need to be prepared to receive a NaN, functions built on top of XInt can ignore them and let the library catch them. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyltAACgkQp9x9jeZ9/wQuLACcDwv6i++eGuPfRTpJIgdFX3D/ ZssAoKuiT/Fp8jEEgJtuox5KcZOw+D4v =zH04 -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/30/2010 07:42 PM, Peter Dimov wrote:
Besides, the problem introduced by the NaN, that every function taking a xint must be prepared to receive it, is not affected by the number of functions that produce NaNs.
Why is that a problem? It's only library functions that need to be prepared to receive a NaN, functions built on top of XInt can ignore them and let the library catch them.
A function taking an xint has to decide for itself how NaNs should be treated. Will that function emit XInt exceptions? Will it translate those exceptions? Will it handle NaN inputs via an alternate code path? _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On 30 March 2010 17:05, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Now that's an argument I can finally agree with. :-)
Yay! =]
Here's how I propose to solve it: make a "core" version of the integer class and functions, with no exception-blocking and no Not-a-Number value, in the namespace xint::core. Then make the main integer class and functions in namespace xint, with exception-blocking, the Not-a-Number value, and maybe infinity values.
I like the idea. Here's a brain dump of a slightly different way it could look: The user would see two classes, finite_xint and nothrow_xint. (Names subject to refinement, of course.) They'd share representation somehow for move semantics, CoW, or whatever support (which means that mixing the two is still efficient, since a temporary of one can turn into a temporary of the other cheaply). A finite_xint maintains the invariant that it always holds a specific, finite value. A nothrow_xint, on the other hand, allows for special values. Clearly converting a finite_xint to a nothrow_xint would always succeed. Converting a nothrow_xint to a finite_xint would throw an exception if the number isn't finite. Consider for this post at least that they have bidirectional implicit conversions. (The throwing implicit conversion is scary, so perhaps not a good idea, but you'll see why I kept it anyways. It should also mean that mixed operations would be ambiguous -- like finite_xint() + nothrow_xint() -- which would be a good thing, imho.) Then just about every function currently in the library would change to accept a finite_xint. That pretty much gives the current library behaviour, but with at least two advantages. 1) No need to explicitly spell out the "throws on NaN" behaviour for every function, since it's clear from the argument type that passing a non-finite number will give an exception in the implicit conversion. (And there's no possible efficiency complaint about the check, since if you just pass a finite_xint in the first place, there's no check done.) 2) For sqrt, division, invmod (and any other functions that can give NaN), you choose the behaviour by where you store it. finite_xint x = sqrt(finite_xint(-1)); will throw even though the sqrt returned a NaN. If you'd rather check for NaN yourself, then you just do nothrow_xint x = sqrt(finite_xint(-1)); (And, again, with move semantics, it's guaranteed that there's no excess copying involved even when storing to a different type.) It does mean that the NaN is essentially still a signalling NaN, though. Since I personally prefer a quiet(-as-possible) NaN, I'd want it taken another step further. Another version of every operation is added, taking nothrow_xints instead; the current NaN-returning functions are renamed with a nothrow_prefix, so for instance nothrow_sqrt(finite_xint(-1)) == nothrow_xint::NaN(); and the current NaN-returning functions are re-writen to throw internally so they can return finite_xints. (Initially all these functions would be simple wrappers, but plausibly they'd eventually be rewriten using the unspecified common representation either by someone with a slow try-catch implementation or by the "exception-haters".) All of the nothrow_xint functions would be noexcept, since bad_alloc or length_error would result in +/-Inf and any domain error would give a NaN. That would allow people to choose between fail-hard-and-fast code and safely-do-as-much-as-we-can code as the situation requires. Mixing them will still remain reasonable, since calling is_odd(nothrow_xint::NaN()) would end up treating it like a signalling NaN if -- as is likely -- there's no implementation of is_odd that takes a nothrow_xint. And if only a nothrow_xint-taking version of some function is available, finite_xint users will still be happy since they'll still get the exception; it'll just be a bit later (when they store the result instead of ASAP). P.S. Upon further reflection, please keep x/0 resulting in NaN. I agree that multiple zeros in an integer class is evil, and that means that 1/(1/-Inf) and 1/(1/Inf) have to evaluate to the same thing, so it should be NaN.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 08:51 PM, Scott McMurray wrote:
Here's how I propose to solve it: [...]
I like the idea. Here's a brain dump of a slightly different way it could look:
It sounds like the two aren't all that different. I'll have to study your proposal at length. In the mean time, I've just uploaded a second version for review, with the current interface. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyowYACgkQp9x9jeZ9/wQVBQCggmlS0XtD+6H07ASfXQWWQzS2 bk0AoKElWe/dWeOh7WaKYo/9XNni9plQ =ZSLf -----END PGP SIGNATURE-----
Scott McMurray wrote:
On 30 March 2010 17:05, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Here's how I propose to solve it: make a "core" version of the integer class and functions, with no exception-blocking and no Not-a-Number value, in the namespace xint::core. Then make the main integer class and functions in namespace xint, with exception-blocking, the Not-a-Number value, and maybe infinity values.
I like the idea. Here's a brain dump of a slightly different way it could look:
The user would see two classes, finite_xint and nothrow_xint. (Names subject to refinement, of course.) They'd share representation somehow for move semantics, CoW, or whatever support (which means that mixing the two is still efficient, since a temporary of one can turn into a temporary of the other cheaply). A finite_xint maintains the invariant that it always holds a specific, finite value. A nothrow_xint, on the other hand, allows for special values.
[snip lots of goodness] I like your idea Scott as it provides the right mix of flexibility and functionality to satisfy most (all?) needs. It sounds to me like the policy-based approach we suggested before: a policy-based basic_xint and two typedefs, finite_xint and nothrow_xint, specifying different behavior via policies. (Names still subject to refinement.) _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 07:15 AM, Stewart, Robert wrote:
Existing code may rely on getting a NaN, or may rely on *not* getting a NaN. Policies allow users to decide.
Exactly what I was intending with the exception-blocking mechanism.
Your approach involves runtime cost, I think. Policies allow altering the implementation, at compile time.
Which isn't necessarily the best way to do it, and certainly isn't the only one. There is effectively zero runtime cost for XInt's exception-blocking mechanism, since the code used for it is only evaluated when an exception needs to be thrown. Perhaps you're thinking of the earlier comment that having a Not-a-Number value in the library involves some runtime cost. That's true, but the cost is so minimal (one comparison to zero for each integer-type parameter to a function) as to be unnoticeable -- a handful of clock cycles per function in the very worst case. If that's a problem, I can reduce it even further, but I don't expect anyone will be able to show that it is.
How does one mix code wanting exceptions with code not wanting them? With policies, the two types differ, but can be designed for interoperability.
And with XInt's exception-blocking, nothing differs except the behavior. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyBNAACgkQp9x9jeZ9/wSpaACcCPYXh15ZMbGx6eU1VxTH4tLj pUAAnjbUGY1mGiB621B3it3GpnxM4DOy =Dra8 -----END PGP SIGNATURE-----
On 30 March 2010 10:04, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Which isn't necessarily the best way to do it, and certainly isn't the only one. There is effectively zero runtime cost for XInt's exception-blocking mechanism, since the code used for it is only evaluated when an exception needs to be thrown.
There is, however, conceptual and infrastructure overhead from supporting it. First, there's the fact I've previously mentioned than NaN weakens the invariant of the xint type. This requires extra effort in specifying functions that take and return xints. The most obvious evidence of this is the fact that almost every function in the library has the following line in its documentation: "Can throw: xint::not_a_number if n is Not-a-Number." Second, the blocking is stateful. That means that if I write another library that accepts xints, I'll have to either write every function to work no matter the blocking mode or change it to what I want to work with. This state maintenance means bringing in the threading complications that are otherwise unnecessary.
Scott McMurray wrote:
On 30 March 2010 10:04, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Which isn't necessarily the best way to do it, and certainly isn't the only one. There is effectively zero runtime cost for XInt's exception-blocking mechanism, since the code used for it is only evaluated when an exception needs to be thrown.
Second, the blocking is stateful. That means that if I write another library that accepts xints, I'll have to either write every function to work no matter the blocking mode or change it to what I want to work with. This state maintenance means bringing in the threading complications that are otherwise unnecessary.
With a policy-based approach, Scott's library specifies which behavior it wants. It might need to provide interfaces to accept the other type, too, but that's a conscious choice. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On 30 March 2010 11:45, Stewart, Robert <Robert.Stewart@sig.com> wrote:
With a policy-based approach, Scott's library specifies which behavior it wants. It might need to provide interfaces to accept the other type, too, but that's a conscious choice.
I would definitely prefer a policy-based approach. And I think the interfaces for the "other type" would be fairly simple -- even built-in to the xints. Passing an xint to a nothrow_xint can be implicit, no different from a normal copy of a nothrow_xint, and even allows a noexcept move. nothrow_xint -> xint would work well as an explicit conversion that throws on special values. Actually, that latter conversion, if implicit, would essentially give the same result as the current library without the need for the explicit "Will throw if given NaN" on every single function.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 11:39 AM, Scott McMurray wrote:
Which isn't necessarily the best way to do it, and certainly isn't the only one. There is effectively zero runtime cost for XInt's exception-blocking mechanism, since the code used for it is only evaluated when an exception needs to be thrown.
There is, however, conceptual and infrastructure overhead from supporting it.
First, there's the fact I've previously mentioned than NaN weakens the invariant of the xint type. This requires extra effort in specifying functions that take and return xints. The most obvious evidence of this is the fact that almost every function in the library has the following line in its documentation: "Can throw: xint::not_a_number if n is Not-a-Number."
Sorry, but I can't agree. You, the person using the XInt library, don't have to write any code to handle NaNs, unless you either explicitly block exceptions or call one of the two functions that can normally return them. If some other code passes yours a NaN, or blocks exceptions before calling yours so that you get a NaN when you don't expect one, the library will throw the exception for you, the first time you use it in any function.
Second, the blocking is stateful. That means that if I write another library that accepts xints, I'll have to either write every function to work no matter the blocking mode or change it to what I want to work with. This state maintenance means bringing in the threading complications that are otherwise unnecessary.
Now that's an argument I can finally agree with. :-) Here's how I propose to solve it: make a "core" version of the integer class and functions, with no exception-blocking and no Not-a-Number value, in the namespace xint::core. Then make the main integer class and functions in namespace xint, with exception-blocking, the Not-a-Number value, and maybe infinity values. If you want to write something like an arbitrary floating-point library on top of XInt, you do so using the class and functions from xint::core, and deal solely with exceptions. If you just want to use XInt, with all the bells and whistles, you use the functions in the xint namespace. Will that satisfy your concerns? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyZ30ACgkQp9x9jeZ9/wSqHQCg9MJlErQZM8e5qes5kMKxk6vG Fl0AoL2QOD8ulWmxtSarzkEzeqe41iU7 =iLcA -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
An xint::integer which is +infinity or -infinity is more meaningful than one which is NaN.
Agreed -- but only slightly. It carries one additional bit's worth of meaning, the sign.
Even if you identify +infinity and -infinity as a single infinity, it should *still* mean something different from an NaN. You might group infinity into the class of NaNs, but that doesn't mean that every operation which results in an NaN may as well result in an infinity (signed or unsigned). 0/0 and sqrt(-1) should evaluate to an NaN (or throw); it would be unsettling to evaluate these as infinity.
I guess I'm not explaining myself very well. I was suggesting using the NaN value as infinity only where you need an infinity value. The only viable use I've seen suggested for infinity, in this library, is for unbounded intervals (which I'll address below).
At the very least, you can make more refined calculations and comparisons with +/-infinity (compared to NaN),
Do you have an example where this would make any noticeable difference in XInt?
Noticeable in what sense? 1/NaN is NaN; 1/+infinity is +0 (or 1/infinity is 0 if you don't want signed infinities and zeros). Assuming, of course, you allow calculations with NaNs.
Noticeable in the sense that it would make any difference to people using the library.
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
Since NaN compares false to anything else, good luck getting your intervals with NaN endpoints to work in any kind of generic setting ;)
Now that's a decent argument for infinity values. Though I'm still not sure whether they'd ever be used... is there a scientific or mathematical use of intervals that you can foresee this library being used for?
Not completely. There *are* the two functions that return Not-a-Number as part of their normal operation, not counting the string- and stream-reading functions. As I said on the rationales page of the documentation, I tried using Boost.Optional for those, but it made the library harder for people not already familiar with Boost.Optional to understand. An error code is an idiom that every C or C++ developer already understands well and knows how to deal with.
Which 2 functions? invmod and random_prime? These hardly seem like fundamental operations that necessitate this "invasion" into an otherwise pure big-integer interface ;)
I have to disagree, only because one of the main reasons people want to use a large-integer library is for cryptography, and those two functions *are* fundamental to that.
Returning optional values is precisely the raison d'etre of Boost.Optional, and you're ending up just building its functionality directly into the xint::integer class, so instead of xint::integer, we really have a boost::optional< xint::integer >. I don't like that :/ What did you find about Boost.Optional that was difficult for users to understand?
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use.
Keep going, one more valid argument might be enough to change my mind. :-)
The interface to invmod and random_prime should be built around the interface of xint::integer, not the other way around.
Sorry, not good enough. They're an important part of the interface, and their requirements affect it too.
Also, why does invmod always return an NaN on an invalid inverse, and not throw a blockable exception?
Because exceptions should, to my mind, be reserved for exceptional behavior -- things that should never happen under normal circumstances, and which demand special handling. Unless the specified modulus is prime, which cannot be trivially determined, invmod is *expected* to discover that some numbers have no inverse for it. That's neither unexpected nor exceptional, and depending on the application, doesn't automatically require special handling.
I sympathize with this reasoning. Generally speaking, if the user cannot trivially check the preconditions, it could make sense to return some kind of error condition rather than throwing.
We finally have agreement, at least on a small part of the problem. :-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxBCoACgkQp9x9jeZ9/wQReQCeKDNOZgtgk2bquSXc3/9PzkgZ VfYAoNX7FCbhD8QdT9YCrHI7CnFJaOqB =LEjB -----END PGP SIGNATURE-----
Chad Nelson wrote:
Someone-else-whose-name-was-elided wrote:
invmod and random_prime? These hardly seem like fundamental operations that necessitate this "invasion" into an otherwise pure big-integer interface ;)
I have to disagree, only because one of the main reasons people want to use a large-integer library is for cryptography, and those two functions *are* fundamental to that.
"One of the main reasons," not "the only" reason. Hence, cryptography functionality, which surely is more than those two functions, should be in a separate library.
Returning optional values is precisely the raison d'etre of Boost.Optional, and you're ending up just building its functionality directly into the xint::integer class, so instead of xint::integer, we really have a boost::optional< xint::integer >. I don't like that :/ What did you find about Boost.Optional that was difficult for users to understand?
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use.
This is being proposed as a Boost library. We can assume enough knowledge to use Boost.Optional, which isn't great.
The interface to invmod and random_prime should be built around the interface of xint::integer, not the other way around.
Sorry, not good enough. They're an important part of the interface, and their requirements affect it too.
That's not a sufficient reason for their inclusion in a big integer library. Rather, the big integer library needs to be designed well to support those functions and many others. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 07:13 AM, Stewart, Robert wrote:
I have to disagree, only because one of the main reasons people want to use a large-integer library is for cryptography, and those two functions *are* fundamental to that.
"One of the main reasons," not "the only" reason. Hence, cryptography functionality, which surely is more than those two functions, should be in a separate library.
I'm sure it should. But those two functions should not.
What did you find about Boost.Optional that was difficult for users to understand?
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use.
This is being proposed as a Boost library. We can assume enough knowledge to use Boost.Optional, which isn't great.
Knowledge and patience are two things that I've learned never to assume that a would-be programmer has.
The interface to invmod and random_prime should be built around the interface of xint::integer, not the other way around.
Sorry, not good enough. They're an important part of the interface, and their requirements affect it too.
That's not a sufficient reason for their inclusion in a big integer library. Rather, the big integer library needs to be designed well to support those functions and many others.
invmod is a basic modular math function. random_prime is a basic requirement for the most common reason people would want the library. They belong there, and they stay. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyAhIACgkQp9x9jeZ9/wQDpgCgwOXpAHKdTHqTcKF2HGJScJ8B HFYAoJtfsFU+tmdKRr3mykj7uSQyVdcY =Zd4D -----END PGP SIGNATURE-----
Chad Nelson wrote:
Returning optional values is precisely the raison d'etre of Boost.Optional, and you're ending up just building its functionality directly into the xint::integer class, so instead of xint::integer, we really have a boost::optional< xint::integer >. I don't like that :/ What did you find about Boost.Optional that was difficult for users to understand?
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use.
I can't buy this, given that pointer syntax is so prevalent in C++ (pointers, iterator, smart pointers). Boost.Optional is not complicated, very well documented, and very syntactically clean. Smart pointers are more difficult to understand, but the smart pointer library seems to be among the most popular Boost libraries (caveat: my only evidence to this latter claim is anecdotal). IMHO, any developer should be fine with a Boost.Optional return value (as long as you reference the documentation, and optionally provide a brief 2-sentence summary of Boost.Optional), and he/she might even appreciate the opportunity to learn the utility of another Boost library. This would remove the necessity of this special NaN value, noticeably simplifying the interface, implementation, and reasoning of this library. Sorry to be such a bear; I'm only trying to improve things. - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/30/2010 01:38 PM, Jeffrey Hellrung wrote:
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use.
I can't buy this, given that pointer syntax is so prevalent in C++ (pointers, iterator, smart pointers). [...]
I wish I could avoid buying it. My previous company wrote tools for developers, and I had to deal with a lot of customers who couldn't program their way out of a wet paper bag. Including ones that used C++, but probably shouldn't have.
IMHO, any developer should be fine with a Boost.Optional return value (as long as you reference the documentation, and optionally provide a brief 2-sentence summary of Boost.Optional), and he/she might even appreciate the opportunity to learn the utility of another Boost library.
Should, definitely. Would... well, we can hope. :-) That wouldn't necessarily stop them from using C++, or Boost, though -- that's why I wanted to make it as simple as possible.
This would remove the necessity of this special NaN value, noticeably simplifying the interface, implementation, and reasoning of this library.
Sorry to be such a bear; I'm only trying to improve things.
And I'm sorry if I seem to be a stubborn mule about it too. I'm not trying to be, no matter how it might look. :-) I just need a strong enough reason to change the design. I think Scott McMurray just provided such a reason; please see my reply to him for my proposed solution. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuyaDkACgkQp9x9jeZ9/wQxvQCg37pglFD5NaWfyxa+NPxd3xd4 AKEAoOsm+IbqObZu9rZonSISZwIajlYT =plll -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 03/30/2010 01:38 PM, Jeffrey Hellrung wrote:
That it acts like a pointer but isn't one. Less experienced developers often find even pointer syntax hard to master, and unfortunately, they are the majority of programmers. I was trying to make it as easy as possible for anyone, no matter what their level of experience, to use. I can't buy this, given that pointer syntax is so prevalent in C++ (pointers, iterator, smart pointers). [...]
I wish I could avoid buying it. My previous company wrote tools for developers, and I had to deal with a lot of customers who couldn't program their way out of a wet paper bag. Including ones that used C++, but probably shouldn't have.
IMHO, any developer should be fine with a Boost.Optional return value (as long as you reference the documentation, and optionally provide a brief 2-sentence summary of Boost.Optional), and he/she might even appreciate the opportunity to learn the utility of another Boost library.
Should, definitely. Would... well, we can hope. :-) That wouldn't necessarily stop them from using C++, or Boost, though -- that's why I wanted to make it as simple as possible.
If all Boost libraries catered to the lowest common denominator "developer"...well...Boost.MPL and Boost.Fusion might be the first to go... ;) In all seriousness, though, usability is certainly important, but you have to draw the line somewhere. I think if you're submitting your library for review to Boost, you should embrace what Boost makes available to you.
This would remove the necessity of this special NaN value, noticeably simplifying the interface, implementation, and reasoning of this library.
Sorry to be such a bear; I'm only trying to improve things.
And I'm sorry if I seem to be a stubborn mule about it too. I'm not trying to be, no matter how it might look. :-) I just need a strong enough reason to change the design. I think Scott McMurray just provided such a reason; please see my reply to him for my proposed solution.
Yes: Separate the NaN stuff from the rest of the fundamental operations (arithmetic operations, etc.), and, if you're really tied to it, add it back in a wrapper class. However, I still maintain that this NaN framework, as is, is not fundamental to any operation, and it's only motivation is to make the return values of no-more-than TWO crytographic-specific functions "convenient" for developers who have difficulty with pointer syntax (even though, for those developers who have no problem with pointer syntax (i.e. me) it's less convenient). Am I exaggerating? An NaN framework which I actually consider useful would be one which is always signaling (i.e., throwing, even upon creation), or always quiet (NaNs are propagated), or even runtime configurable with your exception blocking idiom (which I think is useful). A "half-signaling" NaN (quietly manufactured but noisy when touched) seems to me a near-useless middle ground. Also, you shouldn't be looking for a "strong reason to change the design". Look for the best design, regardless of what the current design is. - Jeff
On 31 March 2010 11:59, Jeffrey Hellrung <jhellrung@ucla.edu> wrote:
An NaN framework which I actually consider useful would be one which is always signaling (i.e., throwing, even upon creation), or always quiet (NaNs are propagated),
I have a sketch of a way to offer both here: http://lists.boost.org/Archives/boost/2010/03/164346.php
A "half-signaling" NaN (quietly manufactured but noisy when touched) seems to me a near-useless middle ground.
This is a good point. When the option of a policy-based scheme for exception control was brought up I just sort of assumed on principle that it would somehow be useful. Can anyone give an example where a middle ground would be best?
on 31.03.2010 at 20:15 Scott McMurray wrote :
I have a sketch of a way to offer both here: http://lists.boost.org/Archives/boost/2010/03/164346.php
i thought a while and came to a conclusion that making different flavors of xint as distinct types or different specializations or even policy based implementation is a good idea indeed particularly having xint::raw_integer and xint::integer (exception blocking and NaN are here) makes sense these two (possibly) implicitly share the value for run time efficiency (for fast convertions of one to another) then if 'op(xint::raw_integer)' wraps 'op(xint::integer)' the former checks for NaN and throws (otherwise 'op(xint::integer)' throws itself) if 'op(xint::integer)' wraps 'op(xint::raw_integer)' then the former catches the possible exception and returns NaN if exceptions are blocked but this case seems less efficient actually there are some things to think of
A "half-signaling" NaN (quietly manufactured but noisy when touched) seems to me a near-useless middle ground. This is a good point. When the option of a policy-based scheme for exception control was brought up I just sort of assumed on principle that it would somehow be useful. Can anyone give an example where a middle ground would be best?
i vote for quiet NaN since operations are throwing already by default but actually the original design was sane too for example xint::integer i; while ((i = foo())==NaN) //doing some important work ask_user_what_to_do(); //failed! worth it to try again? i think this is conscious was NaN a signaling one this would not be possible but if i try accidentally to use a NaN in an operation it throws like in the following example xint::integer i = bar(a); //fails sometimes because of its nature //if (i==NaN) do_something(); //oh! forgot to check if bar() i *= 2; //succeeded! here to indicate that 'bar()' may fail not as an exceptional situation but due to its nature we say that it returns NaN was NaN a signaling beast 'bar()' would throw anyway -- exception missuse -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/31/2010 01:16 PM, DE wrote:
i vote for quiet NaN since operations are throwing already by default but actually the original design was sane too for example
xint::integer i; while ((i = foo())==NaN) //doing some important work ask_user_what_to_do(); //failed! worth it to try again?
i think this is conscious [...]
If you mean, you think it was a conscious decision on my part: yes, you're right. That's how I intended it to be used. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuz5I0ACgkQp9x9jeZ9/wR3gwCghYN0mKa6G/FGFpOmkhTH5taU EsQAoOzOfoivPzD5QmwBsZ3rTm5uzP7U =tsmi -----END PGP SIGNATURE-----
on 01.04.2010 at 4:10 Chad Nelson wrote :
i vote for quiet NaN since operations are throwing already by default but actually the original design was sane too for example
xint::integer i; while ((i = foo())==NaN) //doing some important work ask_user_what_to_do(); //failed! worth it to try again?
i think this is conscious [...]
If you mean, you think it was a conscious decision on my part: yes, you're right. That's how I intended it to be used. indeed my point was that the use case described in the example seems to be perfectly conscious
our views on this library appear to be curiously close... -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/01/2010 12:13 PM, DE wrote:
i think this is conscious [...]
If you mean, you think it was a conscious decision on my part: yes, you're right. That's how I intended it to be used.
indeed my point was that the use case described in the example seems to be perfectly conscious
our views on this library appear to be curiously close...
"Great minds think alike." Or, as my wife tartly replies when I use that line in front of her: "small minds seldom differ." ;-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku1LOgACgkQp9x9jeZ9/wTnuwCggW4RKVwu5ycGwy0Rg8cZwgzi +1sAniT4QuroTgafcT7/6+7MnWDQS+Hl =993Y -----END PGP SIGNATURE-----
On 31 March 2010 20:10, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
If you mean, you think it was a conscious decision on my part: yes, you're right. That's how I intended it to be used.
The worry I have is with compound expressions. It looks nice for a single function call, but compare these two lines: w = x/y*z; w = x*y/z; With a signalling NaN, their exceptional behaviour is drastically different. This is another example of the advantage of the split types: If x, y, and z are nothrow_xints, the type of w is what decides whether the statement will throw. Alternatively, if x, y, and z are finite_xints, both statements will throw and never touch w.
on 01.04.2010 at 23:59 Scott McMurray wrote :
The worry I have is with compound expressions. It looks nice for a single function call, but compare these two lines:
w = x/y*z; w = x*y/z;
With a signalling NaN, their exceptional behaviour is drastically different.
This is another example of the advantage of the split types: If x, y, and z are nothrow_xints, the type of w is what decides whether the statement will throw. Alternatively, if x, y, and z are finite_xints, both statements will throw and never touch w.
they are throwing anyway whether or not exceptions are blocked blocking of exceptions allows you to check explicitly if a number of operations like division succeeds that number of operations is relatively small so you don't need to check result of every operations but blindly writing such expressions is irrelevant to the nan behaviour because both eventually throw we are spinning and spinning around the same thing for a week is there an end? -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
DE wrote:
on 01.04.2010 at 23:59 Scott McMurray wrote :
The worry I have is with compound expressions. It looks nice for a single function call, but compare these two lines:
w = x/y*z; w = x*y/z;
With a signalling NaN, their exceptional behaviour is drastically different.
This is another example of the advantage of the split types: If x, y, and z are nothrow_xints, the type of w is what decides whether the statement will throw. Alternatively, if x, y, and z are finite_xints, both statements will throw and never touch w.
they are throwing anyway whether or not exceptions are blocked blocking of exceptions allows you to check explicitly if a number of operations like division succeeds
I was under the impression that "w = x*y/z" wouldn't throw under the current NaN behavior... [...]
but blindly writing such expressions is irrelevant to the nan behaviour because both eventually throw
It is certainly relevant since varying when a certain sequence of operations throws alters the state of the program at the catch site! This is why I prefer "throw as early as possible", since you're not overwriting your variables (e.g., w) with NaNs, hence you have more information available to you. And if you don't want to throw as early as possible (e.g., because exceptions are blocked, or that's what the policy parameter dictates), then don't throw at all.
we are spinning and spinning around the same thing for a week is there an end?
How the library handles exceptions (or doesn't) is an important part of the interface. - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/01/2010 03:59 PM, Scott McMurray wrote:
If you mean, you think it was a conscious decision on my part: yes, you're right. That's how I intended it to be used.
The worry I have is with compound expressions. It looks nice for a single function call, but compare these two lines:
w = x/y*z; w = x*y/z;
With a signalling NaN, their exceptional behaviour is drastically different.
That shouldn't be a problem with the new design. If I go with the exception-blocker system, I've been convinced that the not_a_number exception should be blockable too, so if exceptions are blocked and you get a NaN, it will propagate instead of throwing. If they're not blocked, the library will still throw as soon as it sees one. And of course, if you're using the core integer, or whatever it's eventually called, there won't be a NaN value to worry about.
This is another example of the advantage of the split types: If x, y, and z are nothrow_xints, the type of w is what decides whether the statement will throw. Alternatively, if x, y, and z are finite_xints, both statements will throw and never touch w.
I haven't had time to delve into your design description (a combination of real life and professional life have gotten in the way), but I think I see how that would work. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku1M7oACgkQp9x9jeZ9/wTPKACcCwT7EjAn/XAOF8q6dMC+hIUt xq0An1Fv2UwL7HGjnktFd/50LtPd6UMW =mrSD -----END PGP SIGNATURE-----
I've mostly missed the train on this, but if I could quickly bring up a couple of comments from earlier in the thread(s). Paraphrasing: 1. infinity is not a number 2. something about 1/inf and infinity stuff being INEXACT my responses: 2. 1/inf = 0 *IS* exact. It is inexact while approaching inf, but finally exactly 0 'at' infinity. 1. depends on your definition of 'number'. You can definitely say infinity is not an integer. (NaI ?) But for a reasonable definition of 'number' infinity IS a number (or more accurately, a bunch of numbers, as there is a bunch of infinities). The best definition, that I know of for number is "The answer to the question: 'how many?' " and infinity fulfills that definition. And now some background, and why I bring this up - Many moons ago when the web was young-ish, I took Gottlob Frege as a 'web-identity' (back when alta-vista was a search engine and Yahoo was king and wanted all your personal info, etc...), and as a habit I have carried it around ever since. Call me Gottlob on the web vs Tony (my real name) and I usually don't even notice. Anyhow, the real Gottlob Frege was a turn of the century Mathematician/Philosopher. He wrote an excellent book called "The Foundations of Arithmetic" - one of my favorites. It mainly attempted to answer the question "what is a number". The first answer is that it is the answer to the question 'how many' (for mathematicians this is now called 'cardinality'). After that answer the book moves forward and gets quite interesting and complicated. Anyhow, whenever anyone says infinity is not a number, I feel compelled to reply that it answers the question 'how many", and thus is a number. ( Typically the more precise question is 'how many integers are there" and the answer being aleph0 or 'aleph-not' - the first infinity). Anyhow, feel free to ignore this. I'm not actually taking sides on whether/how you treat NaN/infinity - sounds like you may be able to avoid it altogether. P.S. for the logicians out there - he was also basically the first to introduce rules for quantifiers "For all", "there exists at least one", etc; And for all those wearing programmer-hats instead of their mathematician-hats: I also consider Gottlob Frege the father of 'duck-typing'. A man before his time... Tony
On 2 April 2010 02:48, Gottlob Frege <gottlobfrege@gmail.com> wrote:
2. 1/inf = 0 *IS* exact. It is inexact while approaching inf, but finally exactly 0 'at' infinity.
Arguably, since we're dealing in round-toward-0 division, even 1/2 is exactly 0. The question I have then is whether at infinity the remainder somehow manages to disappear. Care to shed some light on that? \forall x > 1, divrem(1,x) = (0, 1), so as x -> inf, it'd still be (0, 1). I think the idea of "inexact" zeros came from the idea that 1/0 would give infinity, where you'd then want a "-0" so that 1/-0 can give negative infinity (like in floating point). I think I was advocating that at one point, but have since some to my senses.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 02:48 AM, Gottlob Frege wrote:
I've mostly missed the train on this, but if I could quickly bring up a couple of comments from earlier in the thread(s). Paraphrasing:
1. infinity is not a number
[Other point removed, as it was addressed by Scott McMurray]
my responses: [...]
1. depends on your definition of 'number'. You can definitely say infinity is not an integer. (NaI ?) But for a reasonable definition of 'number' infinity IS a number (or more accurately, a bunch of numbers, as there is a bunch of infinities).
The best definition, that I know of for number is "The answer to the question: 'how many?' " and infinity fulfills that definition.
Yes, by that definition it's definitely a number. But it's not a *countable* number, which is the definition that I was using. :-) In relation to the XInt library, I'd say that an infinity value should also be counted as a not-a-number, in that an is_nan function should return true for it -- it's not something that can be calculated with, generally.
And now some background, and why I bring this up [...]
Thanks for the interesting information.
Anyhow, feel free to ignore this. I'm not actually taking sides on whether/how you treat NaN/infinity - sounds like you may be able to avoid it altogether. [...]
If I don't add an infinity value, I could. I'm leaning toward adding one (with sign), but it will act exactly like a NaN except for comparisons. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2LNYACgkQp9x9jeZ9/wTd7QCfS8VYBIPytFY3i8mvpiiUY5O4 HAgAn25gK/HQkEvf9DB2PUTcRaQqDC5X =W8tS -----END PGP SIGNATURE-----
On 2 April 2010 13:43, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Yes, by that definition it's definitely a number. But it's not a *countable* number, which is the definition that I was using. :-) In relation to the XInt library, I'd say that an infinity value should also be counted as a not-a-number, in that an is_nan function should return true for it
Well, iirc some infinities are countable and others are not, but... I think is_nan(Inf) should be false, but is_finite(Inf) should also be false.
it's not something that can be calculated with, generally.
[...]
If I don't add an infinity value, I could. I'm leaning toward adding one (with sign), but it will act exactly like a NaN except for comparisons.
Actually, you *can* calculate with infinity. That's the reason for having it separate from NaN, and why it needs a sign. Any operation with NaN gives a NaN, but at least the following for Infs don't give NaNs (for any x, y where is_finite(x) && !is_nan(y)): -(Inf) => -Inf -(-Inf) => Inf x + Inf => Inf x - Inf => -Inf x % Inf => x Inf + Inf => Inf -Inf - Inf => -Inf x < Inf => true x > -Inf => true y <= Inf => true y >= -Inf => true x / Inf => 0 x / -Inf => 0 if (y != 0) y * Inf => sign(y)Inf if (y != 0) y * -Inf => sign(-y)Inf But the indeterminate forms do, of course, give NaNs: Inf - Inf => NaN -Inf + Inf => NaN 0 * Inf => NaN 0 * -Inf => NaN Inf / Inf => NaN Inf / -Inf => NaN Inf % y => NaN Hopefully that'll make you lean further :P
on 02.04.2010 at 22:07 Scott McMurray wrote :
Actually, you *can* calculate with infinity. That's the reason for having it separate from NaN, and why it needs a sign. Any operation with NaN gives a NaN, but at least the following for Infs don't give NaNs (for any x, y where is_finite(x) && !is_nan(y)):
-(Inf) => -Inf -(-Inf) => Inf x + Inf => Inf x - Inf => -Inf x % Inf => x Inf + Inf => Inf -Inf - Inf => -Inf x < Inf => true x > -Inf => true y <= Inf => true y >= -Inf => true x / Inf => 0 x / -Inf => 0 if (y != 0) y * Inf => sign(y)Inf if (y != 0) y * -Inf => sign(-y)Inf
But the indeterminate forms do, of course, give NaNs:
Inf - Inf => NaN -Inf + Inf => NaN 0 * Inf => NaN 0 * -Inf => NaN Inf / Inf => NaN Inf / -Inf => NaN Inf % y => NaN
i can not imagine any circumstances under which this stuff would be useful can you? i see main applications of a big int lib as convenient implementation of crypto algorithms, compression algos and building an arbitrary precision floating (or fixed) point environment floating/fixed points built on top of a big int deal with infs and all that stuff beside the big int and remaining two cases don't need infs at all so what's on *your* mind? apart from that the presence of infs complicates things -- both the conception and the implementation -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
On 2 April 2010 14:31, DE <satan66613@yandex.ru> wrote:
i can not imagine any circumstances under which this stuff would be useful can you?
In crypto and compression a non-finite result is never useful, so people writing in those domains would probably use what I call a finite_xint that throws instead of generating such special values. For a fixed-point numeric application, though, it's plausible that the person would rather get out any information that does calculate properly, and just be able to know at the end whether the result is precise or not. Certainly people wanting them to replace current floating-point code would likely rather have them act like the floating point values did, and not throw exceptions, which means defining reasonable semantics for operations on special values.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 02:31 PM, DE wrote:
Scott McMurray wrote :
Actually, you *can* calculate with infinity. That's the reason for having it separate from NaN, and why it needs a sign. [...]
i can not imagine any circumstances under which this stuff would be useful can you?
I can see some very limited uses for calculations with infinities, mostly involving endpoints in a range.
i see main applications of a big int lib as convenient implementation of crypto algorithms, compression algos and building an arbitrary precision floating (or fixed) point environment floating/fixed points built on top of a big int deal with infs and all that stuff beside the big int and remaining two cases don't need infs at all so what's on *your* mind?
I'm not sure what Scott has in mind, but there's one application you haven't mentioned: simply using it as a much larger capacity integer, as the Fibonacci example in the documentation demonstrates. Something like that couldn't be calculated with the built-in integer types without a lot of work-arounds, and would likely be problematic with floating-point types as well, depending on their sizes (I haven't looked at floats and doubles in many years, so I can't comment intelligently on them).
apart from that the presence of infs complicates things -- both the conception and the implementation
Only slightly. Not enough to give me pause, if the details are already known. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2PgYACgkQp9x9jeZ9/wRKkwCgsmE3nMiP63t5vEStHuLZh1bB 1kEAoMgvhQK6oRmhONXA2ijUL44QtkV+ =q32r -----END PGP SIGNATURE-----
Scott McMurray wrote:
On 2 April 2010 13:43, Chad Nelson <chad.thecomfychair@gmail.com> wrote: [...] I think is_nan(Inf) should be false, but is_finite(Inf) should also be false.
Well is_finite(NaN) should be false as well; is_infinity would be a more appropriate predicate.
it's not something that can be calculated with, generally.
[...]
If I don't add an infinity value, I could. I'm leaning toward adding one (with sign), but it will act exactly like a NaN except for comparisons.
Actually, you *can* calculate with infinity. That's the reason for having it separate from NaN, and why it needs a sign. Any operation with NaN gives a NaN, but at least the following for Infs don't give NaNs (for any x, y where is_finite(x) && !is_nan(y)):
-(Inf) => -Inf -(-Inf) => Inf x + Inf => Inf x - Inf => -Inf x % Inf => x Inf + Inf => Inf -Inf - Inf => -Inf x < Inf => true x > -Inf => true y <= Inf => true y >= -Inf => true x / Inf => 0 x / -Inf => 0 if (y != 0) y * Inf => sign(y)Inf if (y != 0) y * -Inf => sign(-y)Inf
But the indeterminate forms do, of course, give NaNs:
Inf - Inf => NaN -Inf + Inf => NaN 0 * Inf => NaN 0 * -Inf => NaN Inf / Inf => NaN Inf / -Inf => NaN Inf % y => NaN
Hopefully that'll make you lean further :P
Don't forget (assuming a single unsigned 0): x / 0 => NaN and I think you'd want Inf to compare equal with itself (unlike NaN, which does not compare equal with itself...and doesn't compare unequal with itself, either :/ ). This is of secondary consideration to the core set of algorithms that should just throw whenever something bad happens (e.g., division by 0), though. Another topic: Chad, how natural is it, implementation-wise, to have a signed zero? I'm guessing you have a sign bit, leading naturally to either providing both a +0 or a -0, or ensuring after each operation that -0 is normalized to +0. What are the arguments against a signed zero? Is it possible to simply be agnostic to the sign bit when the mantissa is 0? - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 02:32 PM, Jeffrey Hellrung wrote:
Don't forget (assuming a single unsigned 0):
x / 0 => NaN
Eh? I thought we'd decided that anything divided by zero, other than zero itself, was infinity (or negative infinity, if x is negative)?
and I think you'd want Inf to compare equal with itself (unlike NaN, which does not compare equal with itself...and doesn't compare unequal with itself, either :/ ).
Yes, the infinity values will be comparable to anything (except NaN, of course), and will do what you logically expect them to.
This is of secondary consideration to the core set of algorithms that should just throw whenever something bad happens (e.g., division by 0), though.
Of course. :-)
Another topic: Chad, how natural is it, implementation-wise, to have a signed zero? I'm guessing you have a sign bit, leading naturally to either providing both a +0 or a -0, or ensuring after each operation that -0 is normalized to +0.
It wouldn't be a problem to implement it, and yes, I do have a sign bit (or rather, a sign Boolean, but that's essentially the same thing).
What are the arguments against a signed zero?
That there's no need for it in an integer library. I may have gotten some things wrong, but I don't think anyone refuted that part. Quoting from my earlier message on the subject: - ----------------8<---------------- Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero. - ----------------8<---------------- As such, there's no real need for it in XInt.
Is it possible to simply be agnostic to the sign bit when the mantissa is 0?
Isn't that the same as saying that -0 is identical to +0? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2QSMACgkQp9x9jeZ9/wR6VgCfeIu9Kjt1ZEAwMBXpHLGs1vX/ VdkAoKxtlp4xAHxknrlg+OKB5QQMjSwA =xi4n -----END PGP SIGNATURE-----
On Fri, 2 Apr 2010, Chad Nelson wrote:
On 04/02/2010 02:32 PM, Jeffrey Hellrung wrote:
What are the arguments against a signed zero?
That there's no need for it in an integer library. I may have gotten some things wrong, but I don't think anyone refuted that part. Quoting from my earlier message on the subject:
- ----------------8<---------------- Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero. - ----------------8<----------------
As such, there's no real need for it in XInt.
I tend to agree. In a "real" valued float, there are cases where you want to distinguish a value approaching 0 from the positive or negative. With integers, there are no infinitesimals and hence no need for a distinction. The integer zero is simply the only integer between +1 and -1; it also happens to be the additive identity, and there is no other (hence -0 has no meaning). - Daniel
Chad Nelson wrote:
On 04/02/2010 02:32 PM, Jeffrey Hellrung wrote:
Don't forget (assuming a single unsigned 0):
x / 0 => NaN
Eh? I thought we'd decided that anything divided by zero, other than zero itself, was infinity (or negative infinity, if x is negative)?
Of course you can define whatever arithmetic you like, but I think it makes more sense for products and quotients of like signs being positive, of opposite signs being negative, and anything involving (unsigned) zero giving either (unsigned) zero or NaN. [...]
Another topic: Chad, how natural is it, implementation-wise, to have a signed zero? I'm guessing you have a sign bit, leading naturally to either providing both a +0 or a -0, or ensuring after each operation that -0 is normalized to +0.
It wouldn't be a problem to implement it, and yes, I do have a sign bit (or rather, a sign Boolean, but that's essentially the same thing).
What are the arguments against a signed zero?
That there's no need for it in an integer library. [...] As such, there's no real need for it in XInt.
I was looking more for objections based purely on logical inconsistencies. Can you think of any?
Is it possible to simply be agnostic to the sign bit when the mantissa is 0?
Isn't that the same as saying that -0 is identical to +0?
If you don't have any infinities or NaNs to worry about, yes! For this case, I'm just suggesting you may not have to normalize zeros if -0 behaves exactly the same as +0. But it still may be useful to distinguish between them for libraries built on top of the core implementation. An arbitrary-precision floating point type may make a distinction between +0 and -0, and it would be convenient if the underlying integer core allowed this distinction naturally. Additionally, in the presence of an infinity value, you can then say x / +0 = +infinity x / -0 = -infinity if x > 0. Other than that (and maybe a few more exceptional cases), +0 and -0 behave identically. This has the (minute) advantage that you have simpler sign relationships on divisions: + / + = - / - = + + / - = - / + = - NaN / x = x / NaN = NaN This really only makes sense if your natural representations for +0 and -0 naturally behave identically, thus incurring no overhead (and perhaps simplifying implementation by avoiding a renormalization to "+0"). What do you think? - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 03:43 PM, Jeffrey Lee Hellrung, Jr. wrote:
Don't forget (assuming a single unsigned 0):
x / 0 => NaN
Eh? I thought we'd decided that anything divided by zero, other than zero itself, was infinity (or negative infinity, if x is negative)?
Of course you can define whatever arithmetic you like, but I think it makes more sense for products and quotients of like signs being positive, of opposite signs being negative, and anything involving (unsigned) zero giving either (unsigned) zero or NaN.
You've completely lost me. Zero doesn't have a sign, so anything divided by zero would have to take its sign from 'x'.
What are the arguments against a signed zero?
That there's no need for it in an integer library. [...] As such, there's no real need for it in XInt.
I was looking more for objections based purely on logical inconsistencies. Can you think of any?
Several. To begin with, would there be different values for positive zero, negative zero, and "true" zero? If not, zero would have to be assumed to be positive zero, and that's a slight logical inconsistency right there. And if all two or three zero types evaluated the same, how would you detect a positive zero or a negative zero? The sign() function wouldn't do it; it's spec'd to return zero for zeros, and it would break a lot of things in the code if that were changed. Comparison functions would see them as the same too. You'd have to add a special function just to detect the sign on a zero. To make a sensible signed-zero value work, I'd have to make up portions of the math, or adopt them from floating-point stuff even though that doesn't make sense here. It gets very messy and arbitrary, and I'd rather avoid it.
Is it possible to simply be agnostic to the sign bit when the mantissa is 0?
Isn't that the same as saying that -0 is identical to +0?
If you don't have any infinities or NaNs to worry about, yes! For this case, I'm just suggesting you may not have to normalize zeros if -0 behaves exactly the same as +0. But it still may be useful to distinguish between them for libraries built on top of the core implementation. An arbitrary-precision floating point type may make a distinction between +0 and -0, and it would be convenient if the underlying integer core allowed this distinction naturally. [...]
That's about the only argument that had any chance of swaying me. :-)
What do you think?
That I still don't see any way to cleanly and logically implement it. The aforementioned arbitrary-precision floating point package will just have to handle that itself, maybe by making an extremely small but non-zero value and calling it negative zero. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2knYACgkQp9x9jeZ9/wRpYgCfU7212WL2DPOBjqYVZfieb408 +eUAnjs9uxudwZEBHeufFwfNn7qxN5xD =hHEW -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 04/02/2010 03:43 PM, Jeffrey Lee Hellrung, Jr. wrote:
Don't forget (assuming a single unsigned 0):
x / 0 => NaN Eh? I thought we'd decided that anything divided by zero, other than zero itself, was infinity (or negative infinity, if x is negative)? Of course you can define whatever arithmetic you like, but I think it makes more sense for products and quotients of like signs being positive, of opposite signs being negative, and anything involving (unsigned) zero giving either (unsigned) zero or NaN.
You've completely lost me. Zero doesn't have a sign, so anything divided by zero would have to take its sign from 'x'.
Like I said, you can define whatever arithmetic you want. I prefer to extend the semantics that floats have, where x/+0 = +infinity and x/-0 = -infinity (if x > 0). If you have a single unsigned 0, it is the identification of the +0 and -0 float-counterparts, so x/0 should be NaN, since it *could* be either +infinity or -infinity in floats. (However, if you allow signed 0s, then you don't have this problem.)
What are the arguments against a signed zero? That there's no need for it in an integer library. [...] As such, there's no real need for it in XInt. I was looking more for objections based purely on logical inconsistencies. Can you think of any?
Several. To begin with, would there be different values for positive zero, negative zero, and "true" zero? If not, zero would have to be assumed to be positive zero, and that's a slight logical inconsistency right there.
Let's just assume that if someone constructs "zero" directly, it's +0. Although I'm betting it doesn't make any difference. You seem to really want some kind of one-to-one identification between integers and xint::integer objects, but I implore you to step back a moment and relax that requirement. Your implementation naturally suggests two representations of zero, and I'm arguing to keep those distinct representations available for derived/wrapper classes, and for simplicity of implementation. I have yet to see where this makes a difference in the core interface or complicates the internal implementation.
And if all two or three zero types evaluated the same, how would you detect a positive zero or a negative zero? The sign() function wouldn't do it; it's spec'd to return zero for zeros, and it would break a lot of things in the code if that were changed. Comparison functions would see them as the same too. You'd have to add a special function just to detect the sign on a zero.
Yes, sign() should return (the int) 0 for either +0 or -0, and yes, you'd have to add one single itty-bitty function to get whether the underlying zero had a + or - sign. That doesn't sound very difficult or surprising. float +0 and -0 behave the same way.
To make a sensible signed-zero value work, I'd have to make up portions of the math, or adopt them from floating-point stuff even though that doesn't make sense here.
I don't know what you mean here. Isn't the arithmetic involving zeros fairly straightforward, signed or not?
It gets very messy and arbitrary, and I'd rather avoid it.
Well, one of my questions was, phrased another way: *Does* it *really* get messy and arbitrary? Does it really make a difference if your zeroed mantissa has a + or - sign in front of it, implementation-wise? Maybe I'm thinking a bit naively, but if you add an integer to +0, any sane implementation will give the same result if you instead added -0, except if the result itself was +/-0 (in which case, it doesn't make any difference). And certainly, interface-wise, other than that special "sign-of-zero" function, it makes no difference whether, underneath, your zero has a + or - sign.
Is it possible to simply be agnostic to the sign bit when the mantissa is 0? Isn't that the same as saying that -0 is identical to +0? If you don't have any infinities or NaNs to worry about, yes! For this case, I'm just suggesting you may not have to normalize zeros if -0 behaves exactly the same as +0. But it still may be useful to distinguish between them for libraries built on top of the core implementation. An arbitrary-precision floating point type may make a distinction between +0 and -0, and it would be convenient if the underlying integer core allowed this distinction naturally. [...]
That's about the only argument that had any chance of swaying me. :-)
What do you think?
That I still don't see any way to cleanly and logically implement it.
Maybe you already have and just haven't realized it ;)
The aforementioned arbitrary-precision floating point package will just have to handle that itself, maybe by making an extremely small but non-zero value and calling it negative zero.
*That* seems "messy and arbitrary" ;) - Jeff
let me try to summarize arguments for infinities and other stuff assumption: it'll be convenient if a thing, upon which some another thing would be built, provide natively some features which would be useful only in the implementation of that other thing built on top of it this looks like some kind of an inversion or degeneralization sure the prime thing shoud provied complete set of functionality with wich any other extension can be built but since the prime thing is not generally aware of other things which could be built around it it should not provide any feature which would *possibly* be useful assumption: there should be signed zeros like that of ieee floating point numbers floating point numbers is the generalization of integers but not the other way round i think you forgot that trying to make integer behavior similar to that of floating point numbers is wrong imho that's why you have no sound argument for this -- because it's not natural for ints assumption: the presence of (signed) infinities would provide ultimate set of relationships of the domain entities as well as consistence of some operations' behavior since there was no example of an application of infinities except interval arithmetics i see no reason to provide it considering intervals if we use floating point numbers we can define an interval as (-inf; +inf) here a finite number of distinct values fill the interval when we use ordinary ints we define it possibly as (-MAX_INT; MAX_INT) or even [-MAX_INT; MAX_INT] (including endpoints) notice lack of infinities here here as well we have finite number of values filling the interval, namely 2^(sizeof(int)*8) so to be consistent we should define an interval for xint as (-SaneBigValue; SaneBigValue) only this way the interval would be useful (considering finite memory, time etc.) the provision of infinities would render such interval unuseful since there would be a strong possibility of popping of an unrepresentable number during computations (unrepresentable due to memory limitations) moreover in that situation it would be inexact -> no need to use the lib at all, better use floating point numbers so i still don't see any sane application of infinities in a integer domain and hence the need of infinities at all -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/03/2010 06:11 AM, DE wrote:
let me try to summarize arguments for infinities and other stuff
assumption: it'll be convenient if a thing, upon which some another thing would be built, provide natively some features which would be useful only in the implementation of that other thing built on top of it
this looks like some kind of an inversion or degeneralization sure the prime thing shoud provied complete set of functionality with wich any other extension can be built but since the prime thing is not generally aware of other things which could be built around it it should not provide any feature which would *possibly* be useful
In general, I agree. But if XInt is accepted into Boost, there will *definitely* be an arbitrary-precision real type built onto it. I may do it myself, if no one else steps up, but I'm fairly certain that someone will -- it's a perfect GSoC project, for example. As such, planning for it isn't really degeneralization in this particular case.
assumption: there should be signed zeros like that of ieee floating point numbers
floating point numbers is the generalization of integers but not the other way round i think you forgot that trying to make integer behavior similar to that of floating point numbers is wrong imho that's why you have no sound argument for this -- because it's not natural for ints
Exactly my thoughts. But if it does make life noticeably easier for whoever implements the real type, and doesn't cause any problems with the integer type, I'm willing to entertain the idea.
assumption: the presence of (signed) infinities would provide ultimate set of relationships of the domain entities as well as consistence of some operations' behavior
since there was no example of an application of infinities except interval arithmetics i see no reason to provide it [...]
The more I think about it, the less decided I am over it. I believe there are a few cases where it would be useful to have infinities, at least for comparisons, but I can't think of any concrete examples and no one else has provided any. And it does make for more work, both for me in writing it, and (slightly) for the computer when using it. At the moment, I'm inclined to leave it out of the library for now, at least until someone can show an application where it would be more useful than the Not-a-Number value. But there's still at least a few days for people to make their cases before I have to make a decision. And we can always revisit the idea after the 1.0 release is stable. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku3xJcACgkQp9x9jeZ9/wQDBwCgp1aMiGzNM0/umLyMiqoaJYWC NroAn1f9wN2narrDVbKOUyuHE2l854PT =qFCs -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 04/03/2010 06:11 AM, DE wrote: [...]
assumption: it'll be convenient if a thing, upon which some another thing would be built, provide natively some features which would be useful only in the implementation of that other thing built on top of it
this looks like some kind of an inversion or degeneralization sure the prime thing shoud provied complete set of functionality with wich any other extension can be built but since the prime thing is not generally aware of other things which could be built around it it should not provide any feature which would *possibly* be useful
In general, I agree. But if XInt is accepted into Boost, there will *definitely* be an arbitrary-precision real type built onto it. I may do it myself, if no one else steps up, but I'm fairly certain that someone will -- it's a perfect GSoC project, for example. As such, planning for it isn't really degeneralization in this particular case.
Chad gave the practical reason. But perhaps more fundamentally, the information (the sign bit) is *there*, and I'd like it to be usable, even if the mantissa is zero. If you don't want to distinguish between -0 and +0 (and I don't see why you would when strictly in the domain of integers), then you won't ever notice there are 2 different representations.
assumption: there should be signed zeros like that of ieee floating point numbers [...] that's why you have no sound argument for this -- because it's not natural for ints
Exactly my thoughts. But if it does make life noticeably easier for whoever implements the real type, and doesn't cause any problems with the integer type, I'm willing to entertain the idea.
And it *is* natural for sign + magnitude (which I had been slightly mistakenly calling "sign + mantissa") representations. If builtin integers were based on a sign + magnitude or 1's complement representation, we'd already be used to dealing with signed zeros: http://en.wikipedia.org/wiki/Signed_number_representations I'm guessing it's simpler in hardware to use 2's complement, but we're pretty much stuck with sign + magnitude AFAICT for an unbounded integer library.
assumption: the presence of (signed) infinities would provide ultimate set of relationships of the domain entities as well as consistence of some operations' behavior
since there was no example of an application of infinities except interval arithmetics i see no reason to provide it [...]
The more I think about it, the less decided I am over it. I believe there are a few cases where it would be useful to have infinities, at least for comparisons, but I can't think of any concrete examples and no one else has provided any. And it does make for more work, both for me in writing it, and (slightly) for the computer when using it.
At the moment, I'm inclined to leave it out of the library for now, at least until someone can show an application where it would be more useful than the Not-a-Number value. But there's still at least a few days for people to make their cases before I have to make a decision. And we can always revisit the idea after the 1.0 release is stable.
True, infinities would have somewhat specialized applications, but it makes some sense (to me) to include it if you're already going to waste a byte on an NaN flag anyway. - Jeff
On Sat, Apr 3, 2010 at 7:27 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
Chad Nelson wrote:
On 04/03/2010 06:11 AM, DE wrote:
[...]
assumption: it'll be convenient if a thing, upon which some another thing would be built, provide natively some features which would be useful only in the implementation of that other thing built on top of it
this looks like some kind of an inversion or degeneralization sure the prime thing shoud provied complete set of functionality with wich any other extension can be built but since the prime thing is not generally aware of other things which could be built around it it should not provide any feature which would *possibly* be useful
In general, I agree. But if XInt is accepted into Boost, there will *definitely* be an arbitrary-precision real type built onto it. I may do it myself, if no one else steps up, but I'm fairly certain that someone will -- it's a perfect GSoC project, for example. As such, planning for it isn't really degeneralization in this particular case.
Chad gave the practical reason. But perhaps more fundamentally, the information (the sign bit) is *there*, and I'd like it to be usable, even if the mantissa is zero. If you don't want to distinguish between -0 and +0 (and I don't see why you would when strictly in the domain of integers), then you won't ever notice there are 2 different representations.
assumption: there should be signed zeros like that of ieee floating point numbers
[...]
that's why you have no sound argument for this -- because it's not natural for ints
Exactly my thoughts. But if it does make life noticeably easier for whoever implements the real type, and doesn't cause any problems with the integer type, I'm willing to entertain the idea.
And it *is* natural for sign + magnitude (which I had been slightly mistakenly calling "sign + mantissa") representations. If builtin integers were based on a sign + magnitude or 1's complement representation, we'd already be used to dealing with signed zeros:
http://en.wikipedia.org/wiki/Signed_number_representations
I'm guessing it's simpler in hardware to use 2's complement, but we're pretty much stuck with sign + magnitude AFAICT for an unbounded integer library.
assumption: the presence of (signed) infinities would provide ultimate set of relationships of the domain entities as well as consistence of some operations' behavior
since there was no example of an application of infinities except interval arithmetics i see no reason to provide it [...]
The more I think about it, the less decided I am over it. I believe there are a few cases where it would be useful to have infinities, at least for comparisons, but I can't think of any concrete examples and no one else has provided any. And it does make for more work, both for me in writing it, and (slightly) for the computer when using it.
At the moment, I'm inclined to leave it out of the library for now, at least until someone can show an application where it would be more useful than the Not-a-Number value. But there's still at least a few days for people to make their cases before I have to make a decision. And we can always revisit the idea after the 1.0 release is stable.
True, infinities would have somewhat specialized applications, but it makes some sense (to me) to include it if you're already going to waste a byte on an NaN flag anyway.
With all of the issues I have seen so far, from signed zeros and infinities to exception throwing and NaN's, seems it all could be policy based, would be more work, but it does not all need to be done at once, just make sure a good, powerful policy framework is ready, and it can be extended over time, and user code can expand it themselves to allow for other representations of what they need. All modern compilers will easily optimize out all the cruft, so just the code needs to be written for it. P.S. I love the ideas of fixed_xint and so forth, why not expand it to xint<fixed,infinities> and so forth, with some typedefs for generic versions?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/03/2010 09:54 PM, OvermindDL1 wrote:
P.S. I love the ideas of fixed_xint and so forth, why not expand it to xint<fixed,infinities> and so forth, with some typedefs for generic versions?
One thing at a time. :-) Once the 1.0 release of the library is finished, there will be plenty of time to suggest enhancements. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku39YgACgkQp9x9jeZ9/wQtcwCg8dm5jhbjxip5kfo0hT13Oukb PMoAoLQuqvszaJHm6CF77ufKlzQnTe4+ =BJFZ -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/03/2010 09:27 PM, Jeffrey Lee Hellrung, Jr. wrote:
At the moment, I'm inclined to leave it out of the library for now, at least until someone can show an application where it would be more useful than the Not-a-Number value. But there's still at least a few days for people to make their cases before I have to make a decision. And we can always revisit the idea after the 1.0 release is stable.
True, infinities would have somewhat specialized applications, but it makes some sense (to me) to include it if you're already going to waste a byte on an NaN flag anyway.
Ah, but I'm not. :-) Since each xint::integer has a pointer to a data_t object (which holds the actual information), I simply set that pointer to zero for a NaN. No flags or extra storage involved. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku39NEACgkQp9x9jeZ9/wR7CgCfVsJzld8j2sdxKYCY8kvXPZFq KVgAoKWvmGBUN7p3j/HIwZYfDmpnELzM =32J7 -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 04/03/2010 09:27 PM, Jeffrey Lee Hellrung, Jr. wrote:
At the moment, I'm inclined to leave it out of the library for now, at least until someone can show an application where it would be more useful than the Not-a-Number value. But there's still at least a few days for people to make their cases before I have to make a decision. And we can always revisit the idea after the 1.0 release is stable. True, infinities would have somewhat specialized applications, but it makes some sense (to me) to include it if you're already going to waste a byte on an NaN flag anyway.
Ah, but I'm not. :-) Since each xint::integer has a pointer to a data_t object (which holds the actual information), I simply set that pointer to zero for a NaN. No flags or extra storage involved.
Ah, okay, that makes sense. I can fly with that. - Jeff
on 04.04.2010 at 5:27 Jeffrey Lee Hellrung, Jr. wrote :
Chad gave the practical reason. But perhaps more fundamentally, the information (the sign bit) is *there*, and I'd like it to be usable, even if the mantissa is zero. If you don't want to distinguish between -0 and +0 (and I don't see why you would when strictly in the domain of integers), then you won't ever notice there are 2 different representations. [...] And it *is* natural for sign + magnitude (which I had been slightly mistakenly calling "sign + mantissa") representations. If builtin integers were based on a sign + magnitude or 1's complement representation, we'd already be used to dealing with signed zeros:
I'm guessing it's simpler in hardware to use 2's complement, but we're pretty much stuck with sign + magnitude AFAICT for an unbounded integer library.
i think that designing the interface assuming the implementation is a very bad idea but designing the interface keeping the implementation in mind is whole lot better so assuming that "the sign bit is there" (but rather a sign bool) is a bad idea because you restrict the implementation given such restrictions prevents you from easily switching to arbitrary implementation so my point is that the interface must be design regardless of the implementation (but keeping it in mind) -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 09:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
You seem to really want some kind of one-to-one identification between integers and xint::integer objects,
Well, yes -- the xint::integer objects represent integers, after all. ;-)
but I implore you to step back a moment and relax that requirement. Your implementation naturally suggests two representations of zero, and I'm arguing to keep those distinct representations available for derived/wrapper classes, and for simplicity of implementation. I have yet to see where this makes a difference in the core interface or complicates the internal implementation.
It would a bit, because there may be code in there that assumes that if the negative Boolean is true, the value is less than zero.
To make a sensible signed-zero value work, I'd have to make up portions of the math, or adopt them from floating-point stuff even though that doesn't make sense here.
I don't know what you mean here. Isn't the arithmetic involving zeros fairly straightforward, signed or not?
If the zeros aren't signed, yes. If they are, and the library is supposed to honor the signs, things could get hairy. But it appears that I misunderstood your intentions... if a negative zero is still treated as zero, then all the math works out.
The aforementioned arbitrary-precision floating point package will just have to handle that itself, maybe by making an extremely small but non-zero value and calling it negative zero.
*That* seems "messy and arbitrary" ;)
It might be, it would depend on the design goals of the library. You've convinced me not to dismiss the idea out of hand. I'm still not sure that it's worthwhile, but I'll probably add it, with the understanding that any calculations done with it (except a unary minus) will come out with a positive-zero result. If someone needs a negative zero, they'll have to explicitly request it via the unary minus. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku3vGQACgkQp9x9jeZ9/wTGjACaA6fT/xiF5lziT6GCQXo5ogiP c1UAnR5SHSVXp94B1wVr6tr0PKCHm8PM =9zP1 -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 04/02/2010 09:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
You seem to really want some kind of one-to-one identification between integers and xint::integer objects,
Well, yes -- the xint::integer objects represent integers, after all. ;-)
Yes, and IEEE floats represent (limited precision and limited range) dyadic rationals. My point is, it can be practical and efficient to have 2 different underlying representations for the same abstract instance. You're already carrying around a sign bit + mantissa to represent an integer, so it seems to me unnatural to bend over backwards (exaggeration) to keep that sign bit unset when the mantissa drops to 0, if you really don't have to.
have yet to see where this makes a difference in the core interface or complicates the internal implementation.
It would a bit, because there may be code in there that assumes that if the negative Boolean is true, the value is less than zero.
Isn't the sign just (mantissa == 0 ? 0 : sign_bit ? -1 : 1) ? Perhaps I should've been clearer: I have yet to see where this makes the internal implementation more complicated than assuming a unique zero representation, and it appears like it would simplify implementation as you avoid "cleaning up" a -0. However, the one thing I haven't done is actually *look* at the current implementation, and I was hoping your familiarity would be able to pinpoint some precise issue.
I don't know what you mean here. Isn't the arithmetic involving zeros fairly straightforward, signed or not?
If the zeros aren't signed, yes. If they are, and the library is supposed to honor the signs, things could get hairy. But it appears that I misunderstood your intentions... if a negative zero is still treated as zero, then all the math works out.
For reference, wikipedia outlines the arithmetic rules specific to signed zeros in their "signed zeros" article: http://en.wikipedia.org/wiki/Signed_zeros What I would like to happen is, for example, the "natural" implementation of addition, where you don't specifically consider the rules for adding signed zeros, automatically works anyway for signed zeros. I might have to delve into the code to actually see what would happen...
The aforementioned arbitrary-precision floating point package will just have to handle that itself, maybe by making an extremely small but non-zero value and calling it negative zero. *That* seems "messy and arbitrary" ;)
It might be, it would depend on the design goals of the library.
I think the utility of signed zeros in floating point has been proven, so "it would be nice" if that was implemented as naturally as possible. I don't necessarily consider this a requirement of the core library, but I think it should be seriously considered.
You've convinced me not to dismiss the idea out of hand. I'm still not sure that it's worthwhile, but I'll probably add it, with the understanding that any calculations done with it (except a unary minus) will come out with a positive-zero result. If someone needs a negative zero, they'll have to explicitly request it via the unary minus.
Well, hopefully whatever zero (whether it's +0 or -0) "falls out" of an operation will suffice. I don't think you want to guarantee every result equal to either +0 and -0 (save a unary minus) will be fixed to +0. That defeats the whole point of my proposal. - Jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/03/2010 09:03 PM, Jeffrey Lee Hellrung, Jr. wrote:
You seem to really want some kind of one-to-one identification between integers and xint::integer objects,
Well, yes -- the xint::integer objects represent integers, after all. ;-)
Yes, and IEEE floats represent (limited precision and limited range) dyadic rationals. My point is, it can be practical and efficient to have 2 different underlying representations for the same abstract instance. You're already carrying around a sign bit + mantissa to represent an integer, so it seems to me unnatural to bend over backwards (exaggeration) to keep that sign bit unset when the mantissa drops to 0, if you really don't have to.
I have to call that cleanup function anyway, to skip past any leading zeros left over from whatever operation is being done.
have yet to see where this makes a difference in the core interface or complicates the internal implementation.
It would a bit, because there may be code in there that assumes that if the negative Boolean is true, the value is less than zero.
Isn't the sign just (mantissa == 0 ? 0 : sign_bit ? -1 : 1) ?
That's essentially the definition of the sign function. But before I discovered n1692 and its specification of that function, I just had an is_negative function in there. There may still be code that relies on the current behavior. Most likely if there is, I'll be able to find it quickly, but it's something I'll have to keep in mind if I do that.
Perhaps I should've been clearer: I have yet to see where this makes the internal implementation more complicated than assuming a unique zero representation, and it appears like it would simplify implementation as you avoid "cleaning up" a -0. However, the one thing I haven't done is actually *look* at the current implementation, and I was hoping your familiarity would be able to pinpoint some precise issue.
Other than the potential problem mentioned above, there should be no issues with implementing it -- *if* I stick with the rules I mentioned, so that every operation that results in a zero gets a positive zero, and negative zero is only provided when someone explicitly asks for it.
I don't know what you mean here. Isn't the arithmetic involving zeros fairly straightforward, signed or not?
If the zeros aren't signed, yes. If they are, and the library is supposed to honor the signs, things could get hairy. But it appears that I misunderstood your intentions... if a negative zero is still treated as zero, then all the math works out.
For reference, wikipedia outlines the arithmetic rules specific to signed zeros in their "signed zeros" article:
Noted for possible future reference, but as mentioned, I'd rather not deal with that stuff right now. Once the library is fully functional, I could add it, if there's any call for it.
What I would like to happen is, for example, the "natural" implementation of addition, where you don't specifically consider the rules for adding signed zeros, automatically works anyway for signed zeros. I might have to delve into the code to actually see what would happen...
I don't know off the top of my head either. They could work as written (once the sign function is modified to check for zero before negative), or they could get it completely wrong, I'd have to examine the code for each function to find out.
You've convinced me not to dismiss the idea out of hand. I'm still not sure that it's worthwhile, but I'll probably add it, with the understanding that any calculations done with it (except a unary minus) will come out with a positive-zero result. If someone needs a negative zero, they'll have to explicitly request it via the unary minus.
Well, hopefully whatever zero (whether it's +0 or -0) "falls out" of an operation will suffice. I don't think you want to guarantee every result equal to either +0 and -0 (save a unary minus) will be fixed to +0. That defeats the whole point of my proposal.
I thought the whole point of your proposal was to make it easier for people writing code on top of XInt? If the point is just to save the one or two clock cycles that are used for flipping the sign, it's hardly worth the effort. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku39DYACgkQp9x9jeZ9/wSFEwCg3ZaMR1SStcmgEHU9Uvb7sw1P dnoAn2a/55B6O4pYCHW+NCO8lj2oEKr0 =Fedg -----END PGP SIGNATURE-----
Chad Nelson wrote: [...]
Well, hopefully whatever zero (whether it's +0 or -0) "falls out" of an operation will suffice. I don't think you want to guarantee every result equal to either +0 and -0 (save a unary minus) will be fixed to +0. That defeats the whole point of my proposal.
I thought the whole point of your proposal was to make it easier for people writing code on top of XInt? If the point is just to save the one or two clock cycles that are used for flipping the sign, it's hardly worth the effort.
I'd want the signed zero arithmetic for integers to be compatible with the signed zero arithmetic for floats. Otherwise the wrapping floating point class would have to "undo" whatever work the enclosed integer class did to enforce only +0's. The (second) point was (hopefully) to simplify the implementation, but as it looks like that will take some time to work out, and it won't make an immediate difference at this point (with the lack of a floating point type built on top), I would be satisfied with revisiting this issue later. - Jeff
On Apr 3, 2010, at 9:03 PM, Jeffrey Lee Hellrung, Jr. wrote:
Chad Nelson wrote:
On 04/02/2010 09:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
You seem to really want some kind of one-to-one identification between integers and xint::integer objects, Well, yes -- the xint::integer objects represent integers, after all. ;-)
Yes, and IEEE floats represent (limited precision and limited range) dyadic rationals. My point is, it can be practical and efficient to have 2 different underlying representations for the same abstract instance. You're already carrying around a sign bit + mantissa to represent an integer, so it seems to me unnatural to bend over backwards (exaggeration) to keep that sign bit unset when the mantissa drops to 0, if you really don't have to.
To me, the key question is whether the signed 0 shows through the interface. I would consider it a mistake if it did so. Besides any "purity" arguments, doing so would eliminate the option of using some otherwise plausible internal representation, such as 2s-complement (*). The fact that the implementation presently under the discussion happens to be signed-magnitude should not be driving the interface. And if the signed 0 doesn't show through the interface, then why are we having this discussion at all. (*) That's not just a theoretical possibility; several of the (non-C++) unbounded integer packages I've had occasion to do some work on or look at in detail over my career used a 2s-complement internal representation.
Kim Barrett wrote:
On Apr 3, 2010, at 9:03 PM, Jeffrey Lee Hellrung, Jr. wrote:
Chad Nelson wrote:
On 04/02/2010 09:56 PM, Jeffrey Lee Hellrung, Jr. wrote:
You seem to really want some kind of one-to-one identification between integers and xint::integer objects, Well, yes -- the xint::integer objects represent integers, after all. ;-) Yes, and IEEE floats represent (limited precision and limited range) dyadic rationals. My point is, it can be practical and efficient to have 2 different underlying representations for the same abstract instance. You're already carrying around a sign bit + mantissa to represent an integer, so it seems to me unnatural to bend over backwards (exaggeration) to keep that sign bit unset when the mantissa drops to 0, if you really don't have to.
To me, the key question is whether the signed 0 shows through the interface. I would consider it a mistake if it did so. Besides any "purity" arguments, doing so would eliminate the option of using some otherwise plausible internal representation, such as 2s-complement (*). The fact that the implementation presently under the discussion happens to be signed-magnitude should not be driving the interface. And if the signed 0 doesn't show through the interface, then why are we having this discussion at all.
(*) That's not just a theoretical possibility; several of the (non-C++) unbounded integer packages I've had occasion to do some work on or look at in detail over my career used a 2s-complement internal representation.
Good point. Do you have any references to such packages? I'm curious about the implementation advantages and disadvantages of using 2s-complement vs sign+magnitude. - Jeff
On Apr 6, 2010, at 11:54 AM, Jeffrey Hellrung wrote:
Good point. Do you have any references to such packages?
Not really, at this point; it's been too many years since I did any work in this area. Most are buried inside various obsolete and likely unobtainable lisp implementations (where I use the term "lisp" somewhat loosely).
I'm curious about the implementation advantages and disadvantages of using 2s-complement vs sign+magnitude.
I really don't recall what the tradeoffs were anymore. I know that all of the implementations I actually did any work on used a 2s-complement representation. My present guess is that a signed magnitude representation is probably better if one can make use of COW or move semantics (nothing like either were available in any of the implementations I did any work on). I might even be convinced that signed magnitude is simply better; certainly it was my intent to at least try that choice if I ever needed to write another one. But I wouldn't want to close off that choice point in the xint interface.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
To me, the key question is whether the signed 0 shows through the interface. I would consider it a mistake if it did so. Besides any "purity" arguments, doing so would eliminate the option of using some otherwise plausible internal representation, such as 2s-complement [...]
Good point. Do you have any references to such packages? I'm curious about the implementation advantages and disadvantages of using 2s-complement vs sign+magnitude.
I tried it with the first large-integer library I developed, many years ago. As I recall, it made addition and subtraction slightly easier to implement, but multiplication and division were slightly harder, as were any more-advanced functions that needed to access the internals of the number (like exponentiation). It was slightly more efficient storage-wise to use 2s-complement, you could just allocate an array instead of having to have a struct *and* an array. (Though if that's all you're after, you could do the same thing with sign+magnitude, if you're willing to engage in some pointer trickery.) It was slightly less efficient for processing, because for anything other than addition and subtraction, you had to remove the sign bit, then calculate, then re-add the sign bit. Overall there wasn't much difference. I prefer sign+magnitude because it's easier to write readable code that way. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku7lVYACgkQp9x9jeZ9/wRq9QCeNLESN3qXOlHgEhKVFLdhnSn4 Pw4An3SxilFV4IPNaskDGz7HHNZW48P9 =60mH -----END PGP SIGNATURE-----
on 07.04.2010 at 0:11 Chad Nelson wrote :
Overall there wasn't much difference. I prefer sign+magnitude because it's easier to write readable code that way. and i believe it's more portable
by the way you could store the sign in the MSB of the most significant digit though i didn't dig the implementation and not sure you have a distinct bool for the sign -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/07/2010 11:34 AM, DE wrote:
Overall there wasn't much difference. I prefer sign+magnitude because it's easier to write readable code that way.
and i believe it's more portable
No, it's about the same either way.
by the way you could store the sign in the MSB of the most significant digit
Maybe I'm mistaken, but I thought that's what two's-complement meant.
though i didn't dig the implementation and not sure you have a distinct bool for the sign
Yes, I do. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku8uwwACgkQp9x9jeZ9/wTjcACfZmU36jEvBuulUCkRjnHCImBx /XQAnjxSyY0XD0aHKyY32/xKjPNyejqT =DRvg -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Wednesday 07 April 2010, Chad Nelson wrote:
by the way you could store the sign in the MSB of the most significant digit
Maybe I'm mistaken, but I thought that's what two's-complement meant.
You are mistaken, it's not just using the most signficant bit as a sign bit. There's a wikipedia article on two's complement if you care. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAku8x3QACgkQ5vihyNWuA4UUrgCgzUvwkrtIbl40GamI1WS/Rpge fioAn35nuWgTVO2g8LZ+C+BY7n9VhoiV =CAOx -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/07/2010 01:57 PM, Frank Mori Hess wrote:
by the way you could store the sign in the MSB of the most significant digit
Maybe I'm mistaken, but I thought that's what two's-complement meant.
You are mistaken, it's not just using the most signficant bit as a sign bit. There's a wikipedia article on two's complement if you care.
Ah, yes, I'd forgotten the different encoding for negative numbers. It has been about fifteen years since I looked at it last. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku877MACgkQp9x9jeZ9/wTgbACfaDw1zlEOYqjycNenJdE77aAh SzcAoJgouizvfWEO+whB1L9dkzKbr0dq =nvhq -----END PGP SIGNATURE-----
on 07.04.2010 at 21:04 Chad Nelson wrote :
by the way you could store the sign in the MSB of the most significant digit
Maybe I'm mistaken, but I thought that's what two's-complement meant. a number is stored in two's complement in the following way: if it is positive -- MSB is 0 an values is encoded straightforwardly if it is negative -- it is encoded as 'radix^digits - value' e.g. for 32 bit binary ints it is '2^32 - value'
or simply put if 'v' is positive or negative number to encode and 'm' is some modulo (such as 2^32) then a number is encoded as (m - v)%m the advantage is that addition and subtraction works straightforward with no special care about the signs of operands e.g. a + b == (m + a + b)%m or a - b == (m + a - b)%m i may misunderstand all this so better see e.g. http://en.wikipedia.org/wiki/Two's_complement
though i didn't dig the implementation and not sure you have a distinct bool for the sign
Yes, I do.
i suggest to pack the sign in the MSB of the most significant digit to get rid of the bool it still would be a sign-magnitude representation so retrievel would be like digits[n_digits - 1]&(1<<15)/*==0*/ but perhaps you would need to set that bit to 0 during some operations which involves some additional overhead -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/07/2010 02:30 PM, DE wrote:
i may misunderstand all this so better see e.g. http://en.wikipedia.org/wiki/Two's_complement
Thanks, I glanced through it to refresh my memory.
i suggest to pack the sign in the MSB of the most significant digit to get rid of the bool it still would be a sign-magnitude representation
so retrievel would be like
digits[n_digits - 1]&(1<<15)/*==0*/
but perhaps you would need to set that bit to 0 during some operations which involves some additional overhead
Since the savings would be minimal, and it would increase the overhead (even more than you mentioned), I don't think it's worth it. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEUEARECAAYFAku88R8ACgkQp9x9jeZ9/wSJ6gCXbUGaElqm4nYPJnB12BsitZta 2ACeL/B7FzzLK4pF9kCOML2RCVQeAwM= =fbh5 -----END PGP SIGNATURE-----
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Chad Nelson Sent: Friday, April 02, 2010 8:10 PM To: boost@lists.boost.org Subject: Re: [boost] New Boost.XInt Library, request preliminary review
- ----------------8<---------------- Forgive any mathematical terminology errors, I'm only an armchair mathematician. But in the domain of natural numbers, zero, by definition, has no sign. It's neither positive nor negative (or if you prefer, it's both). Signed zero seems to be an invention of computer science, where it represents a fraction that's so small that the inexact computer representation is indistinguishable from zero, but where the number itself isn't necessarily true zero. - ----------------8<----------------
As such, there's no real need for it in XInt.
Is it possible to simply be agnostic to the sign bit when the mantissa is 0?
Isn't that the same as saying that -0 is identical to +0?
IMO this is computing - whatever mathematicians feel about it. 1 There *really is a sign bit*, so either we should ensure that it is never set with zero (which *might* involve some runtime cost - if we negate a value, so we have to check for zero?) or just accept acknowledge that it is there ? 2 Is it relevant that that floating point types have sign and copysign functions that might be applied by some generic code to this 'user-defined' type? Would be simplest for these to be provided and to do the obvious thing? Or are we saying that this can't be used in this way? 3 Likewise there *really is a limit to the size of this infinite sized integer*, and many users will want to place an arbitrary limit on its size (and to know that that is). "Calculate Fib numbers, but don't use more than 1 Mbyte for it". 4 Some users may also want to limit the size to some chosen fixed arbitrary maximum number that is much smaller in order to mimic some of the fixed big integers about (128 bit, 256 bit, 100 decimal digits like NTL ZZ type etc). Would it be logical to provide the std::numeric_limits<integer>::max() function for this? And what about the std::numeric_limits digits and digits10()? All these decisions seem to me arbitrary and pragmatic. Perhaps we should leave the author to make a full proposal with some use case and provide a rationale and pros and cons. Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/03/2010 07:49 AM, Paul A. Bristow wrote: (I'm not sure who this one was addressed to, but I'll answer it anyway.) :-)
Is it possible to simply be agnostic to the sign bit when the mantissa is 0?
Isn't that the same as saying that -0 is identical to +0?
IMO this is computing - whatever mathematicians feel about it.
1 There *really is a sign bit*, so either we should ensure that it is never set with zero (which *might* involve some runtime cost - if we negate a value, so we have to check for zero?) or just accept acknowledge that it is there ?
At the moment, that's handled in the cleanup code. If the number is only one digit in length, and that digit is zero, then it automatically clear the negative bit. So yes, it involves a (very small) runtime cost.
2 Is it relevant that that floating point types have sign and copysign functions that might be applied by some generic code to this 'user-defined' type? Would be simplest for these to be provided and to do the obvious thing? Or are we saying that this can't be used in this way?
Sorry, I don't understand. This isn't a floating-point type, so generic code shouldn't assume that it can be treated as such. I do plan to add a numeric_limits for it (as you suggested), which will clearly identify it as an integral type for generic code.
3 Likewise there *really is a limit to the size of this infinite sized integer*, and many users will want to place an arbitrary limit on its size (and to know that that is). "Calculate Fib numbers, but don't use more than 1 Mbyte for it".
That's fairly easy to do at the user level, for those who want it.
4 Some users may also want to limit the size to some chosen fixed arbitrary maximum number that is much smaller in order to mimic some of the fixed big integers about (128 bit, 256 bit, 100 decimal digits like NTL ZZ type etc). Would it be logical to provide the std::numeric_limits<integer>::max() function for this? And what about the std::numeric_limits digits and digits10()?
Such a thing could easily be done by creating a wrapper around (or subclass of) xint::integer.
All these decisions seem to me arbitrary and pragmatic. Perhaps we should leave the author to make a full proposal with some use case and provide a rationale and pros and cons.
I'll do my best. :-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku3x2IACgkQp9x9jeZ9/wQrowCgwKtC0cmfAEmcuZNdnECwfmiB DXIAnjd3FRSwm640K+D9aedu7GzR+v3c =p75f -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 02:07 PM, Scott McMurray wrote:
I think is_nan(Inf) should be false, but is_finite(Inf) should also be false.
Since it won't be representable by the finite_xint that you proposed, it would have to.
If I don't add an infinity value, I could. I'm leaning toward adding one (with sign), but it will act exactly like a NaN except for comparisons.
Actually, you *can* calculate with infinity. That's the reason for having it separate from NaN, and why it needs a sign. [...]
Hm, point taken. I was only planning to make it work for comparisons, since the only reason proposed for it was for boundary markers, but that works too.
But the indeterminate forms do, of course, give NaNs: [...]
I can agree with all of those except 0 * Inf and 0 * -Inf. If I remember correctly, zero times anything is zero, and that would apply to infinities too. Or am I missing something again?
Hopefully that'll make you lean further :P
:-) I'm not sure how useful the operations on infinities would be, but it looks like it would be easy enough to add them. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2OIIACgkQp9x9jeZ9/wTahACgwTmqzynd1JtQlFayU6cnWZ6U rU4AoN2S381U5lJtz9kXkKUxhFDoyGPn =MGNu -----END PGP SIGNATURE-----
On 2 April 2010 14:33, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
I can agree with all of those except 0 * Inf and 0 * -Inf. If I remember correctly, zero times anything is zero, and that would apply to infinities too. Or am I missing something again?
It's because if the 0 came from x/Inf, the "0*Inf" is more like a x*(Inf/Inf). We used to call it the difference between a "real zero" and a "calculus zero". The former times anything -- even infinity -- is zero, but the latter leads to indeterminate forms.
:-) I'm not sure how useful the operations on infinities would be, but it looks like it would be easy enough to add them.
I doubt anyone would use them directly. I see them as there for defaults in cases where you need to provide something, but there's no finite value that's acceptable -- the interval example, or a modulo where you want the full value, for instance -- and as a way to intelligently propegate the bad_alloc error code.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 02:50 PM, Scott McMurray wrote:
I can agree with all of those except 0 * Inf and 0 * -Inf. If I remember correctly, zero times anything is zero, and that would apply to infinities too. Or am I missing something again?
It's because if the 0 came from x/Inf, the "0*Inf" is more like a x*(Inf/Inf).
We used to call it the difference between a "real zero" and a "calculus zero". The former times anything -- even infinity -- is zero, but the latter leads to indeterminate forms.
Since this is an integer library, x/Inf would be rounded to zero, even if it isn't technically zero. Then 0*Inf would also equal zero.
:-) I'm not sure how useful the operations on infinities would be, but it looks like it would be easy enough to add them.
I doubt anyone would use them directly. I see them as there for defaults in cases where you need to provide something, but there's no finite value that's acceptable -- the interval example, or a modulo where you want the full value, for instance -- and as a way to intelligently propegate the bad_alloc error code.
I can agree with most of that, but I still can't see how returning an infinity value on a bad_alloc would help anyone. It *isn't* infinity, it's just a number that can't (presently) be represented. NaN may not be completely appropriate for that, but infinity seems even less so, since it implies something that was arrived at by definite calculation. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2QsoACgkQp9x9jeZ9/wS6OACeO5qsQEkXbqaf6H8IcQmcX90H lmsAoJ5bQZzs8ab4er1Om56SvEjBXxb4 =SOH4 -----END PGP SIGNATURE-----
and finally: arbitrary and infinite are rather distinct words are we talking about arbitrary precision integers or infinite numbers? -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
and finally: arbitrary and infinite are rather distinct words
are we talking about arbitrary precision integers or infinite numbers?
Arbitrary-precision integers. But it could sometimes be useful to have a value representing infinity, just as it's sometimes useful to have one representing Not-a-Number. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2QXoACgkQp9x9jeZ9/wRM5wCfQ9/1G+2fbXe0gbznaY2Gf+cc n7wAoMsV8+toWDzGME+oKfBpU8ZdkPfm =iiPm -----END PGP SIGNATURE-----
on 02.04.2010 at 23:11 Chad Nelson wrote :
and finally: arbitrary and infinite are rather distinct words are we talking about arbitrary precision integers or infinite numbers? Arbitrary-precision integers. But it could sometimes be useful to have a value representing infinity, just as it's sometimes useful to have one representing Not-a-Number.
I can see some very limited uses for calculations with infinities, mostly involving endpoints in a range.
i agree with the presence of NaN and i agree that NaN should propagate when exceptions are blocked but nobody convinced me so far of usefulness of infinities in an integer domain as well as signed zero on 02.04.2010 at 22:57 Chad Nelson wrote : that seems very doubtful to me
I'm not sure what Scott has in mind, but there's one application you haven't mentioned: simply using it as a much larger capacity integer, as the Fibonacci example in the documentation demonstrates. sure it can, i implied it
-- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/02/2010 03:27 PM, DE wrote:
Arbitrary-precision integers. But it could sometimes be useful to have a value representing infinity, just as it's sometimes useful to have one representing Not-a-Number.
i agree with the presence of NaN and i agree that NaN should propagate when exceptions are blocked
but nobody convinced me so far of usefulness of infinities in an integer domain
I tried to come up with an example, but I couldn't think of anything useful, or even contrived. I was considering it because Scott McMurray pointed out that it would be useful for containers of intervals, and that a NaN value wouldn't be sufficient there. I can see his argument, but I'm not familiar with any use of intervals.
as well as signed zero
We're still arguing that.
I can see some very limited uses for calculations with infinities, mostly involving endpoints in a range.
that seems very doubtful to me
I'm still struggling to see where it's necessary too. Most of those "very limited uses" that I mentioned above would be in generic code, and I can't for the life of me think of an example of them. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku2jSgACgkQp9x9jeZ9/wQlAwCfdZ3qTNizXkLHNJ57ctcrpckp fDwAoM4WxzJTAtlr1VtDOjKMNHbdPc5w =a7VC -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/31/2010 11:59 AM, Jeffrey Hellrung wrote:
Should, definitely. Would... well, we can hope. :-) That wouldn't necessarily stop them from using C++, or Boost, though -- that's why I wanted to make it as simple as possible.
If all Boost libraries catered to the lowest common denominator "developer"...well...Boost.MPL and Boost.Fusion might be the first to go... ;) In all seriousness, though, usability is certainly important, but you have to draw the line somewhere. I think if you're submitting your library for review to Boost, you should embrace what Boost makes available to you.
While I agree with the theory, I'd still like to avoid it if at all possible. And since I only need it for two functions, which (as has been proven to me) ;-) can equally well return zero for invalid values, there's no particular need for it.
Sorry to be such a bear; I'm only trying to improve things.
And I'm sorry if I seem to be a stubborn mule about it too. I'm not trying to be, no matter how it might look. :-) I just need a strong enough reason to change the design. I think Scott McMurray just provided such a reason; please see my reply to him for my proposed solution.
Yes: Separate the NaN stuff from the rest of the fundamental operations (arithmetic operations, etc.), and, if you're really tied to it, add it back in a wrapper class. However, I still maintain that this NaN framework, as is, is not fundamental to any operation, and it's only motivation is to make the return values of no-more-than TWO crytographic-specific functions "convenient" for developers who have difficulty with pointer syntax (even though, for those developers who have no problem with pointer syntax (i.e. me) it's less convenient). Am I exaggerating?
Only in that it's also used for the exception-blocking system. If those two functions were the *only* reason for it, I'd have stuck with Boost.Optional for them.
An NaN framework which I actually consider useful would be one which is always signaling (i.e., throwing, even upon creation), or always quiet (NaNs are propagated), or even runtime configurable with your exception blocking idiom (which I think is useful). A "half-signaling" NaN (quietly manufactured but noisy when touched) seems to me a near-useless middle ground.
Also, you shouldn't be looking for a "strong reason to change the design". Look for the best design, regardless of what the current design is.
Ah, but I already *had* a very good design, in my opinion. I needed a strong enough argument to convince me that there was a better one. :-) Which Scott McMurray provided, by pointing out that it would simplify the job of writing other libraries that use XInt. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuz424ACgkQp9x9jeZ9/wSAJwCg3vQXIN83OAYl2k1GPpVviooO eL0AoKkj7t/o0X2+JrMtM0H4iLHmvvJJ =pzzE -----END PGP SIGNATURE-----
2010/3/29 Chad Nelson <chad.thecomfychair@gmail.com>:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
An xint::integer which is +infinity or -infinity is more meaningful than one which is NaN.
Agreed -- but only slightly. It carries one additional bit's worth of meaning, the sign.
Even if you identify +infinity and -infinity as a single infinity, it should *still* mean something different from an NaN. You might group infinity into the class of NaNs, but that doesn't mean that every operation which results in an NaN may as well result in an infinity (signed or unsigned). 0/0 and sqrt(-1) should evaluate to an NaN (or throw); it would be unsettling to evaluate these as infinity.
I guess I'm not explaining myself very well. I was suggesting using the NaN value as infinity only where you need an infinity value. The only viable use I've seen suggested for infinity, in this library, is for unbounded intervals (which I'll address below).
At the very least, you can make more refined calculations and comparisons with +/-infinity (compared to NaN),
Do you have an example where this would make any noticeable difference in XInt?
Noticeable in what sense? 1/NaN is NaN; 1/+infinity is +0 (or 1/infinity is 0 if you don't want signed infinities and zeros). Assuming, of course, you allow calculations with NaNs.
Noticeable in the sense that it would make any difference to people using the library.
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
Since NaN compares false to anything else, good luck getting your intervals with NaN endpoints to work in any kind of generic setting ;)
Now that's a decent argument for infinity values. Though I'm still not sure whether they'd ever be used... is there a scientific or mathematical use of intervals that you can foresee this library being used for?
Hi Chad, as an author of a library of intervals and interval containers, I have encountered places in my library design, where infinity values not only seemed to be useful but also appeared to be a "natural" solution. Natural, in this context means, easy to understand and in line with common math knowledge. (1) Complement of an interval set: complement({[0..0]}) == {(-inf..0), (0..+inf)} If we had infinity values, we could always define the complements of interval sets, like in the example above. (2) Size of an interval set: Throughout the stl, the size function returns the number of elements for containers. So for an std::set, we have {1,2, 5,6,7}.size() == 5 As interval set of integers this is {[1..2], [5..7]}.size() == 5 but for an interval set of doubles we have a "theoretic" result {[1.0..2.0], [5.0..7.0]}.size() == inf because the number of elements in this set of reals is *theoretically* infinite. In both cases, if felt kind of compelled to use infinity values. While these use cases seem to provide good reasons to introduce infinity values for integral numbers, I never had any use for "not a number" values. Contrary to infinities that are a part both of natural and mathematical language, not-a-number values appear pretty bizarr to me ... Their meaning is a contradiction in itself and their properties are non-intuitive. Meanwhile I doubt the usefulness of both of them, NaN and Infinity, on fundamental numeric types. Since there is the IEEE 754 for floating point numbers that proposes them, there is probably a vast amount of mathematical and numerical expert knowledge that this standard is based on. But my gut feeling is different. I think, the values of a numeric types should be (1) closed under their fundamental operations e.g. +. (2) Their values should be reachable from the initial value 0 or T() applying (fundamental) operations. Where operations are not defined like y/0, instead of introducing NaN, the undefined case should be guarded against by (1) program logic (asserts) or (2) denominator checks, if the condition can not be determined from the program logic otherwise. Neither NaN nor +/-Inf can be computed from 0 using fundamental operations like ++, +, -- and -. But the user can assign them to variables integer myNaN = integer(not_a_number()); and pass them to any operation that is provided by your type. So you have to check for NaN in every single function you implement. IIUC you provide NaN as emergency result for 3 functions only. Neither of these is fundamental to integral types. I don't think these functions justify to spoil the whole type with NaNs. My be it would be more interesting to provide the minimal and "pure" numeric type and provide a NaN and Infinity closure as template template<class IntegralT, class ClosureTraits=...> closed { ... } because the way in which NaNs, Infinities (and maybe more special values) are handled should be the same for all the different implementations of integral numeric types. Concerning my own yearning for infinity, I had the insight, that I can provide infinitely open interval borders myself as a property of my interval type. So I can be independent of the properties of my parameter types in case of example (1: complement). For example (2: size) I can provide an is_infinite() function instead, with a little loss of simplicity though. Generally I think we should avoid special values for integral numeric types. Thank you for submitting your library. If I find time, I might try to use it with my ITL library of interval containers. Cheers Joachim
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 04/07/2010 05:04 PM, Joachim Faulhaber wrote:
Now that's a decent argument for infinity values. Though I'm still not sure whether they'd ever be used... is there a scientific or mathematical use of intervals that you can foresee this library being used for?
Hi Chad,
as an author of a library of intervals and interval containers, I have encountered places in my library design, where infinity values not only seemed to be useful but also appeared to be a "natural" solution. [...]
That makes sense. Thank you for the information.
While these use cases seem to provide good reasons to introduce infinity values for integral numbers, I never had any use for "not a number" values. Contrary to infinities that are a part both of natural and mathematical language, not-a-number values appear pretty bizarr to me ... Their meaning is a contradiction in itself and their properties are non-intuitive.
Meanwhile I doubt the usefulness of both of them, NaN and Infinity, on fundamental numeric types. Since there is the IEEE 754 for floating point numbers that proposes them, there is probably a vast amount of mathematical and numerical expert knowledge that this standard is based on. But my gut feeling is different.
Coming from the background of a pretty good developer, but only a mediocre mathematician, it seems to me that the NaN value was added to floating-point types for basically the same reason that it's now used in XInt: to avoid throwing an exception. It's a lot more important for the floating-point type than for XInt though, since floating-point numbers are basic types that have to work in any language.
I think, the values of a numeric types should be (1) closed under their fundamental operations e.g. +. (2) Their values should be reachable from the initial value 0 or T() applying (fundamental) operations.
I'm not sure what your first point means, but I think I agree, for the most part.
Where operations are not defined like y/0, instead of introducing NaN, the undefined case should be guarded against by (1) program logic (asserts) or (2) denominator checks, if the condition can not be determined from the program logic otherwise.
Which is exactly what the library does, under normal circumstances (i.e. when exceptions aren't blocked).
Neither NaN nor +/-Inf can be computed from 0 using fundamental operations like ++, +, -- and -. But the user can assign them to variables
integer myNaN = integer(not_a_number());
and pass them to any operation that is provided by your type. So you have to check for NaN in every single function you implement. IIUC you provide NaN as emergency result for 3 functions only. Neither of these is fundamental to integral types. I don't think these functions justify to spoil the whole type with NaNs.
As a matter of fact, those functions no longer use the Not-a-Number value in the current code. They now return zero as a failure value, since I was shown that zero isn't a valid response for either of them.
My be it would be more interesting to provide the minimal and "pure" numeric type
Already done, in the version currently in the sandbox. There are now two separate types; the one in the core namespace is the pure one.
and provide a NaN and Infinity closure as template
template<class IntegralT, class ClosureTraits=...> closed { ... }
because the way in which NaNs, Infinities (and maybe more special values) are handled should be the same for all the different implementations of integral numeric types.
I'm not sure what you mean by "a NaN and Infinity closure". I understand templates, and I think I understand closures (at least as provided by languages like Lisp), but I can't make out what you're trying to say there. Is that a C++0x (or C++1x, now) thing? (I used to think that I knew C++ pretty well. <sigh>) :-)
Concerning my own yearning for infinity, I had the insight, that I can provide infinitely open interval borders myself as a property of my interval type. So I can be independent of the properties of my parameter types in case of example (1: complement). For example (2: size) I can provide an is_infinite() function instead, with a little loss of simplicity though.
Generally I think we should avoid special values for integral numeric types.
As much as I hate to say it, I'm starting to agree with you. I don't want to give up the exception-blocking system entirely though, so I'm still looking for some solution that would allow for it, without the problems.
Thank you for submitting your library. If I find time, I might try to use it with my ITL library of interval containers.
If you do, I'd highly recommend the version in the Sandbox. The interface isn't locked down yet, but it fixes several problems that are still in the version in the Vault, and has a superior design. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAku+FtcACgkQp9x9jeZ9/wS6bQCgzDISkhQCN/dYg7wi3E9g1iUe /vAAoJOMxejhawYbI81feIUkqOZp9WIL =1SK4 -----END PGP SIGNATURE-----
Chad Nelson wrote:
On 04/07/2010 05:04 PM, Joachim Faulhaber wrote: [...]
I think, the values of a numeric types should be (1) closed under their fundamental operations e.g. +. [...]
I'm not sure what your first point means, but I think I agree, for the most part.
Closed in the sense that if x, y in S, then (x op y) in S as well. [...]
and provide a NaN and Infinity closure as template
template<class IntegralT, class ClosureTraits=...> closed { ... }
because the way in which NaNs, Infinities (and maybe more special values) are handled should be the same for all the different implementations of integral numeric types.
I'm not sure what you mean by "a NaN and Infinity closure". I understand templates, and I think I understand closures (at least as provided by languages like Lisp), but I can't make out what you're trying to say there. Is that a C++0x (or C++1x, now) thing?
Closure in the (general) mathematical sense, not in the programming language sense. I.e., extend your set to make previously-undefined operations defined (and somehow consistent with the existing properties of interest). - Jeff
On 29 March 2010 02:32, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
No, because -Inf < finite and finite < Inf will always return true, whereas NaN < finite and finite < NaN will either throw an exception or, if a quiet NaN acting like IEEE 754, return false.
guys you are killing me what infinity??? its an integer library integers represent exact numbers and operations infinities and operations with 'em ARE INEXACT! (hit me if i'm wrong) while reading docs/messages on this lib replace the "NaN" with "invalid" word ok, forget the NaN, forget the exception blocking operations ALWAYS throw on error end of story but if and only if you want a "return code"-like interface you consider NaNs and exception blocking it is a feature of the lib and is defined according to its author furthermore it's an OPTIONAL feature furthermore wikipedia says that a NaN is used for values which can not be represented (ta-da!) 'sqrt(int(-1))' can not be represented (as integer) -> NaN 'n/0' can not be represented -> NaN etc. -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
DE wrote:
guys you are killing me
Well I hope it isn't that bad, but yes, I've been unusually pedantic about this, so I'll hang it up. I'm not convinced there should even be an NaN (prefer throwing and returning boost::optional<>). I'll leave it to Chad to evaluate my opinion accordingly. Now on to see what else I pick on this library for... - Jeff
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of DE Sent: Monday, March 29, 2010 5:28 PM To: boost@lists.boost.org Subject: Re: [boost] New Boost.XInt Library, request preliminary review
guys you are killing me what infinity???
Chill man - we have no homicidal intent! Infinity in this case is when you don't have or want to use more memory to hold any more bits/digits ;-) (just like floating-point when you run out of bits, 32, 64, 128, 300 decimal digits ..., it is convenient to have a bigger number that you can decide to call 'infinity'). It not about a math definition, it about what works for you :-) That's why a policy based solution will avoid all these arguments. Paul I think it was Godel who was asked "How do you compare infinities?" - His reply was "Very carefully!" ;-) --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 12:27 PM, DE wrote:
guys you are killing me what infinity??? its an integer library integers represent exact numbers and operations infinities and operations with 'em ARE INEXACT! (hit me if i'm wrong) [...]
Thank you, that's exactly what I've been trying to say. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxRowACgkQp9x9jeZ9/wQ3MwCeMNuLcSHsOhph3s6okRKHazM6 12sAnjkjhAN3kOZbZMWH4ooqPBDpianb =Mp2L -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 11:14 AM, Scott McMurray wrote:
An interval consists of two points. Setting the lower point to Not-a-Number would work exactly the same as setting it to -infinity. Same with the higher point and +infinity. It wouldn't make any sense to set the lower point to +infinity, or the higher one to -infinity, so the sign doesn't convey any useful information in that case.
No, because -Inf < finite and finite < Inf will always return true, whereas NaN < finite and finite < NaN will either throw an exception or, if a quiet NaN acting like IEEE 754, return false.
Agreed, see my most recent response to Jeffrey Hellrung. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxRjoACgkQp9x9jeZ9/wQZjgCfZC6016hkPd2dHuhvBX3ON7g+ 3uIAoIV4/r40hRgijrT8F/X8RD/dNEK+ =CA3c -----END PGP SIGNATURE-----
On 29 March 2010 02:32, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Not completely. There *are* the two functions that return Not-a-Number as part of their normal operation, not counting the string- and stream-reading functions. As I said on the rationales page of the documentation, I tried using Boost.Optional for those, but it made the library harder for people not already familiar with Boost.Optional to understand. An error code is an idiom that every C or C++ developer already understands well and knows how to deal with.
Those two functions, invmod and random_prime, can use xint() as their error code, if the relevant exception is blocked, since 0 is obviously neither a multiplicative inverse or a prime. That even lets you use them like error codes: xint z = invmod(x, y); if (z) { ... worked ... } else { ... no inverse exists ... } Though personally I think I'd still prefer an exception. If I'm doing RSA and there's no inverse, something has gone drastically wrong.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 08:42 PM, Scott McMurray wrote:
Those two functions, invmod and random_prime, can use xint() as their error code, if the relevant exception is blocked, since 0 is obviously neither a multiplicative inverse or a prime.
Close, but not quite: the inverse of zero is zero.
That even lets you use them like error codes: [...] Though personally I think I'd still prefer an exception. If I'm doing RSA and there's no inverse, something has gone drastically wrong.
Agreed, if you're doing RSA. And in that case, you can ignore the Not-a-Number return value, secure in the knowledge that, if your prime number isn't actually prime, you'll get a signaling NaN back, and the library will pitch a fit (and an exception) when you try to use it. ;-) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxTjAACgkQp9x9jeZ9/wRMFgCfY2O80R2cLxhvrDsLCjpRlC7I dCwAoMVBxyh6d04e5Q9OfR9mLsaCmyRU =Px5N -----END PGP SIGNATURE-----
On 29 March 2010 21:04, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Close, but not quite: the inverse of zero is zero.
Uh, what? I thought that the point of an inverse is that multiplication gives 1 -- that's certainly what I read at http://en.wikipedia.org/wiki/Modular_multiplicative_inverse Wouldn't the modulo inverse of 0 be a NaN just like the result of 1/0?
Scott McMurray wrote:
On 29 March 2010 21:04, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Close, but not quite: the inverse of zero is zero.
Uh, what? I thought that the point of an inverse is that multiplication gives 1 -- that's certainly what I read at http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Wouldn't the modulo inverse of 0 be a NaN just like the result of 1/0?
I believe this to be more relevant: http://planetmath.org/encyclopedia/AdditiveInverseOfTheZeroInARing.html
AMDG Arash Partow wrote:
Scott McMurray wrote:
On 29 March 2010 21:04, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Close, but not quite: the inverse of zero is zero.
Uh, what? I thought that the point of an inverse is that multiplication gives 1 -- that's certainly what I read at http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Wouldn't the modulo inverse of 0 be a NaN just like the result of 1/0?
I believe this to be more relevant: http://planetmath.org/encyclopedia/AdditiveInverseOfTheZeroInARing.html
modinv returns the multiplicative inverse, not the additive inverse. In Christ, Steven Watanabe
On 29 March 2010 21:11, Arash Partow <arash@partow.net> wrote:
I believe this to be more relevant: http://planetmath.org/encyclopedia/AdditiveInverseOfTheZeroInARing.html
That's the Additive inverse, -x, which is always (m-x)%m. It's always defined, so cannot be the one which needs a discussion of how to represent the unusual result.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 09:09 PM, Scott McMurray wrote:
Close, but not quite: the inverse of zero is zero.
Uh, what? I thought that the point of an inverse is that multiplication gives 1 -- that's certainly what I read at http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
<sigh> If you guys are going to make me eat crow so often, could I at least have some ketchup?
Wouldn't the modulo inverse of 0 be a NaN just like the result of 1/0?
Yes, it would. In my defense, I *did* have a reason to think that it was valid -- if you list the inverses of all the numbers by a particular prime, you're supposed to get every number back again, each a single time, in a different order. The only way that's true is if zero were its own inverse. That being the case, zero *would* be a valid response for those two functions. If I'm convinced that the Not-a-Number value shouldn't be included in the library, that's probably how I'll do it. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxVC0ACgkQp9x9jeZ9/wQmkQCgxtjMY3e9AlkoWaH5kEsKEE/d JjAAoKXwgfeuQHXXBNpa9QiuAkWan1sc =0Fg/ -----END PGP SIGNATURE-----
On 28 March 2010 11:59, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Certainly, in both computer science and mathematics. But by the mathematical definition, infinity isn't a number, it's a representation of an impossible number. So logically, representing it with the not-a-number value is correct.
+Infinity represents the concept of something larger than any specific value you can state, and -Infinity something smaller. So while you could choose to just use NaN in place of the infinities, there are situations in which infinity is reasonable where NaN is not. Imagine a container of intervals, for example -- there, +/- infinity would be very useful for the two outermost endpoints. And something like atan(Infinity) can reasonably give \pi/2, whereas atan(NaN) can only give NaN.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 04:45 PM, Scott McMurray wrote:
+Infinity represents the concept of something larger than any specific value you can state, and -Infinity something smaller.
So while you could choose to just use NaN in place of the infinities, there are situations in which infinity is reasonable where NaN is not.
Certainly.
Imagine a container of intervals, for example -- there, +/- infinity would be very useful for the two outermost endpoints. And something like atan(Infinity) can reasonably give \pi/2, whereas atan(NaN) can only give NaN.
No argument. But in the context of an integer library that will exactly represent any value that it can find the memory for, and will throw an exception if it can't get the memory it needs to represent a number exactly, I can't see much need for a specific value to represent infinity. In the case of boundaries provided to a function, the NaN value would represent the same idea as an infinity value -- that there is no specified boundary in that direction. If you can suggest a case where a separate infinity value would be necessary, I'll certainly add it. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuvzloACgkQp9x9jeZ9/wS5ZwCdG7MTk1b6wziIXXPBTsCL77H2 gS4AnRNBXFvlsTG0ae9OkpopFU6PRzLF =uYjy -----END PGP SIGNATURE-----
On 28 March 2010 17:32, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-)
On 28 March 2010 17:47, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
No argument. But in the context of an integer library that will exactly represent any value that it can find the memory for, and will throw an exception if it can't get the memory it needs to represent a number exactly, I can't see much need for a specific value to represent infinity.
Do those two quotation imply that NaNs will also result from the "overflow" condition of running out of memory? If so, there's your reason for an Infinity special value.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 05:47 PM, Scott McMurray wrote:
On 28 March 2010 17:32, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Which would defeat the primary purpose of the NaN value in the XInt library, which is to have something to return instead of throwing an exception when exceptions are blocked. :-)
On 28 March 2010 17:47, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
No argument. But in the context of an integer library that will exactly represent any value that it can find the memory for, and will throw an exception if it can't get the memory it needs to represent a number exactly, I can't see much need for a specific value to represent infinity.
Do those two quotation imply that NaNs will also result from the "overflow" condition of running out of memory? If so, there's your reason for an Infinity special value.
Sorry, but no. n1692 specifies that it's supposed to throw an std::overflow exception when it can't get the memory it needs to represent a number. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuv1FgACgkQp9x9jeZ9/wQ+5wCfXDfNnYPZLlLo8IQpKumh6Qcz 0eYAoPPALWzuZo5UbbjS7W1qr6Mx9zTI =c2U4 -----END PGP SIGNATURE-----
On 28 March 2010 18:12, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Sorry, but no. n1692 specifies that it's supposed to throw an std::overflow exception when it can't get the memory it needs to represent a number.
Doesn't this statement that "the standard says it must throw" conflict with your justification for having NaN as being "for when exceptions are blocked"?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 06:14 PM, Scott McMurray wrote:
Sorry, but no. n1692 specifies that it's supposed to throw an std::overflow exception when it can't get the memory it needs to represent a number.
Doesn't this statement that "the standard says it must throw" conflict with your justification for having NaN as being "for when exceptions are blocked"?
It would, if std::overflow were a blockable exception. :-) Most of the library's exceptions can be blocked, but not all of them. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuv2GQACgkQp9x9jeZ9/wRZogCgrXslErqTTMqy7ZrTLUHCRnma Rp0AnRC0/e4OXchzpp/qmtiteaE4fTdL =DMUv -----END PGP SIGNATURE-----
On 28 March 2010 18:29, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
It would, if std::overflow were a blockable exception. :-) Most of the library's exceptions can be blocked, but not all of them.
Can you point me to a subsection? I couldn't find a mention of blockable exceptions in n3035.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
It would, if std::overflow were a blockable exception. :-) Most of the library's exceptions can be blocked, but not all of them.
Can you point me to a subsection? I couldn't find a mention of blockable exceptions in n3035.
Blockable exceptions are an XInt library thing, which I added because people are asking for them. See the XInt documentation, the page labeled "Exceptions and Exception Blocking" (ref_exceptions.html). - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwChkACgkQp9x9jeZ9/wRW6gCgyz4idxRyRXgbmdlj5RAnTIYG IAkAoKhN1aDlwiFmTHIcpfeEECXO0bdO =ydsP -----END PGP SIGNATURE-----
On 28 March 2010 22:02, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
Blockable exceptions are an XInt library thing, which I added because people are asking for them. See the XInt documentation, the page labeled "Exceptions and Exception Blocking" (ref_exceptions.html).
Then the obvious question is, "Why isn't overflow blockable"? If the point is to be useful when exceptions are off, they should all be able to generate special values instead of throwing.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 10:13 PM, Scott McMurray wrote:
Blockable exceptions are an XInt library thing, which I added because people are asking for them. See the XInt documentation, the page labeled "Exceptions and Exception Blocking" (ref_exceptions.html).
Then the obvious question is, "Why isn't overflow blockable"?
And it's an excellent question. The only justification for making it non-blockable is that, if it were blockable, then nearly every function in the library could potentially return a Not-a-Number value, and you'd have to check for it constantly when blocking exceptions. That would defeat the intended purpose of the exception-blocking mechanism (see below). As it's not, you only have to check for the Not-a-Number value on the few functions that can throw a blockable exception.
If the point is to be useful when exceptions are off, they should all be able to generate special values instead of throwing.
There's no other logical response if there's no cryptographically-secure random number generator, and the user asks the library to instantiate one. (That's not in the version that was uploaded to the Boost Vault yet.) And it's debatable whether there's any other consistent and mathematically logical way to handle passing Not-a-Number values to functions that return anything but xint::integers. The mechanism isn't there so that the exception-hating crowd can get away with avoiding exception-handling. It's there to give the developer using the library the flexibility to treat its functions as returning error codes, rather than throwing exceptions, when it would make for more readable code. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwJPcACgkQp9x9jeZ9/wTmDQCff6ggBH/+qmL+hQ/Gll3mhaTc JCEAoPs003wuenRQbe3zjgmicmc0QdEW =8uDr -----END PGP SIGNATURE-----
On 28 March 2010 23:56, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
And it's an excellent question. The only justification for making it non-blockable is that, if it were blockable, then nearly every function in the library could potentially return a Not-a-Number value, and you'd have to check for it constantly when blocking exceptions. That would defeat the intended purpose of the exception-blocking mechanism (see below). As it's not, you only have to check for the Not-a-Number value on the few functions that can throw a blockable exception.
The mechanism isn't there so that the exception-hating crowd can get away with avoiding exception-handling. It's there to give the developer using the library the flexibility to treat its functions as returning error codes, rather than throwing exceptions, when it would make for more readable code.
You advocate Signalling NaNs. That means that you haven't actually made your checking any easier by blocking exceptions, because if you pass a result to anything else, it still needs to be checked. Since you said earlier that the most complicated look-before-you-leap[1] check required to avoid an exception is "x < 0", I fail to see the advantage, since there's just as much code required and no speed advantage. In fact, there may well be a speed disadvantage, since now every single function that takes in an XInt has to check "x.isNaN()" before doing anything. In fact, the only place where couple-leaping-with-looking[2] is advantageous is the overflow exception, so that's the only one where being able to block it could make a substantial readability improvement in my code. (Quiet NaNs may as well, since I could check once at the end instead of before every function call that throws when given a signalling NaN.) [1] http://www.c2.com/cgi-bin/wiki?LookBeforeYouLeap [2] http://www.c2.com/cgi-bin/wiki?CoupleLeapingWithLooking
There's no other logical response if there's no cryptographically-secure random number generator, and the user asks the library to instantiate one. (That's not in the version that was uploaded to the Boost Vault yet.) And it's debatable whether there's any other consistent and mathematically logical way to handle passing Not-a-Number values to functions that return anything but xint::integers.
There are at least 2 other possibilities: 1) Prevent it from compiling in the first place 2) Block until you have the required entropy Or the I'm-not-even-counting-it option of having the function default to an insecure RNG like Mersenne Twister...
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 12:57 AM, Scott McMurray wrote:
You advocate Signalling NaNs. That means that you haven't actually made your checking any easier by blocking exceptions, because if you pass a result to anything else, it still needs to be checked.
When it's possible that you've gotten a Not-a-Number value. As I've said before, those can only be returned by a small number of functions, even if you're blocking exceptions.
Since you said earlier that the most complicated look-before-you-leap[1] check required to avoid an exception is "x < 0", I fail to see the advantage, since there's just as much code required and no speed advantage. In fact, there may well be a speed disadvantage, since now every single function that takes in an XInt has to check "x.isNaN()" before doing anything.
An unavoidable consequence of having a Not-a-Number value. Fortunately, the check is extremely fast.
In fact, the only place where couple-leaping-with-looking[2] is advantageous is the overflow exception, so that's the only one where being able to block it could make a substantial readability improvement in my code.
It might improve individual checks, but there would have to be a lot more of them. And the overflow exception should be extremely rare on modern systems, unless you're using a staggering number of unbelievably large numbers.
(Quiet NaNs may as well, since I could check once at the end instead of before every function call that throws when given a signalling NaN.)
Now that's a valid argument, and it might be strong enough to outweigh my logical-return-values complaint. I don't have a strong objection to making the not_a_number exception blockable -- give me a reasonably non-contrived example where having it would make code more readable, and I'll find a way to make it happen.
There's no other logical response if there's no cryptographically-secure random number generator, and the user asks the library to instantiate one. (That's not in the version that was uploaded to the Boost Vault yet.) And it's debatable whether there's any other consistent and mathematically logical way to handle passing Not-a-Number values to functions that return anything but xint::integers.
There are at least 2 other possibilities: 1) Prevent it from compiling in the first place
Not acceptable. I want it to be easily portable, which means it has to compile even if the machine doesn't support any cryptographically-secure random number generator that the library recognizes. The developer using it can always plug in a generator that gets entropy from something the library doesn't know about, like an Internet site dedicated to that, after all -- they do exist.
2) Block until you have the required entropy
XInt isn't in the business of providing random numbers, the random number system in it is there solely for the random prime number generation facility. Gathering entropy isn't part of its job description. That may not be obvious from the version in the Boost Vault at present, but it will be with the next iteration.
Or the I'm-not-even-counting-it option of having the function default to an insecure RNG like Mersenne Twister...
Which is exactly what the library did in the current Vault version. The as-yet-unreleased version throws an exception, because that is an exceptional circumstance, and one that the developer must not ignore. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuwPTUACgkQp9x9jeZ9/wQk1gCfecl2Gwv0clT9hDf6kBnNALBQ 1hwAoNnZdaDgUWp7alOMI/CBvAb5lyaj =icpx -----END PGP SIGNATURE-----
On 29 March 2010 01:40, Chad Nelson <chad.thecomfychair@gmail.com> wrote:
An unavoidable consequence of having a Not-a-Number value. Fortunately, the check is extremely fast.
But not an unavoidable consequence, since there's nothing that necessitates that XInt allow a NaN value.
Not acceptable. I want it to be easily portable, which means it has to compile even if the machine doesn't support any cryptographically-secure random number generator that the library recognizes. The developer using it can always plug in a generator that gets entropy from something the library doesn't know about, like an Internet site dedicated to that, after all -- they do exist.
If the library is promising something cryptographically-secure, then failing to compile when it can't is the *best* possible response. Quietly doing something else is the worst possible option when it comes to security. If the library can't provide entropy, then it should require that the user provide some before compiling anything that demands entropy.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/29/2010 11:12 AM, Scott McMurray wrote:
Not acceptable. I want it to be easily portable, which means it has to compile even if the machine doesn't support any cryptographically-secure random number generator that the library recognizes. The developer using it can always plug in a generator that gets entropy from something the library doesn't know about, like an Internet site dedicated to that, after all -- they do exist.
If the library is promising something cryptographically-secure, then failing to compile when it can't is the *best* possible response. Quietly doing something else is the worst possible option when it comes to security. [...]
If the user of the library wants a secure random number generator, it's up to him to read the documentation. I explain exactly how to get it, with example code that shows it too. But most people using the library won't care about the issue, and just want it to work without any added effort or learning on their part, so an insecure (but always available) default is acceptable. (After Steven Watanabe pointed out the flaws in my original implementation, I redesigned it to accept any source from Boost.Random, including random_device. That's finished for the second iteration, which I'll probably upload this week. You can critique it then.) - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuxRcwACgkQp9x9jeZ9/wQ+AgCeNuVvSwOzTIsx7KY90LPwEa1E iV8An1n7YZj3McHfG59/xsMQb4TXd6bP =Vpnv -----END PGP SIGNATURE-----
On 28 March 2010 03:56, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
If you are going to represent NaNs, you might as well represent +/-infinity and +/-0. I think the principle of least surprise says to follow the semantics of IEEE floating point. But the best short term solution might be to just throw an exception and not worry about NaN's or infinities for now.
What operations result in NaNs, anyways? Are there any whose preconditions can't be trivially checked? The only ones that come to mind are checking for 0 before division and checking for negatives before taking a square root, both of which are just as easily checked outside the operation as inside it. So I'd say just throw instead of generating the NaN in the first place. With unbounded integers there's no underflow or overflow to worry about, so the advantage of the special values is questionable. (And I could make a wrapper to add the special values -- NaN, +Inf, -Inf, 1/+Inf, 1/-Inf -- if I needed.)
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 03/28/2010 04:50 PM, Scott McMurray wrote:
What operations result in NaNs, anyways?
Copying from the documentation: - ---------------------8<---------------------- To create a Not-a-Number, use the integer constructor that exists solely for that purpose. No other library function will return a Not-a-Number except under the following circumstances: * If a function that returns a non-reference integer tries to throw a blockable exception, but exceptions are blocked; * If the string-to-integer functions are asked to convert the string "#NaN#"; * If you call the function invmod, and there is no valid inverse; * If you call the function random_prime with a callback, and the callback function cancels it. - ---------------------8<----------------------
Are there any whose preconditions can't be trivially checked?
If you know your modular math, and never block exceptions, then no.
The only ones that come to mind are checking for 0 before division and checking for negatives before taking a square root, both of which are just as easily checked outside the operation as inside it.
Hm... you're right, taking the square root of a negative number *should* throw an exception. The library presently (and erroneously) returns zero. Thanks for the accidental catch. ;-)
So I'd say just throw instead of generating the NaN in the first place. With unbounded integers there's no underflow or overflow to worry about, so the advantage of the special values is questionable. (And I could make a wrapper to add the special values -- NaN, +Inf, -Inf, 1/+Inf, 1/-Inf -- if I needed.)
As mentioned in my last response to Jeffrey Hellrung, the NaN value is returned when the library needs to throw a blockable exception, but exceptions are blocked. Throwing an exception in that case is exactly what I *don't* want to do. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuv0/kACgkQp9x9jeZ9/wQA8gCgrxkYowV1b/7ZEkFVtPPqXhvP 2oYAnjY2BmDuELhqpz5OdA0RpPQvPOb2 =QNcb -----END PGP SIGNATURE-----
participants (18)
-
Anders Dalvander -
Arash Partow -
Chad Nelson -
Christopher Jefferson -
DE -
dherring＠ll.mit.edu -
Frank Mori Hess -
Gottlob Frege -
Jeffrey Hellrung -
Jeffrey Lee Hellrung, Jr.
-
Joachim Faulhaber -
Kim Barrett -
OvermindDL1 -
Paul A. Bristow -
Peter Dimov -
Scott McMurray -
Steven Watanabe -
Stewart, Robert