Author Topic: CAS Theory  (Read 10357 times)

0 Members and 1 Guest are viewing this topic.

Offline alberthrocks

  • Moderator
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 876
  • Rating: +103/-10
    • View Profile
CAS Theory
« 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.
« Last Edit: June 07, 2011, 03:35:34 pm by alberthrocks »
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: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #1 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.
I'm not a nerd but I pretend:

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: CAS Theory
« Reply #2 on: June 07, 2011, 12:46:18 am »
If you need math stuffs I can help.
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #3 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.
I'm not a nerd but I pretend:

Offline Juju

  • Incredibly sexy mare
  • Coder Of Tomorrow
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 5730
  • Rating: +500/-19
  • Weird programmer
    • View Profile
    • juju2143's shed
Re: CAS Theory
« Reply #4 on: June 07, 2011, 12:51:38 am »
Sounds nice :) Could be cool to have a CAS on my 83+ :P

Remember the day the walrus started to fly...

I finally cleared my sig after 4 years you're happy now?
THEGAME
This signature is ridiculously large you've been warned.

The cute mare that used to be in my avatar is Yuki Kagayaki, you can follow her on Facebook and Tumblr.

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #5 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])
I'm not a nerd but I pretend:

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55918
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: CAS Theory
« Reply #6 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.

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #7 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)
I'm not a nerd but I pretend:

Offline DJ Omnimaga

  • Former TI programmer
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55918
  • Rating: +3152/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: CAS Theory
« Reply #8 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.

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #9 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.
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 #10 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...
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: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #11 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.
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 #12 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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3913
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: CAS Theory
« Reply #13 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
« Last Edit: June 08, 2011, 03:20:27 am by aeTIos »
I'm not a nerd but I pretend:

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: CAS Theory
« Reply #14 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).
There's something about Tuesday...


Pushpins 'n' stuff...