[Algorithms] Finding primes ...

Index > Tutorials and Examples > [Algorithms] Finding primes ...

Goto page Previous 1, 2

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4227
Location: vpcmpistri

bitRAKE 27 Mar 2025, 12:47

It's been some time, but IIRC:
a. download fasmg: https://flatassembler.net/download.php
b. clone the repo
c. navigate to the file P003.asm
d. execute the assembler: fasmg P003.asm

You'll need the include path setup.

If you don't mind me asking, what are you doing currently? I'm assuming you have something configured to assembler x86 instructions? What is that?

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

27 Mar 2025, 12:47

six_L

Joined: 03 Jan 2005
Posts: 15

six_L 27 Mar 2025, 13:42

Hello,bitRAKE
Thanks for your patience and times to the respones.

I'm using the UASM64, interested in your algorithm for obtaining prime numbers.
because of needing the 1048575(T) memory, I'v still thought that it is impossible to obtain all primes smaller than 2^64.

Regards
six_L

27 Mar 2025, 13:42

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 27 Mar 2025, 14:35

six_L wrote:

... I'v still thought that it is impossible to obtain all primes smaller than 2^64.

It is possible, and has been done. But it takes a lot of compute resources.

Storing all of them is also a challenge. I would like to see someone do it.

27 Mar 2025, 14:35

macomics

Joined: 26 Jan 2021
Posts: 1149
Location: Russia

macomics 27 Mar 2025, 14:58

revolution wrote:

It is possible, and has been done. But it takes a lot of compute resources.

Storing all of them is also a challenge. I would like to see someone do it.

Even if you use bits to store numbers and save only the odd ones, then you will still need 2^60 bitmap. It seems modern desktop processors only support virtual memory up to 2^48.

27 Mar 2025, 14:58

bitRAKE

Joined: 21 Jul 2003
Posts: 4227
Location: vpcmpistri

bitRAKE 27 Mar 2025, 15:11

If a prime was calculated every nano-second - a single processor would take over 13 years. If you could split the parallel calculation across 256 cores it'd still take ~20 days.

27 Mar 2025, 15:11

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 27 Mar 2025, 15:49

macomics wrote:

Even if you use bits to store numbers and save only the odd ones, then you will still need 2^60 bitmap. It seems modern desktop processors only support virtual memory up to 2^48.

Using a sieve would be the way to generate them all for best efficiency. But using RAM wouldn't be an option, it would have to be a large set of HDDs/SSDs or tape, or something, that can be scaled to 1EB.

27 Mar 2025, 15:49

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 27 Mar 2025, 15:51

bitRAKE wrote:

If a prime was calculated every nano-second - a single processor would take over 13 years. If you could split the parallel calculation across 256 cores it'd still take ~20 days.

A sieve can be used by shifting and masking. So multiple primes are "computed" for each cycle. I think that going through each individual number would be way too slow and inefficient.

27 Mar 2025, 15:51

macomics

Joined: 26 Jan 2021
Posts: 1149
Location: Russia

macomics 27 Mar 2025, 16:13

I've been thinking about something else. It turns out the following: for 64-bit, it is enough to store signs of simplicity for the first 4 GB (e.g. sqr of 4GB = 2^64). 256 MB of memory is enough for storage in a 4GB bitmap (only odd). The rest of the simplicity features can simply be saved to disk. For example, after accumulating a 256 MB block. But you'll still need a hell of a lot of space.

And also need a bitmap scanning algorithm for one bits. It is efficient enough to get the numbers of the bits in the bitmap and thus not go through the checks of this bitmap in search of the next prime number.

27 Mar 2025, 16:13

six_L

Joined: 03 Jan 2005
Posts: 15

six_L 27 Mar 2025, 16:31

Hello,revolution

revolution wrote:

It is possible, and has been done. But it takes a lot of compute resources.

Yes, is it. I knew that the largest prime discovered untill now by humans is 2^(282589933)−1. The process of implemented it does not rely on PCs and us, but on supermachines and mathematicians.

27 Mar 2025, 16:31

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 27 Mar 2025, 23:15

six_L wrote:

Hello,revolution

revolution wrote:
It is possible, and has been done. But it takes a lot of compute resources.

Yes, is it. I knew that the largest prime discovered untill now by humans is 2^(282589933)−1. The process of implemented it does not rely on PCs and us, but on supermachines and mathematicians.

The larget known prime today is 2^136279841-1. Found using an ordinary computer that anyone can buy.

But it is a number of special form that we know of a very fast algorithm to test it. For general numbers of no special form it is not as easy. And also, not all numbers from 1 up to that number have been tested, only the powers of two are being tested.

27 Mar 2025, 23:15

bitRAKE

Joined: 21 Jul 2003
Posts: 4227
Location: vpcmpistri

bitRAKE 27 Mar 2025, 23:32

revolution wrote:

bitRAKE wrote:
If a prime was calculated every nano-second - a single processor would take over 13 years. If you could split the parallel calculation across 256 cores it'd still take ~20 days.
A sieve can be used by shifting and masking. So multiple primes are "computed" for each cycle. I think that going through each individual number would be way too slow and inefficient.

I meant this more as a simple mental guide. Rather than work with such big numbers we can approximate with simpler terms to estimate the time needed. For example, if 20 primes could be computed per nano-second, it would take 256 cores running in parallel, one day.

On a practical note, I wouldn't use my sieve implementation beyond L3 cache - that is the intended use. Sieve of Atkin is typically used for very large sequential primes (implementation).

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

27 Mar 2025, 23:32

six_L

Joined: 03 Jan 2005
Posts: 15

six_L 28 Mar 2025, 02:36

Hi, All

All infromation about Prime is come from the "https://www.mersenne.org/"

Quote:

The current record:
As of July 2024, the largest prime number discovered by humans is 2^82589933-1, which is a Mersenne Prime discovered by the Great Internet Mersenne Prime Search (GIMPS) project on December 7, 2018.
Discoverer: Patrick Laroche(GIMPS volunteer)

Do you know: Here, there is an example of the mature implementation of distributed computing ?

28 Mar 2025, 02:36

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 28 Mar 2025, 02:46

That prime has been surpassed recently. See this link as shown above
https://www.mersenne.org/report_exponent/?exp_lo=136279841&full=1

28 Mar 2025, 02:46

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20631
Location: In your JS exploiting you and your system

revolution 28 Mar 2025, 02:47

six_L wrote:

Do you know: Here, there is an example of the mature implementation of distributed computing ?

I have been contributing to that since 1999.

28 Mar 2025, 02:47

six_L

Joined: 03 Jan 2005
Posts: 15

six_L 28 Mar 2025, 03:41

Hi,revolution

revolution wrote:

I have been contributing to that since 1999.

Pay my respects to you.

28 Mar 2025, 03:41

Goto page Previous 1, 2

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum