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.

You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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
about trigs in the HP12C.*

Did you see this, perchance ?

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

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

03-10-2003, 07:20 AM

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

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

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.

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, 08:39 PM

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

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

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

03-11-2003, 08:11 AM

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

03-11-2003, 09:03 AM

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

03-11-2003, 09:13 AM

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

03-11-2003, 09:25 AM

I'll find a way to have it.

Best regards.

Luiz C. Vieira - Brazil

03-11-2003, 12:55 PM

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.

03-11-2003, 01:02 PM

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

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

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

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

Powered By MyBB, © 2002-2021 MyBB Group