Merci pour le compliment, je pense que nous prenons tous un certain plaisir à nous triturer ainsi les méninges ! La page que tu fournis est très impressionnante, j'ai l'impression de recréer chacune des améliorations au fur et à mesure ! Pourtant je ne me documente presque pas, car ici je m'amuseStarwolf20 a écrit :Djes : je suis vraiment impressioné par l'elegance et les performances de ton dernier code.
Ce thread est super interessant et les echanges entre Djes, Fweil et Ollivier passionants.
NB : je suis tombé sur ce lien http://compoasso.free.fr/primelistweb/p ... sthene.php
Je le soumets a votre sagacité.
J'ai vu qu'à la fin il parle de masques, j'en parlais précédemment, si on s'amuse à faire des masques (et avec mini 64 bits, il y a de quoi faire), on peut cribler à toute vitesse, et ça ferait gagner pas mal de temps.Bon, bon, on le sait bien ! J'espère quand même qu'Ollivier va nous pondre un truc miraculeux pour sauver l'honneurfweil a écrit :Bon pour le résultat final, mon 1e12 sort en moins de 3.000 secondes calcul et statistiques sur les écarts compris. C'est pas pour me la péter, mais je vais plus vite ... et plus loin grâce à la pagination.
Moi, pour le moment, je suis sur un travail de compression des nombres, car si on veut travailler plus loin, il faudra y passer. J'ai bricolé un truc sur les écarts. C'est améliorable ! Le fichier des écarts résultant est plus gros que le fichier des np, certes, mais regardez sa composition
En le compressant en zip, on voit tout de suite qu'on y gagne... (nb : le code est moins propre, c'est du test...)
Code : Tout sélectionner
;All rights reserved :) All rights reversed :)) Feel aaaaaalright !!!
#Max = 100000000
EnableExplicit
Define u.i, time.i, counter = 0, file
Define *pn.INTEGER, *sieve.INTEGER
Define lastpn.i
OpenConsole()
;-*** Primes lookup ***
*pn = AllocateMemory(#Max)
*sieve = AllocateMemory(#Max / 8 )
time = ElapsedMilliseconds()
u = 3 ;start after the "2"
EnableASM
mov rax, u
mov r9, rax
mov rdx, *sieve
mov rbx, *pn
;*** 1 is set manually ;)
mov qword [rbx], 1
add rbx, 8
;***
!LP:
;If BitNotSet(*sieve, u)
bt [rdx], rax
jc BITSET
;Store pn number
mov [rbx], rax
add rbx, 8
;Sieve(*sieve, u)
mov rcx, rax
mov r8, #Max
!@@:
bts [rdx], rax
add rax, rcx
cmp rax, r8
jl @b
!BITSET:
add r9, 2 ;jump over even numbers
mov rax, r9
cmp r9, #Max
jl LP
; How many pn ? (rbx - *pn) / 8
sub rbx, *pn
shr rbx, 3
mov counter, rbx
DisableASM
time = ElapsedMilliseconds() - time
PrintN("Time elapsed : " + Str(time) + " ms")
FreeMemory(*sieve)
file = CreateFile(#PB_Any, #PB_Compiler_FilePath + "primes-org.txt")
WriteStringN(file, "2, ")
For u = 1 To counter - 1
WriteStringN(file, StrU(PeekI(*pn + u * 8)) + ",")
Next u
WriteStringN(file, "Found " + counter + " prime numbers")
lastpn = PeekI(*pn + counter * 8 - 8)
PrintN("Found " + counter + " prime numbers")
;- *** Crunching ***
PrintN("Let's start the crunch demo")
Define *pnPtr.INTEGER = *pn, n.i, *gaps, *gapsPtr.INTEGER, gapsNb.i
*gaps = AllocateMemory(#Max * 8)
*gapsPtr = *gaps
;First operation : pn / 2 (as a pn is always after a multiple of 2)
For u = 0 To counter - 1
*pnPtr\i = *pnPtr\i >> 1
*pnPtr + 8
Next u
*pnPtr = *pn
For u = 0 To lastpn / 2 + 2
;store only the gaps in the (0, 1, 2, 3, 4, 5, ...) serie
If *pnPtr\i = u
*pnPtr + 8
Else
*gapsPtr\i = u
*gapsPtr + 8
EndIf
Next u
gapsNb = (*gapsPtr - *gaps) / 8
PrintN("Found " + StrU(gapsNb) + " gaps")
FreeMemory(*pn)
Define *crunched, *crunchedPtr.INTEGER
*crunched = AllocateMemory(#Max * 8)
file = CreateFile(#PB_Any, #PB_Compiler_FilePath + "primes-crunched.txt")
*gapsPtr = *gaps
*crunchedPtr = *crunched
n = 0
For u = 0 To gapsNb - 1
;store the difference between two gaps
*crunchedPtr\i = *gapsPtr\i - n
n = *gapsPtr\i
WriteString(file, StrU(*crunchedPtr\i) + ",")
*crunchedPtr + 8
*gapsPtr + 8
Next u
CloseFile(file)
FreeMemory(*gaps)
PrintN("Done ! ")
;- *** Uncrunching ***
PrintN("Let's start the uncrunch")
*gaps = AllocateMemory(#Max * 8)
*gapsPtr = *gaps
*crunchedPtr = *crunched
n = 0
For u = 0 To gapsNb - 1
;extract the difference between two gaps
n + *crunchedPtr\i
*gapsPtr\i = n
*crunchedPtr + 8
*gapsPtr + 8
Next u
*pn = AllocateMemory(#Max * 8)
*pnPtr = *pn
*gapsPtr = *gaps
For u = 0 To lastpn / 2 + 2
;recreate the pn based upon gaps
If u <> *gapsPtr\i
*pnPtr\i = u
*pnPtr + 8
Else
*gapsPtr + 8
EndIf
Next u
FreeMemory(*gaps)
*pnPtr = *pn
For u = 0 To counter - 1
*pnPtr\i = *pnPtr\i << 1 + 1
*pnPtr + 8
Next u
;- PN definition bugfix ;)
*pn\i + 1
file = CreateFile(#PB_Any, #PB_Compiler_FilePath + "primes-uncrunched.txt")
For u = 0 To counter -1
WriteStringN(file, StrU(PeekI(*pn + u * 8)) + ",")
Next u
FreeMemory(*pn)
WriteStringN(file, "Found " + counter + " prime numbers")
CloseFile(file)
PrintN("Found " + counter + " prime numbers")
PrintN("Press enter to exit...")
Input()
CloseConsole()Code : Tout sélectionner
;Primes nb lookup with trial division
; (c)djes 2016
; http://www.purebasic.fr/french/viewtopic.php?p=187333#p187333
Min = 100000000000000003
Max = 100000000000000100
EnableExplicit
Define u.i, i.i, n.i, time.i, counter = 0, sqrt.i
Define *pn, *sieve
OpenConsole()
If Max > 2 And Max >= Min + 1 And Min >= 3
If Min & 1 = 0
Min + 1
EndIf
PrintN("Lookup for primes between " + Str(Min) + " and " + Str(Max))
For i = Min To Max Step 2
sqrt = Int(Sqr(i) + 1) ;beware of the int() !
time = ElapsedMilliseconds()
For n = 3 To sqrt Step 2
u = i / n
If u * n = i
Break
EndIf
Next n
If n >= sqrt
Print(Str(i) + ", ")
Print("time elapsed : " + Str(ElapsedMilliseconds() - time) + " ms (div/mul), ")
EndIf
time = ElapsedMilliseconds()
For n = 3 To sqrt Step 2
If i%n = 0
Break
EndIf
Next n
If n >= sqrt
counter + 1
Print(Str(i) + ", ")
PrintN(Str(ElapsedMilliseconds() - time) + " ms (modulo)")
EndIf
Next i
PrintN("Finished !")
PrintN("Found " + Str(counter) + " primes numbers ")
PrintN("")
PrintN("Press enter to exit")
Input()
CloseConsole()
EndIf
