Jump to content



Photo
- - - - -

Large Integer multiplication with C.Basic vs CasioBasic


  • Please log in to reply
4 replies to this topic

#1 tsiozos

tsiozos

    Casio Fan

  • Members
  • PipPip
  • 40 posts

  • Calculators:
    fx-9860gII

Posted 20 August 2019 - 06:21 AM

Here's a large number multiplication test I did to compare the speed of CasioBasic vs C.Basic.

 

A little theory:

When you multiply two integers if the result is larger than 10 digits the calculator will convert it to floating point and display it in scientific notation. As a result you lose the least significant digits. This algorithm uses the method we learn in elementary school (called "long" multiplication) to get the result. This algorithm has a running time of O(n2) where n is the number of digits.

 

If you want more info on how the algorithm is implemented in computers read this: https://en.wikipedia...ation_algorithm

 

To enter the 2 numbers you want multiplied change the first two lines where they are assigned to matrices A and B. Start entering from the least to the most significant digit.

Say you want to multiply 23456 by 45678. You should enter this:

 

[[6,5,4,3,2]] -> Mat A

[[8,7,6,5,4]] -> Mat B

 

If one number has fewer digits than the other pad it with 0's until they have the same length. Example:

1234567 x 456

should be entered as

[[7,6,5,4,3,2,1]] -> Mat A

[[6,5,4,0,0,0,0]] -> Mat B

 

Then run the algorithm and the result will be displayed. I didn't bother with a fancier data entry since this is just a test.

 

MEMORY LIMITS ON A CASIO fx-9860 GII

In Casio Basic it seems the max numbers that can be multiplied is around 47 digits each. In C.Basic the limits are much higher. Your limits might vary depending on your calculator.

 

SPEED TESTS

I'm testing the algorithm with two 47-digit numbers.

CasioBasic: ~39sec

C.Basic: ~0.5sec

 

Huge difference. Such differences can be observed between interpreted and compiled languages for example between Python vs C++.

 

So here's the program to try for yourselves.

'ProgramMode:RUN
'=== Large number
'=== multiplication
'=== least_->_most sgnf
[[4,5,6,7,8,9,3,3,3,7,8,9,6,6,6,4,4,4,4,2,2,1,1,0,0,6,6,6,0,0,1,6,7,8,9,4,3,1,2,8,8,8,8,2,4,6,8]]->Mat A
[[3,2,1,2,2,8,8,8,8,1,6,6,6,1,0,4,4,4,4,0,0,0,3,3,3,6,6,6,0,0,0,1,7,8,9,2,7,8,9,4,3,2,1,2,4,6,8]]->Mat B

Trn Mat A*Mat B->Mat C
Mat C
ClrList 1
Dim Mat C
List Ans[1]->D
1->L
0->C
For 1->I To D
C->S:0->C
For 1->J To I
S+Mat C[J,I-J+1]->S
'"J,I-J+1"
'J_Disps_
'I-J+1_Disps_

Next
S Rmdr 10->List 1[L]
S Int/ 10->C
1+L->L
Next

For 2->I To D
C->S:0->C
For D->J To I Step -1
S+Mat C[I+D-J,J]->S
'"I+D-J"
'I+D-J_Disps_
'"J"
'J_Disps_

Next
S Rmdr 10->List 1[L]
S Int/ 10->C
1+L->L
Next
'"C="
'C_Disps_
'===ADD LAST CARRIER
C>0=>C->List 1[L]

'=== List 1 to str
""->Str 1
"0123456789"->Str 2
For 1->I To Dim List 1
StrMid(Str 2,List 1[I]+1,1)+Str 1->Str 1
Next

Locate 1,2,StrMid(Str 1,1,20)
Locate 1,3,StrMid(Str 1,21,20)
Locate 1,4,StrMid(Str 1,41,20)
Locate 1,5,StrMid(Str 1,61,20)
Locate 1,6,StrMid(Str 1,81,20)
Locate 1,7,StrMid(Str 1,101,20)

In case you're bored to copy/paste download the .g1m file from here:

https://1drv.ms/u/s!...56KD8w?e=wJCmfb

 

Congrats to sentario21 for the amazing C.Basic language.



#2 piu58

piu58

    Casio Freak

  • Members
  • PipPipPipPip
  • 102 posts
  • Gender:Male

  • Calculators:
    Casio fx-9860G, Casio fx-CG20

Posted 20 August 2019 - 05:06 PM

I find this interesting.

 

In my younger days I wrote an arithmetic program with variable accuracy, up to 256 bit mantissa (around 77 digits). This program was for Z80 microprocessor and took around 4 kBytes. It included an RPN calculator, with +-*/, all trigonometric functions, e^x and log and loops.

To make a calculation I had to write a small program first, an ascii files with the upn commands. The resut was another ascii file.

 

You method of storing values in matrices reminds me at my old experiments.


Edited by piu58, 21 August 2019 - 04:13 AM.

  • tsiozos likes this

#3 sentaro21

sentaro21

    Casio Freak

  • Members
  • PipPipPipPip
  • 233 posts
  • Gender:Male
  • Location:JAPAN

  • Calculators:
    FX-603P fx-4800P fx-5800P
    CFX-9850GC PLUS
    fx-9860G
    fx-9860GII
    fx-9860GII-2
    fx-9860GII-2 SD
    fx-CG10
    fx-CG20
    fx-CG50
    HP-Prime
    HP 50G
    TI-Nspire CX CAS
    TI-84+CE

Posted 21 August 2019 - 01:38 AM

@tsiozos
Thanks!! 
This is a very interesting program. :D
It's important to work with the same code both Casio Basic and C.Basic.
I tried some benchmarks.(All are default clock speed.)
The SH3 model is also quite fast for Casio Basic.
The SH4A model will be slower.
Approximately 80x speed was achieved with the integer mode in CG50. ^_^
 
                         Casio Basic    C.Basic 2.23(DBL#)  (INT%)
9860GII(SH3   29MHz OS 2.04)  21.5s    1.20s (x17.9)     0.70s (x30.7)
9860GII(SH4A  29MHz OS 2.09)  33.0s    0.94s (x35.1)      0.57s (x57.9)
35+E II(SH4A  58MHz OS 3.10)  24.0s       0.82s (x29.3)      0.45s (x53.3)
fx-CG50(SH4A 117MHz OS 3.20)  16.3s    0.34s (x47.9)      0.21s (x77.6)
 
 
 
@piu58
I have also tried multiple length arithmetic in the calculation of pi.
It was very interesting. :D
I think that is a good subject to try with the programable calculator. ^_^


#4 tsiozos

tsiozos

    Casio Fan

  • Members
  • PipPip
  • 40 posts

  • Calculators:
    fx-9860gII

Posted 21 August 2019 - 05:10 AM

@piu58 that's interesting. What platform was that?

#5 tsiozos

tsiozos

    Casio Fan

  • Members
  • PipPip
  • 40 posts

  • Calculators:
    fx-9860gII

Posted 21 August 2019 - 05:21 AM

@sentaro21 wow that's some speed improvement with C.Basic.

I'll try long integer division next.




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users