Algebraic calculator algorithm

[legacy]

I have improved my code, and I have chosen the RPN way, definitively

Code: [Select]

# eval 1+2+3

yards analysis: PASSED
stack analysis: PASSED

function_pool_show_all ... 0 functions

rpn_v[]={ 0 2 1 4 3 }

[1]  1 K3 cookie     token_DecValue, type12
[2]  1 K3 cookie     token_DecValue, type12
[+] -1 K5 operator   token_Plus, type53
[3]  1 K3 cookie     token_DecValue, type12
[+] -1 K5 operator   token_Plus, type53

#########################
#    good expression    #
#########################


Code: [Select]

# eval 1+Fa(2)+Fb(3+4)

yards analysis: PASSED
stack analysis: PASSED
function_pool_show_all ... 2 functions
 + function1 [Fa] { type12 } 1 args ticket_rpn=2
 + function2 [Fb] { type12 } 1 args ticket_rpn=7

rpn_v[]={ 0 4 2 1 9 11 10 7 6 }

[1]  1 K3 cookie     token_DecValue, type12
[2]  1 K4 f_cookie   token_DecValue, type12
[Fa]  0 K2 function   token_StrictAlphaNum, type19
[+] -1 K5 operator   token_Plus, type53
[3]  1 K4 f_cookie   token_DecValue, type12
[4]  1 K4 f_cookie   token_DecValue, type12
[+] -1 K6 f_operator token_Plus, type53
[Fb]  0 K2 function   token_StrictAlphaNum, type19
[+] -1 K5 operator   token_Plus, type53

#########################
#    good expression    #
#########################


Code: [Select]

# eval 1+(2.2*3.0E9+ ( 0xdeadbeaf logicalAnd 0xffffffff ) )

yards analysis: PASSED
stack analysis: PASSED

rpn_v[]={ 0 3 5 4 8 10 9 6 1 }

[1] 1 token_DecValue, type12
[2.2] 1 token_FloatinPointENGValue, type15
[3.0E9] 1 token_FloatinPointSCIValue, type16
[*] -1 token_Asterisk, type55
[0xdeadbeaf] 1 token_HexValue, type13
[0xffffffff] 1 token_HexValue, type13
[logicalAnd] -1 token_LogicalAnd, type41
[+] -1 token_Plus, type53
[+] -1 token_Plus, type53

#########################
#    good expression    #
#########################
(ops, type check is needed)

[legacy]

it works over a lexer

the input string (from a shell) is divided into tokens, tokens enter into a yards algorithm, the result is a vector, plus a boolean

the vector tells the order of the token on the stack (RPN notation)
the boolean tells if the expression is valid or not

functions are allowed, but ... to support them the complexity has grown of a factor of 3

[djacobow]

Miguelvp's program brings a tear to this oldster's eye. When computers were computers.

[TheWinterSnow]

Edit: I forgot another thing you have to do without (*): floating point !, specially double.
* AVR had only support for float, it is emulated anyways. The Cortex-M4 has built-in float support. There are emulation libraries, you may want to look at gcc, the sources, it had double support, code to emulate I mean.

See this is the problem, since I am using more advanced libraries to do trig and other functions, there is no way I am writing my own math functions, not going to happen.  The execution times of FP is completely ok by me as even some of the worst math functions can still be executed in less than 1ms.  M

My problem right now if trying to find out how to convert FP numbers with their errors (or not in most cases) back to integer fractions.  Converting 1.333333333333333 back into 4/3 is something I am currently blanking on.

[ale500]

The math lib used is just a part of the calculator. Rolling your own is hard because you have to develop one algorithm for every function, rounding and so on. One way to avoid some errors is to use decimal arithmetic instead of binary. Another is to use symbolic math all the time:

Say the user want to do (1 + 2) / 4 and wants 3/4 as an answer...

If you say keep the history of input you get 3 / 4 directly. The problem comes with 0.75 as the result of sin(48.59°). In this case you can only approximate. The TI-92 for instance uses decimal throughout and 64 bit float for transcendental functions, and not only decimal but rational numbers, numbers stored as fractions (to avoid unnecessary divisions).

[DJohn]

My problem right now if trying to find out how to convert FP numbers with their errors (or not in most cases) back to integer fractions.  Converting 1.333333333333333 back into 4/3 is something I am currently blanking on.

Continued fractions are probably your friend here.  You'll never be able to convert exactly (because 4/3 is not representable in floating point), so the best you can do is generate a sequence of rational approximations and pick one that still involves reasonable numbers.

Here's an example: say we want to represent 5.123456789 as a fraction.  Remove the integer part, giving us our first approximation of 5, with remainder 0.123456789.  Take the reciprocal of the remainder, 8.10000007371.  The integer part gives out next approximation, 5 + 1/8, and the remainder is 0.10000007371.  Take the reciprocal again, which is 9.99999262901.  The integer part gives the next approximation, 5 + 1/(8+1/9) = 5 + 9/73.  The remainder is now 0.99999262901.  Taking the reciprocal of this gives 1.00000737104, so out next approximation is 5 + 1/(8+1/(9+1/1)) = 5 + 10/81.  The remainder is 0.00000737104, which is pretty small number.  We're not going to gain much accuracy by continuing, so I'll choose to stop there.

5 + 10/81 = 5.12345679012, which is not bad.

The process is basically saying "The number is 5.  Well, not really 5, but 5 + 1/8.  Well, not really 8, but 8 + 1/9..." and so on.

