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.
The following warnings occurred: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Warning [2] Undefined array key 29376 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
|
Challenge
|
|
« Next Oldest | Next Newest »
|
▼
03-10-2003, 04:15 AM
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.
▼
03-10-2003, 06:14 AM
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 ▼
03-10-2003, 06:54 AM
Luiz wrote:
I remember those ones Ex-PPC member posted Did you see this, perchance ? HP-12C Tried & Tricky Trigonometrics
▼
03-10-2003, 07:03 AM
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 ▼
03-10-2003, 07:10 AM
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 ▼
03-10-2003, 08:05 AM
Hi; look at this article and you'll see Viktor Toth's solution. It is fiteen steps shorter. Best regards. Luiz C. Vieira - Brazil ▼
03-10-2003, 08:14 AM
Thanks, Luiz.
I'll have a detailed look at it and will try both approaches ▼
03-10-2003, 08:26 AM
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
03-10-2003, 07:20 AM
Hi Luiz, ▼
03-11-2003, 09:03 AM
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 20-step solution,
03-10-2003, 08:39 PM
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 :-) ▼
03-10-2003, 09:10 PM
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 ▼
03-11-2003, 04:00 AM
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… ▼
03-11-2003, 06:36 AM
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
03-11-2003, 07:04 AM
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. ▼
03-11-2003, 08:08 AM
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"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.) ▼
03-11-2003, 08:11 AM
The program tests only odd numbers, of course (see steps 40, 41 and 42)
03-11-2003, 09:13 AM
"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
03-11-2003, 01:02 PM
For your precision problem, does it help to use the fact that
▼
03-11-2003, 04:57 PM
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. ▼
03-13-2003, 12:52 AM
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
03-11-2003, 11:13 PM
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. |
Possibly Related Threads… | |||||
Thread | Author | Replies | Views | Last Post | |
RE: 35s sorting routine challenge - Gene's Challenge | Miguel Toro | 4 | 1,537 |
08-01-2007, 08:36 AM Last Post: Miguel Toro |