Sieve of Eratosthenes several variations

[zedd151]

The Sieve of Eratosthenes
with example in C language.

Thanks Timo for you contribution. Seems to be an optimized version. 
Did you make any further changes to the code, or is it code directly copied from the attachment in your linked paper? Sounds like a good candidate for porting to assembly. Further enhancements/optimizations may be possible with asm.    Any takers? Sinsi?  Magnus?  Jochen?  David?  Anyone?  Myself, I am busy with other projects.

"prime_sieve.c" from your attachment compiles fine with gcc. I have no experience with other compilers.
All those extraneous .pp* files are not needed. 

The resulting executable runs just fine. 

[TimoVJL]

I just made a Pelles C project for that code from that site and nothing else from me.

[zedd151]

I just made a Pelles C project for that code from that site and nothing else from me.

Okay, thats fine. I wasn't sure, so I asked.  Nice example regardless. Thanks. 

[NoCforMe]

New version. Improved sieve (mo' faster!), better formatting of output (16 numbers per line), shows correct primes (not 1!). Fully-commented, of course.

[zedd151]

Glad to have inspired you, NoCforMe. I'll take a gander at your latest Sieve of *Eratosthenes code when I am back at my computer. 

A short time later:
328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.
The output looks good, no apparent errors in the range 0-1,000,000.

[NoCforMe]

328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.

Does your timing include the display of those #s? or did you just time the sieve code itself?

[zedd151]

328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.

Does your timing include the display of those #s? or did you just time the sieve code itself?

The whole shebang.

Code Select Expand

start:
      invoke GetTickCount
      mov time1, eax
    CALL    WinMain
      invoke GetTickCount
      sub eax, time1
    INVOKE    StdOut, str$(eax)
    INVOKE    ExitProcess, 0

For longer, time consuming code it works okay, to test relative difference between one program or algorithm against another, or after making changes to the code to test whether the changes yields a speed improvement or not.

For much shorter pieces of code, looping multiple iterations (thousands to millions) are needed (use caution though, to not give erroneous algo results or timing errors), or other timing methods that may be more appropriate like jj's nano timer, or other methods using microsecond timers. 

...
I had to come back and edit the code snippet to what I actually used to get the timing of your code...

[NoCforMe]

I'd rather see timings for just the actual sieve code.
The display code will take f-o-r-e-v-e-r.

For my program, just call Sieve() multiple times in a loop and time that whole shebang. Not hard to do.

Code Select Expand

CALL GetTickCount
MOV startTime, EAX

MOV ECX, [# times to call Sieve() ]
@@: PUSH ECX
INVOKE Sieve, maxNum, PrimeBuffer
POP ECX
LOOP @B

CALL GetTickCount
SUB EAX, startTime

; display total time in EAX


[zedd151]

4,829 milliseconds for 1000 repititions for prime numbers from 0-1000000. So 4.8 microseconds per iteration. Seems fast enough.

By the way, it registers 0 MS running the function only once. 

Here using the 'repeat' macro to run 1000 iterations of the Sieve function for the timing.

Code Select Expand

; Find those primes!

      invoke GetTickCount
      mov time1, eax
     
      repeat 1000
    INVOKE    Sieve, maxNum, PrimeBuffer
      endm
      invoke GetTickCount
      sub eax, time1
      invoke MessageBox, 0, str$(eax), 0, 0

The modified code attached, including file 'run.bat'


run.bat:

Code Select Expand

SieveOfErastothenes 1000000>out.txt

pauseI prefer using batch files than typing at the command prompt. I didn't grow up using DOS. 

[NoCforMe]

So what's the timing of your code?

BTW, you don't have to use INVOKE with GetTickCount(), since it takes no parameters. A simple CALL will do.

[NoCforMe]

I prefer using batch files than typing at the command prompt. I didn't grow up using DOS. 

Well, then you have no idea what kind of fun you missed!

But really: not trying to convince you to do something that goes against your grain, but it's actually easier in the long run having a command window open without having to continually get new ones. Of course, I use a different command processor (4DOS, been using it for decades, still works great on Windows 7) that's a bit smarter than plain old "cmd".

But the DOS commands are pretty basic and easy to remember: of course, there are your existing batch files that you simply invoke by typing their name. Then there's COPY, DEL, etc. for files. And the command window keeps a history of previous commands executed, so you can look back and see which assembler errors are still there, f'rinstance.

Even "cmd" has a HELP command.

You might try it some day when you have time and maybe are really bored ...

[zedd151]

So what's the timing of your code?

It took me a minute to procedurize that part of the code....

11,487 milliseconds for 1,000 iterations for primes 0-1,000,000... Yikes! almost takes three times longer than your latest.

Bbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... 

BTW, you don't have to use INVOKE with GetTickCount(), since it takes no parameters. A simple CALL will do.

it's muscle memory that forces me to always write 'invoke'. That's my story and I'm sticking to it. 

I 'invoke' and 'call' --- ALL CAPS IS SO 1980's...


... I had some weird formatting bugs when posting originally. I musta accidentally hit some formatting buttons...

[NoCforMe]

I 'invoke' and 'call' --- ALL CAPS IS SO 1980's...

Ackshooly, it's more like 1960s. Like those programs that ran the Apollo mission.

[NoCforMe]

11,487 milliseconds for 1,000 iterations for primes 0-1,000,000... Yikes! almost takes three times longer than your latest.

Bbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... 

Normally I don't. But in this case I get to say:

Nya nya nya nya: My code's faster than your code!

(If you care, you need to skip computing multiples of numbers that are already taken out as primes, as sinsi suggested upthread. Then yours will be as fast as mine.)

[zedd151]

Bbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... 

Normally I don't. But in this case I get to say:

Nya nya nya nya: My code's faster than your code!

When I wrote that code, I was more concerned about accuracy and simplicity than speed. If you give me a coupla days, I'll make mine faster than yours. 

Just kidding, mine still serves a purpose, as is.