Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

Author Topic: 32-bit primality testing  (Read 620 times)

MarkMLl

• Hero Member
• Posts: 858
32-bit primality testing
« on: April 04, 2020, 03:22:04 pm »
Can anybody point me at a prime-number test adequate for 32-bit integers? That's small enough that trial division would probably be adequate, but I'm interested if anybody has anything better. I don't want to have to redo this, so would prefer an "is" rather than a "probably is".

I note https://surface.syr.edu/cgi/viewcontent.cgi?article=1159&context=eecs_techreports from Per Brinch-Hansen, but it's probably overkill since he's talking about ~150 digit numbers.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.

marcov

• Global Moderator
• Hero Member
• Posts: 8366
• FPC developer.
Re: 32-bit primality testing
« Reply #1 on: April 04, 2020, 04:12:10 pm »

MarkMLl

• Hero Member
• Posts: 858
Re: 32-bit primality testing
« Reply #2 on: April 04, 2020, 04:26:05 pm »
Ouch :-)  OK, something that can be contained in a simple program and doesn't require web access :-)

Actually, one valid approach would probably be a table of the distance between primes, i.e. rather than having a table 3, 5, 7, 11, 13... store 2, 2, 4, 2... converting trial division to additive iteration.

After all, who would notice an extra 1/2Gb or so extra in a program these days?

(Somewhat later:)

There's some useful-looking stuff at https://rosettacode.org/wiki/Category:PrimTrial

MarkMLl

« Last Edit: April 04, 2020, 06:02:36 pm by MarkMLl »
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.

marcov

• Global Moderator
• Hero Member
• Posts: 8366
• FPC developer.
Re: 32-bit primality testing
« Reply #3 on: April 05, 2020, 12:55:37 am »
Ouch :-)  OK, something that can be contained in a simple program and doesn't require web access :-)

Actually, one valid approach would probably be a table of the distance between primes, i.e. rather than having a table
3, 5, 7, 11, 13... store 2, 2, 4, 2... converting trial division to additive iteration.

You can download the complete table of 32-bit integers and it fits in about 1GB when converted to binary.

So why would you need trial division at all. It is just binsearch in the array.

440bx

• Hero Member
• Posts: 1821
Re: 32-bit primality testing
« Reply #4 on: April 05, 2020, 03:05:24 am »
I think Marco's suggestion has merit.

If I faced that problem, I'd use the table Marco suggested and an "array[dword] of bit" and use the primes in the table to set their corresponding bit to 1.

After that, it is a direct access to the array element to determine if a number is prime or not.  In addition to that, it would provide a reasonably quick way of determining the prime "floor" and "ceil" of any number that is not a prime.

The bit array would occupy about 1/2gig but you wouldn't need to have it all in memory if you sectioned the array into equal number of primes per range.  1024 ranges would create sections of less than 1 mb each.  Each section could be a resource loaded on demand.

Just some thoughts...
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

ASBzone

• Sr. Member
• Posts: 346
Re: 32-bit primality testing
« Reply #5 on: April 05, 2020, 03:15:52 am »
Can anybody point me at a prime-number test adequate for 32-bit integers? That's small enough that trial division would probably be adequate, but I'm interested if anybody has anything better. I don't want to have to redo this, so would prefer an "is" rather than a "probably is".

I note https://surface.syr.edu/cgi/viewcontent.cgi?article=1159&context=eecs_techreports from Per Brinch-Hansen, but it's probably overkill since he's talking about ~150 digit numbers.

MarkMLl

How high do you need to go?

I've been playing with this and a have two routines, one that does trial division up to the SQRT, and one that uses a segmented sieve.

The first routine can get prime numbers up to 100,000,000 (100 mil) in less than 9 minutes, on a 5th generation mobile i5 processor.

The second routine can get prime numbers up to 10,000,000,000 (10 bil) in less than 2 minutes on the same system.
-ASB: https://www.BrainWaveCC.com

Lazarus v2.0.9 r63081 / FPC v3.2.0-beta-r45317 (via FpcUpDeluxe) -- Windows 64-bit install w/32-bit cross-compile
Primary System: Windows 10 Pro x64, Version 1909 (Build 18363.778)
Other Systems: Windows 10 Pro x64, Version 1909 or greater

