Jump to content



Photo
- - - - -

Short And Speedy Prime Factorization Programs For Casio Fx-9860gii Sd


  • Please log in to reply
3 replies to this topic

#1 Jenab6

Jenab6

    Newbie

  • Members
  • Pip
  • 14 posts
  • Gender:Male
  • Location:Hillsboro, West Virginia, USA
  • Interests:Astronomy, math, physics, nationalist politics.

  • Calculators:
    CASIO fx-115ES, fx-9860g, fx-9860g ii SD
    SHARP el-506a, el-509d, el-546g
    Texas Instruments TI-89T
    Base 8 DG-1000

Posted 11 December 2010 - 07:37 PM

Here is the code for my prime factors calculation program for the Casio fx-9860gii SD. It can factorize the integer 44355599 into the prime numbers 6659 and 6661 in 38.2 seconds. I will use this example as a benchmark.

"Prime factorize"
?→N
{N}→List 1
N→M
0→I
Lbl 1
If M<2 or Int M≠M
Then Goto 9
IfEnd
While MOD(M,2)=0
I+1→I
2→List 1[I]
M÷2→M
WhileEnd
1→K
Lbl 2
If M=1 Or K>M
Then Goto 9
IfEnd
K+2→K
If M=N And K>√N
Then Goto 9
IfEnd
While MOD(M,K)=0
I+1→I
K→List 1[I]
M÷K→M
WhileEnd
Goto 2
Lbl 9
List 1

There is some inefficiency in the program because after it finishes finding the divisors of 2 (if there are any) to the input number, it thereafter checks to see whether all of the odd-integers might be a divisor, whether the odd-integer is a prime or not. However, it seems to me that filtering out the composite odd-integers will require tests that might consume as much CPU time as just going ahead with the check.

This code will not work on the original fx-9860g calculator until you replace two lines.

While MOD(M,2)=0
is replaced by
While M÷2−Int(M÷2)=0

While MOD(M,K)=0
is replaced by
While M÷K−Int(M÷K)=0

However, when this is done, the Casio fx-9860g performs the same task in only 25.8 seconds, which is only 67.5% of the time required by its successor model, the fx-9860gii.

If anybody can create a speedier SHORT prime factorization code for the fx-9860gii SD, I'd like to see it in format like above shown.

Edited by Jenab6, 11 December 2010 - 08:03 PM.


#2 Jenab6

Jenab6

    Newbie

  • Members
  • Pip
  • 14 posts
  • Gender:Male
  • Location:Hillsboro, West Virginia, USA
  • Interests:Astronomy, math, physics, nationalist politics.

  • Calculators:
    CASIO fx-115ES, fx-9860g, fx-9860g ii SD
    SHARP el-506a, el-509d, el-546g
    Texas Instruments TI-89T
    Base 8 DG-1000

Posted 11 December 2010 - 11:00 PM

In the line that reads

If M=1 Or K>M

The last part isn't necessary, so change it to

If M=1

I made that change, and the program still works, with a gain of about 8% in speed. At the point where K=M, M is divided by K and assigned to M, leaving M=1, so K should never be greater than M. I think that I put the extra stop loop condition there while anticipating division round-off error which does not seem to be occurring.

#3 Guest_bee_*

Guest_bee_*
  • Guests

Posted 05 February 2011 - 01:06 PM

In the line that reads

If M=1 Or K>M

The last part isn't necessary, so change it to

If M=1

I made that change, and the program still works, with a gain of about 8% in speed. At the point where K=M, M is divided by K and assigned to M, leaving M=1, so K should never be greater than M. I think that I put the extra stop loop condition there while anticipating division round-off error which does not seem to be occurring.


hello
I have a casio graph 35 + and this is not working for me. Do I have to change something?

thanks in advance

#4 Guest_Anton_*

Guest_Anton_*
  • Guests

Posted 01 May 2011 - 10:01 AM

Hello! I've made a factorization program that only takes one third of the time it takes for yours. It uses the fact that all primes except 2 and 3 can be expressed as 6k±1. But note that I'm not used to Casio basic, so I'm sure I've missed a lot of optimization.

"FAKTOR"
{0}→List 1
1→I
?→N
While Frac (N÷2)=0
N÷2→N
2→List 1[I]
I+1→I
WhileEnd
While Frac (N÷3)=0
N÷3→N
3→List 1[I]
I+1→I
WhileEnd
5→F
While F≤√N
While Frac (N÷F)=0
N÷F→N
F→List 1[I]
I+1→I
WhileEnd
F+2→F
While Frac (N÷F)=0
N÷F→N
F→List 1[I]
I+1→I
WhileEnd
F+4→F
WhileEnd
N≠1=>N→List 1[I]
List 1

I sincerely hope that someone will write a more efficient factorization program than this, cause 12 seconds for an eight digit long number is slow.




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users