The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

Hp 71 program to perform prime factor
Message #1 Posted by wildpig on 20 Dec 2007, 12:27 a.m.

Hi, just wondering if anyone got a hp71b program to do prime factor of a number (and to calculate Euler's function)? appreciate if i can get it. thanks.

      
Re: Hp 71 program to perform prime factor
Message #2 Posted by Meenzer on 20 Dec 2007, 9:47 a.m.,
in response to message #1 by wildpig

Here is a program for the Casio FX-850/880P that does prime factoring; with some modification it should run on the 71B as well. At least you can use it as a guideline...

5 ONERRORGOTO1000

10 MODE8:DIM:x=2:c$=CHR$(5)

20 CLS:PRINT"Prime factors (2ˇBase<10ă°)";:a$=" *"

40 LOCATE0,1:PRINTc$;"Base ?";:INPUT@11;x:LOCATE0,0

45 IFx<2 ORx>=1e10 ORFRACx<>0 THEN40

50 LOCATE0,1:PRINTc$;x;"= .....";

60 u=0:v=0:n=1:t$="":a=x

70 GOTO130

100 u=2:GOSUB500

110 a=a/2

120 IFa-1=0 THEN240

130 IFFRAC(a/2)=0 THEN100

140 b=3

150 c=SQRa+1

160 IFb>=c THEN230

170 IFFRAC(a/b)=0 THEN190

180 b=b+2:GOTO160

190 IFa/b*b-a=0 THEN210

200 GOTO180

210 u=b:GOSUB500

220 a=a/b:GOTO150

230 u=a:GOSUB500

240 a$="":GOSUB530

250 PRINTc$;x;"=";t$;:z$=INPUT$(1,@):GOTO20

500 IFv=u THENn=n+1:GOTO550

520 IFv=0 THEN550

530 IFn>1 THENt$=t$+STR$(v)+"^"+MID$(STR$(n),2)+a$ELSEt$=t$+STR$(v)+a$

540 n=1

550 v=u:RETURN

1000 IFERR=1 THENCLS:ONERRORGOTO0

1010 IFERL=40 THENRESUME40

1050 LOCATE0,1:PRINTc$;"not found";:z$=INPUT$(1,@):RESUME20

EDIT: Just to give credit where credit is due - I downloaded this from the internet some time ago, but if I remember right, it's a dump from a build in function of the 850/880P's scientific library.

Edited: 20 Dec 2007, 10:16 a.m.

            
Re: Hp 71 program to perform prime factor
Message #3 Posted by wildpig on 20 Dec 2007, 7:29 p.m.,
in response to message #2 by Meenzer

Appreciate everyone's help so far. Afraid I am still relatively new at this. Never really program in BASIC (or really much of any programming). Appreciate as much hand holding as anyone can give. I just got this recent urge to collect HP calcs. Got 8 of them (50g, 28s, 71b, 42s, 41cv, 41cx, 67, 35) in the last 2 months. This is in addition to 48sx and 32sii which i bought over 10 yrs ago.

I got the prime factor program for hp 41/42s and hp 67. just want to test out how efficent and fast the hp 71 would be compared to others.

I also got an hp 50g and hp 28s. Anyone know where i can get RPL prime factor programs? ;)

Thank you.

                  
Re: Hp 71 program to perform prime factor
Message #4 Posted by Gerson W. Barbosa on 20 Dec 2007, 8:14 p.m.,
in response to message #3 by wildpig

Quote:
Anyone know where i can get RPL prime factor programs? ;)

Try http://www.hpcalc.org/

The basic version I sent you is based upon this one:

http://www.hpcalc.org/search.php?query=primefac

Note:

1) There is at least one instance of NOT NOT in the RPL program. Of course they cancel each other and should be omitted;

2) K=IP(SQR(R)) in the BASIC program can be replaced with simply K=SQR(R).

Regards,

Gerson .

Edited: 20 Dec 2007, 8:16 p.m.

      
Re: Hp 71 program to perform prime factor
Message #5 Posted by Don Shepherd on 20 Dec 2007, 10:22 a.m.,
in response to message #1 by wildpig

Here is a very simple although inefficient method, in generalized BASIC:

Input A
B=2
Do 
  While Frac(A/B)=0
    Print B
    A=A/B
  EndWhile
  If B=2 Then B=3 Else B=B+2
