Omnimaga

Calculator Community => Other Calc-Related Projects and Ideas => Topic started by: alberthrocks on June 06, 2011, 03:10:37 pm

Title: CAS Theory
Post by: alberthrocks on June 06, 2011, 03:10:37 pm
INCOMPLETE. I'm still writing this, but since aeTIos bugged me to post this ASAP, here it is. :P
Will update tonight or tomorrow depending on if I have time or not.

So, I was lying in bed one day thinking random thoughts, and suddenly I have this idea in my head: CAS for the calc!
Actually, it wasn't that - it was CAS theory, which led to me thinking that this could be implemented as a calc app or program with Axe.

So - the theory. Basically, the core of this is simply arrays and strings. Numbers of course are in it, but only for non-variable calculations and integer calculations.

With that, let's get started!

Variable multiplication
Say, the user inputs this into the CAS:
Code: [Select]
AwesomeCAS v1.0
> (2x+5)(x+4)(5x+6)^5
How can we solve that?
First, we need to make our lives easier and apply existing laws/theorem to solving certain parts of the equation.
One thing comes to mind - Pascal's triangle!
A brief explanation of this theorem - Pascal's triangle is a very simple concept. You start with 1, and then 1, 1. You keep adding 1s to the side to make a triangle while adding the above numbers to place below inbetween them. Sound confusing? Here's an example:
Code: [Select]
       1
      1 1
     1 2 1
    1 3 3 1
  1 4  6 4 1
 1 5 10 10 5 1
So you (kinda) get it. But why does this have anything to do with CASes?
Take a look at this equation:
(x+y)^3
No one really knows what that is, right?
Multiply it out, and you get:
x^3+3(x^2)y+3x(y^2)+y^3
The coeficients are 1, 3, 3, and 1. Hold on! Did we see that before??
Code: [Select]
     1 2 1
    1 3 3 1
We did indeed! Basically, you can the (n-1)th row's numbers for the coefficients!
(And you simply start at the highest degree of the first variable - x^3 - and add Ys to it at the same time decreasing the X power until you get y^3!)

BUT... no one wants to loop through this insanity to get the triangle. What if someone typed in (x+y)^9000?
That's where combinations come in :)
[more details here]
quick and dirty info: Enter "3 nCr 0" into your calc, going from 0 to 3. See the pattern? :D

So for this, we need to find such easy problems. Going back to the problem:
Code: [Select]
> (2x+5)(x+4)(5x+6)^5We treat this as a STRING. I first verify to see if all the parenthesises are closed or not.
Then, I look for ^[number]. If the number is enclosed in (), I evaluate the () and then use that.
Using the above method, I find that the base equation is:
Code: [Select]
1x^5 + 5(x^4)y + 10(x^3)(y^2) + 10(x^2)(y^3) + 5x(y^4) + 1y^5Now substitute x for 5x, and y for 6. You finally get:
Code: [Select]
3125 x^5+18750 x^4+45000 x^3+54000 x^2+32400 x+7776
But wait! How is this calculated in the first place??
Well, the above base equation is split into an array. Python style:
Code: [Select]
equArray = [ [1, ["x", 5]], equPlus, [5, ["x",4], ["y",1]], equPlus, [10,["x",3],["y",2]], equPlus, [10,["x",2],["y",3]], equPlus, [5,["x",1],["y",4]], equPlus, [1,["y",5]]]
equEquateX = ["x",[5, ["x", 1]]]
equEquateY = ["y", [6]]
...where equPlus is a special constant/type defined in program to signify a + sign, equArray is the array that contains our base equation, and equEquateX/Y contain the substitution we want to do.

