Here is a small prime finder that I wrote that may be of interest to some.
This program uses a prime factor sieve to speed up the process that checks to see if number is prime or not. Number range is limited to a range from 1 to a maximum of 2^32 - 1 (almost 4GB)

Files can also be created that contain the prime numbers, or factor every number in the selected range.

enjoy

Very good work (in my opinion). I like precisely commented programs. This program is really handy.

Nice one! But there something to optimise. All data initialized to zero (db 0, dw 0, dd 0, etc.) make uninitialized - db ?, dw ?, dd ?
System inits it itself to 0 and no memory stored in file (on disk). Move all uninit data to end of section. it'll reduce size of exe. I made this and got only 7KB exe against 30KB.

asmfan - Nice optimise suggestion. I tried it and it sure works. I'll have to remember that.

[ Post removed by author. ]

Every section has its virtual size and its physical size, when all data at the end is uninitialized then there is no point to store it in the file and in such case the physical size become lower than the virtual size.

also some remarks: Should be

and

To exclude cancel button from previous - radiobuttons' group.

[ Post removed by author. ]

asmfan - thanks for the button and export changes. They just blew by me cause this code it has been 'working' for me for a while, even as far as sending the export values to the debugger.

Here's an old thread from 2004 that has pretty much the same concept. Only I used a bit mask for the primes < 65536 and a (division) table for the larger primes < 4.29billion. Also an old PRNG is in there.

http://board.flatassembler.net/topic.php?t=3540

handyman, your code is very neat, koodos on the good organization.

also should be

asmfan,

Thanks for the info on the missing brackets, nothing like another pair of eyes to check out the code!


r22,

I looked at code at

http://board.flatassembler.net/topic.php?t=3540

and all I can say is Wow! if you managed to type all that data in the table in without error first time! Debugging it must of been interesting to say the least! If I try to enter a lot of numbers in a table like that the data starts to make me go buggy and I end up missing or duplicating stuff somewhere along the line, so I try to avoid if at all possible .

Unless I am missing something, I do not think that the mentioned program can guarantee whether or not a particular 32 bit number is prime or not since the divisor table seems to be incomplete, and a complete table would need 6543 unsigned 32-bit items to be complete - kinda big for manual entry I think. In my program 16-bit numbers require up to a maximum of 55 prime numbers to be checked to see if they are a factor, but in asm this does not take long, for 32-bit this goes up to 6542. This is why I believe my program is much better on 32 bit numbers since the divisor table is complete and it can guarantee whether a particular 32-bit number is prime or not. Plus my program generates the prime number divisor table, so it completely eliminates human typo errors, which I make enough of.

Why 6543? Because that is how many prime numbers there are in the 16-bit number range, and squaring the largest 16-bit number gives a 32-bit number, so the table can handle the whole 32-bit number range for prime number checking. I made the table a nice round size of 6600 just to be sure it would not overflow and I did not want to mess with dynamic memory allocation. With bigger numbers I do not know if this will work as well, but I believe that somehow you still have check all primes less than the square root of the number to be sure of prime. There may be some high level math that can generate a large prime but I do not think there are any quick methods that can generate a sequence of primes without skipping some. If I am wrong on this I would sure like to hear about it, even if I may not understand it.

My aim with this program was to try to check for a series of primes as fast as possible using unsigned 32-bit integer mode only, and along the way I threw in a few extras to make the output a bit more interesting.

I had run across a program (executable only, no source) written by someone else that checked for all the prime numbers between 1 and 1,000,000 in about 2 seconds on my PC and I wanted to see what flat assembler could do using an idea I happened to think of. I got it down to about .75 seconds and figured that was not to bad, so after a while I just thought I would share it and see what anyone else thought about it.

handyman,
I'm pretty sure I created a script, probably JavaScript to make those data tables and then pasted them into my asm file.

