Books about CAS

[compsystems]

CAS0: Doing Mathematics with Scientific WorkPlace & Scientific Notebook Version 6

https://s3-us-west-2.amazonaws.com/macki...ath-60.pdf



CAS1: Computer Algebra and Symbolic Computation: Mathematical Methods
https://www.ukma.edu.ua/~yubod/teach/com...i.org).pdf



CAS2: COMPUTER ALGEBRA AND SYMBOLIC COMPUTATION: ELEMENTARY ALGORITHMS
https://epdf.pub/computer-algebra-and-sy...ithms.html



College Algebra & Trigonometry with examples on TI calculator
https://www.amazon.com/-/es/Julie-Miller...lie+Miller

What other books do you know about CAS ?, please add links.
Thank you

[Nad]

There is also Computer Algebra with SymbolicC++, which according to the description gives a step-by-step guide to implementing a CAS in C++.

[Jonathan Busby]

(10-26-2019 01:38 PM)compsystems Wrote:  CAS0: Doing Mathematics with Scientific WorkPlace & Scientific Notebook Version 6

https://s3-us-west-2.amazonaws.com/macki...ath-60.pdf



CAS1: Computer Algebra and Symbolic Computation: Mathematical Methods
https://www.ukma.edu.ua/~yubod/teach/com...i.org).pdf



CAS2: COMPUTER ALGEBRA AND SYMBOLIC COMPUTATION: ELEMENTARY ALGORITHMS
https://epdf.pub/computer-algebra-and-sy...ithms.html



What other books do you know about CAS ?, please add links.
Thank you

I also have these two books, which I read a long time ago :



A cursory search of my bookcases didn't reveal "Computer Algebra and Symbolic Computation: Mathematical Methods" which I also own and read a while ago -- it's lost somewhere in my piles of notes and books

Regards,

Jomnathan

[Nad]

Hello,

Did you ever implement the algorithms in software? I am wondering how large a CAS is in MB. Of course it would depend on the number of features.

I have the development board used by the creator of this open source calculator, which has 16MB flash.

I'm looking at adding some "simple" CAS functions. A good place to start is arbitrary precision big integer storage and arithmetic. There's a lot on the web, e.g. this

[Jonathan Busby]

(01-12-2020 06:26 AM)Nad Wrote:  Hello,

Did you ever implement the algorithms in software?

I have *dozens* of half-to-mostly finished projects. Whether I'll ever release them to the public
depends on how my pathological perfectionism judges them for public consumption

Quote: I am wondering how large a CAS is in MB. Of course it would depend on the number
of features.

In my experience, the parser, the abstract-syntax-tree to intermediate representation code generator, and the term re-writing rules and system take up the most space and effort. Everything else is implemented with special purpose functions, which are optional. I'd say around 20KiB to 50KiB at a minimum in Saturn assembly and System-RPL.

Quote:I have the development board used by the creator of this open source calculator, which has 16MB flash.

Looks like a neat project

Quote:I'm looking at adding some "simple" CAS functions. A good place to start is arbitrary precision big integer storage and arithmetic. There's a lot on the web, e.g. this

If it's possible, you might want to use an ARM Cortex M4 embedded CPU for your calculator, as one can then use the embedded versions of the GNU Multi-Precision ( aka "Bignum" ) library, without having to start from scratch See the following link : https://singletonresearch.com/2017/07/11...cortex-m4/

Regards,

Jonathan

[Nad]

Hello Jonathan,

(01-14-2020 08:56 PM)Jonathan Busby Wrote:  If it's possible, you might want to use an ARM Cortex M4 embedded CPU for your calculator, as one can then use the embedded versions of the GNU Multi-Precision ( aka "Bignum" ) library, without having to start from scratch See the following link : https://singletonresearch.com/2017/07/11...cortex-m4/

Thanks, that's an impressive library, and appears to be well documented. It would be cool to use it on the higher performance Cortex M7.

If I can get something simple to work, e.g. addition function (page 33 in pdf manual) "void mpz_add (mpz t rop, const mpz t op1, const mpz t op2)" then I should be able to add the rest over time

[Jonathan Busby]

(01-18-2020 11:03 PM)Nad Wrote:  Hello Jonathan,

(01-14-2020 08:56 PM)Jonathan Busby Wrote:  If it's possible, you might want to use an ARM Cortex M4 embedded CPU for your calculator, as one can then use the embedded versions of the GNU Multi-Precision ( aka "Bignum" ) library, without having to start from scratch See the following link : https://singletonresearch.com/2017/07/11...cortex-m4/

