Storing and retrieving the first 1000 primes with an HP41?

Storing and retrieving the first 1000 primes with an HP41?

Postby floppy_stuttgart » Fri Jul 16, 2021 3:36 pm

Hello,
is there any known method for storing (compressed) integer data in an HP41?
Idea: making a file with the first 1000 primes and retrieving the Nb X of them via a function x ENTER XEQ "PRIMNB" and it would give back the Xth prime.
1 -> 3
2 -> 5
3 -> 7
..
In Python, thats defined: find the file in the internet, upload the file in an array, postion X of the array is the Xth prime (no need to "find" the prime with any scanning of the numbers; just retrieving the existing prime from the file/array).
Any advice is welcome (I have already some basic ideas but they are all register consuming and it never comes to a large number of primes).
floppy_stuttgart
.........
.........
 
Posts: 112
Joined: Mon Mar 29, 2021 2:36 pm

Re: Storing and retrieving the first 1000 primes with an HP4

Postby mike-stgt » Sat Jul 17, 2021 2:20 am

floppy_stuttgart wrote:is there any known method for storing (compressed) integer data in an HP41?
Yes, there is. See program PR in PPC ROM.
Idea: making a file with the first 1000 primes and retrieving the Nb X of them via a function x ENTER XEQ "PRIMNB" and it would give back the Xth prime.
1 -> 3
2 -> 5
3 -> 7
..
That's wrong. The first prime is 2. 3 is already the 2nd.
In Python, [...]
Any advice is welcome (I have already some basic ideas but they are all register consuming and it never comes to a large number of primes).
Your "basic ideas" are fine for BASIC -- 'Beginner’s All-purpose..' and so on, you know it.
I assume you'd like to store prime numbers in a structure (file, field, array, list, stem, ...) with line nubers or index to be the prime count. 7919 is the 1000th prime number. Even if you use the higher compaction rate of a. m. PR routne for smaller numbers (up to 100 five numbers in one register, above 1413 only two) it will take a fair amount of registers to hold the first 1000 prime numbers.
I suggest just one single bit/flag per possible prime number candidate. There are eight candidates within 30 numbers, 8 bits = one byte = one alpha digit, with ASTO six chars are saved in one register. So 44 registers are sufficient to hold the first 1000 prime numbers, 44 registers x 6 bytes per register x 30 numbers per byte = 7920. Maybe an ASCII file in 'XF/XMem could do better.
Advantage: more bang per byte, with a simple index calculation you may find out if for example 7333 is prime or not.
Drawback: to get the n-th prime number you need the Hamming weight of the data -- computed with a Nut-CPU.
Note: typically it is faster to compute the first 1000 prime numbers than reading a file from disk that contains them. To attack prime numbers with an HP41 is an attempt similar to blow up a cow at back side to make its cornets stand straight :mrgreen:
mike-stgt
.........
.........
 
Posts: 179
Joined: Tue Dec 24, 2019 12:12 pm

Re: Storing and retrieving the first 1000 primes with an HP4

Postby floppy_stuttgart » Sat Jul 17, 2021 11:51 am

mike-stgt wrote:The first prime is 2. 3 is already the 2nd.

Looks like you use another definition. Not a question of being right or wrong. Just a question of definition.
My personal view/definition (perhaps not mainstream; but I dont care):
- 1 is an increment
- 2 is a doubling function (philophically correct for later use in elliptic consideration: X + Y = "2" * A)
- primes has a minimum of "double increment" as distance between them
You have your view. I have my view. They differ. Thats fine.

PR in PPC ROM? I will have a look.

"Hamming weight of the data". Dont know this. I have to search what this mean.
floppy_stuttgart
.........
.........
 
Posts: 112
Joined: Mon Mar 29, 2021 2:36 pm

Re: Storing and retrieving the first 1000 primes with an HP4

Postby Garth » Sat Jul 17, 2021 6:20 pm