440bx

• Hero Member
• Posts: 1821
Re: 32-bit primality testing
« Reply #6 on: April 05, 2020, 04:07:34 am »
The first routine can get prime numbers up to 100,000,000 (100 mil) in less than 9 minutes, on a 5th generation mobile i5 processor.

The second routine can get prime numbers up to 10,000,000,000 (10 bil) in less than 2 minutes on the same system.
That's quite good.  The real question is, how quickly does he need to establish primality.

Maybe I'm missing something but, how come the routine that goes up to 10billion takes a fifth/fourth of the time of the routine that only goes up to 100mil ?.   Sounds like the second algorithm is a lot better than the first one.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

winni

• Hero Member
• Posts: 1338
Re: 32-bit primality testing
« Reply #7 on: April 05, 2020, 04:08:47 am »
Hi!

The lookup table from Marcov's reply #1 is unpacked  773 MB.

It is loaded from file into an array of dWord in around a second from  a SDD - with blockread.

Winni

mercurhyo

• Full Member
• Posts: 177
Re: 32-bit primality testing
« Reply #8 on: April 05, 2020, 04:32:49 am »
you can do it yourself in case if one day you decide to change the high limit

https://rosettacode.org/wiki/Sieve_of_Eratosthenes

Go to the above link, scroll down the page to get FreePascal solutionS

Get one, then alter it to write resulting table(s) of your size in a file (and maybe compressed by your hand)

the app using the table has just to read it back
« Last Edit: April 05, 2020, 04:36:57 am by mercurhyo »
DEO MERCHVRIO - Linux Mint latest, Windows 7 - Laz latest fixes- RAD Studio XE7
god of financial gain, commerce, eloquence (and thus poetry), messages, communication (including divination), travelers, boundaries, luck, trickery and thieves; he also serves as the guide of souls to the underworld

mercurhyo

• Full Member
• Posts: 177
Re: 32-bit primality testing
« Reply #9 on: April 05, 2020, 04:42:16 am »
you also have the FAST assembly versions of the Sieve algorithm for many CPU, so you can implement it with FreePascal in ASM mode, keeping it multiplatform
« Last Edit: April 05, 2020, 04:44:29 am by mercurhyo »
DEO MERCHVRIO - Linux Mint latest, Windows 7 - Laz latest fixes- RAD Studio XE7
god of financial gain, commerce, eloquence (and thus poetry), messages, communication (including divination), travelers, boundaries, luck, trickery and thieves; he also serves as the guide of souls to the underworld

julkas

• Hero Member
• Posts: 576
• KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: 32-bit primality testing
« Reply #10 on: April 05, 2020, 07:45:59 am »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
mov rax, a
mov rdx, b
mul rdx
mov [clo], rax
mov [chi], rdx
end;

avk

• Sr. Member
• Posts: 265
Re: 32-bit primality testing
« Reply #11 on: April 05, 2020, 10:32:20 am »
The lookup table from Marcov's reply #1 is unpacked  773 MB.
Winni
Using an array of bits, only 512 MB and, as a bonus, a very fast lookup.

MarkMLl

• Hero Member
• Posts: 858
Re: 32-bit primality testing
« Reply #12 on: April 05, 2020, 11:48:16 am »
Can anybody point me at a prime-number test adequate for 32-bit integers?

How high do you need to go?

32-bit, as stated. I've used a couple of routines from the Rosetta link I posted which appear to work adequately.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.

MarkMLl

• Hero Member
• Posts: 858
Re: 32-bit primality testing
« Reply #13 on: April 05, 2020, 11:49:32 am »
So why would you need trial division at all. It is just binsearch in the array.

To avoid the overhead of a few hundred Mb which might only be needed once.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.

440bx

• Hero Member
• Posts: 1821
Re: 32-bit primality testing
« Reply #14 on: April 05, 2020, 12:04:35 pm »
To avoid the overhead of a few hundred Mb which might only be needed once.

MarkMLl
In that case, you could have the array of bits in a separate file which is loaded only when needed and unloaded afterwards.  That would give you reasonable speed and reasonably efficient memory utilization since you'd free the array once you no longer need it.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.