So now let's plug the variables in!
(The below python code does not necessarily work, and is very crudely designed, but it does explain what I'm thinking. In the future, the code will be much more flexible and have more possibilities than this.)
Code: [Select]
for equPart in equArray: # This loops grabs every item of equArray into equPart
   buffInt = 1 # Initialize a "blank" integer for us to use. This will serve as a standing point to create the final coefficient... for this part, anyway. :P
   for varEquPart in equArray: # This loop grabs every item of the equPart into varEquPart
      if type(varEquPart) == int:
         buffInt = buffInt * varEquPart # Multiple the coefficient into the final one
      else: # This should be an elemental array
         for actVarEquPart in varEquPart: # You see why I don't exactly like turning this idea into code, eh? :P
            if type(actVarEquPart) == str:
               if actVarEquPart == equEquateX[1]:
                  # Substitute X in!
                  for varEquPartInSubstitution in equEquateX
                     if type(varEquPart) == int:
                        buffInt = buffInt * varEquPart # Multiple the coefficient into the final one
                     else: # This should be an elemental array
The above code is incomplete; my brain is hurting from writing this code. :P Any help possible is appreciated! Optimizing, prettifying, organizing, coding - you name it! Depending on my schedule, I may come back tonight or tomorrow to work on this code snipplet. I quickly outlined my ideas below with no concept code.

Floating Point Math - Addition
WIP code posted below - this is in Python. Hopefully it's self explanatory (with assistance from the theory posted below!)
Code: [Select]
#!/usr/bin/env python
# Experimental floating point implementation
# Written by Albert H

# Variables
DEBUG = 1

n1 = raw_input("> Enter 1st floating point number: ")
n2 = raw_input("> Enter 2nd floating point number: ")
op = raw_input("> Enter operation (+, -, *, or /) to perform: ")

# Now for the REAL guts of this program!
# We use absolutely NO floating point operations here at all. NONE.
# If you enable the DEBUG var above, you get to see every part of the
# process. No single number used is a floating point number at all.
if op == '+':
# Easiest one of the bunch. Align the decimal point!
pointpos1 = n1.index(".")
pointpos2 = n2.index(".")
if pointpos1 < pointpos2:
# If pointpos1 has a lower index than pointpos2... that means
# we have n1 being 3.14 and n2 being 12.4.
for n in range(0, pointpos2-pointpos1):
n1 = " " + str(n1)
if DEBUG == 1:
print ">> DEBUG: n1 string is: "+str(n1)
print ">> DEBUG: n2 string is: "+str(n2)

# Number crunching time!
lenOfNum1 = len(n1)
lenOfNum2 = len(n2)

# TODO: Fix bug with entering same number/dec place == crash
# TODO: Fix 0.9+12.9 =12.18 due to lack of carryover correction

result = ""
tempResult = ""
for nIndex in range(0, max(lenOfNum1, lenOfNum2)):
if nIndex <= (lenOfNum1 - 1):
if nIndex <= (lenOfNum2 - 1):
if n1[nIndex] != ' ':
if n2[nIndex] != ' ':
# TODO: add checking for misalign of decimal points
if n1[nIndex] != '.':
if DEBUG == 1:
print ">> DEBUG: Both n1 and n2 digits are present! Adding integers: "+n1[nIndex]+" + "+n2[nIndex]
tempResult = int(n1[nIndex]) + int(n2[nIndex])
result = result + str(tempResult)
else:
if DEBUG == 1:
print ">> DEBUG: Decimal point detected! Appending decimal point to result."

result = result + "."
else:
if DEBUG == 1:
print ">> DEBUG: n2[nIndex] is a space, so adding n1's digit to result. Digit: "+str(n1[nIndex])
result = result + str(n1[nIndex])
else:
if n2[nIndex] != ' ':
if DEBUG == 1:
print ">> DEBUG: n1[nIndex] is a space, so adding n2's digit to result. Digit: "+str(n2[nIndex])
result = result + str(n2[nIndex])
else:
print "ERROR: Something went wrong in preprocessing!"
print "Guru meditation: n1[nIndex] and n2[nIndex] are both spaces! n1='"+n1+"', n2='"+n2+"', nIndex="+str(nIndex)
exit(1)
else:
if DEBUG == 1:
print ">> DEBUG: n2[nIndex] does not exist, so adding n1's digit to result. Digit: "+str(n1[nIndex])
result = result + str(n1[nIndex])
else:
if nIndex <= (lenOfNum2 - 1):
print ">> DEBUG: n1[nIndex] does not exist, so adding n2's digit to result. Digit: "+str(n2[nIndex])
result = result + str(n2[nIndex])
else:
print "ERROR: Something went wrong in preprocessing!"
print "Guru meditation: nIndex is out of range! n1='"+n1+"', n2='"+n2+"', nIndex="+str(nIndex)
print "> Result: "+result

Floating Point Math - Multiplication
This method can also be applied to other operations as well.
Z80 calcs don't have floating point math. It's all software. How can we do it without using TI's stuff?
Probably not the best way to do it, but...
HANDLE IT AS A STRING! :)
Take for instance: 0.51 X 0.003
Quickly outlining the method:
1) Find number of decimal places, figure it which one is longer or if they are both the same
2) Perform hand-done multiplication on computer... aka:
   a) Cut string into numbers
   b) Multiply based on place
   c) Shift around as needed, like what you usually do when you switch places
   d) Add things, AGAIN
   e) Organize numbers into string
   f) Figure out where to put decimal point, and put it there
   g) Simplification as needed ("0.50000 => 0.5")
   h) Done!
