How to determine whether an expression equals to zero
in [General Programming]
|
From: nikov on 11 Apr 2008 14:48 Hi all. I have the following data type: data Expr = Literal Integer | Add Expr Expr -- x + y | Multipy Expr Expr -- x*y | Power Expr Expr -- x^y It represents an expression, which can consist of signed integer literals (arbitrary size), and operators: addition, multiplication, exponentiation. Semantically, this expression may denote a complex number. If an exponentiation is ambiguous, let it represent a complex number with a minimal non-negative argument. For instance, Power (Literal (-1)) (Power (Literal 2) (Literal (-1))) represents I (the imaginary unit), not (-I). One can see, that it is possible to encode all rational numbers and some algebraic numbers in this way. I need to write an algorithm, which accepts an expression (a value of type Expr) and produces one of the following results: 1) the expression is invalid, in other words, it contains a subexpression of the form p^q, where p=0 and Re(q)<=0 (for instance, the expression Power (Literal 0) (Literal 0) is invalid) 2) the expression equals to zero (for instance, the expression Add (Literal 1) (Literal (-1)) equals to zero) 3) the expression is not equal to zero (for instance, the expression Literal 2 is not equal to zero) Is this task decidable? Thanks, nikov
From: Barb Knox on 11 Apr 2008 17:55 In article <910f39c9-119d-43db-ae77-ba7c2bcc0576(a)w5g2000prd.googlegroups.com>, nikov <v.reshetnikov(a)gmail.com> wrote: > Hi all. > > I have the following data type: > > data Expr = > Literal Integer > | Add Expr Expr -- x + y > | Multipy Expr Expr -- x*y > | Power Expr Expr -- x^y > > It represents an expression, which can consist of signed integer > literals (arbitrary size), and operators: > addition, multiplication, exponentiation. Semantically, this > expression may denote a complex number. If > an exponentiation is ambiguous, let it represent a complex number with > a minimal non-negative argument. > For instance, Power (Literal (-1)) (Power (Literal 2) (Literal (-1))) > represents I (the imaginary unit), not (-I). > > One can see, that it is possible to encode all rational numbers and > some algebraic numbers in this way. > > I need to write an algorithm, which accepts an expression (a value of > type Expr) and produces one of the following results: > 1) the expression is invalid, in other words, it contains a > subexpression of the form p^q, where p=0 and Re(q)<=0 > (for instance, the expression Power (Literal 0) (Literal 0) is > invalid) So you don't accept that 0^0 = 1 ? > 2) the expression equals to zero (for instance, the expression Add > (Literal 1) (Literal (-1)) equals to zero) > 3) the expression is not equal to zero (for instance, the expression > Literal 2 is not equal to zero) > > Is this task decidable? Clearly yes. Just evaluate the expression normally (from the inside out), keeping track of the complex results. > Thanks, -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | -----------------------------
From: Jon Harrop on 11 Apr 2008 20:01 Barb Knox wrote: > Clearly yes. Just evaluate the expression normally (from the inside > out), keeping track of the complex results. What would be the result of evaluating this subexpression: 2^(1/2) -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com/products/?u
From: Barb Knox on 11 Apr 2008 21:08 In article <dr6dneyhd9gkYGLanZ2dnUVZ8sSrnZ2d(a)plusnet>, Jon Harrop <jon(a)ffconsultancy.com> wrote: > Barb Knox wrote: > > Clearly yes. Just evaluate the expression normally (from the inside > > out), keeping track of the complex results. > > What would be the result of evaluating this subexpression: > > 2^(1/2) Just that. Or am I incorrect in assuming that there is a normal form for nested complex rational exponentials? -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | -----------------------------
From: cr88192 on 12 Apr 2008 01:23
"Barb Knox" <see(a)sig.below> wrote in message news:see-B33A47.13083212042008(a)lust.ihug.co.nz... > In article <dr6dneyhd9gkYGLanZ2dnUVZ8sSrnZ2d(a)plusnet>, > Jon Harrop <jon(a)ffconsultancy.com> wrote: > >> Barb Knox wrote: >> > Clearly yes. Just evaluate the expression normally (from the inside >> > out), keeping track of the complex results. >> >> What would be the result of evaluating this subexpression: >> >> 2^(1/2) > > Just that. Or am I incorrect in assuming that there is a normal form > for nested complex rational exponentials? > luckily, complexes are weird, but not "that" weird... the biggest issue I would think would be determining whether or not imaginaries count as non-zero. (3i==0)? (2^(1/2)) is, luckily, the same as sqrt(2). this is like 1.414213562373... (-2)^(1/2) is likewise, just imaginary... now, if someone wants a little fun, they can add quaternions to their numeric tower... I actually did this as an extension in my C compiler... the only "real" issue IMO is that there is at present no 'double __quat' (unlike '_Complex', there is only a single-precision variant). this is itself due to SSE (it gives 2-elem double vectors or 4-elem single vectors), so mixing a quat and a double complex, produces a single-precision result, rather than a double-precision result (this is against the usual type-promotion rules). also, presently, there is no notion of a quaternion exponent (this would be such a horrid and scary beast that I did not bother...). in a few other places, definitions were arbitrary... in time these issues may be fixed. > -- > --------------------------- > | BBB b \ Barbara at LivingHistory stop co stop uk > | B B aa rrr b | > | BBB a a r bbb | Quidquid latine dictum sit, > | B B a a r b b | altum viditur. > | BBB aa a r bbb | > ----------------------------- |