Author Topic: CAS Theory  (Read 14986 times)

0 Members and 1 Guest are viewing this topic.

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #15 on: June 08, 2011, 03:24:02 am »
Wait, I dont get it. could you explain a bit more? (about the part after infix)
« Last Edit: June 08, 2011, 03:24:31 am by aeTIos »
I'm not a nerd but I pretend:

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: CAS Theory
« Reply #16 on: June 08, 2011, 03:29:04 am »
For the Floating point design, I recommend sticking with *exactly* the IEEE specification of [sign][exponent+15][significand] (which is the format for the 16 bit FP). That format really simplifies operations. For example, Abs(<FP var>) = 2*<FP var>/2 in Axe. It also allows you to generate the exponent and the significand simultaneously when converting to regular integers.

EDIT: I actually PM'ed Alberthro a rather lengthy explanation of how to parse expressions and how to convert to RPN (with a few errors in there, I'll admit  :P). You should ask him to send it to you.
« Last Edit: June 08, 2011, 03:31:07 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #17 on: June 08, 2011, 03:30:28 am »
O.O but that only gives you 30 exponents? Maybe you mean exponent+150?
I'm not a nerd but I pretend:

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: CAS Theory
« Reply #18 on: June 08, 2011, 03:32:33 am »
Nope. That's the standard 16 bit floating point format. You can use larger formats, like the 32 bit single or the 64 bit double, but they're probably going to a bit painful to do in Axe.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #19 on: June 08, 2011, 03:33:46 am »
Ouch, but we're making this for a CAS... can't I use just exponent+100 or so?
I'm not a nerd but I pretend:

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: CAS Theory
« Reply #20 on: June 08, 2011, 03:36:41 am »
Well, the 80 bit extended version is what's generally used in computer CAS's :P

100+ bits are used in high precision scientific computing and by the time you get to that point, the algorithms actually start becoming unstable and inaccurate (meaning other concerns are more important than the number format). I'd stick with 64 bit at most, to align with the machine's word size nicely.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #21 on: June 08, 2011, 03:37:16 am »
Could you explain how the TI-OS works, then? (I mean, with the exponents like 99)
« Last Edit: June 08, 2011, 03:37:43 am by aeTIos »
I'm not a nerd but I pretend:

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: CAS Theory
« Reply #22 on: June 08, 2011, 03:45:11 am »
TI's FP number format is kind of...

Well you can read about it for yourself here. I'm not very good at explaining it.


If you want to match the number range, you'll need to use the IEEE 754 Double FP format. That can handle numbers up to around 10^308, compared to the 10^128 handled by TI's routines. It's only 8 bytes large, so you sacrifice some precision for that, but you'll still get excellent accuracy within normal ranges.
« Last Edit: June 08, 2011, 04:42:10 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #23 on: June 08, 2011, 04:36:03 am »
O.o Awesome. How many digits can it handle?

