Books about CAS

[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