Thanks, that's an impressive library, and appears to be well documented. It would be cool to use it on the higher performance Cortex M7.

If I can get something simple to work, e.g. addition function (page 33 in pdf manual) "void mpz_add (mpz t rop, const mpz t op1, const mpz t op2)" then I should be able to add the rest over time

Yeah It's an easy to use library and it's *very* fast

If you're confused as how to get your code working, then I'll give a short explanation :

1. First declare the mpz_t variables that you'll be using.
2. You now have to initialize the variables using mpz_init(variable_name). Alternately, you can initialize the variables and set them to a long int value with mpz_init_set_ui(variable_name, initial_value), where initial_value can be a constant or a long int variable.
3. You probably want user supplied values in your variables, so you can use gmp_scanf("%Zd", variable_name) to do that. The format specifier string and the function work like the C standard library's scanf().
4. You can now perform an addition using mpz_add(dest_variable, source_variable_1, source_variable_2), and, note, that dest_variable *can* be the same variable as any of the source variables
5. To get the variables' contents displayed to the user, you can use either use gmp_printf("%Zd", variable_name) or, alternately, you can get the text representation into a buffer via eg. char *buffer = mpz_get_str(NULL, 10, variable_name) . Note that you'll have to manually free() the buffer.
6. After you're done using the variables, you need to clear them either via mpz_clear(variable_name) or mpz_clears(variable_name_1, variable_name_2, variable_name_3, NULL) ( mpz_clears() takes a list of an arbitrary numbers of mpz_t variables and the list is terminated by NULL).
   

Hope this helps

Regards,

Jonathan

[Eddie W. Shore]

I love this forum so much - grateful to everyone here.

[Eddie W. Shore]

Computing Handbook, 3rd Edition
Edited by Teofilo Gonzalez and Jorge Diaz Herrera
Editor In Chief Allen Tucker
CRC Press
https://www.pdfdrive.com/computing-handb...66057.html

[Jonathan Busby]

(01-22-2020 03:05 AM)Eddie W. Shore Wrote:  Computing Handbook, 3rd Edition
Edited by Teofilo Gonzalez and Jorge Diaz Herrera
Editor In Chief Allen Tucker
CRC Press
https://www.pdfdrive.com/computing-handb...66057.html

That looks to be a very interesting book -- thanks for the info

Regards,

Jonathan

[rprosperi]

(01-23-2020 04:29 PM)Jonathan Busby Wrote:  

(01-22-2020 03:05 AM)Eddie W. Shore Wrote:  Computing Handbook, 3rd Edition
Edited by Teofilo Gonzalez and Jorge Diaz Herrera
Editor In Chief Allen Tucker
CRC Press
https://www.pdfdrive.com/computing-handb...66057.html

That looks to be a very interesting book -- thanks for the info

Regards,

Jonathan

1 +

Thanks for sharing this Eddie. It's a huge book, and relatively recent (2014), both unexpected for a free resource.

[Nad]

Hello!

Yes thanks Eddie, and thank you Jonathan for the tips on implementing Bignum. I will need help to get started, but should be O.K. once I've implemented a few functions I'll report on how I'm going.