I've never paid much attention to prime numbers; but as I look at the Wikipedia article about them now, I read:

    A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.
    <snip>
    The first 25 prime numbers (all the prime numbers less than 100) are:

      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Garth
Moderator
Moderator
 
Posts: 290
Joined: Tue Jan 20, 2009 1:31 am

Re: Storing and retrieving the first 1000 primes with an HP4

Postby mike-stgt » Sun Jul 18, 2021 1:02 am

I've done it the dull way:
Code: Select all
 01▶LBL "FKP"
ABS  INT  X=0?  LN  1  -
"FKP"  SEEKPTA  GETREC
ATOX  ATOX  X≠0?  X<>Y
256  *  +  END
                  CAT 4
FKP     A421
       177,00000    ***

I assume it's quite obvious how I packed the data. To build the file I used ILDoslink.
Edit: inserted ABS and INT to avoid the pointer point to where it shouldn't.
Edit once more: inserted X=0? LN after INT, there is no 0th prime. (Presumed F25 clear at entry.)
Last edited by mike-stgt on Wed Jul 21, 2021 4:52 pm, edited 2 times in total.
mike-stgt
.........
.........
 
Posts: 179
Joined: Tue Dec 24, 2019 12:12 pm

Re: Storing and retrieving the first 1000 primes with an HP4

Postby mike-stgt » Sun Jul 18, 2021 5:49 pm

floppy_stuttgart wrote:Looks like you use another definition. Not a question of being right or wrong. Just a question of definition.
My personal view/definition (perhaps not mainstream; but I dont care):
[...]
Also you might not mind, natural numbers (positive integers) are either prime or composite. Composite means, they can be formed by multiplying two smaller positive integers. Between 1 and 2 are no smaller integers than 2 and 1 is regarding the multiplication the neutral element. Hence number 2 is prime.
"Hamming weight of the data". Dont know this. I have to search what this mean.
Modern CPUs offer a popcount or sideways sum for that, which is pretty fast. On a HP41 it is a drudgery.
mike-stgt
.........
.........
 
Posts: 179
Joined: Tue Dec 24, 2019 12:12 pm

Re: Storing and retrieving the first 1000 primes with an HP4

Postby mike-stgt » Mon Jul 19, 2021 2:00 am

mike-stgt wrote:I suggest just one single bit/flag per possible prime number candidate.
To show how it could look like I prepared a file to be saved as ASCII in XF/XMem. Following takes 42 registers what is 1/10th compared to a file of 1000 "packed" primes.
Code: Select all
76 FF F7 EE FC DB B7 79 3F 57 E4 F1 9E AE CB 6E F2 CE 61 97 97 B9 77
5F 35 4A AD CC 93 7A 3C F0 CA D4 D5 8F 6B 68 F6 A8 65 55 37 8A 1F F3
53 80 55 0A 3E E9 7E 45 2E CC DF 90 B8 3A 65 A8 B9 45 11 FA 54 63 06
53 BD 9A 26 7A 63 E5 08 35 1D 1D B3 07 D1 EE 54 D2 B0 21 4F 82 62 C4
52 9D BE EB 4C 93 E2 35 C2 96 92 37 03 4C C9 8E 0B 10 39 C6 C8 79 03
54 AF 33 63 14 22 F8 49 9F 99 64 B5 A2 71 CA A8 5A 34 64 E4 C8 DF 30
4C 82 77 83 86 69 1E 38 81 5B 67 66 80 9A A4 52 61 D4 64 BC 19 85 A1
4D 1F A6 44 6C 48 3F 31 01 52 2A 75 9C AF 62 48 D3 A8 14 CA 88 F0 47
4F 16 24 C0 56 B9 E8 5C 73 C0 AD 40 23 FA 2D 50 E8 0D 55 8F DB 14 32
49 20 50 C2 B4 AB 45 65 24 1D C8 97 93 56 A7 AA 81 83 0D 40 48 E7 C2
4B 88 87 2B 6A 30 63 64 3D 17 22 D0 1B D5 C6 8C 8A 06 58 48 94 EA B4
48 04 99 63 08 21 84 58 DA 96 DB 37 31 0E 0D CC B1 38 0C 16 44 BC 52