Loop While B<=A
            
Re: Hp 71 program to perform prime factor
Message #6 Posted by Steve Perkins on 20 Dec 2007, 5:34 p.m.,
in response to message #5 by Don Shepherd

I like that small, easy to understand program, Don.

The only change I would suggest is the ending test. You should only have to check up to the square root of the number being factored. Then print the number tested. I would change it to:

Loop While B*B<=A

Print A

I may have missed something, but this should make it much more efficient.

                  
Re: Hp 71 program to perform prime factor
Message #7 Posted by Don Shepherd on 20 Dec 2007, 6:53 p.m.,
in response to message #6 by Steve Perkins

Hey Steve, I agree it would make it more efficient, but it won't work. I tried that when I first saw this particular algorithm. You are right, you normally only want to go up to the square root of the number, but doing so in this algorithm won't give you the final factor. For example, for input 45, it only gives you 3 and 3, and you don't get the 5.

It may be an easy change to fix this (and only go to the square root), but I have not figured it out yet. Any takers?

                        
Re: Hp 71 program to perform prime factor
Message #8 Posted by Don Shepherd on 20 Dec 2007, 7:00 p.m.,
in response to message #7 by Don Shepherd

Steve, I'm a moron. I didn't see your Print A until after I posted. I think you are right! Thanks!

Don

      
Re: Hp 71 program to perform prime factor
Message #9 Posted by Gerson W. Barbosa on 20 Dec 2007, 7:32 p.m.,
in response to message #1 by wildpig

You can try the following, before you get something faster:

10 INPUT N
15 I=2 @ GOSUB 40 @ I=3
20 GOSUB 40
25 I=I+2
30 IF N<>1 THEN 20
35 END
40 IF MOD(N,I)<>0 THEN RETURN
45 N=N DIV I
50 PRINT I;
55 IF MOD(N,I)=0 THEN 45
60 GOSUB 70 @ IF MOD(N,J)<>0 THEN I=N-2
65 RETURN
70 R=N @ J=1 @ K=IP(SQR(R))
75 J=J+2
80 IF J<K AND MOD(N,J)<>0 THEN 75
85 RETURN

>RUN ? 12345678901 857 14405693

About 100 seconds on the real 71B, I would guess.

Regards,

Gerson.

            
Re: Hp 71 program to perform prime factor
Message #10 Posted by wildpig on 20 Dec 2007, 7:33 p.m.,
in response to message #9 by Gerson W. Barbosa

Thanks will try this

            
Re: Hp 71 program to perform prime factor
Message #11 Posted by wildpig on 20 Dec 2007, 8:05 p.m.,
in response to message #9 by Gerson W. Barbosa

That does work but seem a little slow. The program on my hp42s gives the answer about 3 times as fast. Good starting point though i guess.

                  
Re: Hp 71 program to perform prime factor
Message #12 Posted by Gerson W. Barbosa on 20 Dec 2007, 8:31 p.m.,
in response to message #11 by wildpig

A port of the 42s program to the 71b would be fine, considering the 71b is about 2.5 times faster than the the 42s. Anyway, the BASIC program is based on an RPL program I wrote for the 28s, which in turn was based on the way I used to do that by hand...

Regards,

Gerson.

                        
Re: Hp 71 program to perform prime factor
Message #13 Posted by Jean-Michel on 21 Dec 2007, 7:29 a.m.,
in response to message #12 by Gerson W. Barbosa

Bom dia, Gerson!

Glad to welcome you here after this three months absence. You're as usually: accurate and helpful!

Cheers,

Jean-Michel.

                  
Re: Hp 71 program to perform prime factor
Message #14 Posted by wildpig on 22 Dec 2007, 3:18 p.m.,
in response to message #11 by wildpig

Anyone else have any other idea to shorten the execution time? The above program is giving slower answer than would be expected for the hp 71. Thanks

                        
Re: Hp 71 program to perform prime factor
Message #15 Posted by Meenzer on 22 Dec 2007, 3:45 p.m.,
in response to message #14 by wildpig

wildpig says:

Quote:
Never really program in BASIC (or really much of any programming).

Quote:
Anyone else have any other idea to shorten the execution time? The above program is giving slower answer than would be expected for the hp 71. Thanks

There are faster machines and faster ways to do this. Knowing this and still wanting to be doing it on the 71B means you're doing it just for the fun of it.

Why should anybody rob you of this fun??? Why should anybody do YOUR hobby for you????

                              
Re: Hp 71 program to perform prime factor
Message #16 Posted by wildpig on 22 Dec 2007, 3:59 p.m.,
in response to message #15 by Meenzer

Just trying to see how fast these calculators can be. Which is one reasons why i collect hp calcs

                                    
Re: Hp 71 program to perform prime factor
Message #17 Posted by Don Shepherd on 22 Dec 2007, 4:10 p.m.,
in response to message #16 by wildpig

Pig, I think Valentin and others have written that the 71B is NOT a fast machine, certainly by today's standards. But it is fun to see if they can do these tasks at all, especially given the limited resources on many vintage HP calcs. I recently implemented the HCC2007 programming contest problem on a HP-65, and it was a lot of fun to see if it could be done on a 33-year-old machine with 8 usable registers and 100 lines of code. And it works!

So if speed is what you want, go modern! Otherwise enjoy doing things on old calcs for the fun of it!

                                          
Re: Hp 71 program to perform prime factor
Message #18 Posted by wildpig on 22 Dec 2007, 9:46 p.m.,
in response to message #17 by Don Shepherd

Sorry for being so persistent. Hate to see the hp71 which is supposed to be faster than the 42s keeps losing... ;)

                                                
Re: Hp 71 program to perform prime factor
Message #19 Posted by Egan Ford on 24 Dec 2007, 11:33 a.m.,
in response to message #18 by wildpig

Quote:
Hate to see the hp71 which is supposed to be faster than the 42s keeps losing... ;)
Where is this stated?

The 71B and 42S both use a Saturn processor. The 71B is clocked at 640MHz [http://en.wikipedia.org/wiki/Saturn_(microprocessor)] and the 42S at 1MHz. The 42S also has a less complex programming and operating environment.

I would be surprised if the 71B/BASIC bested the 42S/RPN. Input FACTORLX if you want to see 71B/Assembly in action.

                                                      
Re: Hp 71 program to perform prime factor
Message #20 Posted by wildpig on 24 Dec 2007, 11:15 p.m.,
in response to message #19 by Egan Ford

Hmm, don't see it says what 42s clock speed is on there anywhere.

According to HPmuseum, 71b is faster than 42s (http://www.hpmuseum.org/speed.htm)

Same also at http://www.thimet.de/CalcCollection/CalcPerformance.html

I have the optimized fibonacci program for both calcs and the 71b always beat the 42s by a good margin

                                                      
Re: Hp 71 program to perform prime factor
Message #21 Posted by wildpig on 24 Dec 2007, 11:17 p.m.,
in response to message #19 by Egan Ford

Is there a way to resume entering factorlx or do I have to type everything in all in one sitting. ? ;(

                        
Re: Hp 71 program to perform prime factor
Message #22 Posted by Gerson W. Barbosa on 22 Dec 2007, 5:18 p.m.,
in response to message #14 by wildpig

Add the following line to the above program. The program will still be slow but at least this change will allow numbers like 111121121, for instance, to be processed under three minutes rather than hours :-)

12 IF MOD(N,2)=0 THEN 15 ELSE GOSUB 70 @ IF MOD(N,J)<>0 THEN PRINT N; @ END

And make this change to line 70:

70 R=N @ J=1 @ K=SQR(R)

Regards,

Gerson.

                              
Re: Hp 71 program to perform prime factor
Message #23 Posted by wildpig on 22 Dec 2007, 9:42 p.m.,
in response to message #22 by Gerson W. Barbosa

That additional line did speed up the evaluation of a prime number considerably ;). Evaluating a prime number was the cause of the slowdown on the 71. Although i think evaluation of non prime number and factors are still slightly faster on my 42s.

I willl try to learn hp basic ;)

anyone else help is also appreciated.

Thanks G..

      
Re: Hp 71 program to perform prime factor
Message #24 Posted by Egan Ford on 20 Dec 2007, 8:22 p.m.,
in response to message #1 by wildpig

Are you looking for speed or want to study the algorithm?

For speed get FACTORLX and try:

10 INPUT "N: ";N
20 A=FACTOR(N)
30 IF A=N THEN PRINT A @ END
40 PRINT A;
50 N=N/A
60 GOTO 20
E.g.
>RUN
N: 123123123123
 3  7  11  13  41  101  9901
            
