8 replies to this topic

[Tritonio]

Yet another program to do prime factorization for any number. Not the fastest, not the slowest, if there's anything interesting about it is that there is zero explicit primality checks. It's just that the way it extracts factors happens to extract primes only.

"NUMBER"?I
I➔A
A≤1 Or Int(A)≠A⇒Stop
2➔P
0➔C
Lbl 1
 A÷P➔N
 If Int(N)=N:Then
  C+1➔C
  N➔A
 Else
  If C>0:Then
   Cls
   Locate 1,2,P
   Int(log(P))+2➔O
   Locate O,2,"xx"
   Locate 0+2,2,C◢
   A=1⇒Stop
  IfEnd
  P+2>√(A)⇒A-2➔P
  P=2⇒1➔P
  P+2➔P
  0➔C
  Cls
  Locate 1,1,Int(100×P÷√(A))
 IfEnd
Goto 1

Edited by Tritonio, 15 July 2021 - 06:38 PM.

[Krtyski]

Hi Tritonio

 

One of my personal project was how to make faster prime factoring in Casio calculators including fx-5800P.

I was so impressed by a post in UFC by secutor, it is so fast.

 

At this moment I still could not find any faster algorithm yet. So I tried make this faster for not only fx-5800P but also other graphing calculators using not only Casio basic but also C.Basic and Casio Python. I also tried to accept 15 digits input on C.Basic and Casio Python.

 

Anyway, just for your interest, let me introduce fastest prime factoring program (FACTOR-F2) running on fx-5800P. (I'm not sure you are interested in this...)

 

Download Link of FACTOR-F2

 

Prime Factoring of 7,849,516,203 (= 3 x 9811 x 88897) takes rather long time. It's about 101 sec with FACTOR-F2.

secutor's original programs gives 111 sec. FACTOR-F2 is about 9% faster than original.

This file size is rather big:

- FACTOR-F2: 21,456 bytes

- WFSUB (same as original): 147 bytes

Totality 21,603 bytes is required in 28,432 bytes memory space of fx-5800P. 

 

Detailed description how to make this is here in Japanese but using Google translate may help, I hope.

Edited by Krtyski, 31 July 2021 - 09:04 AM.

[Hlib2]

Here is a simple algorithm for CASIO graphic calculators (the version for C. BASIC is shown):

`#CBDBL
Lbl 0:"N="?➝A:Goto 2:
Lbl 1:2◢
A÷2➝A:A=1⇒Goto 7:
Lbl 2:MOD(A,2)=0⇒Goto 1:3➝B:
Lbl 3:√A+1➝C:
Lbl_4:B≥C⇒Goto 6:
MOD(A,B)=0⇒Goto 5:
B+2➝B:Goto 4:
Lbl 5:B◢
A÷B➝A:Goto 3:
Lbl 6:A◢
Lbl 7:"END":Goto 0

Time (for ver.2.45 build 20):
7 849 516 203 = 3×3×9 811×88 897 (1.9_sec)
9 000 000 063 = 3×3×1 000 000 007 (5.5_sec)

Edited by Hlib2, 08 August 2021 - 02:20 PM.

[Hlib2]

It`s hard to come up with a better algorithm than ... +2 +4 +2 +4 ... from post a post in UFC This program does not work in fx-7400/9750/9850 due to restrictions on nested loops of type While. In any case, this is the fastest algorithm for other calculators.

Edited by Hlib2, 12 August 2021 - 02:05 PM.

[Krtyski]

Hi Hlib2 and everyone

 

Yes, the algorism is quite good and I also could not find any other faster one.

 

I do not have old models such as fx-7400G or 9750G. Now I realize there is an restrictions on nested loops of type of While. Thank you for this.

 

The oldest model that I could port the algorism to is CFX-9850G. Same program file also runs properly on CFX-9850GC PLUS. Casio Basic of these models have some problems and do not allow simply running g1m files that run on fx-9860GII or 9750GIII. So I needed to modify to have them run on CFX-9850G range. 

 

I also could port to fx-7400GIII, a next model of fx-7400GII.

 

I ported the nice algorism to Python mode (Casio Python) and C.Basic with more ... +2 +4 +2 +4 ... for faster process and also expanded to accept 15 digits input, because Casio Python and C.Basic has calculation accuracy of 15 digits. Casio Python runs very fast as well as C.Basic.

 

I also ported to many Casio graphing calculators from very old models to latest models as much as passible.

 

If you have any interest on details in source code, please download subsequent program files listed below. 

 

1) Casio Basic for Newer model fx-7400GIII;

    * Download: FactorGL for fx-7400GIII

 

* fx-7400GIII Casio Basic does not have Matrix functions, so I needed to replace matrices to lists in the program to make it work.

 

        

 

 

2) Casio Basic for CFX-9850G range (the oldest model that I could port);

     * Download: Casio Basic - FactorG for CFX-9850G

 

* CFX-9850G range Casio Basic does not allow CR at beginning of line and at right after Then and Else, so I needed to remove CR at those above 3 cases from g1m program file that works on fx-9860G range and fx-9750GIII. This modification gives very poor readability on display.

 

        

 

 