The prototype is up and running (from Dan's webpage, my set-up is the same):



11 GPIO pins are used by the display but only 16 GPIO pins could be found on the development board (even though the i.MX RT1010 mcu has 44 GPIO pins, according to the datasheet), leaving only 5 pins for the keypad (it needs 14). So an Arduino was used to scan the keypad and send the number of the key pressed to the mcu, which works nicely.

The 500 MHz Cortex-M7 core in the i.MX RT1010 is fast - the Mandelbrot set with 250 iterations per pixel is drawn in under 3 seconds - and the 480x320 display shows some nice detail:



A big challenge is to go from the prototype to a hand held version. There are a number of small form factor boards that could perhaps be used, such as the Teensy 4.0, which features an even more powerful member of the i.MX RT family running at 600 MHz.

[Jonathan Busby]

(01-24-2020 12:13 AM)Nad Wrote:  Hello!

Yes thanks Eddie, and thank you Jonathan for the tips on implementing Bignum. I will need help to get started, but should be O.K. once I've implemented a few functions I'll report on how I'm going.

The prototype is up and running (from Dan's webpage, my set-up is the same):



11 GPIO pins are used by the display but only 16 GPIO pins could be found on the development board (even though the i.MX RT1010 mcu has 44 GPIO pins, according to the datasheet), leaving only 5 pins for the keypad (it needs 14). So an Arduino was used to scan the keypad and send the number of the key pressed to the mcu, which works nicely.

The 500 MHz Cortex-M7 core in the i.MX RT1010 is fast - the Mandelbrot set with 250 iterations per pixel is drawn in under 3 seconds - and the 480x320 display shows some nice detail:



A big challenge is to go from the prototype to a hand held version. There are a number of small form factor boards that could perhaps be used, such as the Teensy 4.0, which features an even more powerful member of the i.MX RT family running at 600 MHz.

You're welcome and awesome work!

Regards,

Jonathan

[Nad]

Hello!

Thanks, it's a pretty exciting project

Looking through the Bignum source code I'm not sure if assembly code for the inner loops has been written for the Cortex-M family. There are generic C functions that aren't as fast - this is perhaps what the Cortex-M4 implementation mentioned above is using.

For this reason I may go with my original plan of writing my own mixed C/assembly routines for multiple-precision integers and rationals. Hopefully it won't be too difficult. I will first do addition, followed by multiplication, then GCD. Subtraction and division then follow pretty easily. I'll need to brush up on GNU syntax assembly, as the MCUXpresso IDE uses the GNU ARM toolchain.

But before that I need to determine the data types to use. A rational can be represented by a struct consisting of 2 multiple precision integers, which is what I think Bignum does.

Structs and creating new data types is new territory for me. Here is an overview of the steps I'll take to add two multiple-precision integers:

1) Choose precision. Bignum calls the words "limbs' and I'll use the same terminology. Start with say 4 limbs to make debugging easier (i.e. four 32-bit words) and create new data type "mpz" (as in Bignum). Convert string entered by user to value and use malloc() to push onto stack. Same for second argument.

2) Pressing "+" calls assembly routine to add with carry corresponding words, then use free() to remove second argument from stack and write sum to memory occupied by first argument.

3) Convert result to string for display. The only way I know to do that is to subtract multiples of powers of 10, keeping count as you go, until you reach zero.

I'll try this in a simulator and report back. Dan said he is aiming to upload the open-source firmware to GitHub by March so hopefully I'll have something to try on the real thing soon

Nad

P.S. Talking about data types and memory representation, how are things like "x", pi, sqrt(2), "x^3 +y" etc. stored in memory in a CAS?

[Jonathan Busby]

(01-31-2020 06:44 AM)Nad Wrote:  P.S. Talking about data types and memory representation, how are things like "x", pi, sqrt(2), "x^3 +y" etc. stored in memory in a CAS?

Usually, the CAS has some internal representation for algebraic expressions that's easy to convert to a string. The internal representation could be the AST ( Abstract Syntax Tree ) or something derived from it. In this format it's easy to manipulate the expressions for the purposes of eg. term re-writing and it's also possible to quickly evaluate the expression, assuming all free variables in the expression have been instantiated.

In the case of the 48, the CAS has a stack based, RPN, "meta-object" intermediate representation for symbolic expressions when the CAS needs to transform or manipulate the expression. Such expressions are stored as symbolic objects in another "intermediate representation" which are essentially the same as any other composite object such as lists or secondaries, and, with xEVAL, they're also executable. The symbolic object can contain a mix of variables, functions, and constants etc. basically any RPL word that makes sense in a symbolic. If the CAS needs the value of the symbolic, then EVALing it is quite quick since it can be directly executed like a secondary, assuming that all free variables are bound. In terms of term re-writing and other functions, IIRC, I think that the stack based, RPN, meta-object representation is used.
Regards,

Jonathan

NOTE #1 : The technical definition of a Sys-RPL meta-object is essentially an RPL composite object that has been serialized onto the stack via =INNERCOMP, where the first element on the stack is a system binary integer which indicates the number of objects that have been pushed to the stack.

[Jonathan Busby]

(01-31-2020 06:44 AM)Nad Wrote:  Hello!

Thanks, it's a pretty exciting project

Looking through the Bignum source code I'm not sure if assembly code for the inner loops has been written for the Cortex-M family. There are generic C functions that aren't as fast - this is perhaps what the Cortex-M4 implementation mentioned above is using.

It's actually using the full blown GMP library AFAIK