Variable Manipulation
Basically, aiming for the famous TI-89 (or TI-Nspire CAS) command: solve(2x+6+x^1029=5, x)
Something like the first idea, but with a lot more complexity. Array element shifting to the extreme!
Again, treat variables like a string. Keep track of where they are in the equation, and perform operations to the equation array to isolate them and solve it.
Title: Re: CAS Theory
Post by: aeTIos on June 06, 2011, 03:13:07 pm
I lol'ed @ the first sentence.
Also wow, you know a lot of maths. For the suite and FloatingP math, I can help.
Title: Re: CAS Theory
Post by: phenomist on June 07, 2011, 12:46:18 am
If you need math stuffs I can help.
Title: Re: CAS Theory
Post by: aeTIos on June 07, 2011, 12:49:43 am
I am working on some fp math routines :D I have most things of the adding routine working.
Title: Re: CAS Theory
Post by: Juju on June 07, 2011, 12:51:38 am
Sounds nice :) Could be cool to have a CAS on my 83+ :P
Title: Re: CAS Theory
Post by: aeTIos on June 07, 2011, 12:52:50 am
'ndeed. Thats what we do it for. (K, there is Zoom Math, but thats expensive [$99.95 for zoom math 500])
Title: Re: CAS Theory
Post by: DJ Omnimaga on June 07, 2011, 03:20:50 am
I agree. It might also convince Zoomath author to decrease his price. Just make sure to not make it an OS mod and that teachers can easily delete it, though, so the 83+ won't get banned from schools, lol.
Title: Re: CAS Theory
Post by: aeTIos on June 07, 2011, 03:42:00 am
Haha, its gonna be just a program. Anyway, I'm now working on floating-point multiplication. I have the displaying routine working, will post soon somewhere around here (maybe this topic)
Title: Re: CAS Theory
Post by: DJ Omnimaga on June 07, 2011, 03:53:20 am
Good to hear. I hope you don't have too much troubles implementing the various CAS features.
Title: Re: CAS Theory
Post by: aeTIos on June 07, 2011, 04:02:14 am
Nah, I think the hardest part will be calculating logarithms and so on. (Wiki is your friend :D)
Found this on the web and wanted to share: http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html Very good explaination on floating-point arithmetics.
Title: Re: CAS Theory
Post by: alberthrocks on June 07, 2011, 03:36:35 pm
If you need math stuffs I can help.
Please assist! :D We are looking for knowledge on equation factoring, solving, and the such.

I am working on some fp math routines :D I have most things of the adding routine working.
Wow... you are fast, eh? :) Did you use my little theorem for implementing? And are you writing this in Axe, ASM, or in a computer programming language?

I've edited in my almost complete adding routine... but you're already done it! :P
I think we should start tasking out CAS parts to implement...
Title: Re: CAS Theory
Post by: aeTIos on June 07, 2011, 03:40:55 pm
I lost some progress with RAM clear, rewriting it. fp multiplication and division are brain-splashing D: Its in Axe.
Title: Re: CAS Theory
Post by: AngelFish on June 07, 2011, 04:31:47 pm
If you're following that source, then you're using IEEE 754 FP numbers, which is far better than TI-OS's floating point format in my opinion.

