Prev: String tokenizer place in Chomsky hierarchy?
Next: Help me sort though some complex math
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 |
> -----------------------------

 |  Next  |  Last
Pages: 1 2
Prev: String tokenizer place in Chomsky hierarchy?
Next: Help me sort though some complex math