Post Reply 
[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
02-11-2019, 05:16 PM (This post was last modified: 04-12-2019 12:44 PM by fred_76.)
Post: #1
[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
Hello

My name is Fred, I am from France. I am used to HP calculators since I was young in the 80's. My father was working in a military-like industry and was supplied with new HP calc every two or three years. Therefore I was always fed with the previous calc he had.

It all started to me with the grey HP65, then the HP67, the HP34, the HP41 (don't remember which one exactly). I don't have them anymore, they were trashed ... sigh ...

I bought a HP32S and that was one of the very best I had. It was stollen during a company convention...

I then asked the company to buy me a calc, it was a HP48S, again it was stollen when my office was broken ! The company bought me another calc, a HP48GII that I found desesperatly anoying and hard to program.

My sons just offered me a HP35S and I rediscovered the pleasure of the RPN calculators.

Here is a code that I find quite effective to determine if a number is prime or not, and that also calculates the factors. It make an extensive use of the stack to avoid unecessary STO/RCLs. It also makes use of fast tricks, such as storing repetitive constants and using included operations. For example [6] [+] is about 4.3 times slower than [RCL+S] (with 6 previously stored in S).

The logic below is a brut force with elimination of the trivial factors that are multiples of 2, 3 and 5. From 7, you just loop by adding 4,2,4,2,4,6,2,6 to the trial factor.

Here is the code :

Code:

P001    LBL P    :Prime calc routine
P002    ENTER    :stack N in the pile
P003    ENTER    :to Z 
P004    ENTER    :so that it is in T at the next line
        
P005    2    
P006    STO T    :store 2 (t as two)
P007    RCL+T    :add 2
P008    STO F    :store 4 (f as four)
P009    RCL+T    :add 2
P010    STO S    :store 6 (S as six)
        
P011    RCL-F    :subtract 4 to get 2
P013    RMDR    :check if N is a mult of 2
P013    x=0?            :if rest is =0 then N is a mult of 2
P014    GTO P087    :so goto end of calc
        
P015    CLx    
P016    3            :check if N is a mult of 3
P017    RMDR    
P018    x=0?    
P019    GTO P087    
        
P020    CLx    
P021    LAST x    
P022    RCL+T    :check if N is a mult of 5
P023    RMDR    
P024    x=0?    
P025    GTO P087    
        
P026    CLx    
P027    LAST x    
P028    RCL+T    :check if N is a mult of 7
P029    RMDR    
P030    x=0?    
P031    GTO P087    
        
                :from that point, it will loop and add successively 4,2,4,2,4,6,2,6 to the 
                :factor and check is N is a mult of the factor
        
P032    CLx    
P033    LAST X    
P034    RCL+F    :4
P035    RMDR    
P036    x=0?    
P037    GTO P087    
        
P038    CLx    
P039    LAST X    
P040    RCL+T    :2
P041    RMDR    
P042    x=0?    
P043    GTO P087    
        
P044    CLx    
P045    LAST X    
P046    RCL+F    :4
P047    RMDR    
P048    x=0?    
P049    GTO P087    
        
P050    CLx    
P051    LAST X    
P052    RCL+T    :2
P053    RMDR    
P054    x=0?    
P055    GTO P087    
        
P056    CLx    
P057    LAST X    
P058    RCL+F    :4
P059    RMDR    
P060    x=0?    
P061    GTO P087    
        
P062    CLx    
P063    LAST X    
P064    RCL+S    :6
P065    RMDR    
P066    x=0?    
P067    GTO P087    
        
P068    CLx    
P069    LAST X    
P070    RCL+T    :2
P071    RMDR    
P072    x=0?    
P073    GTO P087    
        
P074    CLx    
P075    LAST X    
P076    RCL+S    :6
P077    RMDR    
P078    x=0?    
P079    GTO P087    
        
                  :check if the factor^2 is greater than N, 
                :(SQR is 30% faster than SQRT)
                :if greater, then N is prime, otherwise loop
P080    CLx    
P081    LAST X    
P082    x²
P083    x<y?    
P084    GTO P032    
        
P085    Rv            :if N is prime
P086    RTN            :stop and show X=Y=N
        
P087    CLx            :if N is not prime
P088    LAST X    :show first factor
P089 x=y?            :for 2-3-5-7
P090 GTO P085    :2-3-5-7 are prime 
P091    STOP    :stop to show result X=factor, Y=N
P092    INT/            :press R/S to
P093    GTO P001    :start again to find the next factor
P094    RTN

To use it, just enter the number to test, then press XEQ P.
  • If the number is prime, X=Y=Number
  • If the number is not prime, X=first factor found, Y=Number
  • then press R/S to continue the calc and find the next factors until X=Y

It runs quite fast on my HP35S :

PHP Code:
Digits        Prime Number           Total Time
6 digits       999 863               00
:00:10
7 digits       9 999 991             00
:00:28
8 digits       99 999 989            00
:01:28
9 digits       999 999 937           00
:04:36
10 digits      9 999 999 967         00
:14:37
11 digits      99 999 999 977        00
:46:26
12 digits      999 999 999 989       02
:32:18 

All the best

Fred

--- edit : added time for 12 digits
--- edit : added lines P089/P090 to handle exceptions 2/3/5/7
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - fred_76 - 02-11-2019 05:16 PM



User(s) browsing this thread: 1 Guest(s)