Challenge



#20

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.


#21

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


#22

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


#23

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


#24

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.


#25

Hi;

look at this article and you'll see Viktor Toth's solution. It is fiteen steps shorter.

Best regards.

Luiz C. Vieira - Brazil


#26

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.


#27

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

#28

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...


#29

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.


#30

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.

#31

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 :-)


#32

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


#33

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…


#34

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

#35

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.


#36

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.)

#37

The program tests only odd numbers, of course (see steps 40, 41 and 42)

#38

"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


#39

I'll find a way to have it.

Best regards.

Luiz C. Vieira - Brazil

#40

For your precision problem, does it help to use the fact that

(a*b) mod c = ((a mod c) * (b mod c)) mod c


#41

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.


#42

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

#43

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 432 08-01-2007, 08:36 AM
Last Post: Miguel Toro

Forum Jump: