HP Forum Archive 11

[ Return to Index | Top of Index ]

Challenge Message #1 Posted by mapet on 10 Mar 2003, 4:15 a.m. Write a program that checks if the number is a prime. As input it takes last entered number and as output it shows 0 (not prime) or 1 (prime). Platform: 12C, 20S.

Re: Challenge (not yet an answer) Message #2 Posted by Vieira, Luiz C. (Brazil) on 10 Mar 2003, 6:14 a.m., in response to message #1 by mapet Hi, mapet; any particular restriction? I'm asking about this because sometimes the restrictions will dictate teasing conditions, just that. I know no simpler way that the interactive one to generate prime numbers. Is there another? This is just to check if there is a newer algorithm running around that I was not told about. I'd like to know about it, if any. If the classical is the only one, let's go for it. Fewer steps? Good chalenge. I like the ones that may be usefull as a tool or as a general purpose routine. I remember those ones Ex-PPC member posted about trigs in the HP12C. Or another about replicating numbers in the stack (who proposed that one? I don't remember, sorry...). As I have a possibility I'm posting. Best regards. Luiz C. Vieira - Brazil

Did you see this ? Message #3 Posted by John Smith on 10 Mar 2003, 6:54 a.m., in response to message #2 by Vieira, Luiz C. (Brazil) Luiz wrote: I remember those ones Ex-PPC member posted about trigs in the HP12C. Did you see this, perchance ? HP-12C Tried & Tricky Trigonometrics

Re: Did you see this ? Message #4 Posted by Vieira, Luiz C. (Brazil) on 10 Mar 2003, 7:03 a.m., in response to message #3 by John Smith Hi; I downloaded the file right away (about 40K, very small!). Thank you. I was not aware about it. I'll read it and add comments, if so. Best regards. Luiz C. Vieira - Brazil

Re: Did you see this ? Message #5 Posted by John Smith on 10 Mar 2003, 7:10 a.m., in response to message #4 by Vieira, Luiz C. (Brazil) May I suggest you print it ? I've found it's easier to read and much more enjoyable (and easier to try it in your own HP-12C) if printed than reading from the screen. Besides, once printed you can punch some holes in order to file it up with your collection of HP listings and articles, that's exactly what I did.

Did you also see this? (my turn...) Message #6 Posted by Vieira, Luiz C. (Brazil) on 10 Mar 2003, 8:05 a.m., in response to message #5 by John Smith Hi; look at this article and you'll see Viktor Toth's solution. It is fiteen steps shorter. Best regards. Luiz C. Vieira - Brazil

Re: Did you also see this? (my turn...) Message #7 Posted by John Smith on 10 Mar 2003, 8:14 a.m., in response to message #6 by Vieira, Luiz C. (Brazil) Thanks, Luiz. I'll have a detailed look at it and will try both approaches on an actual HP-12C, to see how they compare. I assume the 15 extra steps are probably used to provided faster execution time near extremes, extended accuracy/range, or both, but I'll have to actually test them to find out.

A remark. Message #8 Posted by Vieira, Luiz C. (Brazil) on 10 Mar 2003, 8:26 a.m., in response to message #7 by John Smith Hi; mapet, forgive me for use your initial thread with another (instead related) matter; O.k.? John; Viktor added four shortcomings about a few restrictions; maybe the extra steps also have something with this, I did not read both articles in a comparision manner. Hey, good reading postings and threads like this. Thank you for the concise and usefull words. Keep posting! Luiz C. Vieira - Brazil

No restrictions at all Message #9 Posted by mapet on 10 Mar 2003, 7:20 a.m., in response to message #2 by Vieira, Luiz C. (Brazil) Hi Luiz, No restrictions at all. The shortest listing wins. Second challenge could be for the fastest solution for 12C, as the calc is pretty slow...

Re: No restrictions at all Message #10 Posted by Ex-PPC member on 11 Mar 2003, 9:03 a.m., in response to message #9 by mapet No restrictions at all. The shortest listing wins. Under that condition, "shortest listing", completely disregarding speed, there's a fairly trivial 17-step solution in the HP-12C, which will output 0 if the number is composite, and 1 if it is prime, for any number N>1. But it's extremely slow ... Second challenge could be for the fastest solution for 12C, as the calc is pretty slow... If size is not a problem, there's an equally trivial 20-step solution, much faster than the 17-step one. The fastest solution for large N will require probabilistic primality testing and, due to the lack of subroutine capability on the HP-12C, it may or may not fit in 99 steps.

Re: No restrictions at all Message #11 Posted by Patrick on 11 Mar 2003, 12:55 p.m., in response to message #10 by Ex-PPC member Probabilistic techniques are used to generate "Industrial Strength" primes, not true primes. There are sometimes used, for example, in cryptographic systems where the confidentiality rating of the data involved is modest.