Anyway, if you need help with algorithms or other math stuff, I'd be happy to help with what I can.
Title: Re: CAS Theory
Post by: aeTIos on June 08, 2011, 02:50:50 am
I re-made my floating point add routine. Is this a good IEEE 754 doc? http://www.cs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF

Edit:
The format of my floats is this:
2.544 E4  would be
402544

Exponent-negative?-mantissa. There are no negative exponents now, when I add support for it, the exponent is increased by 256 (so 001337 would be 1.337 E-256)
Any suggestions?

Edit2: My idea for division: Use old-school methods.
Code: [Select]
102
 10 /
----
10 * 10

remainder: 2
do the remainder *10
returns 20
divide remainder
20
10 /
---
2*10

so first decimal is 2

repeat until there is no remainder left

Answer: 10.2
Title: Re: CAS Theory
Post by: ZippyDee on June 08, 2011, 03:23:00 am
Realize with this that you're also gonna want to do InFix parsing. Most likely InFix to PostFix (Reverse Polish).
Title: Re: CAS Theory
Post by: aeTIos on June 08, 2011, 03:24:02 am
Wait, I dont get it. could you explain a bit more? (about the part after infix)
Title: Re: CAS Theory
Post by: AngelFish 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.
Title: Re: CAS Theory
Post by: aeTIos on June 08, 2011, 03:30:28 am
O.O but that only gives you 30 exponents? Maybe you mean exponent+150?
Title: Re: CAS Theory
Post by: AngelFish 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.
Title: Re: CAS Theory
Post by: aeTIos 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?
Title: Re: CAS Theory
Post by: AngelFish 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.
Title: Re: CAS Theory
Post by: aeTIos on June 08, 2011, 03:37:16 am
Could you explain how the TI-OS works, then? (I mean, with the exponents like 99)
Title: Re: CAS Theory
Post by: AngelFish 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 (http://wikiti.brandonw.net/index.php?title=83Plus:OS:Calculator_Variables). 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.
Title: Re: CAS Theory
Post by: aeTIos 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... :,(
Title: Re: CAS Theory
Post by: alberthrocks 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 (http://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail), 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! :)
Title: Re: CAS Theory
Post by: aeTIos 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.
Title: Re: CAS Theory
Post by: AngelFish 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.
Title: Re: CAS Theory
Post by: aeTIos 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?
Title: Re: CAS Theory
Post by: kyllopardiun 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
Title: Re: CAS Theory
Post by: Deep Toaster 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.
Title: Re: CAS Theory
Post by: aeTIos on June 14, 2011, 03:18:17 am
Seconded. I haven't made any progress this weekend, we went to a camping. I hope to make progress soon.
Title: Re: CAS Theory
Post by: AngelFish on October 25, 2011, 09:48:22 pm
Here's an Axe backup that I'm fairly sure contains an infix to RPN converter (and I don't have a link cable to restore it to .8xp state). I remember commenting it fairly heavily, so the code should be relatively self-explanatory.
Title: Re: CAS Theory
Post by: mrmprog on October 25, 2011, 10:32:27 pm
Great job on this! I am very curios about how you are planning to do this. I am interested in CAS systems, but I don't think my understanding of them is good enough to make one. Where did you learn the concepts you used in this?
Title: Re: CAS Theory
Post by: alberthrocks on October 25, 2011, 11:08:37 pm
Great job on this! I am very curios about how you are planning to do this. I am interested in CAS systems, but I don't think my understanding of them is good enough to make one. Where did you learn the concepts you used in this?
If you're referring to me, I don't have a clue :P I just make up theories that I think will work...

Qwerty, on the other hand... he's amazing, that's all! ;)
Title: Re: CAS Theory
Post by: AngelFish on October 25, 2011, 11:13:32 pm
Great job on this! I am very curios about how you are planning to do this. I am interested in CAS systems, but I don't think my understanding of them is good enough to make one. Where did you learn the concepts you used in this?

If that was directed towards me, libraries and Google ;)

If you're curious about the actual algorithms, some good resources are "Algorithms for Computer Algebra" and Wikipedia.

Thanks, Alberthro