Prime Numbers



#27

Ever since I was in high school, I've always been facinated with prime numbers and computers. In a math class there was a desktop computer that could be programmed with punch cards (around 1971). I don't remember the make of the computer but a classmate programmed the computer to print out prime numbers. I made a copy of his punch cards and between the two of us filled the walls of the classroom with printouts of prime numbers over the next few months. Looking back, our teacher was amused and very patient with our after school activity of printing out prime numbers cluttering the walls of his classroom and destroying trees.

I never understood the program my classmate wrote but when I got my first programmable calculator, an HP-55 which I still own and works well, the first program I ever wrote on it was how to generate a list of prime numbers.

The program was slow and had no printout, but it forced me to try and program. My little program worked but not very well, and since the 55 is so limited in programming, I didn't continue with this passion until I got an HP-41C.

With the HP-41C, a card reader and a printer, I started trying to modify my program to print out prime numbers on my 41C. Again, my program worked but it was slow and took a long time to print out prime numbers and was nothing like the desktop computer back in high school.

As A member of the PPC, I purchesed back issues of the PPC Journal and on page 31 of V7 N1, there was what I was looking for. An article about Faster Primes by Walter Castles with a 41C program listing on page 32. I put it in immediately and was astounded at how fast it was. I tried every way I could think of to analyze and understand Walter's program without success.

(As a side note, I recently loaded this program into a 41 PC emulator and it ran like the wind until it crashed because data registers above 99 can't be accessed directly. I've always wondered why. I assume it was never designed to calculate prime numbers that large.)

I gave up on it until I got a 48GX and tried to figure out how to translate this program into RPL. I was not able to figure out how to do it and felt very frustrated.

I have since purchased a 49G, a 49g+ and a 50G and this has motivated me to once again try again to translate this 41C program to RPL.

To minimize my frustration, I will begain by admitting defeat in trying to understand how this program works. It's only 66 steps long but it's a puzzle to me. If anyone who has read this story has some insights on how this proggram works I would be grateful. I would like to put this little fetish to rest until the next generation of calculators comes out.

Thanks for reading,

Gerry


#28

Hi Gerry.

What about posting the program listing on the Forum, so that everyone can

have a look at it and may help you (and teach others)?

Best regards.

Giancarlo


#29

http://www.brouhaha.com/~eric/hpcalc/hp41c/faster_primes.html

I have not spent time proofreading it, so I may have introduced errors.


#30

Thanks Eric!

I just typed it in to post it and the formatting was destroyed, rendering it unreadable. I am so looking forward to all your feedback. I've wondered about this for over 20 years!

I also checked your listing, Eric and it looks correct to me.

Thank you,

Gerry


#31

Gerry,

posting program listings is easy, just surround your code with special tags which are understood by the forum software:

[pre]
Your
code
goes
here
[/pre]

The tags mean "preformatted" and cause the insertion of HTML <pre>...</pre> tags in the generated page. Just try it yourself!

Marcus

#32

Prepare for something ugly:

;
; Prime number for Hewlett-Packard 29C
; April 26, 2004
;
; This program determines whether a number is a prime number or not
;
; key in the program
; input a positive integer number
; GSB 1 => positive result (number is prime)
; negative result (number is not prime)


LBL 1 ; start of prgram
STO 1 ; store number to examine
sqrt
STO 3 ; criterion for end of program
FRAC
x=0
GTO 7 ; number is square => not prime
0
STO 2 ; holds divisor
GSB 5
1
GSB 4
GSB 5
LBL 2 ; loops divisors
4
GSB 4
4
GSB 4
4
GSB 6
6
GSB 4
6
GSB 6
GTO 2
LBL 4
GSB 6
LBL 5
2
LBL 6
STO+ 2 ; next divisor
RCL 1
RCL 2
PAUSE ; show progression
RCL 3
x!=y ; x>=y doesn't exist on an HP-29C
x>y
GTO 8
RCL 1 ; checked all divisors => prime
R/S
LBL 8
Rolldown
/
FRAC
x!=0
RTN ; goto next divisor
LBL 7 ; show negative number (=not prime)
RCL 1
CHS
R/S


; Register usage:
; R 1 number
; R 2 divisor
; R 3 sqrt(number)

; Label usage:
; 0
; 1 (line 01) start of program
; 2 (line 14) main loop, prepare next divisor
; 3
; 4 (line 26)
; 5 (line 28)
; 6 (line 30)
; 7 (line 47) not prime, show negative
; 8 (line 41) divide and check
; 9
;
; To learn about the program
; The rather complex construction with the subroutines 4, 5 and 6
; has been set up to skip divisors that are a multiple of 3 5 and 7
;

I must have aimed to maximum complexity ;-)

I cannot really replay my thoughts, but I guess I once was very ambitious to create the fastest program on a 29C for the larger numbers.

