Challenge  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: Challenge (/thread29376.html) 
Challenge  mapet  03102003 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)  Vieira, Luiz C. (Brazil)  03102003 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 ExPPC 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 ?  john smith  03102003 Luiz wrote:
I remember those ones ExPPC member posted Did you see this, perchance ? HP12C Tried & Tricky Trigonometrics
Re: Did you see this ?  Vieira, Luiz C. (Brazil)  03102003 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 ?  john smith  03102003 May I suggest you print it ?
I've found it's easier to read and much more enjoyable
Besides, once printed you can punch some holes in order No restrictions at all  mapet  03102003 Hi Luiz, Did you also see this? (my turn...)  Vieira, Luiz C. (Brazil)  03102003 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...)  john smith  03102003 Thanks, Luiz.
I'll have a detailed look at it and will try both approaches A remark.  Vieira, Luiz C. (Brazil)  03102003 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
Re: Challenge  hugh  03102003
the old a*b(mod c) problem in disguise again!
lblA fix0 sto1 2 x>y? gto3 x=y? gto4 0 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?
and it should work in theory, but after 20 of waiting minutes who cares. just not fast enough these old machines :)
Re: Challenge  Vieira, Luiz C. (Brazil)  03102003 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  mapet  03112003 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  Vieira, Luiz C. (Brazil)  03112003 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  hugh  03112003 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)  Vieira, Luiz C. (Brazil)  03112003 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 mathgrade 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 eliterature at the www about this pseudoprimes 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 trialdivision routine for the HP41 is listed below. 01 LBL "P"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...  Vieira, Luiz C. (Brazil)  03112003 The program tests only odd numbers, of course (see steps 40, 41 and 42)
Re: No restrictions at all  ExPPC member  03112003 No restrictions at all. The shortest listing wins.
Under that condition, "shortest listing", completely disregarding 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 20step solution, Re: Challenge (also my HP41 PRGM for primes)  ExPPC member  03112003
"I remember reading briefly about obtaining new primes by adding
You might consider getting the book "Primes and Programming" by Peter J. Giblin, as it is a perfect mix of theory and Thank you!  Vieira, Luiz C. (Brazil)  03112003 I'll find a way to have it. Best regards.
Luiz C. Vieira  Brazil
Re: No restrictions at all  Patrick  03112003 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  Patrick  03112003 For your precision problem, does it help to use the fact that
Re: Challenge  hugh  03112003 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: (Prime #) Challenge  Karl Schneider  03112003 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.
Re: Challenge  Vieira, Luiz C. (Brazil)  03132003 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 ExPPC 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
