flat assembler
Message board for the users of flat assembler.
Index
> Windows > example  small prime finder Goto page 1, 2 Next 
Author 

handyman 05 Jun 2007, 02:07
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
Last edited by handyman on 07 Jun 2007, 02:45; edited 1 time in total 

05 Jun 2007, 02:07 

MHajduk 05 Jun 2007, 09:43
Very good work (in my opinion). I like precisely commented programs. This program is really handy.


05 Jun 2007, 09:43 

handyman 05 Jun 2007, 12:33
asmfan  Nice optimise suggestion. I tried it and it sure works. I'll have to remember that.


05 Jun 2007, 12:33 

Yardman 05 Jun 2007, 13:17
[ Post removed by author. ]
Last edited by Yardman on 04 Apr 2012, 02:13; edited 1 time in total 

05 Jun 2007, 13:17 

LocoDelAssembly 05 Jun 2007, 14:07
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.


05 Jun 2007, 14:07 

asmfan 05 Jun 2007, 14:28
also some remarks: Should be
Code: Section 'export' data readable export
and Code: dialogitem 'BUTTON','&Cancel',ID_CANCEL,130,136,45,13,WS_VISIBLE OR WS_TABSTOP OR BS_PUSHBUTTON OR WS_GROUP To exclude cancel button from previous  radiobuttons' group. _________________ Any offers? 

05 Jun 2007, 14:28 

Yardman 05 Jun 2007, 15:28
[ Post removed by author. ]
Last edited by Yardman on 04 Apr 2012, 02:14; edited 1 time in total 

05 Jun 2007, 15:28 

handyman 05 Jun 2007, 15:49
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.


05 Jun 2007, 15:49 

r22 06 Jun 2007, 18:25
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. 

06 Jun 2007, 18:25 

asmfan 06 Jun 2007, 19:36
also should be
Code: exit: invoke DeleteObject,[brushwhite] ; cleanup invoke DeleteObject,[brushyellow] _________________ Any offers? 

06 Jun 2007, 19:36 

handyman 07 Jun 2007, 01:58
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 32bit items to be complete  kinda big for manual entry I think. In my program 16bit 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 32bit 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 32bit 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 16bit number range, and squaring the largest 16bit number gives a 32bit number, so the table can handle the whole 32bit 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 32bit 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.


07 Jun 2007, 01:58 

r22 08 Jun 2007, 02:00
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 0x00xFFFFFFFF and found that optimal list of primes to divide by that's used in the code. 

08 Jun 2007, 02:00 

handyman 08 Jun 2007, 05:38
r22,
You do not want to use any primes over 0xFFFF for checking 32bit 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 16bit 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 32bit 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 16bit prime numbers not in the divisor table that create a 32bit value when squared are going be flagged as prime when they really are not. 

08 Jun 2007, 05:38 

r22 08 Jun 2007, 13:13
good call, the code is obviously incomplete/flawed in that respect.


08 Jun 2007, 13:13 

tom tobias 28 Sep 2008, 17:51
46th Mersenne Prime found using 75 pc's networked
codelab wrote:
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? 

28 Sep 2008, 17:51 

revolution 29 Sep 2008, 03:41
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 multicore, 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. 

29 Sep 2008, 03:41 

tom tobias 29 Sep 2008, 11:28
revolution wrote: ....the current Prime95 is already in assembly.... 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. 

29 Sep 2008, 11:28 

revolution 29 Sep 2008, 11:44
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. 

29 Sep 2008, 11:44 

tom tobias 29 Sep 2008, 20:04
revolution wrote: 486 != Pentium (or later). a. George's code embraces both PrePentium 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. revolution wrote: ...please show proof that your code is faster. Anyone can write "fastest code on the planet..." revolution wrote: ...these are 2560k point FFTs. 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? 

29 Sep 2008, 20:04 

Goto page 1, 2 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.