Re: Hp 71 program to perform prime factor
Message #25 Posted by wildpig on 20 Dec 2007, 11:08 p.m.,
in response to message #24 by Egan Ford

Where do i get FACTORLX? thanks

                  
Re: Hp 71 program to perform prime factor
Message #26 Posted by Egan Ford on 21 Dec 2007, 1:59 a.m.,
in response to message #25 by wildpig

http://membres.lycos.fr/jeffcalc/lexfl1.zip

Unzip, then mount lexfl1.lex under emu71 as :HDRIVE1 or 2.

                        
Re: Hp 71 program to perform prime factor
Message #27 Posted by wildpig on 21 Dec 2007, 2:33 a.m.,
in response to message #26 by Egan Ford

Hmm, a 600k file. Guess this is only for the emu? can't load this into my hp 71b?

                              
Re: Hp 71 program to perform prime factor
Message #28 Posted by Egan Ford on 21 Dec 2007, 9:23 a.m.,
in response to message #27 by wildpig

It's a LIF disk image.

You have a few options:

1. With a DOS or Linux PC you can create a floppy (720K). Then you'll need a 9114 drive and HP-IL to get it on your 71B.

2. Use a PC with DOS/Linux and an HP-IL ISA adapter with the registered version of EMU71. Plus, HP-IL for 71B. Then, copy using HP-IL.

3. You can mount with EMU71, and use dumplex and makelex to hand type it in. I'll make it easy for you, I ran dumplex for you and posted the output here: http://sense.net/~egan/factorlx.txt

You need to type in makelex, run it, and input all 1040 bytes of factorlx.txt.

makelex:

10 SFLAG -1 @ ON ERROR GOTO 30 @ DESTROY ALL 
20 PURGE DUMMY
30 ON ERROR GOTO 220
40 INPUT '# of bytes: ';N
50 CREATE TEXT DUMMY,N
60 A=HTD(ADDR$('DUMMY')) @ A1=A @ P$="----------------"
70 Q=1 @ X=0 @ INPUT '000: ',P$;A$ @ C$=A$ @ GOSUB 200
80 Q=2 @ X=1 @ GOSUB 190
90 A$=A$&C$ @ A=A+37 @ N=N*2+31 @ Q=3 @ SFLAG 5
100 FOR X=2 TO N DIV 16-1
110 GOSUB 190
120 IF FLAG(5) THEN C$=C$[6]
130 POKE DTH$(A),C$ @ A=A+16-5*FLAG(5,0) @ NEXT X @ Q=4
140 DISP DTH$(X)[3]; @ INPUT ': ',P$[1,MOD(N,16)];C$
150 GOSUB 200
160 L=LEN(C$) @ IF C$[L,L]='-' THEN C$=C$[1,L-1] @ GOTO 160
170 POKE DTH$(A),C$ @ POKE DTH$(A1),A$
180 OFF ERROR @ CFLAG -1 @ END 
190 DISP DTH$(X)[3]; @ INPUT ': ',P$;C$
200 DISP DTH$(X)[3]; @ INPUT ' ck ','--';C1$
210 S=0 @ FOR Z=1 TO LEN(C$) @ S=IP(NUM(C$[Z,Z])*Z+S) @ NEXT Z
220 IF C1$=DTH$(MOD(S,256))[4] THEN RETURN 
230 DISP 'Checksum Error' @ BEEP @ POP @ ON Q GOTO 70,80,110,140
240 DISP 'Error:'&ERRM$ @ BEEP @ GOTO 180
                                    
Re: Hp 71 program to perform prime factor
Message #29 Posted by wildpig on 21 Dec 2007, 7:29 p.m.,
in response to message #28 by Egan Ford

No simple program that i can just type in eh? ;(

The above program posted by Gerson does sorta work but is very slow since my 71 is getting the answer slower than the hp42s.

I have the HPIL addon on the calc but not the cable. ;(

                                    
Re: Hp 71 program to perform prime factor
Message #30 Posted by wildpig on 23 Dec 2007, 12:54 a.m.,
in response to message #28 by Egan Ford

Is there anyway to pause and turn off the calc while entering factorlx or will i have to start from scratch? ;(


[ Return to Index | Top of Index ]

Go back to the main exhibit hall