Quote:For this reason I may go with my original plan of writing my own mixed C/assembly routines for multiple-precision integers and rationals. Hopefully it won't be too difficult.

It won't be easy You'll need to use advanced methods suich as Karatsuba multiplication and / or FFT based multiplication if you want to operate on **extremely huge** numbers

Quote: I will first do addition, followed by multiplication, then GCD. Subtraction and division then follow pretty easily. I'll need to brush up on GNU syntax assembly, as the MCUXpresso IDE uses the GNU ARM toolchain.

Well, the GNU GMP library uses pairs of mpz_t integers to represent rationals, but, the numbers must be "canonicalized" so that the numerator and denominator don't share any factors and the denominator is positive
You'll need to implement a GCD function first so you can prevent the integers representing the rational from becoming very large too quickly

From the GMP manual :

Code:

Rational numbers are stored in objects of type mpq_t.

All rational arithmetic functions assume operands have a canonical form, and canonicalize their result. The canonical form means that the denominator and the numerator have no common factors, and that the denominator is positive. Zero has the unique representation 0/1.

Pure assignment functions do not canonicalize the assigned variable. It is the responsibility of the user to canonicalize the assigned variable before any arithmetic operations are performed on that variable.

Function: void mpq_canonicalize (mpq_t op)

    Remove any factors that are common to the numerator and denominator of op, and make the denominator positive.

Quote:But before that I need to determine the data types to use. A rational can be represented by a struct consisting of 2 multiple precision integers, which is what I think Bignum does.

Yep

Quote:3) Convert result to string for display. The only way I know to do that is to subtract multiples of powers of 10, keeping count as you go, until you reach zero.

Well, one usually just uses a "modulo and divide loop" eg . :

Code:

loop:
        r = i % 10
        i = i / 10        // Integer division :)
        print r
        if (i == 0) break
        jump loop

The above algorithm is naïve though, and much faster algorithms can be used. See eg. here .

Regards,

Jonathan

[Nad]

Hello Jonathan,

Thanks for the replies. I'll definitely need to pick your brain when I start thinking about code for implementing some CAS functionality

Aren't / and % for the C integer types? I don't think those functions can be used for converting multiple-precision integers (in binary) to strings.

EDIT: I think I get it now, you must have meant division and remainder functions for mpz's. I'll have another look at the documentation for Bignum to see if there is info on the conversion algorithms used.

Nad

[Jonathan Busby]

(02-01-2020 05:20 AM)Nad Wrote:  EDIT: I think I get it now, you must have meant division and remainder functions for mpz's. I'll have another look at the documentation for Bignum to see if there is info on the conversion algorithms used.

Yep It was just pseudocode For the mpz_t data type in the GMP library you'd need to use the, eg. mpz_cdiv_q() , and the mpz_mod() functions

Regards,

Jonathan

[Nad]

Hello,

I've written assembly routines for string to mpz conversion as well as addition/subtraction of 100 digit mpz's (I set LIMB to 11 so mpz_max = 2^(11 x 32) > 10^100).

I had some difficulties with malloc() so for the 100-level stack I'm using a 100x11 array, and everything is working nicely.

The next step is multiplication, division and GCD of mpz's. Then I'll expand to rationals and finish my Bignum implementation with a function to display mpq's (later I can add exponentiation).

I picked this book up in a second-hand book store the other day. It's a nice introduction to the algorithms and concepts used in a CAS. There is also a video on it:





The author suggests implementing polynomials after Bignum. I think I'll try univariate polynomial addition/subtraction soon

[F-73P]

(02-09-2020 05:24 AM)Nad Wrote:  ...for the 100-level stack I'm using a 100x11 array...

I would avoid using a fixed-length array representation for the following reasons:
1) The size of numbers is limited by the number of limbs
2) A considerable amount of memory is wasted storing high-order 0's
3) Processor time is wasted performing arithmetic operations on high-order 0's

Even storing the polynomial x^2 + 5x + 6 will waste large amounts of memory since the coefficients and exponents are stored as rationals. E.g. using 11 limbs would require 6 x 22 = 132 limbs = 528 bytes for a 32-bit processor.

A better approach is to use dynamic array representation, as described by the creators of Maple in the book "Algorithms for Computer Algebra". This method is also used in Mathematica.

Since the integers in this example are small, only two words are required for each - one to store the length of the integer in limbs and the other the value of the limb. So the polynomial now requires only 6 x 4 = 24 words = 96 bytes.