Books about CAS

[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.