What's this for? This is the hex dump of the first 1000 primes (three less, 2, 3, and 5 are not included, it starts with 7), every prime coded with a single bit only (using a 2*3*5-wheel there are 8 prime candidates in 30 numbers, so I keep only the flags/bits of the candidates). Each line is saved as a record, first byte is the Hamming weight of the rest of the record (that is how many bits are set in the following 22 bytes).
Single step explanation:
leftmost byte of first line is 76x = 118d so there are 118 primes in the range 7 .. (6 + 22 x 30). Check: 7 is the 4th prime, 661 the 121th. The 122th prime is 673 and its flag part of next record.
2nd byte of first record is FFx what means, every candidate from 7 to 36 is prime. 3rd byte is F7 so in the range 37..66 one candidate is not prime, 49 is 7^2. Next byte is EE so in this third "30-numbers-swath" two candidates are not prime, obviously:
Code: Select all
 7   11   13   17   19   23   29   31
37   41   43   47        53   59   61
67   71   73        79   83   89

Here a routine to use this data set:
Code: Select all
 01▶LBL "FKPX"
ABS  INT  X=0?  LN  3 
X<Y?  GTO 01  DSE X 
X<Y?  X>Y?  DSE X 
GTO 11 

 14▶LBL 01
"FKPB"  0  STO 00 
SEEKPTA  + 

 20▶LBL 08
GETREC  ATOX  +  X<Y? 
GTO 08  LASTX  - 

 28▶LBL 09
ATOX  X<>F  7  R^  R^ 
SF 19 

 35▶LBL 10
FS?C IND Z  ISG X  "" 
X=Y?  GTO 01  DSE Z 
GTO 10  FS?C 19  GTO 10
R^  X<>F  RDN  ISG 00 
""  GTO 09 

 51▶LBL 01
R^  X<>F  R^  7 
GTO IND Y 

 57▶LBL 00
2  + 

 60▶LBL 01
6  + 

 63▶LBL 02
4  + 

 66▶LBL 03
2  + 

 69▶LBL 04
4  + 

 72▶LBL 05
2  + 

 75▶LBL 06
4  + 

 78▶LBL 07
RCLPT  INT  22  * 
RCL 00  +  30  * 

 87▶LBL 11
+  END
The hex dump of corresponding RAW file:
Code: Select all
C6 00 F5 00 46 4B 50 58 61 68 67 50 13 44 B2 00
97 73 44 45 97 73 BC 00 02 F4 46 4B 50 42 10 30
A6 6B 40 09 A6 54 A6 47 40 44 B9 00 76 41 0A A6
47 A6 6E 17 74 74 A8 13 0B AA F1 96 73 F0 78 B2
00 97 71 BB 00 AA 13 BB 00 74 A6 6E 75 96 00 F0
BA 00 02 74 A6 6E 74 17 AE 72 01 12 40 02 16 40
03 14 40 04 12 40 05 14 40 06 12 40 07 14 40 08
A6 61 68 12 12 42 20 40 13 10 42 0C 40 C0 00 0F

Addendum: So this bitwise index file taking just 42 records in XMem, which offers 600 at max, could lead to the idea to use the complete XMem for such an index file. Alas, there are gaps in the row of primes which result in null bytes, hex 00, the first shows between 15683 and 15727. Null bytes are complicating the use of the alpha register as buffer (see HP82183A X-IO Own Mnl, Section 3), not impossible but "big PITA". The reward would be an index file up to 115499, that are 10913 prime numbers. Something for the experts (with Hepax, RamBox, ...), not me.
mike-stgt
.........
.........
 
Posts: 179
Joined: Tue Dec 24, 2019 12:12 pm


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron