experiment on primes

Index > Main > experiment on primes

Author

Thread

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 13 Feb 2010, 11:08

hello, i'm newbie

i would make an experiment

i have this :

http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.c

it possible convert this in fasm for see time and efficent differences ?

some good soul help me ?

TY

13 Feb 2010, 11:08

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20292
Location: In your JS exploiting you and your system

revolution 13 Feb 2010, 11:16

Maybe this can help you to get started.

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

13 Feb 2010, 11:16

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 13 Feb 2010, 12:27

revolution wrote:

Maybe this can help you to get started.

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

thanks for the link,
but i would use the same c algo of my link
for run equivalent code on c and asm,

i want to see how much time takes ASM
and how much time takes C
with the same type of code,

shure ASM is more fast , but how much time is more fast ? Smile

i have compiled the c, report :

Code:

The number of primes below 10^8 is 5761455.

Process returned 0 (0x0)   execution time : 0.790 s
Press any key to continue.

13 Feb 2010, 12:27

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 13 Feb 2010, 14:40

I use the binary prime sieve sometimes. Although it is very fast to generate, memory access will bring both implementations towards similar timing. Where the assembly version might benefit is in accessing the binary array after generation - a single instruction.

Try the Sieve of Atkin for faster results.

13 Feb 2010, 14:40

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20292
Location: In your JS exploiting you and your system

revolution 13 Feb 2010, 14:42

SolidThink wrote:

it possible convert this in fasm for see time and efficent differences ?

It depends upon how good you are with assembly code.

SolidThink wrote:

some good soul help me ?

What specifically do you need help with? Post what you have so far and see if someone can give you some pointers to improve it.

13 Feb 2010, 14:42

Plue

Joined: 15 Dec 2005
Posts: 151

Plue 14 Feb 2010, 14:39

That is a ridiculously unreadbly written C code.

14 Feb 2010, 14:39

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 15 Feb 2010, 08:24

Plue wrote:

That is a ridiculously unreadbly written C code.

I can ask why?

15 Feb 2010, 08:24

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 16 Feb 2010, 03:00

<Rant>

Code:

void make() {
    uint32_t i, j, k;
    memset(sieve, 0, sizeof(sieve));
    for (k = 1; k <= P3; k++)
        if (GET(k)==0) for(j=2*k+1,i=2*k*(k+1);i<P2;i+=j) sieve[i>>5]|=1<<(i&31);
}

int isprime(int p) { return p==2 || (p>2 && (p&1)==1 && (GET((p-1)>>1)==0)); }

You don't know why the above code is cryptic?

Imagine someone is used to looking at:

Code:

@@:     mov eax,1
   mov ecx,edx
 and ecx,11111b
      shl eax,cl

      mov ecx,edx
 shr ecx,5
   or [edi+ecx*4],eax

      add edx,ebx
 cmp edx,P2
  jc @B

...which is a literal translation of the inner loop of make(). Does it seem cryptic now? There is no additional cost for longer symbolic names, or more verbose code. True, a seasoned C(++) programmer can easily read through a dense code block without difficulty. Yet, have you ever missed a single character which changed the interpretation of the code?

The same can be said for assembly language programmers which use the full instruction set. In fact I dread reading some assembly code where the author only knows a dozen instructions. So, artistically it adds flavor and style, or might even say something about the author.

Except it was presented on a web page for a wider audience. Razz

</Rant>

