Books about CAS

[johanw]

(01-12-2020 06:26 AM)Nad Wrote:  I am wondering how large a CAS is in MB. Of course it would depend on the number of features.

I still have a copy of Derive for MS-DOS that I used during my graduation project, that is 900kb (0.9MB) total. AFAIK Derive was later bought by TI and used as the basis for their CAS calculators.

Then there is the open source NCalc that implements a CAS system (and much more): https://github.com/tranleduy2000/ncalc . The zipfile of thayt Github repo is 30MB but it contains of course much more than just the CAS.

[BruceH]

(05-02-2020 09:45 PM)johanw Wrote:  I still have a copy of Derive for MS-DOS that I used during my gradiation project, that is 900kb (0.9MB) total. AFAIK Derive was later bought by TI and used as the basis for their CAS calculators.

Ah yes, so do I, thanks for reminding me...

[Nad]

Hello!

Thank you for the posts above. I was wondering if 16MB is enough for a CAS but now see that it is. A manual for Derive can be found here.

The dynamic array representation certainly has its benefits but is more difficult to implement. Even rewriting my string to mpz conversion routine is presenting somewhat of a challenge

[compsystems]

Texas should release Derive source. although it is in LISP I think that the CAS of the TINSPIRE was rewritten in another language.

Maxima is still being developed at LISP
http://maxima.sourceforge.net/docs/manua...ma_35.html

[Jonathan Busby]

(05-06-2020 05:39 PM)compsystems Wrote:  Texas should release Derive source. although it is in LISP I think that the CAS of the TINSPIRE was rewritten in another language.

Maxima is still being developed at LISP
http://maxima.sourceforge.net/docs/manua...ma_35.html

That's interesting, because if it's written in Lisp, then one could "easily" write a just-in-time Lisp to RPL compiler for it that would run on the HP48/49/50 The main challenge, though, would be re-implementing all the Lisp functions that require access to the hardware which are platform specific or dependent.

( Some work along these lines has already been done a long while ago, although it's not a JIT compiler and the syntax is different : https://www.hpcalc.org/details/403 )

Regards,

Jonathan

[jonmoore]

I'm not particularly a fan of either Derive or XCas (I'm a hardcore Mathematica user of many years) but having worked with XCas on the 50g and Prime (and 48GX before that), I believe XCas is a better pocket calculator CAS solution.

In recent years I've dabbled in Derive as it's built into a great HP-41cx emulator on iOS - i41cx. It's a klutzy integration so that might have coloured my view, but I think Bernard Parisse deserves a lot of praise with regards to just how far he's pushed CAS on pocket calculators.

I believe that the Casio Classpad now uses XCas too. But much like GeoGebra, they've changed many of the operator naming conventions, however the underlying UX has a very XCas feel to it.

My favourite XCas mobile implementation is PocketCAS on iOS, it does a better job of being a 'pocket' Mathematica, than iOS Mathematica itself.

[Nad]

(05-06-2020 05:39 PM)compsystems Wrote:  I think that the CAS of the TINSPIRE was rewritten in another language.

From Edmund Lamagna's Computer Algebra : concepts and techniques:

"In 1999, the Soft Warehouse sold its interest in Derive to Texas Instruments, whose intent was to develop a line of calculators based on CAS technology. The software powering the TI products is not simply a rewrite of Derive code, but an entirely new system implemented from scratch in the C programming language"

[F-73P]

(05-06-2020 05:08 AM)Nad Wrote:  Even rewriting my string to mpz conversion routine is presenting somewhat of a challenge

The following C/assembly code converts the string commandLineString to an mpz and stores the result in mpz1, and gives the length of mpz1 in limbs:

Code:


#define MAXLIMBS  1000       //adjust depending on amount of RAM available
typedef uint32_t mpz[MAXLIMBS];
uint32_t mpz_10[] = {10};
mpz mpz1;
mpz mpz2;
mpz w;
uint32_t i;
uint32_t j;
uint32_t limbs;

  i = 0;
  limbs = 1; 

  while (commandLineString[i]) {
    limbs = multiply_mpz(limbs, mpz1, 1, mpz_10);
    for (j=0;j<limbs;j++) mpz1[j]=w[j];
    init_w();             //set w = 0
        limbs = mpzx10PlusDigit(limbs,commandLineString[i]-48);
        i++;
  }

