flat assembler
Message board for the users of flat assembler.

Index > Windows > example - small prime finder

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
handyman



Joined: 04 Jun 2007
Posts: 40
Location: USA - KS
handyman
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 Smile


Description: Small prime number finder. load file source into flat assember and compile it to run.
(updated version can be found below)

Download
Filename: Prime32.ASM
Filesize: 18 KB
Downloaded: 214 Time(s)



Last edited by handyman on 07 Jun 2007, 02:45; edited 1 time in total
Post 05 Jun 2007, 02:07
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Very good work (in my opinion). Very Happy I like precisely commented programs. This program is really handy. Smile
Post 05 Jun 2007, 09:43
View user's profile Send private message Visit poster's website Reply with quote
asmfan



Joined: 11 Aug 2006
Posts: 392
Location: Russian
asmfan
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.
Post 05 Jun 2007, 11:38
View user's profile Send private message Reply with quote
handyman



Joined: 04 Jun 2007
Posts: 40
Location: USA - KS
handyman
asmfan - Nice optimise suggestion. I tried it and it sure works. I'll have to remember that.
Post 05 Jun 2007, 12:33
View user's profile Send private message Reply with quote
Yardman



Joined: 12 Apr 2005
Posts: 245
Location: US
Yardman
[ Post removed by author. ]


Last edited by Yardman on 04 Apr 2012, 02:13; edited 1 time in total
Post 05 Jun 2007, 13:17
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
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.
Post 05 Jun 2007, 14:07
View user's profile Send private message Reply with quote
asmfan



Joined: 11 Aug 2006
Posts: 392
Location: Russian
asmfan
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?
Post 05 Jun 2007, 14:28
View user's profile Send private message Reply with quote
Yardman



Joined: 12 Apr 2005
Posts: 245
Location: US
Yardman
[ Post removed by author. ]


Last edited by Yardman on 04 Apr 2012, 02:14; edited 1 time in total
Post 05 Jun 2007, 15:28
View user's profile Send private message Reply with quote
handyman



Joined: 04 Jun 2007
Posts: 40
Location: USA - KS
handyman
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.
Post 05 Jun 2007, 15:49
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
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.
Post 06 Jun 2007, 18:25
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
asmfan



Joined: 11 Aug 2006
Posts: 392
Location: Russian
asmfan
also should be
Code:
  exit: invoke DeleteObject,[brushwhite]            ;   cleanup
        invoke DeleteObject,[brushyellow]
    

_________________
Any offers?
Post 06 Jun 2007, 19:36
View user's profile Send private message Reply with quote
handyman



Joined: 04 Jun 2007
Posts: 40
Location: USA - KS
handyman
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 Smile.

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.


Description: program has the changes suggested by asmfan
so far
load into flat assembler to compile and run.

Download
Filename: Prime32.ASM
Filesize: 18.05 KB
Downloaded: 130 Time(s)

Post 07 Jun 2007, 01:58
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
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.
Post 08 Jun 2007, 02:00
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
handyman



Joined: 04 Jun 2007
Posts: 40
Location: USA - KS
handyman
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.
Post 08 Jun 2007, 05:38
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
good call, the code is obviously incomplete/flawed in that respect.
Post 08 Jun 2007, 13:13
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
46th Mersenne Prime found using 75 pc's networked
codelab wrote:

Hi, all, Another optimization of primesearching:
....
had fewer iterations caused by the startstep is less or equal to sqrt {prime range}

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?
Post 28 Sep 2008, 17:51
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
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.
Post 29 Sep 2008, 03:41
View user's profile Send private message Visit poster's website Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
revolution wrote:
....the current Prime95 is already in assembly....
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.

Smile
Post 29 Sep 2008, 11:28
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
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.
Post 29 Sep 2008, 11:44
View user's profile Send private message Visit poster's website Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
revolution wrote:
486 != Pentium (or later).
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.
revolution wrote:
...please show proof that your code is faster.
EXACTLY!
Anyone can write "fastest code on the planet..."
revolution wrote:
...these are 2560k point FFTs.
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?
Smile
Post 29 Sep 2008, 20:04
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< 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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.