[rational] Announcing new maintainer -- call for feature requests
Dear All, Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library. I would like to know: 1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters? 2. What changes or additions would people like to see? Here are the changes that have been proposed: A. [me and others] Make int_type (and possibly param_type) public. This will be done. B. [Andras Erdei] Make rational more usable with limited precision integral types by providing automatic rounding when the result of a computation can not be represented exactly, or by asserting or throwing an exception in such cases. C. [Andras Erdei] Provide automatic selection of the underlying int_type which would be fastest for representing rational arithmetic with a specified precision. ---- Proposal B Andras's original proposal, if I understood it correctly, was to use a form of rounding which could be computed as the natural side-effect of the existing algorithm to compute a rational arithmetic operation, in the case that the actual result could not be represented exactly using the underlying int_type. At the time, I questioned whether it would be acceptable to change the current behavior of rational, since some current users may be relying on it. This is partly why I am asking question 1) above. A more general solution would be to add an optional template parameter representing a rounding policy, which could - implement no rounding, silently resulting garbage in some cases (this is the current implementation) - implement Andras's rounding method - throw an exception if rounding would be required - assert if rounding would be required, or - (possibly) implement some other rounding algorithm The reason I qualified the last option with "possibly" is that implementing alternate rounding policies may require completely different algorithms for the basic operations, meaning that the implementations of the basic operations would have to be moved into the rounding policy, which I'm reluctant to do. Andras, please let me know if I have misrepresented your ideas. For background, see these threads: http://lists.boost.org/MailArchives/boost/msg76375.php http://lists.boost.org/MailArchives/boost/msg80121.php ---- Jonathan
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters?
I'm not using it now, but I will probably want to throw it at my upcoming linear algebra code, using an unlimited precision integer type (if I can find one) as the template parameter. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Thursday 24 March 2005 01:05 pm, David Abrahams wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters? type (if I can find one) as the template parameter.
I use rational<int> in a scientific application. It's specifying a step size, and I wanted to avoid situations where, e.g., someone gave a step of 1/3 and didn't get exactly 3 steps from 0 to 1. I'm happy with it as is.
Ross Boylan wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters? type (if I can find one) as the template parameter.
I use rational<int> in a scientific application. It's specifying a step size, and I wanted to avoid situations where, e.g., someone gave a step of 1/3 and didn't get exactly 3 steps from 0 to 1.
I'm happy with it as is.
This is good to know. I'm definitely committed to keeping the current behavior available as an option. I'm also strongly inclined to make sure it is the default behavior, now that I have verified that the template is indeed used ;-) Andras's proposal to add optional rounding or error checking seems reasonable, but I can't really justify adopting it if there is only one interested user. Jonathan
Le vendredi 25 mars 2005 à 19:36 -0700, Jonathan Turkanis a écrit :
I'm definitely committed to keeping the current behavior available as an option. I'm also strongly inclined to make sure it is the default behavior, now that I have verified that the template is indeed used ;-)
Andras's proposal to add optional rounding or error checking seems reasonable, but I can't really justify adopting it if there is only one interested user.
If the rational type supports rounding (up and down), it will become a target for interval arithmetic, a possible alternative to floating point types. It is already possible to apply rationals of big integers to interval arithmetic. The ranges are computed exactly, but the computations get slower when the rationals get bigger. Floating point types do not suffer from this limitation, since their fixed precision allows for constant-time computations. But the results suffer from rounding to dyadic numbers (m*2^n). With rounded rational numbers, you would get a bit of both worlds: the computations would still be constant-time, and yet you would keep the exactness of the results for the smaller rationals. And since it is interval arithmetic we are talking about, the loss of precision for the bigger rationals is no problem at all (as long as there is up and down rounding). Best regards, Guillaume
Guillaume Melquiond wrote:
If the rational type supports rounding (up and down), it will become a target for interval arithmetic, a possible alternative to floating point types.
With rounded rational numbers, you would get a bit of both worlds: the computations would still be constant-time, and yet you would keep the exactness of the results for the smaller rationals. And since it is interval arithmetic we are talking about, the loss of precision for the bigger rationals is no problem at all (as long as there is up and down rounding).
Peter Dimov wrote:
My vote is that the default (and only) behavior should be to do the right thing, which in this case means adopting Andras's proposal in its original form. FWIW.
Thanks, guys. It's good to know there is support for rounding. Peter, could you elaborate on why rounding is the only legitimate behaviour when using rational with a limited precision type? Jonathan
Jonathan Turkanis wrote:
Peter, could you elaborate on why rounding is the only legitimate behaviour when using rational with a limited precision type?
Nice phrasing ;-) but I'll try. Since rounding is a subset of unspecified, it can only be worse if it carries an unacceptable overhead when overflow does not occur. I don't think that this is the case here. Asserting on overflow is misguided, because asserts should be used to catch logic errors, and rationals rarely participate in program logic; the source of the computation usually comes from user input. Exception on overflow is only better than rounding if no result is better than an approximate result, that is, when the answer has to be correct no matter what. This requirement is better served by rational<unlimited> which does deliver a correct answer. I don't see how rational<limited>+exception-on-overflow is better.
Peter Dimov wrote:
Since rounding is a subset of unspecified, it can only be worse if it carries an unacceptable overhead when overflow does not occur. I don't think that this is the case here.
yes!
Exception on overflow is only better than rounding if no result is better than an approximate result, that is, when the answer has to be correct no matter what. This requirement is better served by rational<unlimited> which does deliver a correct answer. I don't see how rational<limited>+exception-on-overflow is better.
after i failed to convince people that the current boost::rational is useless, i agreed to make an exception throwing version in the secret hope that it can be made the default, and as in practice it will always throw and never give a result, it will discourage people from using it so far i have tried the following reasonings: - did a boost::rational implementation (moved to www.ccg.hu/pub/src/old/rat.cpp) which does +, -, * and / _at the same speed_ as int +, -, * and / -- if rational computation (without hardware support) has the same speed as integer, then why was floating point (which is much worse than rational) ever introduced in the first place? isn't this suspicious? - did a test with boost::rational, executing +, -, * and / with 10000 random numbers; + and - gave the correct result only in 44 cases, and * and / in 79 cases -- does it sound useable? - gave an example with small numbers (1.055.. + 1.021.. results in -0.229..), and argued that when you use floating point 1.0/5.0 "overflows" in the same sense, but no-one would ever accept a float which only operates on numbers whose denominators must be powers of 2 -- then why is it acceptable for us? - tried to argue that the mental image of "overflow" is in this case faulty: the overflow in the representation is a detail of our _implementation_ (and 1.0/5.0 "overflows" in exactly the same sense, but no-one ever called _that_ an overflow) -- even worse, users will never be able to tell in advance when this overflow will happen (and thus avoid it), even if they know our implementation (the criterion is something like "the distinct prime factors of the numerator of one side and the denominator of the other side are small and few") what really makes this scary is that there is the very same rational proposal before the committee, and if it makes through we will have a standard that cannot be made to work for fixed precision (builtins) and cannot be implemented efficiently for unlimited precision (bigints) sorry, but feeling frustrated :O) andras
"Andras Erdei" <aerdei@gmail.com> wrote
after i failed to convince people that the current boost::rational is useless,
As has been previously stated. it is not the rational Concept that is useless but rather the limitations imposed by finite number representations of the value_type. I feel that boost::rational is being unfairly blamed for that. One could create various integer types that address the problem: eg An integer that is bounded , but in ops the result_type can hold any computed result accurately: int16 operator *(int8,int8) ; int16 operator +(int8,int8) ; int16 operator -(int8,int8) ; rational<int8> operator / (int8,int8) ; // ... :-) int8 quotient (int8,int8) ; mimicks inbuilt int operator / behaviour int32 operator+(int16,int16) ;// etc int64 operator* (int32,int32) // etc and using boost::numeric_converter to downcast, makes this a basis for a family of integers.
- did a boost::rational implementation (moved to www.ccg.hu/pub/src/old/rat.cpp) which does +, -, * and / _at the same speed_ as int +, -, * and / -- if rational computation (without hardware support) has the same speed as integer, then why was floating point (which is much worse than rational) ever introduced in the first place? isn't this suspicious?
IMO rational is useful for storing Exactly a limited range of numbers, float for storing a larger range approximately. Therefore I disagree with a rounding policy on rationals. The roles are different. Rationals can be compared exactly whereas this is not very useful with floats, which is a major advantage for rationals It is possible to cast from rational to float, it is unwise to make a cast from float to rational, because the rational gives a precision guarantee that the float doesnt.
- did a test with boost::rational, executing +, -, * and / with 10000 random numbers; + and - gave the correct result only in 44 cases, and * and / in 79 cases -- does it sound useable?
Except that rational numbers used in practise are not entirely random. I would guess that 1/2 is most common, 1/3 etc.
sorry, but feeling frustrated :O)
FWIW your protestations have pointed out potential errors in some of my code, which is a good thing:-) regards Andy Little
apologies for more subject line mangling... hope this is better regards Andy Little
Andras Erdei wrote:
Peter Dimov wrote:
Since rounding is a subset of unspecified, it can only be worse if it carries an unacceptable overhead when overflow does not occur. I don't think that this is the case here.
yes!
Exception on overflow is only better than rounding if no result is better than an approximate result, that is, when the answer has to be correct no matter what. This requirement is better served by rational<unlimited> which does deliver a correct answer. I don't see how rational<limited>+exception-on-overflow is better.
after i failed to convince people that the current boost::rational is useless, i agreed to make an exception throwing version in the secret hope that it can be made the default, and as in practice it will always throw and never give a result, it will discourage people from using it
what really makes this scary is that there is the very same rational proposal before the committee, and if it makes through we will have a standard that cannot be made to work for fixed precision (builtins) and cannot be implemented efficiently for unlimited precision (bigints)
sorry, but feeling frustrated :O) andras
Hi Andras, I'm sorry you feel frustrated, but I don't think it's warranted. IIRC, when you raised the issues before, after a bit of discussion I essentially said that I didn't have time to consider the matter fully, and would get to it later. Now we're having a fuller discussion of the issues you raised, there seem to be more participants than before, and no final decisions have been made. I'd say things are going well. Jonathan
On Wed, 30 Mar 2005 22:03:58 -0700, Jonathan Turkanis <technews@kangaroologic.com> wrote:
I'm sorry you feel frustrated, but I don't think it's warranted.
it is not that bad :O)
I'd say things are going well.
there were a few quite good comments in this thread lately, but i am at a project deadline, and don't have the time to participate -- hopefully i'll finish early next week, and can start repeating myself again :O) br, andras
Peter Dimov wrote:
Jonathan Turkanis wrote:
Peter, could you elaborate on why rounding is the only legitimate behaviour when using rational with a limited precision type?
Nice phrasing ;-)
This was my interpretation of "do the right thing". ;-)
but I'll try.
Since rounding is a subset of unspecified, it can only be worse if it carries an unacceptable overhead when overflow does not occur. I don't think that this is the case here.
Asserting on overflow is misguided, because asserts should be used to catch logic errors, and rationals rarely participate in program logic; the source of the computation usually comes from user input.
Exception on overflow is only better than rounding if no result is better than an approximate result, that is, when the answer has to be correct no matter what. This requirement is better served by rational<unlimited> which does deliver a correct answer. I don't see how rational<limited>+exception-on-overflow is better.
It seems to me that in some cases developers will be able to reason that based on the numerators and denominators of the instances of rationals they explicitly construct and the type and number of operations they need to perform, no overflow will occur if they use, say, rational<int>. In some cases, they will reason incorrectly; this is the type of logic error which might be usefully signaled using assertions. I believe Andras was arguing that this type of reasoning can almost never succeed in realistic situations; I'm not convinced of this yet. If I change the implementation to implement rounding, but leave the specification the same, I'm not sure I'm helping anyone. To the developer who needs exact representations and has reasoned incorrectly that rational<int> is sufficient, a close approximation may be no better than a wildly wrong result. In fact, the wildly wrong result may make the logic error apparent earlier. Also, a developer who doesn't need exact representations can't rely on unspecifi ed behavior. If, on the other hand, I change the specification to include rounding, I may be excluding future optimized implementations of the arithmetic operations which don't automatically yield a rounded result in cases of overflow. Maybe it's clear no significant improvements are possible along these lines, but I'd like to consider it carefully first. Jonathan
Jonathan Turkanis wrote: [snip]
It seems to me that in some cases developers will be able to reason that based on the numerators and denominators of the instances of rationals they explicitly construct and the type and number of operations they need to perform, no overflow will occur if they use, say, rational<int>. In some cases, they will reason incorrectly; this is the type of logic error which might be usefully signaled using assertions.
I hope you meant using exceptions as it is not possible to test all possible inputs to the calculations Keith Burton
Keith Burton wrote:
Jonathan Turkanis wrote: [snip]
It seems to me that in some cases developers will be able to reason that based on the numerators and denominators of the instances of rationals they explicitly construct and the type and number of operations they need to perform, no overflow will occur if they use, say, rational<int>. In some cases, they will reason incorrectly; this is the type of logic error which might be usefully signaled using assertions.
I hope you meant using exceptions as it is not possible to test all possible inputs to the calculations
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur. If this reasoning is correct -- and usually one must trust the developer's judgment -- using exceptions would be unnecessary. Jonathan
Jonathan Turkanis wrote:
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur.
You do understand that the range of the inputs has almost nothing to do with overflow, right?
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00aa01c536c0$66dd7f60$6601a8c0@pdimov...
Jonathan Turkanis wrote:
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur.
You do understand that the range of the inputs has almost nothing to do with overflow, right?
There is a safe range of values for each operation. eg for an implementation of rational addition where Rationalx = Nx/ Dx and operator + is implemented as : (N1 * D2 + N2 * D1 ) "/ "(D1 * D2) Assuming the same maximaum allowable value for each of N1, D1, N2, D2 max value of ( N1 * D2 + N2 * D1) occurs when N1 == D1 == D2 == N2, max value of (D1 *D2) when D1 == D2, therefore max allowable value of all these is: sqrt(double(std::numeric_limits<int_type>::max()/2)) . For a 16bit int this leaves you with a safe range of +-127 in this case.Of course after 'normalisation' referred to in the boost::rational docs, the result of the addition itself may or may not be out of range. boost::rational uses a more complicated algorithm for addition, but nevertheless the above limit algoritm(which might be improved upon of course) holds I think. I would guess that the limit would need to be 'implementation defined', but (ideally) available as part of rationals interface. The alternative is to simply do the calculation but perhaps then the algorithm used in boost::rational leads to a very unpredictable set of valid numerator ,denominator values per operand per operation, which is not very satisfactory from a users viewpoint. Perhaps both the safe contiguous range and the 'feeling lucky' range could be made available, though one of these would probably not be much used ! Incidentally similar,solvable problems occur in integer multiplication. regards Andy Little
Andy Little wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00aa01c536c0$66dd7f60$6601a8c0@pdimov...
Jonathan Turkanis wrote:
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur.
You do understand that the range of the inputs has almost nothing to do with overflow, right?
There is a safe range of values for each operation. eg for an implementation of rational addition where Rationalx = Nx/ Dx and operator + is implemented as :
(N1 * D2 + N2 * D1 ) "/ "(D1 * D2)
Assuming the same maximaum allowable value for each of N1, D1, N2, D2 max value of ( N1 * D2 + N2 * D1) occurs when N1 == D1 == D2 == N2, max value of (D1 *D2) when D1 == D2,
therefore max allowable value of all these is:
sqrt(double(std::numeric_limits<int_type>::max()/2)) .
For a 16bit int this leaves you with a safe range of +-127 in this case.Of course after 'normalisation' referred to in the boost::rational docs, the result of the addition itself may or may not be out of range.
True, but if your computations do not consist of a single addition, you'll see you "conservative" range shrinking down rapidly to [1, 1] for the denominator. ;-) The real answer is that rational addition is rational-overflow-safe (as opposed to ordinary integer-overflow-safe) if Di == Dj (or the equivalent where all D's divide some Di). That is, when I could have used integer arithmetic instead of rational. This is perhaps an important use case. However it is completely unaffected by rounding (which never occurs in this scenario.) Hence, rational can be improved to support another use case (floating point replacement) without affecting its current users.
"Peter Dimov" <pdimov@mmltd.net> wrote
Andy Little wrote:
For a 16bit int this leaves you with a safe range of +-127 in this case.Of course after 'normalisation' referred to in the boost::rational docs, the result of the addition itself may or may not be out of range.
True, but if your computations do not consist of a single addition, you'll see you "conservative" range shrinking down rapidly to [1, 1] for the denominator. ;-)
The result may be out of range, but nevertheless this can be checked. To automate this one could create a rational<int_type, tri_state range_checked> where range_checked = false on a temporary. (Then += etc must be implemented in terms of *this = check(*this+in)). Only allowing operations on types where both operands have range_checked== true. Users could find their way round the inconvenience by using rational<int_type, dont_care>.
The real answer is that rational addition is rational-overflow-safe (as opposed to ordinary integer-overflow-safe) if Di == Dj (or the equivalent where all D's divide some Di). That is, when I could have used integer arithmetic instead of rational.
However these special case properties of the denominators need to be checked, and integer arithmetic may also overflow (bigger values than int common), so one is back to the problem of 'seemingly-random' combinations of values that will work. regards Andy Little
Peter Dimov wrote:
Andy Little wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:00aa01c536c0$66dd7f60$6601a8c0@pdimov...
Jonathan Turkanis wrote:
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur.
You do understand that the range of the inputs has almost nothing to do with overflow, right?
There is a safe range of values for each operation. eg for an implementation of rational addition where Rationalx = Nx/ Dx and operator + is implemented as :
(N1 * D2 + N2 * D1 ) "/ "(D1 * D2)
Assuming the same maximaum allowable value for each of N1, D1, N2, D2 max value of ( N1 * D2 + N2 * D1) occurs when N1 == D1 == D2 == N2, max value of (D1 *D2) when D1 == D2,
therefore max allowable value of all these is:
sqrt(double(std::numeric_limits<int_type>::max()/2)) .
For a 16bit int this leaves you with a safe range of +-127 in this case.Of course after 'normalisation' referred to in the boost::rational docs, the result of the addition itself may or may not be out of range.
True, but if your computations do not consist of a single addition, you'll see you "conservative" range shrinking down rapidly to [1, 1] for the denominator. ;-)
The real answer is that rational addition is rational-overflow-safe (as opposed to ordinary integer-overflow-safe) if Di == Dj (or the equivalent where all D's divide some Di). That is, when I could have used integer arithmetic instead of rational.
You can always use integer arithmetic instead. ;-)
This is perhaps an important use case. However it is completely unaffected by rounding (which never occurs in this scenario.) Hence, rational can be improved to support another use case (floating point replacement) without affecting its current users.
I basically agree except for the question of whether specifying rounding behavior could lock in an inefficient implementation. Jonathan
"Andy Little" <andy@servocomm.freeserve.co.uk> wrote
There is a safe range of values for each operation. eg for an implementation of rational addition where Rationalx = Nx/ Dx and operator + is implemented as :
(N1 * D2 + N2 * D1 ) "/ "(D1 * D2)
FWIW if one limited values to the contiguous range scheme in my previous post, I think that the 'naive' algorithm above (+ rational.normalize() )gives significantly better speed and memory performance than the addition calc in current version of boost::rational. This is probably also true of other operations. The current implementation is making assumptions about the integer used as the value_type, and may not be optimal for a bigint value_type either. regards Andy Little
Andy Little wrote:
[...] boost::rational uses a more complicated algorithm for addition, but nevertheless the above limit algoritm(which might be improved upon of course) holds I think. [...]
Two years ago I proposed an even more complicated algorithm for addition which further reduces the number of cases where integer overflow occurs. You can find it in http://sourceforge.net/tracker/index.php?func=detail&aid=519635&group_id=7586&atid=107586 I really don't know whether the rational library is useful. I proposed it as an exercise to my students, and it was for that reason that I came across the addition algorithm I proposed in 2002. In any case: a) Using integer traits, it should be easy to distinguish between limited and unlimited range integers. Hence, when rational is used with unlimited range integers, simpler algorithms may be selected at compile time. b) If limited range integers are used, then either rounding is used or not. It seems reasonable to leave the choice to the user of the class. Using policies should be a simple solution. c) For the cases of limited range integers without rounding: i) It makes sense, in my opinion, to use algorithms which minimize the number of cases where integer overflow occurs. I don't like the current solution, since it only makes a half-hearted attempt at this, for of efficiency reasons. ii) It is certainly possible to provide the class with static functions for checking whether overflow would occur for each operation. This would make assertion based error checking possible. Whether this is really appropriate I don't know. d) A possibly useful change to the class would be to add representations for plus and minus infinity, as well as "not a number": 1/0, -1/0 and 0/0. I think an algebra including these extra values is pretty easy to define.
Peter Dimov wrote:
Jonathan Turkanis wrote:
No, I was claiming that in some cases a developer might know the range of all possible inputs, and be able to reason that no overflow could occur.
You do understand that the range of the inputs has almost nothing to do with overflow, right?
I was using range in the general sense, meaning subset. Obviously for a given computation, there is a certain subset of possible inputs which will lead to overflow. Jonathan
Jonathan Turkanis wrote:
Ross Boylan wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters? type (if I can find one) as the template parameter.
I use rational<int> in a scientific application. It's specifying a step size, and I wanted to avoid situations where, e.g., someone gave a step of 1/3 and didn't get exactly 3 steps from 0 to 1.
I'm happy with it as is.
This is good to know.
I'm definitely committed to keeping the current behavior available as an option. I'm also strongly inclined to make sure it is the default behavior, now that I have verified that the template is indeed used ;-)
Andras's proposal to add optional rounding or error checking seems reasonable, but I can't really justify adopting it if there is only one interested user.
My vote is that the default (and only) behavior should be to do the right thing, which in this case means adopting Andras's proposal in its original form. FWIW.
Ross Boylan wrote:
I use rational<int> in a scientific application. It's specifying a step size, and I wanted to avoid situations where, e.g., someone gave a step of 1/3 and didn't get exactly 3 steps from 0 to 1.
am i right, that your usage of rational is equivalent to one of: int d = 3 ; for ( int n = 0 ; n <= d ; ++n ) cout << double( n ) / d ; or int s = 3 ; int d = 17 ; for ( int n = 0 ; n <= d ; n += s ) cout << double( n ) / d ; ? if not, can you send me some simplified code snippet? tia, andras
David Abrahams wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters?
I'm not using it now, but I will probably want to throw it at my upcoming linear algebra code, using an unlimited precision integer type (if I can find one) as the template parameter.
Would it be kosher for me to grab a bigint class from the Yahoo files section -- say the one by Ronald Garcia and Andrew Lumsdaine -- make sure it is in good shape, and let it be the default template parameter to rational? Naturally, as soon as a bigint class is accepted I would use it instead. Jonathan
Hello everybody, I usually do not write a lot here, but sometimes follow some of the discussions. I have coded a bigint lib about 2 years ago and decided to propose it as a Boost lib. At that moment I thought that uBlas had a bigint lib, so I never propose my lib to Boost. If anybody is interested, the possibility is still there. Thanks, Lucas Galfasó "Jonathan Turkanis" <technews@kangaroologic.com> wrote in message news:d22j79$ag5$1@sea.gmane.org...
David Abrahams wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters?
I'm not using it now, but I will probably want to throw it at my upcoming linear algebra code, using an unlimited precision integer type (if I can find one) as the template parameter.
Would it be kosher for me to grab a bigint class from the Yahoo files section -- say the one by Ronald Garcia and Andrew Lumsdaine -- make sure it is in good shape, and let it be the default template parameter to rational? Naturally, as soon as a bigint class is accepted I would use it instead.
Jonathan
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
If you haven't already done so, how about uploading it to the boost files section. Robert Ramey Lucas Galfaso wrote:
Hello everybody,
I usually do not write a lot here, but sometimes follow some of the discussions. I have coded a bigint lib about 2 years ago and decided to propose it as a Boost lib. At that moment I thought that uBlas had a bigint lib, so I never propose my lib to Boost. If anybody is interested, the possibility is still there.
Thanks, Lucas Galfasó
Hi, It is in the boost file section under BigNumbers. Thanks, Lucas Galfasó "Robert Ramey" <ramey@rrsd.com> wrote in message news:d2762m$t96$1@sea.gmane.org...
If you haven't already done so, how about uploading it to the boost files section. Robert Ramey
Lucas Galfaso wrote:
Hello everybody,
I usually do not write a lot here, but sometimes follow some of the discussions. I have coded a bigint lib about 2 years ago and decided to propose it as a Boost lib. At that moment I thought that uBlas had a bigint lib, so I never propose my lib to Boost. If anybody is interested, the possibility is still there.
Thanks, Lucas Galfasó
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Just in case: The lib is not in condition to be presented to be part of Boost, I never did so because I thought that a big int solution was in Boost anyway. If there is some interest in including this lib into Boost distribution, I am willing to (a) write the documentation (b) add some features that some people think are necesary and (c) mantain it. Thanks, Lucas Galfasó. "Robert Ramey" <ramey@rrsd.com> wrote in message news:d2762m$t96$1@sea.gmane.org...
If you haven't already done so, how about uploading it to the boost files section. Robert Ramey
Lucas Galfaso wrote:
Hello everybody,
I usually do not write a lot here, but sometimes follow some of the discussions. I have coded a bigint lib about 2 years ago and decided to propose it as a Boost lib. At that moment I thought that uBlas had a bigint lib, so I never propose my lib to Boost. If anybody is interested, the possibility is still there.
Thanks, Lucas Galfasó
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, 27 Mar 2005 23:22:54 -0300, Lucas Galfaso wrote
Just in case: The lib is not in condition to be presented to be part of Boost, I never did so because I thought that a big int solution was in Boost anyway.
I think you are under a misconception -- there's NO big integer solution in boost as far as I know. I just rechecked the UBLAS docs and couldn't find it... Jeff
I sense a possible chicken/egg problem here. My personal experiences suggests you can't expect people to take an interest in it unless it has documentation and examples. In order to get interest, it has to be usable right out of the box with only about a 10 min review time. That means decent tutorial document and examples. If its in the vault, and people find it meets a need in an expedient manner, there will be sufficient interest to convince you that spending more time on it is worthwhile. Robert Ramey Lucas Galfaso wrote:
If there is some interest in including this lib into Boost distribution, I am willing to (a) write the documentation (b) add some features that some people think are necesary and (c) mantain it.
Thanks, Lucas Galfasó.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Ok, I will write the documentation and get this ready for a mmm... I do not know how to call it... pre review? Thanks Lucas Galfaso "Robert Ramey" <ramey@rrsd.com> wrote in message news:d2813v$al5$1@sea.gmane.org...
I sense a possible chicken/egg problem here.
My personal experiences suggests you can't expect people to take an interest in it unless it has documentation and examples. In order to get interest, it has to be usable right out of the box with only about a 10 min review time. That means decent tutorial document and examples. If its in the vault, and people find it meets a need in an expedient manner, there will be sufficient interest to convince you that spending more time on it is worthwhile.
Robert Ramey
Lucas Galfaso wrote:
If there is some interest in including this lib into Boost distribution, I am willing to (a) write the documentation (b) add some features that some people think are necesary and (c) mantain it.
Thanks, Lucas Galfasó.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Jonathan Turkanis" <technews@kangaroologic.com> wrote in message news:d22j79$ag5$1@sea.gmane.org...
David Abrahams wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> writes:
Dear All,
Several months ago I became the official maintainer of Boost.Rational, and am just now getting around to considering proposed modifications to the library.
I would like to know:
1. Do people use Boost.Rational, and if so, what is it used for, and with what template parameters?
I'm not using it now, but I will probably want to throw it at my upcoming linear algebra code, using an unlimited precision integer type (if I can find one) as the template parameter.
Would it be kosher for me to grab a bigint class from the Yahoo files section -- say the one by Ronald Garcia and Andrew Lumsdaine -- make sure it is in good shape, and let it be the default template parameter to rational?
Surely int should be the default parameter (if any). Using bigint turns it from a relatively lightweight to a heavyweight type. In many uses of rational the values are unlikely to overflow. Some uses are in dividing a circle into degrees, minutes, or seconds, power of dimension in a runtime physical-quantity, Storing imperial lengths eg 1 1/8 " (inch). I would guess that these are the major uses of rational and all have values in quite a small range. And of course making bigint the default parameter introduces a dependency, which is at least untidy. As far as errors due to overflow, the problem is not actually in the domain of rational but of the value_type as has been stated before. rational shouldnt need to know anything about the behaviour of its value_types operations. BTW why doesnt boost::rational have a 'value_type' member rather than the obscure 'int_type'? Further If the mpl rational (or fraction) becomes part of boost: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?MPL_TODO_List. it would be useful to allow interaction between the compile time and run time types: typedef boost::mpl::rational_c<int,1,360> ct; for (boost::rational<int> rt ; rt <= 1; rt += ct()){...} Other useful operation might be an integer_cast which throws if denominator != 1 regards Andy Little
Andy Little wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> wrote:
Would it be kosher for me to grab a bigint class from the Yahoo files section -- say the one by Ronald Garcia and Andrew Lumsdaine -- make sure it is in good shape, and let it be the default template parameter to rational?
Surely int should be the default parameter (if any). Using bigint turns it from a relatively lightweight to a heavyweight type.
The reasons I would make it the default parameter are - it's safer than a limited precision type - I wouldn't have to give it a public name, though it could be accessed as rational<>::int_type. I don't think it would discourage users from using rational<int> where appropriate.
In many uses of rational the values are unlikely to overflow. Some uses are in dividing a circle into degrees, minutes, or seconds, power of dimension in a runtime physical-quantity, Storing imperial lengths eg 1 1/8 " (inch). I would guess that these are the major uses of rational and all have values in quite a small range.
Sounds like a good argument that rational is not completely useless without rounding. Andras?
And of course making bigint the default parameter introduces a dependency, which is at least untidy.
Good point.
BTW why doesnt boost::rational have a 'value_type' member rather than the obscure 'int_type'?
You'd have to ask Paul. I would guess it's mean to reflect the requirements on the template parameter.
Further If the mpl rational (or fraction) becomes part of boost: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?MPL_TODO_List. it would be useful to allow interaction between the compile time and run time types:
I agree. But let's wait a bit. Jonathan
"Jonathan Turkanis" <technews@kangaroologic.com> wrote
Andy Little wrote:
BTW why doesnt boost::rational have a 'value_type' member rather than the obscure 'int_type'?
You'd have to ask Paul. I would guess it's mean to reflect the requirements on the template parameter.
If you are using a rational , you are kind of going to figure out that the value_type should be an integer... I hope. OTOH this requirement can be imposed. However rational should be seen as one of a family of UDT value_type-operable types. (std::complex , boost::rational and boost::interval can all be Op'ed with their value_type. And in fact have a remarkably similar set of function signatures) The nearest precedent in the standard is complex which does have a 'value_type' member. In using UDTs that implement numeric types it is reasonably common to want to know the 'value_type', for which purpose I use a to_value_type<T> function, which by default recursively inspects T::value_type for non-inbuilt types. In determining rational (and incidentally interval) value_types I have had to create specialisations which is tedious. There seems to be no particular reason not to follow the standard name for the value_type in either rational or interval. regards Andy Little
Andy Little wrote:
"Jonathan Turkanis" <technews@kangaroologic.com> wrote
Andy Little wrote:
BTW why doesnt boost::rational have a 'value_type' member rather than the obscure 'int_type'?
You'd have to ask Paul. I would guess it's mean to reflect the requirements on the template parameter.
If you are using a rational , you are kind of going to figure out that the value_type should be an integer... I hope.
It's also documented, of course. But my point was that name was chosen to suit the problem domain.
OTOH this requirement can be imposed.
However rational should be seen as one of a family of UDT value_type-operable types. (std::complex , boost::rational and boost::interval can all be Op'ed with their value_type. And in fact have a remarkably similar set of function signatures)
The nearest precedent in the standard is complex which does have a 'value_type' member. In using UDTs that implement numeric types it is reasonably common to want to know the 'value_type', for which purpose I use a to_value_type<T> function, which by default recursively inspects T::value_type for non-inbuilt types. In determining rational (and incidentally interval) value_types I have had to create specialisations which is tedious. There seems to be no particular reason not to follow the standard name for the value_type in either rational or interval.
The best way to provide a uniform interface for these types would be to provide a TR1 tuple interface. This would be compatible with keeping the name int_type. Jonathan
On Mar 28, 2005 1:29 PM, Andy Little <andy@servocomm.freeserve.co.uk> wrote:
Surely int should be the default parameter (if any). Using bigint turns it from a relatively lightweight to a heavyweight type.
agreed
In many uses of rational the values are unlikely to overflow. Some uses are in dividing a circle into degrees, minutes, or seconds, power of dimension in a runtime physical-quantity, Storing imperial lengths eg 1 1/8 " (inch).
the range of the values has nothing to do with the kind of "overflow" we are talking about; the same way as int or float "overflows" even for small values like 1 divided by 3, rational<> will overflow -- if you recall, there was an example at the very beginning of this discussion where adding 1.xxx to 2.xxx resulted in a negative number with boost::rational<> my guess is that the only application where it does not happen is where you in fact only multiply rational<>s with integers (there was a poster who did this), but you do not need rational<> for that -- maybe your dividing a circle is such an application, but using imperial lengths (even adding two small ones) is not
I would guess that these are the major uses of rational and all have values in quite a small range.
it is very hard to make guesses about the major uses of rational (all we know for sure is our own interest in this) we all want more precise and reliable results, as cheap as possible, and when selecting the arithmetic we use, we make a compromise in some cases (e.g. cryptography) no compromise is acceptable, and there is no choice but to avoid finite precision calculations entirely in most cases we stick with floats, because due to the hardware support they are fast, and most people simply does not know how bad floating point arithmetic really is there are some problems with finite precision (e.g. algebraically equivalent definitions yielding different results due to rounding) that cannot be avoided, but floating point adds its own artifacts on top of this; it was inroduced because it was something that could be implemented efficiently given the knowledge and hardware of those days, and that single advantage overweighted all the disadvantages i can enumerate problems with floating-point endlessly; e.g. in CAD applications these are usually not that we get a result that is not precise enough, but that we get results that are topologically inconsistent, leading to polygons that are convex and concave at same time, points being both before and after another on a line and so on, the end result being correct algorithms getting into infinite loops, aborting or giving impossible results these problems are often solved by obscuring algorithms using tricks, maintaining the history of how these points were calculated (what lines do they match, and what is their ordering), introducing epsiloning (which is an empirical process you can never fully trust) and many other ad-hoc methods (and also by using alternative aritmetic, like interval and lazy) my guess on the major usage of rational<> would be people burnt by floats making CAD, image processing, signal processing, statistical etc applications
And of course making bigint the default parameter introduces a dependency, which is at least untidy.
agreed
BTW why doesnt boost::rational have a 'value_type' member rather than the obscure 'int_type'?
imho rational<> should not have any of these it is not necessary to limit rational<> to use the same type for representing the numerator and denominator, so there is no single value_type/int_type to publish it is not necessary to limit rational<> to represent the numerator and denominator in separate members (i've posted a much more efficient implementation of the current boost::rational<> which requires both the numerator and denominator to be stored in the same data member to be efficient), so the published value_type/int_type may not convey any useful information for the users of rational<>, as you cannot define how is it related to rational<>
As far as errors due to overflow, the problem is not actually in the domain of rational but of the value_type as has been stated before.
stated, but not convincingly explained :O)
rational shouldnt need to know anything about the behaviour of its value_types operations.
but that requirement results in rational<>s that are both inefficient and useless (cannot round) br, andras
"Andras Erdei" <aerdei@gmail.com> wrote in message news:7fe28deb05040601041ad29463@mail.gmail.com...
my guess on the major usage of rational<> would be people burnt by floats making CAD, image processing, signal processing, statistical etc applications
One of the rational<> issues is "Should it be standardized?" The LWG looked at rational<> for TR1, and decided that it would make more sense to consider it later, when a big int class was available. There is now a proposed big int class, so the rational<> question may come up again. One of the questions that the LWG will as is "Are there enough real-world uses to justify the addition of rational<> to the Standard Library?" Thus it might be helpful if real-world users (if any) of boost::rational would occasionally make themselves known. --Beman
On Wed, Apr 06, 2005 at 06:41:56PM -0400, Beman Dawes wrote:
"Andras Erdei" <aerdei@gmail.com> wrote in message news:7fe28deb05040601041ad29463@mail.gmail.com...
my guess on the major usage of rational<> would be people burnt by floats making CAD, image processing, signal processing, statistical etc applications
One of the rational<> issues is "Should it be standardized?"
The LWG looked at rational<> for TR1, and decided that it would make more sense to consider it later, when a big int class was available. There is now a proposed big int class, so the rational<> question may come up again.
One of the questions that the LWG will as is "Are there enough real-world uses to justify the addition of rational<> to the Standard Library?"
Thus it might be helpful if real-world users (if any) of boost::rational would occasionally make themselves known.
I don't know if it qualifies as real-world, but CGAL (www.cgal.org) provides a Quotient<> class and uses it heavily. It is basically the same thing as boost::rational, although I have not checked the differences in detail, nor tried it. It is used together with big ints or big floats, mostly. As far as standardization is concerned, I think a big int class should go together with a big rational class (which can benefit from being template). -- Sylvain
Sylvain Pion wrote:
I don't know if it qualifies as real-world, but CGAL (www.cgal.org) provides a Quotient<> class and uses it heavily. It is basically the same thing as boost::rational, although I have not checked the differences in detail, nor tried it. It is used together with big ints or big floats, mostly.
Since I haven't got many responses from people using boost::rational with finite precision types, maybe Quotient<> can help shed light on the question whether rational<int> is useless without rounding: do you know whether Quotient<> is ever used with finite precision types, and if so, what is its behavior when the result of an operation cannot be expressed exactly?
As far as standardization is concerned, I think a big int class should go together with a big rational class (which can benefit from being template).
Don't you get a "big rational" class for free, as rational<bigint>? Jonathan
On Thu, Apr 07, 2005 at 02:49:17PM -0600, Jonathan Turkanis wrote:
Sylvain Pion wrote:
I don't know if it qualifies as real-world, but CGAL (www.cgal.org) provides a Quotient<> class and uses it heavily. It is basically the same thing as boost::rational, although I have not checked the differences in detail, nor tried it. It is used together with big ints or big floats, mostly.
Since I haven't got many responses from people using boost::rational with finite precision types, maybe Quotient<> can help shed light on the question whether rational<int> is useless without rounding: do you know whether Quotient<> is ever used with finite precision types, and if so, what is its behavior when the result of an operation cannot be expressed exactly?
In the kinds of usages we find in CGAL, I would say that Quotient with a finite precision number type is useless. You can use Quotient<int> of course, it will compile, but I don't see any case where it would be useful. (I don't have any opinion for other application domains such as statistical computations for example.)
As far as standardization is concerned, I think a big int class should go together with a big rational class (which can benefit from being template).
Don't you get a "big rational" class for free, as rational<bigint>?
Basically yes, which is why I don't see why bigint should be standardized without an accompanying way to get a big rational. I would say that one issue is how simplification between numerator/denominator is handled. Various multiprecision rational types I know of and use (from GMP or LEDA) have different policies, so some user tunability might definitely be useful here (via policy or via a run time switch or...). And as far as customizability wrt the template parameter, I would say that the simplification routine between numerator and denominator could be the customization point, so that you do not force gcd or % computation. (I don't know how boost::rational handles it, I should look at it in detail.) -- Sylvain
"Andras Erdei" wrote
On Mar 28, 2005 1:29 PM, Andy Little wrote:
In many uses of rational the values are unlikely to overflow. Some uses are in dividing a circle into degrees, minutes, or seconds, power of dimension in a runtime physical-quantity, Storing imperial lengths eg 1 1/8 " (inch).
the range of the values has nothing to do with the kind of "overflow" we are talking about; the same way as int or float "overflows" even for small values like 1 divided by 3, rational<> will overflow -- if you recall, there was an example at the very beginning of this discussion where adding 1.xxx to 2.xxx resulted in a negative number with boost::rational<>
The use of decimal point representation is not an ideal means to represent a rational number. Use of a bigger int would solve the overflow issue.
my guess is that the only application where it does not happen is where you in fact only multiply rational<>s with integers (there was a poster who did this), but you do not need rational<> for that.
I disagree. . boost::rational provides services such as conversion and i/o which otherwise one has to manually code. It makes the intent clearer and is one less thing to worry about.( you may also require division). You may see this as a trivial use.. but I would certainly prefer to use it in this context, because it models the problem well. -- maybe your dividing a circle
is such an application, but using imperial lengths (even adding two small ones) is not
The imperial lengths example is one where the gcd for different units != 1. This is a special case as Peter Dimov pointed out above in this thread. My use of a rational number would be to store the units only (because of the overflow issues) and use a double for the value. To find the scaling value between units involves only a division. As in the above case one could use an integer, with "a tiny bit more work".
I would guess that these are the major uses of rational and all have values in quite a small range.
it is very hard to make guesses about the major uses of rational (all we know for sure is our own interest in this)
The applications I have cited may be relatively trivial but it is useful for these. [discusion on potential uses of a rational] The heart of the issue seems to be accuracy of analogue numbers. This is obviously a big and important ( and neverending ) topic but I cant help feeling it is a bit bigger than boost::rational. How about a boost::irrational or some other name?
it is not necessary to limit rational<> to use the same type for representing the numerator and denominator, so there is no single value_type/int_type to publish
it is not necessary to limit rational<> to represent the numerator and denominator in separate members (i've posted a much more efficient implementation of the current boost::rational<> which requires both the numerator and denominator to be stored in the same data member to be efficient), so the published value_type/int_type may not convey any useful information for the users of rational<>, as you cannot define how is it related to rational<>
One would require it to interact with other types (presumably inbuilt types) at least for purposes of initialisation and conversion. You need to know what types to use as initialisers.
As far as errors due to overflow, the problem is not actually in the domain of rational but of the value_type as has been stated before.
stated, but not convincingly explained :O)
This is simply the finite_int, versus bigint issue. Use a bigint to avoid overflow. Use an int for speed and small footprint, where you have a small range in numerator, denominators values.
rational shouldnt need to know anything about the behaviour of its value_types operations.
but that requirement results in rational<>s that are both inefficient and useless (cannot round)
Is a rational number implementation that has been rounded, a rational number?... Yes, but not the one you expected. How do you know if it has been rounded? Will the rounding be the same on different implementations. Keep rational for use on 'rational numbers' where absolute predicability, repeatability and accuracy is required. OTOH You have requirements for a type that has some of the theoretical properties of rational but also with some of the properties of a float (approximate representation of numbers which may or may not be rational numbers). That is not rational but is interesting. Perhaps it would be interesting to talk about how this type might be implemented and what its properties and requirements might be. regards Andy Little
On Apr 9, 2005 3:11 PM, Andy Little <andy@servocomm.freeserve.co.uk> wrote:
The use of decimal point representation is not an ideal means to represent a rational number.
of course not, i just did not bother with looking up the the original example which was rational<short> with 191/181 (=1.055...) + 197/193 (=1.021...) resulting in 6984/-30603 (=-0.229...) on my PC [the correct result is 72520/34933 (=2.076...) and the rounding implementation gives 3197/1540, precise to 7 decimal digits]
Use of a bigger int would solve the overflow issue.
if you mean a bigger, but still finite int, then no it doesn't; with a 16 bit short rational<short> can represent roughly 2^29 different values, out of which let's say 2^13 can be used safely (added together without "overflow"), which is less than 0.002% of them; if you try to solve this by switching to rational<int> (assuming 32 bit ints), you will be able to add together all your rational<short>s, *but not the results of these additions* (only about 2*10^-8 percent of those results are still "addable"); so yes, you can make a single operation work, but that is far from having a useful arithmetic, where you can add together even three or four numbers if you mean "bigint" -- i did not want to fight on several fronts, but it looks like we really have to discuss everything at the same time: exact (unlimited precision) precision arithetic is a different issue, which may or may not have something to do with the discussion about rational<> if we want an exact type (and we do want it) the tasks are to reach an agreement about the interface and semantics of the type, and to provide an implementation, where we have several options including some kind of rational<bigint> and also unlimited "fixed point", something based on continued fractions and a lot of more esoteric ones (like linear fractional transformations, iterated exponential functions etc) imho the interface and semantics in any case should allow using expression templates (unlike the current rational rational proposal made for the standard) and possibly some kind of lazy arithmetic (i'm not sure about this latter one), and they definitely should allow _any_ conceivable implementation, and not limit it to rational<bigint> the single rational<bigint> implementation itself should not determine the looks of our exact type imho the finite precision rational<> (which is useful in itself and is a viable alternative for float) is a separate issue from having an exact arithmetic type
I disagree. . boost::rational provides services such as conversion and i/o which otherwise one has to manually code. It makes the intent clearer and is one less thing to worry about.( you may also require division). You may see this as a trivial use.. but I would certainly prefer to use it in this context, because it models the problem well.
this is true, and i actually thought about mentioning it in my post, but then decided to let it go -- rational<> can be used as this kind of convenience class regardless of the issues (rounding) we are discussing
The imperial lengths example is one where the gcd for different units != 1. My use of a rational number would be to store the units only (because of the overflow issues) and use a double for the value. To find the scaling value between units involves only a division. As in the above case one could use an integer, with "a tiny bit more work".
ok, got it now
I would guess that these are the major uses of rational and all have values in quite a small range.
as you can see in the example at the top, the values being small (whenever you mean by this that the actual values are small, or that the numerators and denominators used in the representation are small) is no guarantee against the kind of "overflow" we have been discussing also, imho naive users will not expect things like operator< to "overflow" as they do in the current boost::rational<> imho basically everything overflows, all the time, and in the few cases where it doesn't, you don't gain anything by using the non-rounding legacy implementation
The heart of the issue seems to be accuracy of analogue numbers. This is obviously a big and important ( and neverending ) topic but I cant help feeling it is a bit bigger than boost::rational. How about a boost::irrational or some other name?
not sure i got this one; are you proposing to leave the current boost::rational<> as it is, and introducing some other name instead for the rounding type?
it is not necessary to limit rational<> to use the same type for representing the numerator and denominator, so there is no single value_type/int_type to publish
it is not necessary to limit rational<> to represent the numerator and denominator in separate members (i've posted a much more efficient implementation of the current boost::rational<> which requires both the numerator and denominator to be stored in the same data member to be efficient), so the published value_type/int_type may not convey any useful information for the users of rational<>, as you cannot define how is it related to rational<>
One would require it to interact with other types (presumably inbuilt types) at least for purposes of initialisation and conversion. You need to know what types to use as initialisers.
but that is again a different issue: of course it has to export the types returned by numerator() and denominator(), but iirc you were referring to some other use (something like determining whether the given rational is implemented using built-in types) -- am i wrong?
As far as errors due to overflow, the problem is not actually in the domain of rational but of the value_type as has been stated before.
stated, but not convincingly explained :O)
This is simply the finite_int, versus bigint issue. Use a bigint to avoid overflow. Use an int for speed and small footprint, where you have a small range in numerator, denominators values.
imho use an exact type where computations need to be exact, and use finite precision rationals where floats are crap (or rather, use them by default, and switch to floats when speed requires it, and you are sure you wont be hurt by them)
rational shouldnt need to know anything about the behaviour of its value_types operations.
but that requirement results in rational<>s that are both inefficient and useless (cannot round)
Is a rational number implementation that has been rounded, a rational number?... Yes, but not the one you expected.
can you rephrase this (most likely i don't get this one because of my english)
How do you know if it has been rounded?
one option is to use the rational<> variant which maintains an exactness flag (should worth mentioning here i'm not sure i've chosen the right word, the flag can mean both a rounded result of an operation on exact values and a value which comes from some inexact source, like a measurement) the other option is not to bother with it, just like you do in every other case of finite aritmetic (ints and floats)
Will the rounding be the same on different implementations.
yes for finite precision rationals there is "natural" rounding which is well-defined, independent of the actual implementation, and has tons of nice mathematical and practical properties this is in contrast with rounding in radix-based arithmetic (fixed and floating point) where the rounding can be very suprising (e.g. the default rounding method used by your PC is to round to the nearest number, but it is the nearest *binary* number, so 1/3=0.3333... is 0.33..34, not 0.33..33 as it would be with decimal representation, which comes as quite a shock to most people) also, different rational systems are "embedded" in each other, so if you make conversions between two such systems (be it rational<short> and rational<int> on one machine, or between rational<int>s on different machines) there is at most one step where the number changes (gets rounded to a value in the less precise system) in contrast, converting a number from decimal scientific notation into the best binary floating point approximation cannot be done using finite arithmetic (this is why the IEEE standard does not require the result to be the best approximation), and iirc repeated conversion between two floating point systems can even result in diverging results this may sound as an esoteric problem, after all who uses non-binary machines? but in fact we all do -- computations are made on binary representations, but i/o (including storing/transferring your numbers for non-human consumption) is usually done using decimal representation
Keep rational for use on 'rational numbers' where absolute predicability, repeatability and accuracy is required.
i'm not sure if you mean by this to 'keep the name rational for exact arithmetic' or 'keep the name rational for the legacy boost implementation'
OTOH You have requirements for a type that has some of the theoretical properties of rational
imho boost::rational<> does not have the theoretical properties of rationals (whatever those are), but can mislead people into thinking it does imho boost::rational<bigint> has the theoretical properties of an exact arithmetic type, but there are implementation details leaked into the interface, and it is not a very efficient implementation of an exact type (as it is not very efficient implementation of an unlimited precision rational type, because it makes a half-hearted attempt at being both a finite and an unlimited arithmetic type)
but also with some of the properties of a float (approximate representation of numbers which may or may not be rational numbers). That is not rational but is interesting. Perhaps it would be
that is not a rational, but a finite precision rational
interesting to talk about how this type might be implemented and what its properties and requirements might be.
trying to do that :O) br, andras
On Tue, 12 Apr 2005 18:26:48 +0200, Andras Erdei <aerdei@gmail.com> wrote: [snip]
for finite precision rationals there is "natural" rounding which is well-defined, independent of the actual implementation, and has tons of nice mathematical and practical properties
[snip] ...sorry, I think I slept during that class, what is the "natural" rounding for rational numbers? --- Søren -- Med venlig hilsen
On 4/16/05, Søren Lassen <s.lassen@post.tele.dk> wrote:
On Tue, 12 Apr 2005 18:26:48 +0200, Andras Erdei <aerdei@gmail.com> wrote:
[snip]
for finite precision rationals there is "natural" rounding which is well-defined, independent of the actual implementation, and has tons of nice mathematical and practical properties
[snip]
...sorry, I think I slept during that class, what is the "natural" rounding for rational numbers?
see http://lists.boost.org/MailArchives/boost/msg76956.php br, andras
"Andras Erdei" <aerdei@gmail.com> wrote in message news:7fe28deb05041209262c56cea8@mail.gmail.com...
On Apr 9, 2005 3:11 PM, Andy Little <andy@servocomm.freeserve.co.uk> wrote:
Apologies for not answering the other points. This is a complicated issue and I dont have answers.. Nevertheless I thought I better respond to this, because life is easy for me, English being my native language.
Is a rational number implementation that has been rounded, a rational number?... Yes, but not the one you expected.
can you rephrase this (most likely i don't get this one because of my english)
Assume you add 1/2 + 1/3 and you get the result 2/3 or 1/1. (assume a rational<uint2>) 2/3 is a rational number as is 1/1. BTW what would be the result in your rounding version of the calculation? regards Andy Little .
On 4/17/05, Andy Little <andy@servocomm.freeserve.co.uk> wrote:
Apologies for not answering the other points. This is a complicated issue and I dont have answers..
i also don't know much about rationals (there is much about them i don't know?), so i often fall back to asking mathematician friends when faced with problems, unfortunately it turned out there are lots of things they don't know either
Is a rational number implementation that has been rounded, a rational number?... Yes, but not the one you expected.
can you rephrase this (most likely i don't get this one because of my english)
Assume you add 1/2 + 1/3 and you get the result 2/3 or 1/1. (assume a rational<uint2>) 2/3 is a rational number as is 1/1.
[i also assume that uint2 means the numerator and denominator can be 0..3, thus the representable values are 0/1,1/3,1/2,2/3,1/1,3/2,2/1,3/1,1/0]
BTW what would be the result in your rounding version of the calculation?
[if you haven't yet, please check http://lists.boost.org/MailArchives/boost/msg76956.php] the exact result (5/6) is the median of two representable numbers (1/1 and 2/3), in such cases the algorithm always chooses the simpler one (p/q is simpler than r/s if p <= r and q <= s and at least one inequality is strict), thus the rounded result would be 1/1 you can view the numbers representable with rational<n> as a set of numbers closed under the simpler than relation (any number simpler than a representable number is also representable); an interesting property is that simpler numbers have wider associated rounding intervals -- e.g. in rational<5> where 1/3 and 2/5 are adjacent, more numbers will be rounded towards 1/3 than 2/5, which means that when a series of exact calculations would result in some "special" value, you often get that result even if the intermediate values were rounded btw it's not "my" rounding, the math background comes from continued fractions br, andras
On 4/12/05, Andras Erdei <aerdei@gmail.com> wrote:
exact (unlimited precision) arithmetic is a different issue, which may or may not have something to do with the discussion about rational<>
just found an (non-rational<>) exact type with c++ implementation (but haven't checked it yet): http://more.btexact.com/people/briggsk2/XR.html http://www.google.com/search?hl=en&q=constructive+reals+boehm+hans&btnG=Google+Search br, andras
Hi! Just a couple of words to introduce myself: I am from Denmark, but currently living in Nicaragua, where my wife is employed at the Danish embassy. I suppose this means that my current job title is "spouse". Before moving, I made a living as a Data Warehouse programmer/analyst. Having more time on my hands, I decided to spend some of it learning C++. In my experience, one of the best ways to learn a programming language is by looking at (and possibly trying to improve) existing code, preferably of good quality. Which is why I am now showing up on the boost mailing list. I have spent some time playing around with the rational.hpp file, and have made some improvements. Most important is probably operator<, where my new version is completely safe from overflow and (I think) considerably faster. Other features are: a member template for converting between different types of rationals, functions inverse() and power(). Should I put my version of rational.hpp on the sandbox CVS, or mail it to somebody - or is it not relevant at this time? Anyway, considering the call for new features: Maybe the class should have a representation of +-infinity and NAN (the latter follows logically from the former, because infinity*0->NAN). There may be quite a lot of cases where it is not the best solution to throw exceptions for divisions by zero, e.g. a spreadsheet or calculator application, where the user may do all kinds of funny things - when a division by zero occurs, we just want to mark the affected variable as infinite, and write "DIV/0" or something similar in the relevant space in the application UI. The easiest way to accomplish this is to implement it as a selectable feature in the rational class, rather than checking for zero before each division, or setting up try...catch blocks around all the division operations. Of course, the introduction of NAN rationals makes the class only partially ordered (if we follow the floating-point standard, where all comparison operations involving NAN types return false). --- Søren P.S. Have I posted this reply to the call for features in the right way? If not, what is the right way, using Opera for newsgroups and mail?
Søren Lassen wrote:
Hi!
Just a couple of words to introduce myself: I am from Denmark, but currently living in Nicaragua, where my wife is employed at the Danish embassy. I suppose this means that my current job title is "spouse". Before moving, I made a living as a Data Warehouse programmer/analyst.
Good to meet you!
I have spent some time playing around with the rational.hpp file, and have made some improvements. Most important is probably operator<, where my new version is completely safe from overflow and (I think) considerably faster. Other features are: a member template for converting between different types of rationals, functions inverse() and power().
Should I put my version of rational.hpp on the sandbox CVS, or mail it to somebody - or is it not relevant at this time?
I think the sandbox vault (http://boost-sandbox.sourceforge.net/vault/) would be the right place.
Anyway, considering the call for new features: Maybe the class should have a representation of +-infinity and NAN (the latter follows logically from the former, because infinity*0->NAN). There may be quite a lot of cases where it is not the best solution to throw exceptions for divisions by zero, e.g. a spreadsheet or calculator application, where the user may do all kinds of funny things - when a division by zero occurs, we just want to mark the affected variable as infinite, and write "DIV/0" or something similar in the relevant space in the application UI. The easiest way to accomplish this is to implement it as a selectable feature in the rational class, rather than checking for zero before each division, or setting up try...catch blocks around all the division operations. Of course, the introduction of NAN rationals makes the class only partially ordered (if we follow the floating-point standard, where all comparison operations involving NAN types return false).
Søren
P.S. Have I posted this reply to the call for features in the right way? If not, what is the right way, using Opera for newsgroups and mail?
Yes, you posted correctly. Thanks for all your suggestions. Right now I'm scrambling to make last minute changes to the iostreams library before release 1.33. Because of my tardiness new features for rational will not be introduced until the release following 1.33, but after the release I will carefully consider all the suggestions made by posters in this thread. Jonathan
On Wed, 6 Apr 2005 11:15:31 -0600, Jonathan Turkanis <technews@kangaroologic.com> wrote:
I think the sandbox vault (http://boost-sandbox.sourceforge.net/vault/) would be the right place.
I have a problem: I have now written to two of the sandbox administrators, requesting write access (first mail was sent right after reading your reply, more than a week ago), but no reaction. Is there another way to get write access to the sandbox vault? -- Søren
Søren Lassen wrote:
On Wed, 6 Apr 2005 11:15:31 -0600, Jonathan Turkanis <technews@kangaroologic.com> wrote:
I think the sandbox vault (http://boost-sandbox.sourceforge.net/vault/) would be the right place.
I have a problem: I have now written to two of the sandbox administrators, requesting write access (first mail was sent right after reading your reply, more than a week ago), but no reaction. Is there another way to get write access to the sandbox vault?
I think the sandbox vault is supposed to be publicly accessible using the web interface, but that sandbox CVS requires authorization. If you want CVS access, you're doing the right thing. Perhaps you have received no reply because of the standards committee meeting which just ended. Jonathan
On Sat, 16 Apr 2005 12:47:12 -0600, Jonathan Turkanis wrote
I think the sandbox vault is supposed to be publicly accessible using the web interface, but that sandbox CVS requires authorization.
If you want CVS access, you're doing the right thing. Perhaps you have received no reply because of the standards committee meeting which just ended.
Did you follow the login/register link at the top of the page? I'm not sure that there is actually an admin in the loop... Jeff
On Sat, 16 Apr 2005 12:14:16 -0700, Jeff Garland <jeff@crystalclearsoftware.com> wrote:
On Sat, 16 Apr 2005 12:47:12 -0600, Jonathan Turkanis wrote
I think the sandbox vault is supposed to be publicly accessible using the web interface, but that sandbox CVS requires authorization.
If you want CVS access, you're doing the right thing. Perhaps you have received no reply because of the standards committee meeting which just ended.
Did you follow the login/register link at the top of the page? I'm not sure that there is actually an admin in the loop...
Jeff
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
You are right, I have now registered in the Sandbox Vault instead of the CVS, and it works. I have uploaded my new version of rational.hpp to the vault. Thanks, Søren
"Jonathan Turkanis" <technews@kangaroologic.com> wrote
2. What changes or additions would people like to see?
One could make some modifications to rational to make them it user friendly. For example the following results in a compile time failure n VC7.1: boost::rational<int> r1; boost::rational<long> r2; r1 + r2; Naturally if a bigint rational was to be used, I would expect rational<bigint>() + rational<int>() to work. This is fairly trivial to accomplish using BOOST_TYPEOF: eg something like template <typename Lhs, typename Rhs> typename boost::enable_if< // only for compat with current header boost::mpl::not_< boost::is_same< Lhs, Rhs> >, rational<typename BOOST_TYPEOF(Lhs() + Rhs())> >::type operator + (rational<Lhs> const & lhs, rational<Rhs> const& rhs); FWIW this applies as well to other UDTs including interval and complex. which are currently inconsistent eg std:::complex<double> d ; d * 2; // fails to compile d *= 2; // compiles ok regards Andy Little
participants (15)
-
Andras Erdei -
Andy Little -
Beman Dawes -
David Abrahams -
Guillaume Melquiond -
Jeff Garland -
Jonathan Turkanis -
Keith Burton -
Lucas Galfaso -
Manuel Menezes de Sequeira -
Peter Dimov -
Robert Ramey -
Ross Boylan -
Sylvain Pion -
Søren Lassen