The function multiply_mpz uses the "classic" multiplication algorithm:

Code:


uint32_t multiply_mpz(uint32_t m, uint32_t * u, uint32_t n,uint32_t * v) {
    uint32_t i;
    uint32_t j;
    
    uint32_t carry;    
    
    uint64_t t;
    
    for (j=0;j<n;j++) {
        if (v[j]==0) continue;
        carry = 0;
        for (i=0;i<m;i++) {
            t = limbProduct(u[i],v[j],carry,w[i+j]); 
            w[i+j] = t;
            carry = t >> 32;
        }
        w[m+j]=carry;        
    }
    
    if (w[m+n-1]==0) limbs = m+n-1;
    else limbs = m+n;          
    
    return limbs;
    
}

The assembly routine limbProduct returns a 64-bit result:

Code:


AREA limbProduct_area,CODE,READONLY             
            EXPORT limbProduct

            ENTRY
            
limbProduct UMULL R0,R1,R0,R1
            ADDS R0,R0,R2
            ADC R1,R1,#0
            
            ADDS R0,R0,R3
            ADC R1,R1,#0

            BX lr

            END

For Cortex M4/M7 processors the multiply and accumulate instruction UMAAL can be used in limbProduct, making the algorithm faster.

After mpz1 has been multiplied by 10 the assembly routine mpzx10PlusDigit adds to it the next digit in commandLineString:

Code:


;add mpz1 to commandLineString[i]-0x30 and store in mpz1 

;input: R0 = number of limbs, R1 = commandLineString[i]-0x30
;output: R0 = number of limbs            
            
            AREA mpzx10PlusDigit_area,CODE,READONLY             
            EXPORT mpzx10PlusDigit
            IMPORT mpz1

            ENTRY            
mpzx10PlusDigit              
            PUSH {R4,R5}     
            MOV R4,R0
            
            LDR R5,=0xFFFFFFFF
            LDR R2,=mpz1
            
            SUBS R0,R0,#1
            BEQ section_2
            
            LDR R3,[R2]
            
            ADDS R3,R3,R1
            
            STR R3,[R2],#4
            
            SUB R0,R0,#1
            TST R0,R5
            BEQ section_1
            
loop        LDR R3,[R2]

            ADCS R3,R3,#0 
                    
            STR R3,[R2],#4
                        
            SUB R0,R0,#1
            TST R0,R5
            BNE loop                
                
            ;;;;;;;;;;;;;;;;;add MS limb of mpz_1 and commandLineString[i]-0x30 and add new limb if necessary 
section_1   LDR R3,[R2]
            
            ADCS R3,R3,#0           
            
            STR R3,[R2],#4
            
            BCC exit

            LDR R3,[R2]
            MOV R3,#1
            STR R3,[R2]
            
            ADD R4,R4,#1
            
            B exit
                
            ;;;;;;;;;;;;;;;;;add limb of mpz_1 and commandLineString[i]-0x30 and add new limb if necessary            
section_2   LDR R3,[R2]
            
            ADDS R3,R3,R1
            
            STR R3,[R2],#4
            
            BCC exit

            LDR R3,[R2]
            MOV R3,#1
            STR R3,[R2]
            
            ADD R4,R4,#1
            
exit        MOV R0,R4    

            POP {R4,R5}
            
            BX lr
            END

[Nad]

Hello,

Thank you F-73P, that is very helpful! I can now move on to multi-precision integer division

Is there a calculator that can do multi-precision integer to hexadecimal conversion?

I have found some online converters but it would be very useful to check the results of algorithms on a hand held. My 50g and nSpire seem to give correct results only for integers up to a certain value.

Nad

[John Keith]

