rational variants/alternatives
i've started to work on the variants that were brought up in a previous discussion about boost::rational<> the current code can be found at www.ccg.hu/pub/src/rat atm it is only for getting the calculations right, so no templates, optimizations, boostification, nice interface etc, and i only tested it with MSVC 7.1 there is also no implementation yet geared towards an unlimited precision representation the variants are: - legacy boost (no rounding, silently gives wrong results) - exceptions are thrown if the result overflows or cannot be represented - rounding - rounding & maintaining an exactness indicator is there anything missing from the list? there is also a simple test-bed, it runs the four basic operations 10000 times on random inputs, and collects some statistics: addition and substraction overflowed 0 times, and the result was exactly representable 44 times; the average error of the legacy code is 475%, and of the rounding code is 0.005% (the exception-throwing variant throws, so there is no error figure for that) multiplication and division overflowed once, and the result was exactly representable 79 times; the average error of the legacy code is 2025%, and of the rounding code is 0.01% it would be nice to get some advice on how the final interface should look like (and of course regarding everything else, including whether there is a point to continue the work): - any ideas for naming the variants? - how should the parameters of rational<> look like? my favourite would be rational<prec,method> where prec is the maximum absolute value allowed for numerators and denominators, and method is one of the variants from above, e.g. rational<10000,round> would be a rounding rational with four decimal digits for the numerator and denominator. of course this would cripple rational<> to be int-based, so maybe specifying the number of bits to be used instead of the maximum value is a sensible approach. (still don't know though how would user-defined types be selected based on this, so maybe the original boost approach is the only workable one.) br, andras ps: i have tried to search the archive for past discussions about rational<> to avoid repeating old stuff, but with very limited success (only the latest posts seem to be accessible) -- any hints?
Andras Erdei wrote: I'm sorry I haven't got around to looking at your code yet. I've been swamped with other stuff -- but that's not a good excuse to have put it off this long.
i've started to work on the variants that were brought up in a previous discussion about boost::rational<>
the current code can be found at www.ccg.hu/pub/src/rat
atm it is only for getting the calculations right, so no templates, optimizations, boostification, nice interface etc, and i only tested it with MSVC 7.1
there is also no implementation yet geared towards an unlimited precision representation
the variants are:
- legacy boost (no rounding, silently gives wrong results) - exceptions are thrown if the result overflows or cannot be represented - rounding - rounding & maintaining an exactness indicator
is there anything missing from the list?
We might want to allow different rounding policies. Also, we might want assertion failures instead of exceptions.
there is also a simple test-bed, it runs the four basic operations 10000 times on random inputs, and collects some statistics:
addition and substraction overflowed 0 times, and the result was exactly representable 44 times; the average error of the legacy code is 475%, and of the rounding code is 0.005% (the exception-throwing variant throws, so there is no error figure for that)
The "legacy" code doesn't do too well. Before I was insisting that the current behavior be the default, for backward compatibility. Now I'm open to changing the default behavior, depending on what we can discover about how rational is actually being used.
multiplication and division overflowed once, and the result was exactly representable 79 times; the average error of the legacy code is 2025%, and of the rounding code is 0.01%
it would be nice to get some advice on how the final interface should look like (and of course regarding everything else, including whether there is a point to continue the work):
Definitely it is worthwhile.
- any ideas for naming the variants?
- how should the parameters of rational<> look like?
The most obvious signature would be template< typename Elem, typename Rounding = use_default, typename Checking = use_default > class rational; However, it may be that if we want to avoid sticking all the arithmetic calulations in policy member functions, the only reasonable rounding policy is the one you suggested before. In that case it would just look like template<typename Elem, typename Checking = use_default> class rational;
my favourite would be rational<prec,method> where prec is the maximum absolute value allowed for numerators and denominators, and method is one of the variants from above, e.g. rational<10000,round> would be a rounding rational with four decimal digits for the numerator and denominator.
I don't like this. Shouldn't rational<Elem> make sense for any type Elem for which the Euclidean algorithm makes sense? I think you can get the effect of restricting the absolute value of the numerator and denominator by passing user defined types as Elem. Using a little metaprogramming rational<> could be made to use int in signatures of member functions such as numerator() and denominator(). Something like template<int Max> struct restricted_int { typedef int element_type; restricted_int(int); opertator int() const; ... }; Then you could get the effect you were describing by using rational< restricted_int<1000>, ...> If this seems akward, a restrcted_rational could be built as a thin layer on top off rational. It could even be generalized by allowing the underlying type to vary. ps: i have tried to search the archive for past discussions about
rational<> to avoid repeating old stuff, but with very limited success (only the latest posts seem to be accessible) -- any hints?
Searching my local archives I get lots of messages, going back to Paul's first proposal in 1999. So one way is to download all the old messages with a newsreader. They also seem to be accessible via Google. E.g., search for "I was amazed to find that there isn't a basic rational numbers class" Jonathan
On Sun, 6 Mar 2005 20:50:12 -0700, Jonathan Turkanis <technews@kangaroologic.com> wrote:
We might want to allow different rounding policies.
i'll try to write an explanation on why i think there is a single Right rounding method, but it'll take time in case you can convince me, or i can't convince you, and we end up with several rounding policies, give a thought to this: rounding is a property of the operations, not the representation, so one may want + to round upwards and * to round downwards (or this particular + to round up, and the next one to truncate)...
Also, we might want assertion failures instead of exceptions.
ok, that's a new variant, then :O)
The "legacy" code doesn't do too well.
i'm not sure how indicative a test with 10000 random numbers is, maybe doing the operations on the results of previous operations would be closer to the real-life scenarios, but atm the statistics are a side-effect only, the test bed is only intentended to catch blatant errors in the implementations
The most obvious signature would be
template< typename Elem, typename Rounding = use_default, typename Checking = use_default > class rational;
[i assume checking would mean reacting by assertion failures, throwing exceptions etc. did i misunderstood?] theory: rounding (or not), and checking is an either/or: if you do rounding (or ignore the overflows), you have a result, and the operation succeeded, if you fail/thow the operation failed, and no need to bother with rounding the result you can't return implementation: with assertions and exceptions it seems polite to leave the operands unchanged (so if a *= a fails, you can print the offending a), but that requires temporaries, maintaining which can seriously degrade performance of the rounding/ignoring code
I don't like this. Shouldn't rational<Elem> make sense for any type Elem for which the Euclidean algorithm makes sense?
yes, it should, i was thinking more about what a user wants: "i'm writing an architectural CAD application, and my i/o numbers will be in meters, with millimeter precision, largest value less than a hundred meters, the calculations are this complex, so i want intermediate results with .01mm precision, and volumes at most 1e6 m^3, thus i need rational<1000000>" it is less obvious why a user would say "i want rational<long>" (also if the user is developing for multiple platforms this one gets ugly) still, rational<1000,round> will end up triggering a policy to be used, so a hard-line user can still create her own policy to enforce a rational with unsigned char numerator and unsigned long long denominator for her special high-precision calculations with non-negative numbers less than 1
I think you can get the effect of restricting the absolute value of the <snip>
[the intent was not bother users with what i feel is implementation details of the representation, but] i was wondering whether it makes sense to allow restricting the num/den ranges: why would anyone ever deliberately want less precise results than she can get for free? otoh one may want to get the exact same results on a two's complement 32 bit binary machine as on her other, signed decimal architecture, question is whether something like this will ever happen... (if not, always using the native limits may allow some implementation optimizations, don't know yet) adding an explicit round(num_max,den_max) or round(num_min,num_max,den_max) fn might be a much more useful alternative br, andras
[I thought I already replied to this, but I guess it got lost] Andras Erdei wrote:
On Sun, 6 Mar 2005 20:50:12 -0700, Jonathan Turkanis <technews@kangaroologic.com> wrote:
We might want to allow different rounding policies.
i'll try to write an explanation on why i think there is a single Right rounding method, but it'll take time
This is what I was hinting at here: Jonathan Turkanis wrote:
However, it may be that if we want to avoid sticking all the arithmetic calulations in policy member functions, the only reasonable rounding policy is the one you suggested before. In that case it would just look like
in case you can convince me, or i can't convince you, and we end up with several rounding policies, give a thought to this: rounding is a property of the operations, not the representation,
Agreed.
so one may want + to round upwards and * to round downwards (or this particular + to round up, and the next one to truncate)...
Why would you want that?
Also, we might want assertion failures instead of exceptions.
ok, that's a new variant, then :O)
The "legacy" code doesn't do too well.
i'm not sure how indicative a test with 10000 random numbers is, maybe doing the operations on the results of previous operations would be closer to the real-life scenarios,
True, but I think it would just increase the disparity.
The most obvious signature would be
template< typename Elem, typename Rounding = use_default, typename Checking = use_default > class rational;
[i assume checking would mean reacting by assertion failures, throwing exceptions etc. did i misunderstood?]
Right. I'm borrowing the name "CheckingPolicy" from Andrei Alexandrescu.
theory: rounding (or not), and checking is an either/or: if you do rounding (or ignore the overflows), you have a result, and the operation succeeded, if you fail/thow the operation failed, and no need to bother with rounding the result you can't return
The above declaration was based on the assumption that multiple rounding policies should be supported. If there's only one way to round, then rounding can be merged into the checking policy.
implementation: with assertions and exceptions it seems polite to leave the operands unchanged (so if a *= a fails, you can print the offending a),
but that requires temporaries, maintaining which can seriously degrade performance of the rounding/ignoring code
You're arguing that rational should provide the strong guarantee of exception safety rather than the basic guarantee. If we can verify that providing the strong guarantee does degrade performance, than we shouldn't do it. Or we could make the level of exception safety configurable, but I'd really like to avoid that.
I don't like this. Shouldn't rational<Elem> make sense for any type Elem for which the Euclidean algorithm makes sense?
yes, it should, i was thinking more about what a user wants: "i'm writing an architectural CAD application, and my i/o numbers will be in meters, with millimeter precision, largest value less than a hundred meters, the calculations are this complex, so i want intermediate results with .01mm precision, and volumes at most 1e6 m^3, thus i need rational<1000000>"
it is less obvious why a user would say "i want rational<long>" (also if the user is developing for multiple platforms this one gets ugly)
still, rational<1000,round> will end up triggering a policy to be used, so a hard-line user can still create her own policy to enforce a rational with unsigned char numerator and unsigned long long denominator for her special high-precision calculations with non-negative numbers lessthan 1
I understand what your saying, but I can't tell what template parameters you think rational should have.
I think you can get the effect of restricting the absolute value of the <snip>
[the intent was not bother users with what i feel is implementation details of the representation, but]
i was wondering whether it makes sense to allow restricting the num/den ranges: why would anyone ever deliberately want less precise results than she can get for free? otoh one may want to get the exact same results on a two's complement 32 bit binary machine as on her other, signed decimal architecture, question is whether something like this will ever happen... (if not, always using the native limits may allow some implementation optimizations, don't know yet)
My inclination is to keep everything as simple as possible; we should only add what's clearly missing.
adding an explicit round(num_max,den_max) or round(num_min,num_max,den_max) fn might be a much more useful alternative
This reminds me: perhaps we can borrow some machinery or interface design from numeric_conversion: http://www.boost.org/libs/numeric/conversion/doc/index.html Jonathan
On Mon, 7 Mar 2005 17:50:48 -0700, Jonathan Turkanis <technews@kangaroologic.com> wrote:
I can't tell what template parameters you think rational should have.
(it is because i don't know myself :O) i think we need two parameters: one for specifying the precision, and one for specifying the variant to use the problems: 1. if we specify the precision as an integer, e.g. rational<1000> meaning a rational with numerator range (-1000,1000) and denominator range (1,1000), then we restrict the possible underlying types to the integer type used as the template parameter (and smaller) a possible workaround is to specify the log of the limits instead, so e.g. rational<31> would mean (-2^31,2^31) and (1,2^31) -- this is less flexible, than the above one, but i can't come up with anything better 2. i don't know how can we implement the selection of UDTs: let's say i have implemented a modular arithmetic bigint type, with up to a few hundred bits of precision -- how can i tell rational that it can select this as the underlying type? <snip>
The above declaration was based on the assumption that multiple rounding policies should be supported. If there's only one way to round, then rounding can be merged into the checking policy.
i don't see how this depends on having more than one kind of rounding: either you round, or you check, cannot do both at the same time -- do i miss something? br, andras
Andras Erdei wrote:
On Mon, 7 Mar 2005 17:50:48 -0700, Jonathan Turkanis <technews@kangaroologic.com> wrote:
I can't tell what template parameters you think rational should have.
(it is because i don't know myself :O)
Okay.
i think we need two parameters: one for specifying the precision, and one for specifying the variant to use
But this leaves out the int_type; users must be able to write rational<big_int> or similarly for any UDT which supports the euclidean algorithm.
the problems:
1. if we specify the precision as an integer, e.g. rational<1000> meaning a rational with numerator range (-1000,1000) and denominator range (1,1000), then we restrict the possible underlying types to the integer type used as the template parameter (and smaller)
a possible workaround is to specify the log of the limits instead, so e.g. rational<31> would mean (-2^31,2^31) and (1,2^31) -- this is less flexible, than the above one, but i can't come up with anything better
I believe precision should be specified by supplying an appropriate type as the int type, e.g., restricted_int<1000>.
2. i don't know how can we implement the selection of UDTs: let's say i have implemented a modular arithmetic bigint type, with up to a few hundred bits of precision -- how can i tell rational that it can select this as the underlying type?
It has to be specified as a template parameter. Even if we specified a whole range of types, including big_int, to serve as the underlying type depending on the specified precision, an arbitrary user-supplied type would never be selected.
<snip>
The above declaration was based on the assumption that multiple rounding policies should be supported. If there's only one way to round, then rounding can be merged into the checking policy.
i don't see how this depends on having more than one kind of rounding: either you round, or you check, cannot do both at the same time -- do i miss something?
Okay, I see. The various checking policies, such as assert_check, etc., are just rounding policies which alert the used that something has gone wrong as soon as it is determined that rounding is required. Good. So rational should look like: template<typename Elem, typename Rounding = use_default> class rational; On top of this could be built a restricted precision rational class. Jonathan
Jonathan Turkanis wrote:
i think we need two parameters: one for specifying the precision, and one for specifying the variant to use
But this leaves out the int_type; users must be able to write
rational<big_int>
or similarly for any UDT which supports the euclidean algorithm.
[personally i don't like the name big_int, i always have to translate it mentally from meaning "arbitrary/big, but limited precision" like a modular arithmetic based integer type, to "unlimited (dynamic) precision"] i'm not entirely convinced that the unlimited precision rational should be treated (at the interface level) as a special case of the fixed precision rational type: rounding/checking does not make sense with it, it may turn out to require a (sadly) slightly different interface (e.g. it may be better off with allowing expression templates to be used -- although that could be true for limited precision as well), and the implementation will surely not share code with that of limited precision keeping it separate may also solve our backward compatyibility problem (having no rounding by default): if rational<> is kept for unlimited (but allow instantiation with any type), then we'll still have the legacy behaviour, and we can choose a new name for limited rational, e.g. rational being an alias for unlimited::rational, and having separate limited::rational and unlimited::rational
I believe precision should be specified by supplying an appropriate type as the int type, e.g., restricted_int<1000>.
the point of specifying the limit would be to free the user from having to portably figure out which is the fastest type on the given platform whose precision exceeds the limit given (not having to specify a type at all)
2. i don't know how can we implement the selection of UDTs: let's say i have implemented a modular arithmetic bigint type, with up to a few hundred bits of precision -- how can i tell rational that it can select this as the underlying type?
It has to be specified as a template parameter. Even if we specified a whole range of types, including big_int, to serve as the underlying type depending on the specified precision, an arbitrary user-supplied type would never be selected.
i was hoping for some solution that e.g. allows UDTs to be somehow registered (at compile time) and then selected by rational automagically, but again, i'm not sure it is good what i hope for -- maybe it's simpler and more natural to say rational<modular> than register(modular) and then rational<128>
On top of this could be built a restricted precision rational class.
if you mean rational<10000,round> will translate to something like rational<int,int,...,round>, and the latter would also be directly available to users who need it, then of course, i just wouldn't make it the top-level interface, rather something for advanced users who know what they are doing br, andras
Andras Erdei wrote:
Jonathan Turkanis wrote:
i think we need two parameters: one for specifying the precision, and one for specifying the variant to use
But this leaves out the int_type; users must be able to write
rational<big_int>
or similarly for any UDT which supports the euclidean algorithm.
[personally i don't like the name big_int, i always have to translate it mentally from meaning "arbitrary/big, but limited precision" like a modular arithmetic based integer type, to "unlimited (dynamic) precision"]
i'm not entirely convinced that the unlimited precision rational should be treated (at the interface level) as a special case of the fixed precision rational type: rounding/checking does not make sense with it, it may turn out to require a (sadly) slightly different interface (e.g. it may be better off with allowing expression templates to be used -- although that could be true for limited precision as well), and the implementation will surely not share code with that of limited precision
I've started a new thread "[rational] Announcing new maintainer -- call for feature requests" Jonathan
what would you say to this: namespace rational { template < class unlimited > class unlimited { //... } ; enum policy { round , round_and_exactness , exception , assert } ; // for power users template < typename limited , policy rounding = round > class fxs_ { //... } ; typedef __int64 biggest_builtin ; // for end-users template < biggest_builtin limit = INT_MAX , policy rounding = round > class fxs : public fxs_< fastest type that can hold [-limit...limit] , rounding > { //... } ; // if you are really desperate and want to specify by hand // the num_type, den_type, num_min, num_max, den_min, den_max etc // there is a way to create your own policy blob // of course we need better names than fxs and fxs_ } br, andras
Andras Erdei wrote:
what would you say to this:
namespace rational {
template < class unlimited > class unlimited { //... } ;
enum policy { round , round_and_exactness , exception , assert } ;
// for power users template < typename limited , policy rounding = round > class fxs_ { //... } ;
typedef __int64 biggest_builtin ;
// for end-users template < biggest_builtin limit = INT_MAX , policy rounding = round > class fxs : public fxs_< fastest type that can hold [-limit...limit] , rounding > { //... } ;
// if you are really desperate and want to specify by hand // the num_type, den_type, num_min, num_max, den_min, den_max etc // there is a way to create your own policy blob
// of course we need better names than fxs and fxs_
}
Do I understand correctly that rational::unlimited would be like the current rational, while rational::fxs would provide a separate interface for rationals based on built-in integral types? Would there be any shared implementation? Is fxs for power-users too, or just fxs_? I agree that a better name than "fxs" is needed. Could you give me a hint what it means? ;-) Jonathan
Jonathan Turkanis wrote:
template < class unlimited > class unlimited
Do I understand correctly that rational::unlimited would be like the current rational,
it would be intended for unlimited precision (bigint) types, and be very similar to the current rational (except that it can use expression templates to avoid executing euclid's algorithm at each operation in a complex expression, and an implementation geared towards bigints)
template < typename limited , policy rounding = round > class fxs_
template < biggest_builtin limit = INT_MAX , policy rounding = round > class fxs
while rational::fxs would provide a separate interface for rationals based on built-in integral types?
fxs_ for both built-in and UDT, and fxs for built-ins and pre-known UDTs (and all UDTs if we find a way)
Would there be any shared implementation?
not likely between unlimited and limited (fxs), unless it turns out that expression templates can also have some utility for limited types (and no runtime impact when not needed)
Is fxs for power-users too, or just fxs_?
just fxs_
I agree that a better name than "fxs" is needed. Could you give me a hint what it means? ;-)
it is an implementation detail leaked to the interface :O) fxs stands for "FiXed Slash finite precision rational" _oversimplified_ explanation: fxs (and boost::rational when not used with bigints) represent numbers in a way similar to fixed point +----+ +-------------------+ +--------------------+ fixed point |sign| |fixed integer field| |fixed fraction field| +----+ +-------------------+ +--------------------+ +----+ +---------------------+ +-----------------------+ fxs/rational |sign| |fixed numerator field| |fixed denominator field| +----+ +---------------------+ +-----------------------+ another option is to use a "floating slash" representation like floating point numbers +----+ +--------------------+ +--------------------+ floating point |sign| |fixed mantissa field| |fixed exponent field| +----+ +--------------------+ +--------------------+ ^ | | | +----------------------+ +----+ +-------------------+ +-----------------+ floating slash |sign| |fixed num/den field| |fixed slash field| +----+ +-------------------+ +-----------------+ ^ | | | +----------------------+ this would allow representing very big numbers (when the slash position is right to the num/den field the denominator is 1) and very small numbers (when the slash poition is left to the num/den field the numerator is 1) br, andras
I read a paper in college about floating-slash arithmetic, and possible hardware. Thought it a viable alternative to floating-point. (Paper in storage now, or I would give reference, especially since it is from ~1978.) My 2 cents - I would love to see a floating-slash representation. Best wishes, Kon On Mar 26, 2005, at 2:06 AM, Andras Erdei wrote:
Jonathan Turkanis wrote:
template < class unlimited > class unlimited <snip> fxs (and boost::rational when not used with bigints) represent numbers in a way similar to fixed point
+----+ +-------------------+ +--------------------+ fixed point |sign| |fixed integer field| |fixed fraction field| +----+ +-------------------+ +--------------------+
+----+ +---------------------+ +-----------------------+ fxs/rational |sign| |fixed numerator field| |fixed denominator field| +----+ +---------------------+ +-----------------------+
another option is to use a "floating slash" representation like floating point numbers
+----+ +--------------------+ +--------------------+ floating point |sign| |fixed mantissa field| |fixed exponent field| +----+ +--------------------+ +--------------------+ ^ | | | +----------------------+
+----+ +-------------------+ +-----------------+ floating slash |sign| |fixed num/den field| |fixed slash field| +----+ +-------------------+ +-----------------+ ^ | | | +----------------------+
this would allow representing very big numbers (when the slash position is right to the num/den field the denominator is 1) and very small numbers (when the slash poition is left to the num/den field the numerator is 1)
br, andras _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Andras Erdei -
Jonathan Turkanis -
Kon Lovett