Edit: :O Its binary. I have no clue how to handle that in Axe... :,(
« Last Edit: June 08, 2011, 05:43:00 am by aeTIos »
I'm not a nerd but I pretend:

Offline alberthrocks

  • Moderator
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 876
  • Rating: +103/-10
    • View Profile
Re: CAS Theory
« Reply #24 on: June 08, 2011, 10:26:34 pm »
Oops, sorry, didn't get to get those PMs out! The valley curve of my busyness is over, and work amount is sharply increasing as I head towards the end of the year! This is really going to end up becoming a summer project, in which my summer doesn't start until June 22nd. :P Blame my school system for their weird dates... :P

Here are those PMs!
(Shown with permission, of course!)

Spoiler For CAS Theory PMs:
Qwerty started by informing me about another technique:
Just wanted to point out a few things I think you missed in your CAS topic, on the off chance you don't know about them. The standard (and easiest) way to parse mathematical expressions is actually to work in Reverse polish notation. A lot of CASes convert to RPN before evaluation, so here's a simple algorithm for it (basically the Shunting-yard algorithm).

Given: (2x+5)(x+4)(5x+6)^5

->(2*x+5)*(x+4)((5*x+6)^5)

Using the shunting yard algorithm, we can convert this to RPN:


(2*x+5)-> 2 X * 5 +

(x+4)-> X 4 +

((5*x+6)^5)-> 5 X * 6 + 5 ^


Combining these into one expression, we get*:

 2 X * 5 + X 4 + 5 X * 6 + 5 ^ * *

Recognize that it's essential for a CAS to have an X^n operation. Rather than expanding the expression using pascal's triangle (which would be incredibly tedious/slow for a 9001th degree equation), you can use x^n for numerical evaluation since the expression is constant for each value of the variables. Plug the values in and watch it go. For symbolic operations, you can just apply the normal power laws.

From this messy RPN equation, we can actually get something incredibly useful for a CAS, namely a beautiful syntax tree:
Code: [Select]
              Ans
       |
       *
    /   \
   +       *
  / \     /  \
*   5   +    ^
/ \     / \   / \
2  X   X   4 5   +
        / \
      6   *
         / \
        X  5

Now we have a simple way to evaluate the expression in terms of a few elementary operations. You just need to traverse the tree and evaluate the values at each node. The answer then comes right out. It also allows you to do certain optimizations to the expression, such as evaluating constant values such as 2*3 in the equation (2*3)+X, which would show up as a node with constant arguments. A little pruning of the syntax tree and you get a nice simplified expression.

Anyway, just thought I'd mention it  :)


*Might be wrong. I don't use RPN very often :P

My reply:
Wow.... I honestly did not know that!
Now I know why programming classes LOVE to talk about trees... :P
The basis of my CAS theory is basically asking a computer to do the same thing we do when solving a problem. (I would be actually pleasantly surprised for the FPM!) Of course, humans may not be as

Somehow, someway, the RPN notation makes things a lot faster (and of course, much more efficient then nCr, in which I found out that the calc slows and stops at 36 (ERR:OVR), and my laptop, although "modern", takes quite a while to compute that. (451.583050966 seconds => 7.53 minutes!)

I think I get your idea/theorem... and then again, maybe not! :D
The tree somewhat deviates from the RPN converted equations you posted, and I'm not too sure how I would handle such input.

Either way, the theorem you mentioned is interesting indeed, and I could use all the help I can get!

Thanks!
Albert

P.S - do you mind if I post your PM in the topic? It might be somewhat useful for people to know.
Another reply:
I have absolutely no problem with you posting it.

About the tree deviating slightly, well that's because I'm not very good at RPN :P

Basically, what RPN does is convert the expression into a series of individual operations on the operands in the order they're supposed to occur. What the tree does is group them in such a way that every operations is linked to its operands. The operations are the nodes and the operands are the leaves. You start from the bottom (or top down, they both work) with all of the given constants and variables listed. Then, you connect all of the operands with their operations. Those operations produce new operands which are then operated on by some of the leftover initial operands and so on until you end up with one final operand that is your answer. That's also essentially how you generate trees in code. If you want to start from the top, you just assume an answer, then find the operations that produce that answer, the operands for those operations, and then the operations that produce those operands, etc...


On a side note, Dynamic trees are useful, but they're a serious PITA to organize in memory. I've had nightmares about the internal representations :P
...and that's all! :)
Withgusto Networks Founder and Administrator
Main Server Status: http://withg.org/status/
Backup Server Status: Not available
Backup 2/MC Server Status: http://mc.withg.org/status/


Proud member of ClrHome!

Miss my old signature? Here it is!
Spoiler For Signature:
Alternate "New" IRC post notification bot (Newy) down? Go here to reset it! http://withg.org/albert/cpuhero/

Withgusto Networks Founder and Administrator
Main Server Status: http://withg.org/status/
Backup Server Status: Not available
Backup 2/MC Server Status: http://mc.withg.org/status/

Activity remains limited due to busyness from school et al. Sorry! :( Feel free to PM, email, or if you know me well enough, FB me if you have a question/concern. :)

Don't expect me to be online 24/7 until summer. Contact me via FB if you feel it's urgent.


Proud member of ClrHome!

Spoiler For "My Projects! :D":
Projects:

Computer/Web/IRC Projects:
C______c: 0% done (Doing planning and trying to not forget it :P)
A_____m: 40% done (Need to develop a sophisticated process queue, and a pretty web GUI)
AtomBot v3.0: 0% done (Planning stage, may do a litmus test of developer wants in the future)
IdeaFrenzy: 0% done (Planning and trying to not forget it :P)
wxWabbitemu: 40% done (NEED MOAR FEATURES :P)

Calculator Projects:
M__ C_____ (an A____ _____ clone): 0% done (Need to figure out physics and Axe)
C2I: 0% done (planning, checking the demand for it, and dreaming :P)

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #25 on: June 09, 2011, 02:19:10 am »
Argh, code tags in spoilers D:
I need help on the IEEE754 floating point math in Axe (I dont know how to handle the binary)
Also, alberthrocks, could you send the PMs to me? thx.
I'm not a nerd but I pretend:

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: CAS Theory
« Reply #26 on: June 09, 2011, 03:05:34 am »
Here's a floating point addition/subtraction algorithm to help you:

Quote
1. Exponent subtraction (ES): Subtract the exponents and denote the difference jEa
Ebj = d.
2. Alignment (Align): Right shift the signi ficand of the smaller operand by d bits. Denote
the larger exponent Ef .
3. Signi ficand addition (SA): Perform addition or subtraction according to the e ffective
operation, Eo, which is the arithmetic operation actually carried out by the adder in
the FP unit.
4. Conversion (Conv): Convert the result to sign-magnitude representation if the result
is negative. The conversion is done with an addition step. Denote the result Sf .
5. Leading one detection (LOD): Compute the amount of left or right shift needed and
denote it En. En is positive for a right shift and negative otherwise.
6. Normalization (Norm): Normalize the signi ficand by shifting En bits and add En to
Ef .
7. Rounding (Round): Perform IEEE rounding by adding "1" when necessary to the
LSB of Sf . This step may cause an overflow, requiring a right shift. The exponent,
Ef , in this case has to be incremented by 1.
« Last Edit: June 09, 2011, 03:06:09 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #27 on: June 09, 2011, 04:26:25 am »
I figured out, that if the exponents differ (significand length)+2, you don't have to operate?
I'm not a nerd but I pretend:

Offline kyllopardiun

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 178
  • Rating: +14/-4
  • Kyllopardiun over 2000 results in google.
    • View Profile
    • Kyllo's blog (a blog about poetry, videos and computing)
Re: CAS Theory
« Reply #28 on: June 12, 2011, 06:52:40 pm »
I don't know, if it's possible in axe,
however, I think the easier way to do that is in LISP...

//Although  it isn't that user friendly

Offline Deep Toaster

  • So much to do, so much time, so little motivation
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 8217
  • Rating: +758/-15
    • View Profile
    • ClrHome
Re: CAS Theory
« Reply #29 on: June 12, 2011, 08:22:42 pm »
Coincidence: I was thinking about the same thing last week. Didn't get close to where you are though.

We really need a CAS for Z80 calculators.