Soyez le premier à donner votre avis sur cette source.
Vue 3 219 fois - Téléchargée 121 fois
bool *EratoD(U32 mx) { bool *isPrime=(bool*)malloc(mx+1); memset(isPrime,true,mx+1); isPrime[0]=false; isPrime[1]=false; for (U32 p=2; p*p<=mx; ++p) if (isPrime[p]) for (U32 q=mx/p; q>=p; --q) if (isPrime[q]) isPrime[p*q]=false; return isPrime; } /* EratoD: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=3 ms m=10000000, n=664579, t=42 ms m=100000000, n=5761455, t=464 ms m=1000000000, n=50847534, t=5364 ms */Les temps de calcul mesurés sont un peu plus grands que ceux obtenus sous "Le crible d'Eratosthène classique".
typedef unsigned char U8; typedef unsigned short int U16; typedef unsigned int U32; typedef unsigned long long int U64; #define B8get(u8,idx) (u8[idx>>3] & (1<<(idx&7)) ) #define B8set0(u8,idx) {u8[idx>>3] &= ~(1<<(idx&7));} #define B16get(u16,idx) (u16[idx>>4] & (1<<(idx&15)) ) #define B16set0(u16,idx) {u16[idx>>4] &= ~(1<<(idx&15));} #define B32get(u32,idx) (u32[idx>>5] & (1<<(idx&31)) ) #define B32set0(u32,idx) {u32[idx>>5] &= ~(1<<(idx&31));} #define B64get(u64,idx) (u64[idx>>6] & (1ULL<<(idx&63)) ) #define B64set0(u64,idx) {u64[idx>>6] &= ~(1ULL<<(idx&63));}Ces "#define" ont déjà été implicitement utilisés dans:
U8 *EratoBit(U32 mx) { U8 *bs=(U8*)malloc(1+mx/8); // idx: 0 1 2 3 4 5 6 7 8 9 10 11 12 ... bs[0]=252; memset(bs+1,255,mx/8); // [0,0,1,1,1,1,1,1|1,1, 1, 1, 1,...] bits for (U32 p=2; p*p<=mx; ++p) if (B8get(bs,p)) for (U32 q=mx/p; q>=p; --q) if (B8get(bs,q)) B8set0(bs,p*q); return bs; } /* EratoBit: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=4 ms m=10000000, n=664579, t=53 ms m=100000000, n=5761455, t=760 ms m=1000000000, n=50847534, t=8507 ms */Nous constatons qu'EratoBit est d'environs 50% plus lent que EratoD.
std::vector<bool> EratoVec(U32 mx) { std::vector<bool> vbs(mx+1,true); vbs[0]=vbs[1]=false; for (U32 p=2; p*p<=mx; ++p) if (vbs[p]) for (U32 q=mx/p; q>=p; --q) if (vbs[q]) vbs[p*q]=false; return vbs; } /* EratoVec: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=6 ms m=10000000, n=664579, t=63 ms m=100000000, n=5761455, t=973 ms m=1000000000, n=50847534, t=10958 ms */Malheureusement, EratoVec est encore plus lent, c'est-à-dire que son temps d'exécution correspond environ au double de celui de EratoD (qui utilise bool).
U8 *EratoBit8(U32 mx) { U8 *bs8=(U8*)malloc(1+mx/8); bs8[0]=0xAC; memset(bs8+1,0xAA,mx/8); for (U32 p=3; p*p<=mx; ++p) if (B8get(bs8,p)) for (U32 q=mx/p; q>=p; --q) if (B8get(bs8,q)) B8set0(bs8,p*q); return bs8; } /* EratoBit8: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=3 ms m=10000000, n=664579, t=37 ms m=100000000, n=5761455, t=634 ms m=1000000000, n=50847534, t=7573 ms */
U16 *EratoBit16(U32 mx) { U16 *bs16=(U16*)malloc(2*(1+mx/16)); bs16[0]=0xAAAC; for (U32 n=1; n<=mx/16; ++n) bs16[n]=0xAAAA; for (U32 p=3; p*p<=mx; ++p) if (B16get(bs16,p)) for (U32 q=mx/p; q>=p; --q) if (B16get(bs16,q)) B16set0(bs16,p*q); return bs16; } /* EratoBit16: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=3 ms m=10000000, n=664579, t=42 ms m=100000000, n=5761455, t=636 ms m=1000000000, n=50847534, t=7580 ms */
U32 *EratoBit32(U32 mx) { U32 *bs32=(U32*)malloc(4*(1+mx/32)); bs32[0]=0xAAAAAAAC; for (U32 n=1; n<=mx/32; ++n) bs32[n]=0xAAAAAAAA; // bits impairs for (U32 p=3; p*p<=mx; ++p) if (B32get(bs32,p)) for (U32 q=mx/p; q>=p; --q) if (B32get(bs32,q)) B32set0(bs32,p*q); return bs32; } /* EratoBit32: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=4 ms m=10000000, n=664579, t=39 ms m=100000000, n=5761455, t=642 ms m=1000000000, n=50847534, t=7547 ms */
U64 *EratoBit64(U32 mx) { U64 *bs64=(U64*)malloc(8*(1+mx/64)); bs64[0]=0xAAAAAAAAAAAAAAAC; for (U32 n=1; n<=mx/64; ++n) bs64[n]=0xAAAAAAAAAAAAAAAA; for (U32 p=3; p*p<=mx; ++p) if (B64get(bs64,p)) for (U32 q=mx/p; q>=p; --q) if (B64get(bs64,q)) B64set0(bs64,p*q); return bs64; } /* EratoBit64: m=10, n=4, t=0 ms m=100, n=25, t=0 ms m=1000, n=168, t=0 ms m=10000, n=1229, t=0 ms m=100000, n=9592, t=0 ms m=1000000, n=78498, t=3 ms m=10000000, n=664579, t=42 ms m=100000000, n=5761455, t=648 ms m=1000000000, n=50847534, t=7542 ms */
Commentaires
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.