(05-15-2020 09:06 AM)Nad Wrote:  Is there a calculator that can do multi-precision integer to hexadecimal conversion?

I have found some online converters but it would be very useful to check the results of algorithms on a hand held. My 50g and nSpire seem to give correct results only for integers up to a certain value.

Nad

If you have the ListExt Library on your 50g, the commands I\->BL AND BL\->I can be used to convert between decimal and hex (or any other base) limited only by available memory. See the documentation for details.

[Nad]

Hello!

Thank you John, that is a very good library and is well documented. The command I\->BL performs the conversion quickly but the digits are in decimal rather than hexadecimal, e.g. 314 159 265 358 979 323 846 264 is converted to {4 2 8 6 9 11 9 15 5 12 13 13 15 11 14 10 13 14 7 8}.

So I wrote user RPN programs to change 10, 11,... to A, B,... and vice versa when going the other way.

My programs slow down the conversion, but overall it works nicely, with 314 159 265 358 979 323 846 264 converted to {4 2 8 6 9 B 9 F 5 C D D F B E A D E 7 8} in a little under 3 seconds.

Nad

[John Keith]

(05-17-2020 07:12 AM)Nad Wrote:  The command I\->BL performs the conversion quickly but the digits are in decimal rather than hexadecimal, e.g. 314 159 265 358 979 323 846 264 is converted to {4 2 8 6 9 11 9 15 5 12 13 13 15 11 14 10 13 14 7 8}.

So I wrote user RPN programs to change 10, 11,... to A, B,... and vice versa when going the other way.

My programs slow down the conversion, but overall it works nicely, with 314 159 265 358 979 323 846 264 converted to {4 2 8 6 9 B 9 F 5 C D D F B E A D E 7 8} in a little under 3 seconds.

The next to last example under I\->BL should be exactly what you want, and is much faster than the UserRPL equivalent. If you want a list of characters rather than a string, follow with S\->SL. The program to convert in the other direction is simple, all the commands have inverses.

[Nad]

Hello!

Thanks again, that works beautifully! The conversion in both directions is done almost instantly

Nad

[F-73P]

(05-15-2020 09:06 AM)Nad Wrote:  I can now move on to multi-precision integer division

The book "Modern Computer Arithmetic" by Richard P. Brent and Paul Zimmermann provides a comprehensive coverage of algorithms for arbitrary-precision integer and floating-point arithmetic. Several division algorithms are presented, including exact (useful when dividing numerators and denominators by their GCD), single word divisor (for when denormalising the remainder), and for processors that do not have a machine instruction for the division of two words by one word (such as the Cortex M4/M7).

It isn't light reading but is an invaluable resource for anyone writing and (in particular) optimising arbitrary-precision arithmetic routines.

[Jonathan Busby]

(05-27-2020 04:07 AM)F-73P Wrote:  

(05-15-2020 09:06 AM)Nad Wrote:  I can now move on to multi-precision integer division

The book "Modern Computer Arithmetic" by Richard P. Brent and Paul Zimmermann provides a comprehensive coverage of algorithms for arbitrary-precision integer and floating-point arithmetic. Several division algorithms are presented, including exact (useful when dividing numerators and denominators by their GCD), single word divisor (for when denormalising the remainder), and for processors that do not have a machine instruction for the division of two words by one word (such as the Cortex M4/M7).

It isn't light reading but is an invaluable resource for anyone writing and (in particular) optimising arbitrary-precision arithmetic routines.

My main references are "Digital Arithmetic" by Miloš D. Ercegovac and Tomás Lang when it comes to Verilog hardware design, and "The Art of Computer Programming, Volume 2: Seminumerical Algorithms" by Donald E. Knuth when it comes to arbitrary precision arithmetic in software. The book you mentioned, though, seems to be a very detailed and comprehensive reference to software-based arbitrary precision arithmetic that goes way beyond what Knuth covers. Thanks for the tip!

Regards,

Jonathan

[F-73P]

You’re welcome. I have started a new thread on arbitrary-precision arithmetic.