As for the number of primes you ACTUALLY have to divide by I'm pretty sure you don't need to use every single prime > 0xFFFF. ***I may have dreamed this*** (it was 3 years ago I can't remember) but I think I tested every number from 0x0-0xFFFFFFFF and found that optimal list of primes to divide by that's used in the code.

r22,

You do not want to use any primes over 0xFFFF for checking 32-bit numbers because it will not help any. However, you have to allow for checking against EVERY prime under 0xFFFF and I believe there are 6542 of those ( I said 6543 earlier, but you have to skip the number '1') .

4,292,739,361= (65519^2), and 4,293,001,441=(65521^2) happen to be two numbers created by squaring each of the two largest 16-bit primes, and to get to these points in prime checking all smaller prime divisors had to fail. Was the check against '65521' or '65519' somehow handled in your code? if not then those two 32-bit numbers are flagged as prime when they are not since none of the numbers in the table will factor into them. Try it out using the factoring selection in my program, just be sure not to pick to big a number range or the program will create quite a few large text files. I limit how many lines will be in each file (currently 100,000 in the given code) and you can change it to whatever you want by changing the value for PFILEMAX.

As a thought, all of the 16-bit prime numbers not in the divisor table that create a 32-bit value when squared are going be flagged as prime when they really are not.

good call, the code is obviously incomplete/flawed in that respect.

46th Mersenne Prime found using 75 pc's networked

Some earlier studies from the FASM board:

vid's contribution and
bitrake's.

Here is Yong's contribution, suggesting use of RSA laboratories, with his link embedded.
n.b. please, Handiman's contribution, in this thread, with a "limitation" of maximum size of prime number = 4 GB = 2^32. Today's discovery by the UCLA mathematics team of a Mersenne Prime is 2^ 43,112,609.
Here is codelab, working on 14 digit prime numbers.
Questions:
could Handiman's algorithm, residing at the top of this thread, have revealed today's Mersenne prime number?
Second question, If one computer, programmed in ASM can test for Prime number, up to 2^32, how many computers must be connected together to search a Mersenne Prime, up to 2^44,000,000? Is the answer, 30?, i.e. Would 30 computers, programmed entirely in assembly, be able to test for prime numbers up to 2^500,000,000? If so, why did those UCLA mathematicians employ 75 computers?

Each number is tested on one CPU in it's entirety. Prime95 uses a the FFT method to do the squaring. And BTW the intermediate results for testing the number 2^43112609 can be stored in binary in ~5MB (although during the FFT more memory is used due to the nature of the algorithm).

75 computers means at least 75 separate tests in 75 different exponents (more if some of the machines are multi-core, one test one core is the most efficient in terms of time per test). It was just luck that one of the CPUs at UCLA was assigned that particular exponent to test, it could have been anyone. There are about 70000 computers currently registered in GIMPS, so that means 70000 concurrent tests worldwide. I've been running tests now for quite a few years. The program logs in to the server, gets an exponent assigned, tests it and reports the results back after a few weeks when the test finishes.

I seriously doubt that there is any more efficient test than the current LL used by Prime95. The problem of testing for primality and factorising has been studied by many mathematicians for a long time. Also the current Prime95 is already in assembly and is the fastest known code for large FFT on the planet.

yes, but it has been derived from C++. UGH.

George Woltman's code

George embedds the Sieve in the body of the executable, rather than computing it (what George describes as "optimised") However, the FFT is still computed using FPU, in part at least, according to George, to "free up" some cpu cycles on the integer unit to permit concurrent operations....I already published an article in 1993 showing that this concurrency, for a 486 running a tiny, 256 point FFT, was illusory. There was no time savings gained by interleaving the FFT between fpu and cpu.
So long as the FFT itself is not embedded in the executable (instead of computing on the fly), as is the sieve, George's FFT will not be the "fastest known code ... on the planet". Mine is.

Hmm, 486 != Pentium (or later).

But nevertheless, please show proof that your code is faster. And remember these are not 256 point FFTs, these are 2560k point FFTs.

I agree, completely, however, two small points:
a. George's code embraces both Pre-Pentium Pro cpu's, AND first generation SSE instructions, i.e. spans a wide range.
b. My comment was intended to highlight my question of George's supposition, in one of his comments in his code, that he was ACTUALLY freeing up (integer unit) cpu cycles (on ANY Intel cpu) by computing the FFT via the fpu.
EXACTLY!
Anyone can write "fastest code on the planet..."
Seriously, how many points are there in these FFT's? That's one of the mysteries of this business. More to the question, how does performance of the FFT, of any quantity of points, aid in establishing existence of a prime number, of any size?
Yet another question, intermixing Mathematics with Philosophy: Why is it useful, i.e. why does someone or something give 100K$ for discovery of a prime number with 44 million as the exponent? How does knowledge of this fact change which aspect of society? I am more interested to apply the FFT to PRACTICAL problems, ideally, even, perhaps, helping those with physical impairments. Is there a practical dimension to this Mersenne Prime business?