Petit test du crible d'Eratostène
Publié : lun. 14/juin/2021 6:10
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 :
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 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"