#33

Hi Gerry.
I wrote a program for the HP29C last January that would find all the prime factors for a given integer, and also list all the primes between two given integers. I submitted it to the forum and it's in the archives here. Basically, it starts out by manually dividing the given prime candidate by 2, 3, 5, and 7, after which it adds to the divisor using an eight number repeating pattern (4,2,4,2,4,6,2,6), so that all subsequent multiples of 2,3,and 5 are skipped (I worked the pattern out on a spreadsheet). It declares the number as prime once the divisor is greater than the square root of the candidate and nothing has gone into it evenly. I experimented with using larger patterns to skip more multiples, but surprisingly the increase in speed was neglegable, as well as making the program unduly long.

Perhaps this will shed some light on the program you are trying to analize.

Best regards, Hal


#34

More to Hal's last post. In last February's note, (in responce to Hal's), I misstated the number of program lines in Peter's Henrici's prime program for the HP-25. The correct number is 44. The program also gives all the prime factors of a non-prime number. I will post it if you are interested.

tm


#35

Henrici's HP25 book is a wonderful little Gem. I had a copy in 1979 (which I later on tossed out) and I am happy to say that I was able to find another copy. Henrici's code is very tight and he seems to push the HP25 calculator to its limits.

Namir

#36

Hi Trent,

I'd very much like to see the 44 line program if you get a chance.

Thanks, Hal


#37

Here is Peter Henrici's prime number program for the HP-25/25C:

Fix 0

00

01 STO 0

02 2

03 STO 2

04 1

05 STO 3

06 RCL 0

07 SQRT

08 STO 1

09 RCL 2

10 RCL 1

11 X<Y

12 GTO 41

13 RCL 0

14 RCL 2

15 /

16 FRAC

17 X=0

18 GTO 35

19 4

20 RCL 2

21 X=>Y

22 GTO 28

23 2

24 STO*2

25 1

26 STO-2

27 GTO 09

28 3

29 STO+2

30 RCL 3

31 CHS

32 STO 3

33 STO+2

34 GTO 09

35 RCL 0

36 RCL 2

37 R/S

38 /

39 STO 0

40 GTO 07

41 RCL 0

42 R/S

43 0

44 GTO 00

Examples: 36 = 2 * 2 * 3 * 3 in about 8 sec.
71489 = 11 * 67 * 97 in about 28 sec.
987654321 = 3 * 3 * 17 * 17 * 379721 in about 220 sec.

Have fun!

tm


#38

To All:

Thank you for your feedback and suggestions.

Marcus, I didn't realize that the formatting of a posting is based upon HTML code. What other commands does the editor support?

Bram, you program looks like a little like the prime numbers program that I wrote back on the HP-55, but much more elaborate and the 55 didn't have the space for subroutines. I remember reading somewhere that if you take the square root of the integer under test and don't find a number that divides evenly, then the integer under test is prime. Are there any other "tricks" that can streamline testing a nummber to see if it's prime?

Hal, I quickly scanned your program and I definitely will look at it to see if your programming can give me some insights into Walter's program. As always, my spare time is taken up with "Honey dos" as well as other projects.

Trent, thank you for passing on Peter Henrici's prime number program. I will study that one as well.

I just want to make clear that I'm not simply interested in translating Walter's program into RPL. After reading my original post, I realized that was what it sounded like. To do that it's simply a matter of converting individual commands into an RPL equivalent which says nothing about how his progam works.

In my work, I work with operators that want to know "how" to operate a piece of equipment, not the "why" it works that way. They can do their job but they have no flexibility when circumstances require then to adapt to changing situations. (I work in broadcast television.)

I've always been interested in "why" Walter's program works the way it does and the processes he uses to quickly identify prime numbers. I suspect that his algorithm has been optimized for quick execution but it's a real brain twister when you try to SST through it to understand how it works. Believe me, I have tried. I've got reams of paper tracking storage registers and the stack as the primary loop clicks through the numbers under test. It's funny, the program is 66 steps long and the 14 are inital setup. That means the main program is onlt 52 steps long! Amazing! It seems to me that Walter is one smart cookie. He's probably a mathematician who dabbles in programming.

Thank you for your time and the feedback you've all sent.

Gerry


#39

As an after-thought to Henrici's prime number program for the HP-25, and as a recreational exercise, I though it might be fun to see if I could adapt it to the HP-16C. The 16C does not have the FRAC function, has different conditional tests, and cannot do storage register arithmetic. I finally succeeded, (thanks to help from the Forum on the FRAC problem), but it took 81 steps! Also when you run the program you might as well go to the kitchen and get a cup of coffee because of the amount of time it takes to finish.

tm


#40

The 16-C is probably better suited a different algorithm: "The Sieve of Eratosthenes". Wikipedia has a nice article about the topic: http://en.wikipedia.org/wiki/Eratosthenes%27_Sieve.

The list can be represented as binary bits which are all reset at the start and set by the algorithm in successive passes through the sieve.

Marcus

Edited: 28 Oct 2006, 4:51 a.m.

#41

Quote:
Marcus, I didn't realize that the formatting of a posting is based upon HTML code. What other commands does the editor support?

Go to the main forum page and look for the following sentence:

Quote:
It's possible to use some advanced formatting techniques in this forum if you wish.

The link takes you to a help page detailing what you can do. Some useful commands have their own buttons on the bottom of the "post" window, just try them! Whenever I use these commands, I use the "Preview" button to look at my posting before I finally submit it.

Marcus

#42

I was looking on the net for info about Peter Henrici. He was a professor at ETH (Zurich) and sadly passed away in 1987. There is a prize in math given in his name.

Namir


#43

Namir,

You mentioned that Peter Henrici was a professor at "ETH" in Zurich. What does ETH stand for? Thanks.

tm


#44

Eidgenössische Technische Hochschule.

(The "Eidgenossenschaft" referred to here is the Swiss Confederation; the other two words are Technichal High-school, i.e. University of Technology.)

- Thomas


#45

Thanks Thomas!! I am learning to say it in German as best as possible, even though it is a "Hawaiian" tongue twister.

By the way, did you study there???

Einstein studied at ETH. Some of his teachers thought of his as lazy (oh well ... if Einstein cannot please everyone, how can regular folks like us do???).

My son is interested in doing graduate studies there in astrophysics (assuming they have a strong astrophysics program).

Namir

Edited: 31 Oct 2006, 11:07 a.m.


#46

By the way, did you study there???

No, I went to Delft and Utrecht, both in the Netherlands.

Niklaus Wirth (of Pascal and Modula fame) used to teach at ETH Zürich, BTW.

- Thomas


#47

Thomas thank you so much. I'm putting this information in the back leaf of his book.

tm

#48

Quote:
Niklaus Wirth (of Pascal and Modula fame) used to teach at ETH Zürich, BTW.

Sure! Wirth retired a few years ago. I wrote a few book on Turbo Pascal. So when I visit ETH it is to honor the birthplace of the Pascal programming language. I was also a big fan of Logitech Module-2. I used to go and visit their office when it was in Redwood City, California. That was in the mid 80s.

Namir


#49

Namir,

Your last message is very interesting. I'v lived in Redwood City for the past 49 years and I didn't know about the company. The best known hi-tech company in town years ago was Ampex.

tm


#50

Logitech eventually sold it's Modula-2 compiler and got out of the programming tools business. They focused on hardware. The company (at least then) was run by very clever and enterprising young Italians. They were very nice and had a good sense of business. I was told that Logitech was started in Morge, Switzerland, which is a small town west of Lausanne. I used to go there with my folks as a child and stay in a very nice motel, that was torn down in the mid 70s. I also heard it was started in another small town, Apples, located somewhere between Lausanne and Geneva.

#51

i need quickly generate of prime number in c or c++ language.
please send an e mail in my e mail account to write the sourse code

#52

My 48SX came with several interesting built-in programs when I bought it at the introduction campaign. One of them is 'SJTRI', which gives prime factors for quite large numbers almost instantly (10 digit number in 1 to 2 seconds!).
Curiously, I have never met another 48SX owner who had these programs included with the purchase.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime: complex numbers in CAS. Alberto Candel 1 794 12-06-2013, 02:36 PM
Last Post: parisse
  [HP Prime] Plots containing complex numbers bug? Chris Pem10 7 1,590 12-05-2013, 07:40 AM
Last Post: cyrille de Brébisson
  comparing numbers on the WP 34S Kiyoshi Akima 7 1,360 10-19-2013, 09:28 AM
Last Post: walter b
  HP Prime: Operations with Large Numbers Eddie W. Shore 0 451 10-19-2013, 12:24 AM
Last Post: Eddie W. Shore
  HHC 2013 room numbers David Hayden 2 710 09-20-2013, 05:34 PM
Last Post: sjthomas
  [HP-Prime xcas] operations with complex numbers + BUGs + Request CompSystems 9 1,607 09-08-2013, 10:40 PM
Last Post: CompSystems
  TED Talk: Adam Spencer: Why I fell in love with monster prime numbers Les Bell 3 845 09-05-2013, 12:54 PM
Last Post: Ken Shaw
  Irrationality in numbers....the book Matt Agajanian 4 881 08-30-2013, 04:14 PM
Last Post: Matt Agajanian
  Best HP calculator for crunching numbers rpn fan 51 5,652 08-05-2013, 03:17 PM
Last Post: rpn fan
  HP 50G List of Library numbers already in use? Michael Lopez 2 604 08-04-2013, 10:10 PM
Last Post: Michael Lopez

Forum Jump: