Made a new program for the HP 11C

[vma]

Hi,

Today I received my HP 11C, which I bought second hand. It is in good condition and works fine!

Anyway, here is my frist program (I'm still trying to figure out the programming, but at least it works):

Test if number is a prime

Put a number in X (display) and run LBL A ([f] [A]).
Number is a prime if result is 1
Number is not a prime if result is 0

Code:


000 -
001 - 42,21,11 ' LBL A
002 -    44  1 ' STO 1
003 -        2 ' 2
004 -       10 ' /
005 -    44  2 ' STO 2
006 -        2 ' 2
007 -    44  3 ' STO 3
008 - 42,21, 1 ' LBL 1
009 -    45  1 ' RCL 1
010 -    45  3 ' RCL 3
011 -       10 ' /
012 -    42 44 ' FRAC
013 -        0 ' 0
014 -    42 40 ' X=Y
015 -    22  2 ' GTO 2
016 -    45  3 ' RCL 3
017 -        1 ' 1
018 -       18 ' +
019 -    44  3 ' STO 3
020 -    45  2 ' RCL 2
021 -    42 20 ' X>Y
022 -    22  1 ' GTO 1
023 -        1 ' 1
024 -       31 ' R/S
025 -    43 32 ' RTN
026 - 42,21, 2 ' LBL 2
027 -        0 ' 0
028 -       31 ' R/S
029 -    43 32 ' RTN

Would be nice to have this listed in the almost empty software section for the HP 11C (http://www.hpmuseum.org/software/software.htm), but I don't know who to contact.

Have fun!

Regards,
Vitor

PS: I forgot to mention that testing if a number is a prime this way is incredibly slow! The algorithm needs to be improved and the processor is really slow compared with new machines: my TI Nspire CAS will test 100123456789 for prime (it is) in less than one second, while the HP 11C takes several seconds with my program to test if 7 is a prime. This really shows how CPU power has increased over the last 30 years!

[kakima]

A couple of things you can do to significantly increase the speed of this program.

First, if a number is odd, you only need to test by odd numbers, so you can increment register 3 by two instead of one. Of course, this means that you have to treat 2 as a special case since it's even and prime.

Second, you only need to test up to the square root of the number, or at worst the next larger integer. Steps 003 and 004 can be replaced by SQRT ; 1 ; + . This won't make much difference for smaller numbers but is significant for larger numbers. For example, to test whether 1001 is prime, you only have to go to 32 instead of 500. Combined with the first optimization, this makes the program about thirty times faster. For 10001 it's about a hundred times faster.

Don't take the above as a criticism of your program. It's just that stuff like this becomes second nature by the time you've written your third prime number test. I think I wrote my first one forty years ago...

[vma]

Hi,

Thanks for the reply and no offense taken!

Actually, I do know how to optimize the prime testing algorithm (it's actually part of a VB .net course I lecture), but I got just too excited that it did work at all, as it is, i.e. without most optimizations!

I will try to make a v2 with the following improvements:

1) Search only to SQRT(number)+1
2) Search only odd numbers, creating a first condition for even numbers
3) Try to use the Index register

The beauty of programing a device like the HP 11C is that one needs to simplify the code to the max. This encourages to develop the algorithm/code BEFORE starting to actually program the device. Modern programming enviroments are by now so user friendly, that students have a hard time to accept that they need to create the algorithm (i.e. flowchart) before starting to do the program on the computer, which leads too often to failure.

Anyway: even the optimized algorithm as mentioned above, implemented in VB .net on an Intel Core i7 CPU will take LONGER to calculate than the TI Nspire CAS! There are much better (but more complicated) algorithms around, but still I ask myself how it manages to get the result that fast. I am led to believe that the Nspire just uses a table with the first so many primes...

BTW: I am NOT a math teacher - I work with CAD/CAM systems.

Regards,
Vitor

[vma]

Here is v2 with the following improvements:

- searches up to SQRT(number)+1
- increments +2 (only odd numbers)

Code:


LBL A ' Start of the program - call in RUN mode with [f][A]
STO 1 ' Store value in X to register 1 - This is the number we want to test if prime
SQRT  ' Calculate the square root of X
1     ' 
+     ' Add 1
STO 2 ' Store value in X to register 1 - This is the maximum divisor we will use
3     ' 3 is the start devisor to be used
STO 3 ' It will be stored in register 3
RCL 1 ' Recall the number to test if prime
2     '
/     ' Devide by 2
FRAC  ' Get only the fraction
0     '
X=Y   ' Test if it is 0
GTO 2 ' If so, the number is NOT a prime
LBL 1 ' Start of the cycle, that will devide the number to test if prime from 3 to SQRT(number)
RCL 1 ' Get number to test if prime
RCL 3 ' Get current devisor
/     ' Devide
FRAC  ' Get only the fraction
0     '
X=Y   ' Test if it is 0
GTO 2 ' If so, the number is NOT a prime
RCL 3 ' Get current devisor
2     '
+     ' Add 2 (next odd number)
STO 3 ' Store in register 3
RCL 2 ' Call maximum devisor from register 2
X>Y   ' If it is still greater than current devisor
GTO 1 ' Go to Label 1 and make next devision test
1     ' If not, we did all divisions and never got an integer as a result, thus the number is a prime
R/S   ' Stop program
RTN   ' Return: I'm not sure if this step is needed
LBL 2 ' Label 2: this is where we tell the user, that the number is NOT a prime
0     ' Put a 0 on X
R/S   ' Stop program
RTN   ' Return: I'm not sure if this step is needed

I still have to read and figure out, how to use the Index register.

Regards,
Vitor

[Dieter]

(01-08-2014 10:03 AM)vma Wrote:  Here is v2 with the following improvements:

You may also use storage arithmetics (like 1 STO+ 3) and the dedicated tests that compare X with zero (e.g. X=0? RTN). The max. divisor is sqrt(n), and since the result is exact due to BCD arithmetics, there is no need to add 1.

In your previous post you wrote:

Quote:...even the optimized algorithm as mentioned above, implemented in VB .net on an Intel Core i7 CPU will take LONGER to calculate than the TI Nspire CAS! There are much better (but more complicated) algorithms around, but still I ask myself how it manages to get the result that fast. I am led to believe that the Nspire just uses a table with the first so many primes...

You probably heard of the WP34s project before: a community effort with a homebrew software for a scientific calculator, based on HP30b hardware. The WP34s PRIME? function runs the test you mentioned in less than a second either. For further information take a look at the C code at sourceforge.net (line 1426 ff). For more details regarding the Miller-Rabin primality test, cf. the respective Wikipedia article. So processor speed is one thing, but the really essential part is a carefully chosen algorithm. ;-)

[vma]

Dieter,

Thank you for your reply!

I know about the HP20B/30B open source firmware, unfortunatly I never tried buying one to mod it myself, due to the difficulty in assembling the cable connector. I don't know if there are other alternatives, meanwhile. It is a great project and there is still some hope left, that one day I get a WP34S!

Regarding the storage arithmetics, I honestly did not have time so far, to read the relevant pages of the manual. I know it can be done, but I am/was not sure how to do it exactly. I left it for later improvements.

I do appreciate A LOT that you have linked me to the source code part, where primes are tested! This is simply GREAT! I knew about more advanced algorithms like the Miller-Rabin, but honestly, as a non-mathematician (just a simple engineer), it is a bit dry to read and understand.

But looking at the C code is just great! Again, thanks a lot for this.

Meanwhile I started to hack a simple interpreter for my HP-11C source code, so that it is easier to program for the HP-11C. It does run the prime code v2 so far, but lots of other functions of the calculator are missing. The goal is not to do a HP-11C simulator (there is the perfect nonpareil emulator for that), but to do a simple interpreter, that allows easier and quicker development of the algorithm/code. When (if) it is finished, I can share it, in case someone is interested. Don't expect much, though...

Regards,
vma

PS: I have the feeling there are only math geniuses on this forum, which makes me nervous...

[walter b]

(01-08-2014 09:36 PM)vma Wrote:  I know about the HP20B/30B open source firmware, unfortunatly I never tried buying one to mod it myself, due to the difficulty in assembling the cable connector. I don't know if there are other alternatives, meanwhile. It is a great project and there is still some hope left, that one day I get a WP34S!

Please read p. 2 of the WP 34S Owner's Manual (pdf on sourceforge) and you'll know.

d:-)

[Dave Britten]

This program for the 67 has a rather elegant prime number search algorithm starting at label D. I've adapted it for a few other machines (including the 15C, I think). You might try getting it going on the 11C for kicks. (The 11C does GSB, right?)

http://www.hpmuseum.org/software/67pacs/67factor.htm

[Thomas Klemm]

(01-08-2014 09:36 PM)vma Wrote:  Regarding the storage arithmetics, I honestly did not have time so far, to read the relevant pages of the manual. I know it can be done, but I am/was not sure how to do it exactly. I left it for later improvements.

This is basically what you can do on a 4-banger with M+. But you can use all arithmetic operations and any register. The equivalent of STO+ 0 in C is: r0 += x

Quote:I do appreciate A LOT that you have linked me to the source code part, where primes are tested! This is simply GREAT! I knew about more advanced algorithms like the Miller-Rabin, but honestly, as a non-mathematician (just a simple engineer), it is a bit dry to read and understand.

Writing a program often helps me to unterstand a complicated algorithm. The HP-11C is one of my favorite models though it doesn't provide fancy stuff. But it can still be used to solve challenging problems or implement Bairstow's Method.

Quote:Meanwhile I started to hack a simple interpreter for my HP-11C source code, so that it is easier to program for the HP-11C. It does run the prime code v2 so far, but lots of other functions of the calculator are missing. The goal is not to do a HP-11C simulator (there is the perfect nonpareil emulator for that), but to do a simple interpreter, that allows easier and quicker development of the algorithm/code. When (if) it is finished, I can share it, in case someone is interested. Don't expect much, though...

You might be interested in Effective Computer-aided Calculator Programming.
In a nutshell: it allows to write programs for the voyagers in a text editor and load them in the Nonpareil emulator.

Cheers
Thomas