Petit test du crible d'Eratostène

Vous débutez et vous avez besoin d'aide ? N'hésitez pas à poser vos questions
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Petit test du crible d'Eratostène

Message par Ollivier »

Erratum : ça ne crible que les doubles (nombres pairs) ! J'ai voulu remplacer la multiplication par des additions : manque de bol, il faut un registre supplémentaire. Comme tous les registres volatiles sont utilisés, je dois donc en choisir un supplémentaire non volatile, ici RBX qui doit être sauvegardé avant utilisation (avec Push), et restauré (restitué, etc... : qu'importe le jargon, un registre non volatile, ça s'appelle "revient" !) avec Pop. Je laisse plus bas mon code source bugué et rajoute ici le bon code : (avec ce lien vers un autre code source semblable utilisant seulement les registres volatiles mais ayant besoin d'une multiplication par nombre premier trouvé).

Code correct :

Code : Tout sélectionner

Define max.I = 1048576
Dim ps.I(max - 1)

Define *ps = @ps(0)
ps(0) = %11 ; one (bit 1) and zero (bit 0) are not prime
t0 = ElapsedMilliseconds()

! push rbx
! mov rdx, [v_max]
! mov r9, [p_ps]
! shl rdx, 6
! xor rax, rax ; the test starts from zero plus one
! mov rcx, 1
! xor rbx, rbx
thenextone:
! add rbx, rcx
! inc rax ; we test everything, the even ones, even...
! add rcx, 2
! bt qword [r9], rax ; if GetBit(rax)
! jc l_thenextone ; goto thenextone: endif
isprime:
! mov r8, rbx
! cmp rbx, rdx
! jae l_fin
stamp:
! bts qword [r9], r8 ; BitSet(r8)
! lea r8, [r8+rax]
! cmp r8, rdx
! jb l_stamp
! jmp l_thenextone
fin:
! pop rbx
t1 = ElapsedMilliseconds()
Debug "Nombres testés : " + Str(max * 64)
For i = max - 16 To max - 1
Debug Str(i) + " : " + Bin(ps(i) )
Next
Debug Str(t1 - t0) + " ms"




Ancien message (erroné) :

Je partage ce petit code, qui crible tous les nombres composites (nombres non premiers) dans le tableau ps(). Ça se passe en X86-64. Utilisation des registres volatiles seulement. Les instructions BT et BTS ont été vues par djes il y a 5 ans (déjà...).

Code : Tout sélectionner

Define max.I = 1048576
Dim ps.I(max - 1)

Define *ps = @ps(0)
ps(0) = %11 ; one (bit 1) and zero (bit 0) are not prime
t0 = ElapsedMilliseconds()

! mov rdx, [v_max]
! mov r9, [p_ps]
! shl rdx, 6
! xor rax, rax ; the test starts from zero plus one
! mov rcx, 1
! xor r8, r8
thenextone:
! add r8, rcx
! inc rax ; we test everything, the even ones, even...
! add rcx, 2
! bt qword [r9], rax ; if GetBit(rax)
! jc l_thenextone ; goto thenextone: endif
isprime:
! cmp r8, rdx
! jae l_fin
stamp:
! bts qword [r9], r8 ; BitSet(r8)
! lea r8, [r8+rax]
! cmp r8, rdx
! jb l_stamp
! jmp l_thenextone
fin:
t1 = ElapsedMilliseconds()
Debug max * 64
For i = max - 16 To max - 1
Debug Str(i) + " : " + Bin(ps(i) )
Next
Debug Str(t1 - t0) + " ms"
manababel
Messages : 135
Inscription : jeu. 14/mai/2020 7:40

Re: Petit test du crible d'Eratostène

Message par manababel »

Bonjour Olivier

voici un lien sur ce sujet.

https://www.purebasic.fr/french/viewtop ... lit=primes
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Petit test du crible d'Eratostène

Message par Ollivier »

J'ai lu : ici, je bouffe 8 méga de RAM pour environ 4 millions de nombres premiers stockés en direct en 800ms.
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Petit test du crible d'Eratostène

Message par Ollivier »

Le 17/10/2016, djes a écrit :Pour les benchmarks, je me suis amusé à coder un petit programme de recherche, pas du tout optimisé mais 64 bits, et pour aller jusqu'à 10^9, le programme de fweil met 7 secondes, et le mien ... 155 secondes !

Battu par KO, je vais me coucher
J'utilise les mêmes instructions ASM que djes et je n'ai pas du tout une bête de guerre comme ordinateur.

Entre 155 secondes et 800ms, hormis quelques succintes optimisations dans mon code plus haut, cela signifie surtout que le fabricant de CPU a lourdement optimisé ces instructions concernant les manip au bit près (bt, bts, btr et btc) qui ont une prédiction telle qu'il devient presqu'inutile d'optimiser les multiples de 2 ! (j'atteinds 700ms)
Répondre