[TheWinterSnow]

My problem right now if trying to find out how to convert FP numbers with their errors (or not in most cases) back to integer fractions.  Converting 1.333333333333333 back into 4/3 is something I am currently blanking on.

Continued fractions are probably your friend here.  You'll never be able to convert exactly (because 4/3 is not representable in floating point), so the best you can do is generate a sequence of rational approximations and pick one that still involves reasonable numbers.

Here's an example: say we want to represent 5.123456789 as a fraction.  Remove the integer part, giving us our first approximation of 5, with remainder 0.123456789.  Take the reciprocal of the remainder, 8.10000007371.  The integer part gives out next approximation, 5 + 1/8, and the remainder is 0.10000007371.  Take the reciprocal again, which is 9.99999262901.  The integer part gives the next approximation, 5 + 1/(8+1/9) = 5 + 9/73.  The remainder is now 0.99999262901.  Taking the reciprocal of this gives 1.00000737104, so out next approximation is 5 + 1/(8+1/(9+1/1)) = 5 + 10/81.  The remainder is 0.00000737104, which is pretty small number.  We're not going to gain much accuracy by continuing, so I'll choose to stop there.

5 + 10/81 = 5.12345679012, which is not bad.

The process is basically saying "The number is 5.  Well, not really 5, but 5 + 1/8.  Well, not really 8, but 8 + 1/9..." and so on.

Thanks that is amazing, after a bit of messing around on some of my TI calculators I get what is going on here.  My TI-36X can convert decimal to fractions to some degree, on the one I am designing I will have a flag that denotes whether the answer is exact or an approximate so it will always convert to a fraction if asked to do so. 

I didn't work on the fraction stuff today as I wasn't mentally ready to try and figure out how to implement Least Common Multiples to add and subtract fractions, as well as the recursive in nature algorithm posted above.  I will get around to it though.  Instead I worked on getting the conversion of decimals to exact value irrational numbers.  So far it is working, just need to integrate the exact values into the main calculator.

That leaves me wondering though, since I have no experience in even using graphing calculators, are there calculators that do compute exact values for some irrational numbers?

[ale500]

An irrational number cannot be obtained by the division of two whole numbers. You can approximate, but that is not exact, at least for the definition of exact that I know of.

[helius]

Irrational numbers can, of course, be represented symbolically, which is "exact".
There are several different types, the most familiar being algebraic (a rational raised to a rational power). I think most calculators support that to some degree.
Transcendentals are the non-algebraic type, but some can be calculated in other ways, like Maclaurin series.
There are also some reals that are not computable. So they must be transcendental irrationals, but there is just no way to find them.

[TheWinterSnow]

The way I got the decimal approximations back into their exact form was to compare a preset table of approximates to the input, if they are equal to the tolerance that some of the various math functions have (ex, cos() has one less digit than sqrt()) then the input is stored back into a symbolic form.  It works for squares whose values are above sqrt(2), but not less, however, I already have an exact table for trig functions, so it comes down to just integrating the two tables together.  I still have to do tables for nth-root values depending on how many tables I want to have before the calculator gives up and just keeps the approximate number.

[legacy]

how big (byte size) are these tables ?

[helius]

I'm sure that for most use cases, this comparison process nullifies the speed advantage of using floating point in the first place.

[TheWinterSnow]

how big (byte size) are these tables ?

Right now, 208 Bytes if an int == 16-bits.  I am thinking at the moment to scrap the lookup tables, modify my stack and keep everything in exact form symbolically until I am ready for an approximate answer.  But I am still thinking I need a lookup table of some sort to get exact answers of common trig functions.  Ex: cos(PI/4), there needs to be a table to spit out sqrt(2)/2 symbolically and put that into the stack.  I don't need a table for sqrt() or nth-rt() functions because they can just be symbolically stored in the stack until it is time to evaluate for the final answer.

...I think.

I'm sure that for most use cases, this comparison process nullifies the speed advantage of using floating point in the first place.

I am not worried too much about speed, so long as the final product isn't any slower than my TI-36X, which takes about 5 seconds to process !n(65).  Again being able to spit out math functions within 200-300uS worst case is not a concern.

[legacy]

see this page, funny code inside

[TheWinterSnow]

So this project started to get a little complicated.  The more and more I thought about features the more is slowly starting turning into a CAS like system.  At first I thought that would be easy until I really thought about it, then decided it was too complicated and just going back to the original standard scientific calculator would be best for my sanity.

Since writing CAS capable code is out of the question, I think it would benefit me to get my hands on an existing CAS library and use that to extend my project as needed.  Problem is, I can't seem to find such a library for embedded systems.  I am having the odd feeling such library wouldn't fit onto an AVR 8-bit solution, but I have been debating moving over to a Rasperry Pi setup.  Under both circumstances, what CAS C++ libraries out there would work with AVR or RP/Raspbian? 

GiNaC is more of a Unix setup, with distributions for Debian, but I am not too familiar with Unix-Like OS and have no clue if it could work with an OS like Raspbian.

[legacy]

some time ago we opened this (sw) and this (hw) threads (italian language), in order to realize something similar: RPI linux with a calc engine.

Currently the project is stalled 

I have to check my friend answers, my be he has already found a good open source software for CAS under linux


 

[timofonic]

I'm a totally n00b, but maybe this could inspire you...

http://sourceforge.net/projects/wp34s/