0

My program is supposed to loop forever and give out via print every prime number it comes along. Doing this in x86-NASM btw.

My first attempt divided it by EVERY previous number until either the Carry is 0 (not a prime) or the result is 1.

MY second attempt improved this by only testing every second, so only odd numbers.

The third thing I am currently implementing is trying to not divide by EVERY previous number but rather all of the previous divided by 2, since you can't get an even number by dividing a number by something bigger than its half

Another thing that might help is to test it with only odd numbers, like the sieve of eratosthenes, but only excluding even numbers.

Anyway, if there is another thing I can do, all help welcome.

edit: Left: calculate everything. Then it only uses every 2nd number. Then it only divides through uneven numbers. The last one also only calculates the lower 50% of that number

Community
  • 1
  • 1
Martin
  • 37
  • 1
  • 10
  • 4
    Assuming that probably all primes in the 32 bit range are already listed somehwere, the absolutely most efficient code would be iterating over such a list. – Rudy Velthuis Nov 19 '18 at 12:10
  • You didn't say whether what you tried succeeded or failed. What are you asking? The problem of determining if a given number is prime using a simple brute-force method is fairly common. You can find many implementations in several languages by searching this site. Assuming you pre-check whether a number is > 2 or odd as a condition, then to determine if a given number N is prime using this method involves checking for divisors between 3 and square root of N. Also, since you are limiting results to 32 bits, you shouldn't have to "loop forever". – lurker Nov 19 '18 at 12:12
  • @RudyVelthuis Well, the point is to calculate them – Martin Nov 19 '18 at 12:16
  • @lurker well 1 and 2 are working as wished, 3 not yet. I want to know if there are other methods I dintn't think of – Martin Nov 19 '18 at 12:17
  • @Martin: that is not what your first line says. But there are quite a few algorithms to determine prime numbers. They are probably best found online. And on a 32 bit machine, you can also implement big integers, so your opportunities are almost unlimited. – Rudy Velthuis Nov 19 '18 at 12:18
  • well.. a sieve up to 65536 (2^16) should help tremendously (65536^2 = 32b overflow, so you will never need larger dividend to verify prime-ness of 32 bit value). You can also check this codereview question for further tips in x86 assembly: https://codereview.stackexchange.com/q/148315/110284 – Ped7g Nov 19 '18 at 12:23
  • 1
    either `O(1)` SoE or `O(log(n))` binary search in all prime list is the fastest way I know of ... the list can be computed by SoE but there are also files containing all 32bit primes out there IIRC they are ~700MByte in size also you can take a look at this [Prime numbers by Eratosthenes quicker sequential than concurrently?](https://stackoverflow.com/a/22477240/2521214) as you need nasm I would go for the Soe or file instead of monte carlo methods as code them in nas m might be a pain in the ... so the question is can you store 700MByte DWORDs. The SoE is 256MByte ... I would go for the SoE – Spektre Nov 21 '18 at 10:07

1 Answers1

8

If you need to test an handful, possibly only one, of primes, the AKS primality test is polynomial in the length of n.
If you want to find a very big prime, of cryptographic size, then select a random range of odd numbers and sieve out all the numbers whose factors are small primes (e.g. less equal than 64K-240K) then test the remaining numbers for primality.

If you want to find the primes in a range then use a sieve, the sieve of Erathostenes is very easy to implement but run slower and require more memory.
The sieve of Atkin is faster, the wheels sieve requires far less memory.

The size of the problem is exponential if approached naively so before micro-optimising is mandatory to first macro-optimise.
More or less all prime numbers algorithms require confidence with Number theory, so take particular attention to the group/ring/field the algorithm is working on because mathematicians write operations like the inverse or the multiplication with the same symbol for all the algebraic structures.

Once you have a fast algorithm, you can start micro-optimising.
At this level it's really impossible to answer how to proceed with such optimisations.

Margaret Bloom
  • 41,768
  • 5
  • 78
  • 124
  • me and the other apprentice have both the task of coding an algorithm that calculates all primes from 0-n in the least ammount of time, that's what I wanna know it for – Martin Nov 22 '18 at 12:06
  • @MartinGeidobler Than you have to take a look at the sieves. If memory is not a constrain, start from the Sieve of Atkin. You can search for specific variants (e.g. parallel), the key is "sieve" though. – Margaret Bloom Nov 22 '18 at 14:21
  • 1
    Ignore AKS -- it is **much** slower than other known deterministic tests for numbers in the range we might compute this century. It is of theoretical importance only at this point. Re Sieve of Atkin, in practice it is slower than a decent segmented Sieve of Eratosthenes, especially if not implemented with every optimization shown in the paper. Your general point of primality test vs. sieve is correct barring very large ranges (e.g. 10^100 to 10^100 + 10^6). – DanaJ Nov 30 '18 at 18:22
  • 2
    @DanaJ Yes, that's true. It's been a while since the last time I worked with prime numbers but the general advise was to use a "progressive" approach (sorry I forgot the right term) where theoretically slower but fast to implement algorithms (no setup time) were used first. It's a topic that can easily fill a book or two :) – Margaret Bloom Nov 30 '18 at 18:57