BTW, the inner loop could be reduced to:
(The compiler isn't capable of the reduction.)

Code:

@@:  bts [edi],edx

   add edx,ebx
 cmp edx,P2
  jc @B

...which is similar to what my sieve code does. Wink

16 Feb 2010, 03:00

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 16 Feb 2010, 16:53

bitRAKE wrote:

<Rant>
Code:
void make() {
    uint32_t i, j, k;
    memset(sieve, 0, sizeof(sieve));
    for (k = 1; k <= P3; k++)
        if (GET(k)==0) for(j=2*k+1,i=2*k*(k+1);i<P2;i+=j) sieve[i>>5]|=1<<(i&31);
}

int isprime(int p) { return p==2 || (p>2 && (p&1)==1 && (GET((p-1)>>1)==0)); }    
You don't know why the above code is cryptic?

Imagine someone is used to looking at:
Code:
@@: mov eax,1
   mov ecx,edx
 and ecx,11111b
      shl eax,cl

      mov ecx,edx
 shr ecx,5
   or [edi+ecx*4],eax

      add edx,ebx
 cmp edx,P2
  jc @B    
...which is a literal translation of the inner loop of make(). Does it seem cryptic now? There is no additional cost for longer symbolic names, or more verbose code. True, a seasoned C(++) programmer can easily read through a dense code block without difficulty. Yet, have you ever missed a single character which changed the interpretation of the code?

The same can be said for assembly language programmers which use the full instruction set. In fact I dread reading some assembly code where the author only knows a dozen instructions. So, artistically it adds flavor and style, or might even say something about the author.

Except it was presented on a web page for a wider audience.
</Rant>

BTW, the inner loop could be reduced to:
(The compiler isn't capable of the reduction.)
Code:
@@:  bts [edi],edx

   add edx,ebx
 cmp edx,P2
  jc @B    
...which is similar to what my sieve code does.

I've rewritten the code Smile

Code:

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>

unsigned int PRME_01=2000000;
unsigned int num_01,sel_01,numofprim_01=0,numprim_01=0;
#define DIVPRM sqrt(PRME_01)

int main()
{
char nprime_01[PRME_01+1];
memset(nprime_01,1,PRME_01);
nprime_01[0]=0;
nprime_01[1]=0;
int timea;
timea=clock();
for (num_01=2;num_01<=DIVPRM;num_01++)
{
if (nprime_01[num_01])
{
for (sel_01=2;sel_01<=(PRME_01/num_01);sel_01++)
{
nprime_01[sel_01*num_01]=0;}}}
printf("\nPrimes between 2 and 2.000.000 = ", PRME_01 );
for (num_01=2;num_01<=PRME_01;num_01++)
if (nprime_01[num_01]) ++numofprim_01;
timea=clock()-timea;
printf("%ld \n \nMilliseconds Elapsed = %d\n\n", numofprim_01, timea);
system("PAUSE");
return (0);
}

Code:

Primes between 2 and 2.000.000 = 148933

Milliseconds Elapsed = 7

16 Feb 2010, 16:53

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 16 Feb 2010, 17:05

Oh, that is funny. Laughing

16 Feb 2010, 17:05

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 16 Feb 2010, 18:43

bitRAKE wrote:

Oh, that is funny.

C i'm bit capable, but ..asm ... i do pity Razz

16 Feb 2010, 18:43

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 16 Feb 2010, 19:02

What's the point of rewriting same algorithm in ASM, when ASM has features for much more effective way?

Is it just another "Me vs. C optimizer" contest?

16 Feb 2010, 19:02

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 16 Feb 2010, 19:24

vid wrote:

What's the point of rewriting same algorithm in ASM, when ASM has features for much more effective way?

Is it just another "Me vs. C optimizer" contest?

Code:

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <windows.h>

unsigned int PRME_01=2000000,num_01,sel_01,numofprim_01=0,numprim_01=0;
#define DIVPRM sqrt(PRME_01)

int main(){
char nprime_01[PRME_01+1];
memset(nprime_01,1,PRME_01);
nprime_01[0]=nprime_01[1]=0;
unsigned int timea=clock();
num_01=2;
while(num_01<=DIVPRM){
if(nprime_01[num_01]){
sel_01=2;
while(sel_01<=(PRME_01/num_01)){
nprime_01[sel_01*num_01]=0;
sel_01++;
}}
num_01++;
}
printf("\nPrimes between 2 and 2.000.000 = ", PRME_01 );
num_01=2;
while(num_01<=PRME_01){
if(nprime_01[num_01]) ++numofprim_01;
num_01++;
}
timea=clock()-timea;
printf("%ld \n \nMilliseconds Elapsed = %d\n\n", numofprim_01, timea);
system("PAUSE");
return (0);
}

a bit optimizations of precedent code;

I want to learn asm,
if i see the asm code and compare it
with this C code, that i know well,
i think understand better how start
and where make mistakes... Wink

and i also like to see the execution time, i'll admit...

16 Feb 2010, 19:24

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc 16 Feb 2010, 20:21

Have you ever heard of WHITESPACE? Aligning the C Code for readability under columns? I find it very cryptic as well.

16 Feb 2010, 20:21

baldr

Joined: 19 Mar 2008
Posts: 1651

baldr 16 Feb 2010, 20:27

Borsuc,

Probably he's preparing an entry for IOCCC simultaneously. Wink

16 Feb 2010, 20:27

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 16 Feb 2010, 22:33

SolidThink wrote:

I want to learn asm,
if i see the asm code and compare it
with this C code, that i know well,
i think understand better how start
and where make mistakes...

and i also like to see the execution time, i'll admit...

To learn ASM, I would suggest to start with something simpler, and trace your code in debugger (OllyDbg). That way you learn faster than with comparing ASM code to C code.

Or, just compile your code and look at it in asm dump and dissasembler.

16 Feb 2010, 22:33

baldr

Joined: 19 Mar 2008
Posts: 1651

baldr 16 Feb 2010, 22:43

vid wrote:

Or, just compile your code and look at it in asm dump and dissasembler.

And smile upon that. Wink

16 Feb 2010, 22:43

SolidThink

Joined: 16 Oct 2009
Posts: 23

SolidThink 17 Feb 2010, 12:10

thank you very ... math ... Smile

17 Feb 2010, 12:10

< 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