Recent

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

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

marcov

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

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
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 »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11382
  • 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: 3944
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) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

ASBzone

  • Hero Member
  • *****
  • Posts: 678
  • Automation leads to relaxation...
    • Free Console Utilities for Windows (and a few for Linux) from BrainWaveCC
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.2.7-ada7a90186 / FPC v3.2.3-706-gaadb53e72c
(Windows 64-bit install w/Win32 and Linux/Arm cross-compiles via FpcUpDeluxe on both instances)

My Systems: Windows 10/11 Pro x64 (Current)

440bx

  • Hero Member
  • *****
  • Posts: 3944
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) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

winni

  • Hero Member
  • *****
  • Posts: 3197
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: 242
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, Win10pro - Ryzen9XT 24threads + Geforce Rtx 3080SUPRIM
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: 242
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, Win10pro - Ryzen9XT 24threads + Geforce Rtx 3080SUPRIM
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

  • Guest
Re: 32-bit primality testing
« Reply #10 on: April 05, 2020, 07:45:59 am »

avk

  • Hero Member
  • *****
  • Posts: 752
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: 6676
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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

440bx

  • Hero Member
  • *****
  • Posts: 3944
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) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

 

TinyPortal © 2005-2018