Re: Challenge Message #12 Posted by hugh on 10 Mar 2003, 8:39 p.m., in response to message #1 by mapet the old a*b(mod c) problem in disguise again! here's what i have so far, attempted rabin miller strong pseudoprime test. lblA fix0 sto1 2 x>y? gto3 x=y? gto4 0 sto6 sto8 rcl1 1 - sto7 lbl5 rcl7 rcl7 2 / int sto9 2 * x<>y? gto6 1 sto+6 rcl9 sto7 gto5 lbl6 rcl6 x=0? gto3 1 sto-6 lbl7 2 sto+8 rcl8 7 x=y? gto4 3 - x=y? dse8 rcl8 sto2 rcl1 x=y? gto4 1 sto3 rcl7 sto9 lbl8 rcl9 rcl9 2 / int sto9 2 * x<>y? gsbB rcl9 x=0? gto.0 rcl3 sto0 rcl2 sto3 gsbB sto2 rcl0 sto3 gto8 lbl.0 rcl3 1 x=y? gto7 chs rcl1 + x=y? gto7 rcl6 sto9 lbl.1 rcl9 x=0? gto3 rcl3 sto2 gsbB rcl1 1 - x=y? gto7 1 sto-9 gto.1 lbl4 1 rtn lbl3 0 rtn lblB rcl2 rcl3 * rcl1 / frac rcl1 * rnd sto3 rtn unfortunately, its only good for around 5 digits. the problem lies in subroutine B which computes 2*3 mod 1 -> 3 and therefore breaks if 2*3 is too big integer. substitute this, lblB rcl2 sto5 0 sto4 lbl1 rcl3 rcl3 2 / int sto3 2 * x==y? gto.3 rcl5 sto+4 rcl4 rcl1 x<y? sto-4 lbl.3 rcl3 x==0? gto2 2 sto*5 rcl5 rcl1 x<y? sto-5 gto1 lbl2 rcl4 sto3 rtn and it should work in theory, but after 20 of waiting minutes who cares. just not fast enough these old machines :-)

Re: Challenge Message #13 Posted by Vieira, Luiz C. (Brazil) on 10 Mar 2003, 9:10 p.m., in response to message #12 by hugh Hi, Hugh; I see that your listing is related to a wise, very well written program for the HP15C, as you have a GTO .3 and a GTO .1, and the only Voyager that has [GTO][.]n and [LBL][.]n is the HP15C, right? Or is it for another HP? It seems mapet wants to know if there is a way to fit a program like this in the HP12C, that does not support subroutine calls, or an HP20S, that is algebraic. I'm working on it and it's something "hard" to achieve... Can your program be ported to an HP12C? Best regards. Luiz C. Vieira - Brazil

Re: Challenge Message #14 Posted by mapet on 11 Mar 2003, 4:00 a.m., in response to message #13 by Vieira, Luiz C. (Brazil) HP 20S has subroutine calls (but it is algebraic ) so the program can be ported to it. I am working on my solution. On HP 20S it seems to be much easier…

Re: Challenge Message #15 Posted by Vieira, Luiz C. (Brazil) on 11 Mar 2003, 6:36 a.m., in response to message #14 by mapet Hi; I already have a somewhat short program for the HP41 to compute primes after # 3 (1 and 2 are assumed found) but it has a major handicap to make it "fast": it stores all prime # already found in available registers, so it will compute new primes based on MOD with existing ones. I ran it once in an HP41CX (in the 80's) till it found prime # 2063, but even with time spent saved in the stopwatch, I did not took note (dam...). The program is 61 bytes longs, 39 steps (END not counted) without time measurement and 67 bytes long, 42 steps (END not counted) with time functions for measuring time spent and, in both cases, uses only register R00 as register index. Would you like it to be listed here? Unfortunetely I cannot port it to the HP12C because of indexed register access and number of registers used. I will change it to save only last prime number, but it will surely make it a lot slow. Cheers and congrats. This is one very good chalenge amongst others. Luiz C. Vieira - Brazil

Re: Challenge Message #16 Posted by hugh on 11 Mar 2003, 7:04 a.m., in response to message #13 by Vieira, Luiz C. (Brazil) you are indeed correct. i decided to develop a program first on the 15c. its possible to eliminate the .x labels depending on what version of subroutine `B' is used. although, the logic is correct, i am not very happy with this program and i might still find an improvement. i wanted to attempt something stronger that a trial division derived algorithm. so this is an attempt to verify that the the given number is a strong pseudoprime to bases 2, 3 & 5. this takes the valid range up to 161304000 if i eliminate the case 25326001. the problem is that i need to compute a*b mod c (subroutine B) without loss of precision. you can see that a straightforward approach will only allow a and b to be of 5 digits. the other subroutine B gets around this at the expense of time, which these old machines havent got. i might have a go at a 20s port. although i dont think it will fit. if some of the early tests are removed <2 ==2 and == 2, 3, & 5 some space is saved at the expense of incompleteness. the bottom line is that it might not be feasible to fit and run this approach, meaning sadly that trial division is the only way, albeit lame.

Re: Challenge (also my HP41 PRGM for primes) Message #17 Posted by Vieira, Luiz C. (Brazil) on 11 Mar 2003, 8:08 a.m., in response to message #16 by hugh Hi; I do not know the process of detecting pseudoprimes, instead I heard about it when I was at the university as a solution for the prime chain and math-grade students used to play many algorithms and methods for this subject. Even being an engineer guy, I always liked teasing math and algebraic problems (at least before buying an HP41C, when I developed a pasion for program development in portable devices), but I never found the time for studying them. Is it easy to find e-literature at the www about this pseudo-primes detection? I remember reading briefly about obtaining new primes by adding groups of 2, 3 and 5, but I never got any paper that explained this subject in deep. Thanks for the valuable explanation, Hugh. Best regards. Luiz C. Vieira - Brazil (in time: my classical trial-division routine for the HP41 is listed below. 01 LBL "P" 02 RUNSW 03 SF 25 04 SF 10 05 1.001 06 STO 00 07 3 08 STO 01 09 LBL 08 10 FC?C 10 11 GTO 07 12 ENTER^ 13 ENTER^ 14 ENTER^ 15 RCL IND 00 16 MOD 17 X=0? 18 SF 10 19 X<>Y 20 ISG 00 21 GTO 08 22 STO IND 00 23 FC? 25 24 STOPSW 25 FC? 25 26 OFF 27 RCL 00 28 INT 29 1 E3 30 / 31 GTO 06 32 LBL 07 33 RCL 00 34 FRC 35 LBL 06 36 1 37 + 38 STO 00 39 RDN 40 2 41 + 42 GTO 08 I'm 100% sure I improved it so I used only stack registers, but I cannot find the d*m listing. This is the CX version and you need to clear the stopwatch before starting it. After the last register is used, the program stops the stopwatch and switches calculator to OFF. If you wnat to use it in an HP41C or CV, simply remove lines 03 RUNSW, 23 FC?25 and 24 STOPSW.)

Oh, yes, one more thing... Message #18 Posted by Vieira, Luiz C. (Brazil) on 11 Mar 2003, 8:11 a.m., in response to message #17 by Vieira, Luiz C. (Brazil) The program tests only odd numbers, of course (see steps 40, 41 and 42)

Re: Challenge (also my HP41 PRGM for primes) Message #19 Posted by Ex-PPC member on 11 Mar 2003, 9:13 a.m., in response to message #17 by Vieira, Luiz C. (Brazil) "I remember reading briefly about obtaining new primes by adding groups of 2, 3 and 5, but I never got any paper that explained this subject in deep." You might consider getting the book "Primes and Programming" by Peter J. Giblin, as it is a perfect mix of theory and explicit computer programs to illustrate it, written enthusiastically and with lots of numerical examples, quizs, teasers, challenges, you get the point ... All programs are written in Pascal, but the listings are well commented and extremely clear, so it's very easy to adapt them to most HP calculators, from the 41C or so onwards. Primes and Programming

Thank you! Message #20 Posted by Vieira, Luiz C. (Brazil) on 11 Mar 2003, 9:25 a.m., in response to message #19 by Ex-PPC member I'll find a way to have it. Best regards. Luiz C. Vieira - Brazil

Re: Challenge Message #21 Posted by Patrick on 11 Mar 2003, 1:02 p.m., in response to message #16 by hugh For your precision problem, does it help to use the fact that (a*b) mod c = ((a mod c) * (b mod c)) mod c

Re: Challenge Message #22 Posted by hugh on 11 Mar 2003, 4:57 p.m., in response to message #21 by Patrick unfortunately not, because 0 <= a, b < c already. this problem i have encountered many times. its how to perform a*b (mod c) when all of a, b and c can be up to your machine precision. eg 10 digits on a calculator or 32 bits commonly on a pc. the only attack i am aware of is to code the multiply yourself affecting the modulo as it goes and thus prevent overflow. there was a discussion of this some time ago on this forum. it was pointed out that an internal assembler routine could be used to prevent the requirement for double precision when implementing the mod function. this is correct. you do your multiply one binary digit at a time and subtract the mod if larger. if you're interested, here is some c code that does what i am talking about, http://www.voidware.com/primetest.htm this was my starting point, although i cut a lot of stuff out.

Re: Challenge Message #23 Posted by Vieira, Luiz C. (Brazil) on 13 Mar 2003, 12:52 a.m., in response to message #22 by hugh Hi, Hugh; I downloaded the page you mention and I'm "debugging" it (in fact, depicting line by line...) to get to the prime detection and the strong prime number definition. Thank you. I was looking for something like this. That's the point where you think: "Thanks God I took some time to learn C..." Shrink it to fit in an HP12C is another story... I'm curious about Ex-PPC Member both solutions. About the modulo: the discussion is included in this thread where Kate asked for a modulo function in fewer steps. This was considered the best yet the shortest answer because it gives correct results in a wide range of operators. Best regards. Luiz C. Vieira - Brazil

Re: (Prime #) Challenge Message #24 Posted by Karl Schneider on 11 Mar 2003, 11:13 p.m., in response to message #1 by mapet The 49G can be used to check the answers your program gives, using its "PREVPRIME" or "NEXTPRIME" functions. Matlab computer software has an "isprime" command.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall