Prime factorization for fx-5800P

fx-5800P

5 replies to this topic

#1 Tritonio

Tritonio

• Members
• 67 posts
• Gender:Male

• Calculators:
fx-5800P, fx-991ES+, fx-991EX, HP Prime, fx-9750GIII

Posted 13 July 2021 - 02:12 PM

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.

#2 Krtyski

Krtyski

Casio Freak

• Members
• 129 posts
• Gender:Male
• Location:Tokyo, Japan
• Interests:programming, smooth Jazz and 4-wheel driving.

• Calculators:
FX-502P, FX-602P, FX-603P,
fx-4000P, fx-7000G,
fx-4500P, fx-4800P
fx-5800P,
CFX-9850G,
CFX-9850GC PLUS
fx-9860G,
fx-9860G AU,
fx-9860G Slim
fx-9860GII SD,
fx-9860GII-2,
fx-9860GII-2 SD,
fx-CG20, fx-CG50,
fx-CP400
fx-9860GIII
fx-9750GIII
fx-7400GIII

Posted 31 July 2021 - 08:44 AM

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

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.

#3 Hlib2

Hlib2

Casio Freak

• Members
• 131 posts
• Gender:Male
• Location:Ukraine
• Interests:industrial electronics,
graphing calculators

• Calculators:
fx-9860GII-2, afx-2.0+
fx-9750GII, fx-9750G+
cfx-9850GB+, graph25
fx-991DE_X, fx-991ES+
ti-83+, ti-83+_SE, ti-85
ti-voyage200, graph100+

Posted 01 August 2021 - 07:47 PM

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.

#4 Hlib2

Hlib2

Casio Freak

• Members
• 131 posts
• Gender:Male
• Location:Ukraine
• Interests:industrial electronics,
graphing calculators

• Calculators:
fx-9860GII-2, afx-2.0+
fx-9750GII, fx-9750G+
cfx-9850GB+, graph25
fx-991DE_X, fx-991ES+
ti-83+, ti-83+_SE, ti-85
ti-voyage200, graph100+

Posted 11 August 2021 - 05:47 PM

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.

#5 Krtyski

Krtyski

Casio Freak

• Members
• 129 posts
• Gender:Male
• Location:Tokyo, Japan
• Interests:programming, smooth Jazz and 4-wheel driving.

• Calculators:
FX-502P, FX-602P, FX-603P,
fx-4000P, fx-7000G,
fx-4500P, fx-4800P
fx-5800P,
CFX-9850G,
CFX-9850GC PLUS
fx-9860G,
fx-9860G AU,
fx-9860G Slim
fx-9860GII SD,
fx-9860GII-2,
fx-9860GII-2 SD,
fx-CG20, fx-CG50,
fx-CP400
fx-9860GIII
fx-9750GIII
fx-7400GIII

Posted 16 August 2021 - 03:43 AM

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;

* 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);

* 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)

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

* 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)

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.

#6 Hlib2

Hlib2

Casio Freak

• Members
• 131 posts
• Gender:Male
• Location:Ukraine
• Interests:industrial electronics,
graphing calculators

• Calculators:
fx-9860GII-2, afx-2.0+
fx-9750GII, fx-9750G+
cfx-9850GB+, graph25
fx-991DE_X, fx-991ES+
ti-83+, ti-83+_SE, ti-85
ti-voyage200, graph100+

Posted 24 August 2021 - 11:59 AM

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.

Also tagged with one or more of these keywords: fx-5800P

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users