Hello all, I'm currently extending GiNaC to be used for symbolic range propagation. While the specifics of the extensions are likely not interesting to most users, I do find that I need to handle both Infinite and Undefined values in a sensible manner. I'll describe the approach I've taken thus far and would appreciate feedback. Including Infinity and Undefined within GiNaC seems to weed its way into many areas of the code. For instance, when we have two expair's x and y, we assume that if x->rest == y->rest we can combine the coefficients. Clearly this doesn't hold when we consider Infinity or Undefined, so we end up with a large number of special-case branches when we see Infinity or Undefined in an expression. This happens in quite a few places. My current approach is to defined GiNaC::constant values for Infinity and Undefined, and include functions to quickly check if an expression is the Infinity or Undefined constant. From there we just need to find all of the required special cases... Again, and feedback would be appreciated. I've only been using GiNaC for a short while, and perhaps there are tricks that could make this addition go more smoothly. Doug Gregor gregod@cs.rpi.edu
On Fri, 2 Nov 2001, Douglas Gregor wrote:
I'm currently extending GiNaC to be used for symbolic range propagation. While the specifics of the extensions are likely not interesting to most users, I do find that I need to handle both Infinite and Undefined values in a sensible manner. I'll describe the approach I've taken thus far and would appreciate feedback.
Including Infinity and Undefined within GiNaC seems to weed its way into many areas of the code. For instance, when we have two expair's x and y, we assume that if x->rest == y->rest we can combine the coefficients. Clearly this doesn't hold when we consider Infinity or Undefined, so we end up with a large number of special-case branches when we see Infinity or Undefined in an expression. This happens in quite a few places.
My current approach is to defined GiNaC::constant values for Infinity and Undefined, and include functions to quickly check if an expression is the Infinity or Undefined constant. From there we just need to find all of the required special cases...
Again, and feedback would be appreciated. I've only been using GiNaC for a short while, and perhaps there are tricks that could make this addition go more smoothly.
Cool, you understand and appreciate the problem. So, what advice could we give you? ;-) It is clear that those two constants can easily be introduced but there is some amount of work to be done to make them behave consistently, like Infinity+Infinity -> Infinity, but Infinity-Infinity -> Undefined (or fail?). May I suggest to also include CInfinity (like Mma's ComplexInfinity)? That would be very useful for poles in the complex domain. Also, I don't know if class constant is appropiate for this. They expect to be evalf()'ed at some point, don't they? Perhaps adding a special class for each of them would be more appropiate? I really don't know right now... My main concern is that one has to take some care when wiring that into expairseq, add, mul, power, etc. When the logic is inserted at the wrong place this could lead to a performance downgrade that is too large to be acceptable. Many calculations don't need these constants and we do not want to penalize them. I am sure it can be done in a performant way. Happy hacking -richy. -- Richard B. Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
Cool, you understand and appreciate the problem. So, what advice could we give you? ;-)
It is clear that those two constants can easily be introduced but there is some amount of work to be done to make them behave consistently, like Infinity+Infinity -> Infinity, but Infinity-Infinity -> Undefined (or fail?).
Precisely the case that has caused me the most problems :). There are annoying little subcases as well, like Infinity + Pi*Infinity -> Infinity. Here we're stuck calling evalf() on the constant Pi to determine that it is positive.
May I suggest to also include CInfinity (like Mma's ComplexInfinity)? That would be very useful for poles in the complex domain.
Perhaps I'll just pave the way with Infinity and Undefined. I've never actually dealt with complex infinity, so I'm sure someone more familiar with the concept would do this better.
Also, I don't know if class constant is appropiate for this. They expect to be evalf()'ed at some point, don't they? Perhaps adding a special class for each of them would be more appropiate? I really don't know right now...
Yes, I believe adding a special class for each would be the best option. If nothing else, it will eliminate a dynamic_cast and an integer comparison when testing for Infinity or Undefined.
My main concern is that one has to take some care when wiring that into expairseq, add, mul, power, etc. When the logic is inserted at the wrong place this could lead to a performance downgrade that is too large to be acceptable. Many calculations don't need these constants and we do not want to penalize them. I am sure it can be done in a performant way.
I expected this comment :) I'll do whatever I can to ensure that this addition does not cause a sizeable performance degradation. Doug
Hi, On Sat, 3 Nov 2001, Douglas Gregor wrote:
May I suggest to also include CInfinity (like Mma's ComplexInfinity)? That would be very useful for poles in the complex domain.
Perhaps I'll just pave the way with Infinity and Undefined. I've never actually dealt with complex infinity, so I'm sure someone more familiar with the concept would do this better.
In past I tried to introduce the Infinity and Undefined concepts to GMP in its Python layer (gmpy). I also tried to avoid complex infinity stuff but it is not quite possible. For example, how would you deal with <complex number> * Infinity? Another confusing stuff is arithmetics with Infinities. For example, consider 2 * Infinity + sqrt(-1) * Infinity How would you simplify such expression? There are many seemingly reasonable approaches that, unfortuantely, lead to different results. E.g. 2 * Infinity + sqrt(-1) * Infinity -> (2 + sqrt(-1)) * Infinity or Infinity + sqrt(-1) * Infinity -> (1 + sqrt(-1)) * Infinity. And both results may be incorrect as Infinities may have different weights. There are many approaches possible for introducing Infinity and Undefined "number" types. Each have their advantages and disadvantages depending on the application. My friendly suggestion for you would be to first study these different approaches and propose a complete specification of the extended number model before trying to actually implement its support for GiNaC. This specification should include at least the following tables: <operation> | <finite number> | Infinity | Undefined -------------------------------------------------------- <finite number> | <result?> | <result?> | <result?> Infinity | ... Undefined | ... where <operation>s are +,-,*,/,**,elementary functions. These table may have more rows (e.g. PlusInfinity, MinusInfinity, ComplexInfinity, SignInfinity, ImaginaryUnit, ComplexNumber, ImaginaryNumber, FieldNumber, etc) depending on the approach. If you are able to produce such tables and you get some consensus for different applications, then the next questions are implementation issues but I consider them rather trivial when compared with the problem of proposing a solid number model with Infinities and Undefined (or Notdetermined) concepts. You may copy these models from Mathematica or Maple or whatever, but even they have different solutions and not always suitable for all applications. I hope that I was not too negative about the problem. I think it would be very useful if GiNaC could deal with Infinities and Undefined results. I am certainly interested in such a feature that I am willing to help in anyway I can in this project. Best regards, Pearu
On Sun, 4 Nov 2001, Pearu Peterson wrote: [...]
Perhaps I'll just pave the way with Infinity and Undefined. I've never actually dealt with complex infinity, so I'm sure someone more familiar with the concept would do this better.
In past I tried to introduce the Infinity and Undefined concepts to GMP in its Python layer (gmpy). I also tried to avoid complex infinity stuff but it is not quite possible. For example, how would you deal with <complex number> * Infinity?
Another confusing stuff is arithmetics with Infinities. For example, consider 2 * Infinity + sqrt(-1) * Infinity How would you simplify such expression? There are many seemingly reasonable approaches that, unfortuantely, lead to different results. E.g. 2 * Infinity + sqrt(-1) * Infinity -> (2 + sqrt(-1)) * Infinity or Infinity + sqrt(-1) * Infinity -> (1 + sqrt(-1)) * Infinity. And both results may be incorrect as Infinities may have different weights.
This is a very valid example and in my opinion the only way out of this is to return Undefined if the coefficients are not either on the real axis alone or the imaginary axis alone. They also need to have the same sign, of course. Doesn't the example fall into the same category as (Infinity - Infinity), which should be Undefined, too? [...]
My friendly suggestion for you would be to first study these different approaches and propose a complete specification of the extended number model before trying to actually implement its support for GiNaC. This specification should include at least the following tables: <operation> | <finite number> | Infinity | Undefined -------------------------------------------------------- <finite number> | <result?> | <result?> | <result?> Infinity | ... Undefined | ... where <operation>s are +,-,*,/,**,elementary functions. These table may have more rows (e.g. PlusInfinity, MinusInfinity, ComplexInfinity, SignInfinity, ImaginaryUnit, ComplexNumber, ImaginaryNumber, FieldNumber, etc) depending on the approach.
Uh, oh, while such a table would be helpful in understanding the issues involved, I think we shouldn't bother with all of the rows you are suggesting. BTW, what's a FieldNumber? Regards -richy. -- Richard B. Kreckel <Richard.Kreckel@GiNaC.DE>
On Sat, 10 Nov 2001, Richard B. Kreckel wrote:
On Sun, 4 Nov 2001, Pearu Peterson wrote:
Another confusing stuff is arithmetics with Infinities. For example, consider 2 * Infinity + sqrt(-1) * Infinity How would you simplify such expression? There are many seemingly reasonable approaches that, unfortuantely, lead to different results. E.g. 2 * Infinity + sqrt(-1) * Infinity -> (2 + sqrt(-1)) * Infinity or Infinity + sqrt(-1) * Infinity -> (1 + sqrt(-1)) * Infinity. And both results may be incorrect as Infinities may have different weights.
This is a very valid example and in my opinion the only way out of this is to return Undefined if the coefficients are not either on the real axis alone or the imaginary axis alone. They also need to have the same sign, of course. Doesn't the example fall into the same category as (Infinity - Infinity), which should be Undefined, too?
Sure. However one could extend your rule to: a*Inf + b*Inf -> (a+b)*Inf iff a,b are complex numbers with Arg(a)==Arg(b) -> Undefined in all other cases.
[...]
My friendly suggestion for you would be to first study these different approaches and propose a complete specification of the extended number model before trying to actually implement its support for GiNaC. This specification should include at least the following tables: <operation> | <finite number> | Infinity | Undefined -------------------------------------------------------- <finite number> | <result?> | <result?> | <result?> Infinity | ... Undefined | ... where <operation>s are +,-,*,/,**,elementary functions. These table may have more rows (e.g. PlusInfinity, MinusInfinity, ComplexInfinity, SignInfinity, ImaginaryUnit, ComplexNumber, ImaginaryNumber, FieldNumber, etc) depending on the approach.
Uh, oh, while such a table would be helpful in understanding the issues involved, I think we shouldn't bother with all of the rows you are suggesting.
Absolutely right. The contents of rows depends on the approach one chooses.
BTW, what's a FieldNumber?
I was thinking of quaternions (though they form skew field). However introducing such objects to GiNaC may not be simple. And I am not sure if you are interested in such an extension. Regards, Pearu
On Thu, 15 Nov 2001, Pearu Peterson wrote:
BTW, what's a FieldNumber?
I was thinking of quaternions (though they form skew field). However introducing such objects to GiNaC may not be simple. And I am not sure if you are interested in such an extension.
Hmm, quaternions would just be another indexed object, I think. You certainly don't want to use an explicit 2x2 matrix representation, would you? On the other hand, it would probably be more reasonable implementing Pauli matrices in a fashion completely analogous to class color. Then, the quaternions i, j and k are just related with these by sigma_x = I*i, sigma_y = I*j, sigma_z = I*k, together with the unity sigma_ONE. Cheers -richy. -- Richard B. Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
participants (3)
-
Douglas Gregor
-
Pearu Peterson
-
Richard B. Kreckel