3) Casio Basic for FX models (fx-9860G / GII / GIII, fx-9750GIII) & CG models (fx-CG10 / 20/ 50)

     * Download: FactorG1

 

         

 

 

4) Python mode for fx-CG50, fx-9750GIII and fx-9860GIII;

     * Download: FactorG ver 7.1 - supporting 15 digits input

 

* There was no turtle.py and matplot.py released when I made this, so I used my original user module, u.py including following functions (this modules is much more convenient to me);

- isCG(): determines FX model or CG model

- grp_color(): set color using several different ways for parameter settings

- circle(): draws circle

- line(): draws line

- locate(): sets position, size, color of output characters and parameter to transfer to VRAM or show on display

- frac(): gets decimal part

 

* How many times the algorism search, the search # is indicated. This has good relation to process time.

 

         

 

 

5) C.Basic for FX models (fx-9860G / GII / GIII, fx-9750GIII) and CG models (fx-CG10 / 20 / 50)

     * Download: FactorG2 - fastest as much as possible

 

         

 

 

I measured process time for each then C.Basic for CG on fx-CG50 gives fastest result that is much faster than built-in prime factoring feature of fx-991EX.

 

The second record is given by Python mode of fx-CG50, the third is C.Basic for FX on fx-9750GIII, fourth is Python mode of fx-9750GIII, then fx-991EX comes at the fifth.

 

To be honest, I wanted to make program faster than the built-in feature so I tried to make fastest programs on some different platforms.

 

If you have models of them, please have fun!

Edited by Krtyski, 30 August 2021 - 11:15 PM.

[Hlib2]

This is a very interesting training of programming skills in the problem of decomposing a number into multipliers. Some calculators, for example, do not allow you to change the parameters of the "FOR TO NEXT" loop inside the loop, but this would be the fastest program. Here is a universal program for CASIO-BASIC, wich is almost the same in speed as the program from Krtyski. Saving the solution in the array, in my opinion, is more practically.

0➝A~Z : 13➝Dim List 3 : List 3➝List 4
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}➝List 5
Lbl 1 : "INTEGER 2≤N<10^13 ="?->A
A<2 Or A≥10^13 Or Frac A≠0⇒Goto 3
Fill(0,List 3) : Fill(0,List 4) : 1➝List 4[1]
A➝D : 1➝I 
For 1➝K To 15 Step 1
List 5[K]➝B : B²>A⇒Break
While Frac (A÷B)=0 : A÷B➝A
If B=List 3[I]
Then List 4[I]+1➝List 4[I]
Else Isz I : B➝List 3[I] : List 4[I]+1➝List 4[I]
IfEnd
WhileEnd
Next : √A➝C
For 53➝K To C Step 6
While Frac (A÷K)=0 : A÷K➝A
If K=List 3[I]
Then List 4[I]+1➝List 4[I]
Else Isz I : K➝List 3[I] : List 4[I]+1➝List 4[I]
IfEnd : K²>A⇒D➝K
WhileEnd
While Frac (A÷(K+2))=0 : A÷(K+2)➝A
If K+2=List 3[I] 
Then List 4[I]+1➝List 4[I]
Else Isz I : K+2➝List 3[I] : List 4[I]+1➝List 4[I]
IfEnd : K²>A⇒D➝K
WhileEnd
Next
If A≠1
Then If A=List 3[I]
Then List 4[I]+1➝List 4[I]
Else Isz I : A➝List 3[I] : List 4[I]+1➝List 4[I]
IfEnd
IfEnd
D➝List 3[1] : List➝Mat(3,4)◢
Goto 1
Lbl 3 : "END"

testing 7849516203=3^2×9811×888897:
fx-9750g+: 97_sec
fx-9750gII: 13.3_sec
fx-9860gII: 1.75/1.35_sec(C.BASIC ver.2.45)
Replacing Frac (A÷K) with MOD(A,K) etc. increases the speed in 9860gII C.BASIC mode by 30%, but there are almost no changes in genuine BASIC.

Edited by Hlib2, 24 August 2021 - 05:32 PM.

[Tritonio]

The algorithm with the gotos seems to be using the same logic as mine. I don't know how faster it will be with gotos though.

[Tritonio]

`#CBDBL
Lbl 0:"N="?➝A:Goto 2:
Lbl 1:2◢
A÷2➝A:A=1⇒Goto 7:
Lbl 2:MOD(A,2)=0⇒Goto 1:3➝B:
Lbl 3:√A+1➝C:
Lbl_4:B≥C⇒Goto 6:
MOD(A,B)=0⇒Goto 5:
B+2➝B:Goto 4:
Lbl 5:B◢
A÷B➝A:√A+1➝C:Goto 3:
Lbl 6:A◢
Lbl 7:"END":Goto 0

Hlib2 can you please time the above version on the same calculator? The only change I made is three lines from the end.

[caladrad58]

interesting information

Edited by caladrad58, 23 August 2022 - 06:46 AM.