Page 7 sur 11

Re: A propos de nombres premiers

Publié : ven. 21/oct./2016 10:13
par fweil
@djes,

Tu mets bien le doigt sur le bon point. Pour traiter des plages où la portée est réduite, le traitement par bits est intéressant par rapport à la compression de la représentation des nombres.

Je crois avoir beaucoup travaillé, dans ma vie sur le sujet, pour savoir qu'on ne peut pas en attendre grand chose de plus.

La limite des algorithmes de traitements sur les nombres premiers tient beaucoup plus au fait que pour en traiter de grandes quantités, il faut dresser des mécanismes encombrants, et l'approche permettant de "plier" l'encombrement est une approche qui libère partiellement de cette limite.

Maintenant, jusqu'à prochainement, j'ai limité la portée de mon travail sur le sujet à une représentation 64 bits (donc d'une façon ou d'une autre à des nombres dans la plage 0 - 1e18).

Dans une étape prochaine, je vais m'intéresser à la méthode induite pour dépasser cette contrainte. Ce sera par l'utilisation d'une arithmétique représentative des nombres en 128, 256, 512 bits tout en utilisant le composant clef, le processeur, qui lui reste un processeur 64 bits (je pense que ce sera encore le cas pour un certain temps !). Et dans cette prochaine étape, je voudrais parvenir à dépasser la limite des 64 bits en entrenant un niveau de performances aussi canon.

Je suis en train de m'acharner en temps partiel ces jours-ci pour rédiger une version qui finalisera l'étape actuelle, et dans laquelle les performances seront je crois sensiblement améliorées, en vue de passer aux nombres représentés sur plus de 64 bits.

Entre temps mon matheux de coéquipier sur ce projet m'a donné du grain à moudre pour ajouter une touche au processus de calcul, en installant des tests rigoureux de validation des résultats. Parce que là-dedans, il faut en plus amener la preuve que les suites de premiers que donnent les programmes sont bien vraies et que le programmeur pas plus que le calculateur ne commentent d'erreur :)

Je mettrai ici les points intéressants dans une proche livraison de code mis à jour.

Re: A propos de nombres premiers

Publié : ven. 21/oct./2016 10:41
par djes
Super, tiens-nous au courant ! Cette partie est vraiment difficile, car elle dépasse forcément nos capacités d'entendement. Personnellement, j'ai déjà un mal de chien à différencier la représentation d'un nombre, et sa réalité physique... C'est bien que tu puisses travailler en équipe, et que ce soit avec un matheux ! Je te trouvais déjà pas mal dans le genre... ;)

Sinon, pour le fun, à cause de toi (grâce aussi ;)), je vais faire une petite version assembleur de mon code, parce que forcément, c'est celui que je maîtrise le mieux. Je viens de voir qu'en 64 bits, les instructions étaient très puissantes. Il y en a une que je viens de découvrir : http://www.tptp.cc/mirrors/siyobik.info ... n/BSF.html, et j'ai envie de tester !

Re: A propos de nombres premiers

Publié : ven. 21/oct./2016 11:53
par Ollivier
@PAPIPP

Tes résultats semblent être exécutés sur une version 32 bits : est-ce que tu peux préciser si c'est avec le compilateur en 32 ou 64 bits?

Aussi, merci d'avoir fait le test et rendu tes résultats.

Re: A propos de nombres premiers

Publié : ven. 21/oct./2016 12:35
par djes
Voici la première version optimisée, qui ne fait que jouer avec les instructions de set/test de bits sur la plage mémoire. C'est beaucoup plus rapide, même si ces instructions sont très lentes en accès direct.
Si j'ai le temps, je ferais une version qui fera le boulot en travaillant avec des registres et en les utilisant pour masquer la mémoire à grands coups de OR de 64 bits (minimum vu qu'on a des registres bien plus grands maintenant).

Code : Tout sélectionner

;All rights reserved :) All rights reversed :)) Feel aaaaaalright!!!
#Max = 1000000

EnableExplicit

Define u.i, time.i, counter = 0, file, filename.s = #PB_Compiler_FilePath + "primes64.txt"
Define *pn, *sieve

OpenConsole()

file = CreateFile(#PB_Any, filename)
If file
  
  PrintN("Successfully created file " + filename)
  
  *pn = AllocateMemory(#Max )
  If *pn
    
    PrintN("Successfully allocated prime numbers memory of " + Str(#Max) + " bytes")
    
    *sieve = AllocateMemory(#Max / 8)   
    If *sieve
      
      PrintN("Successfully allocated sieve memory of " + Str(#Max / 8) + " bytes")
      
      time = ElapsedMilliseconds()
      
      u = 3 ;start after the "2"
      EnableASM
      
      mov rax, u
      mov r9, rax
      mov rdx, *sieve
      mov rbx, *pn
      !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
      sub rbx, *pn
      shr rbx, 3
      mov counter, rbx
      DisableASM        
            
      time = ElapsedMilliseconds() - time
      
      PrintN("Time elapsed : " + Str(time) + " ms")
      WriteStringN(file, "Time elapsed : " + Str(time) + " ms")
      
      WriteStringN(file, "2, ")
      For u = 0 To counter - 1
        WriteStringN(file, StrU(PeekI(*pn + u * 8)) + ", ")
      Next u
      counter + 1
      
      WriteStringN(file, "Found " + counter + " prime numbers")
      PrintN("Found " + counter + " prime numbers")
      
      FreeMemory(*sieve)
      
    Else
      PrintN("Can't allocate sieve memory")
    EndIf
    
    FreeMemory(*pn)
    
  Else
    PrintN("Can't allocate prime numbers memory")
  EndIf
  
  CloseFile(file)
  
Else
  PrintN("Can't create file " + filename)
EndIf


PrintN("Press a key to exit...")
Input()
CloseConsole()

Re: A propos de nombres premiers

Publié : ven. 21/oct./2016 23:40
par Ollivier
@fweil

Si tu peux évoquer à ton ami mathématicien cette divergence que l'on a eu sur le départ du crible de chaque premier :
- 2P pour toi
- P * P pour moi

Cette divergence est essentielle pour la suite des événements. Car 2P, effectivement, ça simplifie plein de choses, en virtualisation, c'est clair que ça cartonne.

Mais P*P, ce n'est pas moi qui le veut : ce sont les maths. Ça apporte un lot de coïncidences tout aussi riche en numérique naturelle que 2P en apporte en numérique binaire.

En admettant P un nombre premier, et P(x) le x ième nombre premier.
P(1) = 2
P(2) = 3
P(3) = 5
P(4) = 7
Etc...
(On aurait pu commencer à P(0) = 2, mais bon...)

Je voulais tout simplement économiser de l'écriture de crible au strict minimum, en partant du principe que je vais cribler avec une suite strictement croissante de nombres premiers. (2 puis 3 puis 5 etc...).

Par conséquent, si c'est croissant, quand j'arrive à un nombre premier au pif P(x), tous les multiples < P(x) ont déjà été criblés : c'est le principe d'Erathos.

Mais qu'en est-il de l'état du criblage de P(x) + 1 ? Si P(x) <> 2, P(x) + 1, est forcément multiple de 2, donc déjà criblé alors que... Ben, on y est pas encore !
(Nota : on pouvait écrire l'équivalent
"Si x <> 1, P(x) + 1 est forcément multiple de P(1)")

Alors, qu'en est-il des états de criblage déjà effectués avec P(x) + y ?

Sans vouloir (ni pouvoir) déterminer y, là, on se rend compte qu'avec la permutabilité de la multiplication, il est inutile de cribler les produits z * P(x) tel que z < P(x), puisque, dans le cas d'un procédé strictement croissant, ces cribles ont déjà été effectués. Donc z >= P(x). Le criblage peut commencer avec z = P(x) (borne minimum de l'inéquation z >= P(x) ) donc, avec P(x) * P(x).

Aussi, toujours avec P(x), l'on constate un crible partiel assuré de manière périodique de 0 à l'infini.

La valeur de cette période est :
P(x - 1) * P(x - 2) * ... ... * P(1)
Ce charabia ressemble à une factorielle :
(x) * (x - 1) * (x - 2) * ... ... * 1
Mais, à ceci près qu'au lieu de multiplier x tout seul à chaque terme, on multiplie le x ième nombre premier à chaque terme.

Par convention, écrivons pFact(a) (ou p-fact(a) ) la "prime-factorielle" de a.

Ainsi pFact(5) = 5 * 3 * 2 * 1 = 30
Aussi pFact(5) = 5 * 3 * 2 = 30 : c'est moins "source de débat".

Pourquoi, pour P(x) existe-t-il un crible périodique partiel à partir P(x) * P(x) ?
Et pourquoi cette période est pFact(x - 1) ?
Et puis, qu'est-ce qu'un crible périodique partiel ?

De 3 à 1, on va considérer que...

Un crible périodique partiel (nommons cpp), c'est un crible (ou ensemble fini de naturels)
- qui s'inscrit en strict complément au crible d'Erathos simplifié aux seuls nombres premiers,
- qui ne contient donc absolument aucun nombre premier
- qui admet une répétition périodique à partir d'une valeur de départ (nommons ça une phase) jusqu'à l'infini

Ex (avec N > 0)
2N n'est pas un crible partiel mais c'est un crible quelconque
2(N + 1) est un cpp de période 2
3(N + 1) est un cpp de période 3

(avec x > 0)
x * (N + 1) sont des cpp de période x
P(x) * (N + 1) sont des cpp de période P(x)

P(x) * P(x) * (N + 1) sont des cpp de période (P(x) * P(x) )
pFact(x) * (N + 1) sont des cpp de période pFact(x)

Maintenant, ce qui nous intéresse c'est d'associer à P(x) le cpp disposant de la période la plus grande.
Pourquoi? Pour aller plus vite informatiquement, dès qu'on constate P(x).

On a constaté, plus haut, dès la différence entre 2N et 2(N + 1) que la position de départ est très importante.
La phase est très importante.

Pourquoi le cpp associé à P(x) tel que x > 1 admet une période maximum de
pFact(x - 1)
avec une phase P(x) * P(x)
?

Pour les deux mêmes raisons qui nous permis de trouver la phase minimum P(x) * P(x) :
- Permutabilité de l'opération de multiplication pour les nombres entiers naturels
- Croissance stricte de P(x)

Mais aussi, parce que la position des nombres premiers étant strictement complémentaire à la position des nombres multiples, chaque multiple d'un naturel proscrivant sa possibilité d'être un nombre premier, et chaque multiple d'un produit de termes naturels s'inscrivant dans cette même proscription, la succession contigüe des naturels avec chaque naturel étant périodique, les exclusions de nombres d'être premier sont aussi périodiques, d'une part, et par logique de consensus complémentaire (théorie des ensembles, je suppose), les plus petits diviseurs de chaque produit possible de nombres naturels "supérieurs à un" (pour ne pas annuler la notion de plus petit diviseur) sont les seuls entiers naturels pouvant appartenir au termes du produit formant chaque période d'exclusion des nombres naturels à la candidature au status de nombre premier. Ces plus petits diviseurs étant déjà démontrés comme nombre premier, l'on use de la confortable opération pFact(lambda) pour inventorier ces nombre premiers connus dans la forme d'un produit, et parce que P(x) est déjà "considéré" dans la phase du cpp (P(x) * P(x), et non pas P(x) * 2 qui est une constante donc qui gèle la possibilité d'évoluer mathématiquement.), l'on l'exclut par la réciproque de la multiplication : la division.

pFact(lambda) / P(x)

lambda étant x, on a :

pFact(x) / P(x) (qui, par simplification factorielle donne)

pFact(x - 1)

Ceci est donc la période maximale du cpp correspondant à P(x).

Ainsi, pour le nombre premier P(x) = 5, on va chercher pFact(x-1).
3 étant le nombre premier précédant 5, on a
pFact(3) = 3 * 2 = 6
Le cpp aura une période de 6.
La phase de criblage est à 25.
Toutes les combinaisons de produits de 3 et 2 (les nombres premiers déjà connus avant 5) guideront le criblage périodique par "homothétie" de coefficient.
5 donc ce sont les gaps après 5 qui nous intéressent (c'est un rappel du "protocole" sans faute, valable sans limite jusqu'à l'infini, que je t'ai écrit dans ce sujet, chaque étape bien numérotée) :

Code : Tout sélectionner

Après 5, on a 7  donc gap = 2
Après 7, on a 11 donc gap = 4
On a 2 gaps qui totalisent notre période de 6 : 2 + 4

Avec 25 criblé multiple, on ajoute 2 * 5
On crible donc 35
Avec 35 criblé multiple, on ajoute 4 * 5
On crible donc 55

Et rebelote à l'infini

C'est quand même cool, un processus qui crible uniquement ce qu'il faut à l'avance !

Maintenant, les factorielles étant "explosives" numériquement, il faut trouver un juste milieu, et se servir de chaque période (ce que je t'ai dit appeler une chenille de char d'assaut) comme le maillon d'une....

fractale.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 0:58
par fweil
Ollivier, la réponse est simple.

Même si ton argumentaire est correct, ce que je pense vraiment, il pose justement un problème, c'est qu'il rend le travail compliqué en regard d'un système qui ne fait que sauter d'une case à une autre en utilisant le premier principe de base du crible d'Erathostène. Pour les 2 je vais de 2 en 2, ce qui est le cas le plus coûteux. Pour les 3 je vais de trois en 3, et pour chaque nouvelle colonne, je prend le i-ème premier et je vais de Pi en Pi (c'est un beau voyage !).

Donc pour passer une "page" de nombres de 1 à n avec PI(racine(n)) compteurs (PI() étant la fonction approchée racine(n) / (Ln(racine(n) - 1)), je vais avoir en fait simplement n / 2 + n / 3 + n / 5 + n / 7 + n / 11 ... opérations, ce qui est une suite dont la limite tend vers l'infini quand n tend vers l'infini, mais la limite croît très lentement et pour n voisin de 1e15 ou 1e18, ça donne en fait une valeur comprise entre 3n et 4n ce qui est extrêmement peu de travail comparé à toutes les autres méthodes.

Il est vrai que je n'économise pas le fait de passer sur des cases déjà cochées (des nombres composites déjà identifiés), mais qu'importe ... c'est une bien petite dépense face à toute autre approche.

Dans la mesure où on se contente de vouloir filtrer les premiers plus petits que 1e50 ou 1e100, en termes de calculs effectués, c'est incomparablement plus efficace.

Je n'ai pas analysé vraiment à partir de quel moment une méthode par crible sans précaution (c'est une litote pour qualifier ma rédaction du crible) devient moins intéressante qu'une approche filtrant exactement les endroits à visiter dans la page, mais c'est loin, très loin de nombres représentés en 64 bits, probablement même de nombres représentés en 128 bits.

Ca renvoie un peu au lièvre et à la tortue, avec la tortue qui va gagner la course parce que le lièvre foleye ... et que la durée de la course n'est pas trop longue. Mais on comprend bien avec un minimum de bon sens que si le 100 mètres est transformé en marathon, jamais la tortue n'arrivera première :)

Je ne prétends pas faire une compétition avec qui que ce soit, et surtout pas aller trouver des nombres premiers à 1.000 chiffres Donc dans des portées numériques raisonnables, il n'est pas intéressant de monter des mécanismes sophistiqués. Le seul but est de prendre ce qui est le plus rapide. Et il n'y a pas à chercher longtemps pour voir que les sauts directs et les mises à 1 des éléments du tableau sans aucun test ni autre opération sont les séquences les plus brèves possibles.

J'ai bien regardé toutes les approches de cribles modernes, il en existe un certain nombre maintenant sur papier, mais aucun ne peut donner meilleure satisfaction pour s'appliquer sur des plages de nombres situées "au début" de N.

Ecrit comme je l'ai écrit, l'algorithme répond bien aux objectifs suivants :

- résoudre l'inventaire des nombres premiers jusqu'à 1e18 au maximum, et rendre 1e12 accessbile en un temps très raisonnable sur un PC
- disposer d'un programme capable d'exploiter 100% d'un processeur multi-cœurs d'aujourd'hui.

Dans toutes les écritures qu'on trouve un peu partout, 1e12 est la limite possible qu'on ne sait pas atteindre sur PC, parce que ça prend des heures. J'ai fait tomber le temps à moins d'une heure pour l'instant sur mon PC. Dans ma tête j'ai ... sur le bout de la langue ... une hypothèse non aboutie pour diviser ça encore un peu, mais je ne suis pas sûr d'arriver à l'écrire.

En théorie, mal écrit, 1e12 représente 1e12 * 4 cycles de traitement si on compte à la louche, ce qui peut correspondre à 1e13 * 4 instructions de base. Pour un processeur qui peut produire 10G instructions par secondes, il est raisonnable de penser qu'une heure suffit pour faire ça, voire la moitié.

Je n'en suis pas bien loin.

Au-delà je ne sais pas comment on pourrait faire un progrès significatif.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 7:34
par Ollivier
@fweil

Mon argumentaire n'est pas si correct que tu le dis :
- Il est aussi désordonné que la taille de l'écran que j'ai utilisé est petit !
- Il manque une pluie de "avec telle variable > 1"

Je dis juste que si tu sais virtualiser (P + P * N) comme tu le fais excellemment bien, alors tu sais virtualiser le cas général (ax+b). (avec x un naturel > 1 strictement)

Ton cas de virtualisation c'est :
a = 2 * P
b = P
avec 1 solution par pas et x > 1

Est-ce que tu penses impossible (ou pas rentable en ressource CPU), dans un 1er temps de virtualiser tel que :
a = 30 * P
b = P * P
?

Ce sont de simples saut 30 fois plus grands. (Après, on peut aller jusqu'à des sauts 30 000 fois grands avec un ordi actuel sans bouffer lourd de mémoire).

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 9:42
par fweil
@Ollivier, je pense que ça ne pose pas de problème de faire des sauts 30 fois plus grands, mais quel est l'intérêt ?

Au bout du compte, si tu veux marquer les premiers, ou inversement marquer les composites, tu devras bien aller dans chaque case au moins une fois. Et tu ne peux pas aller réellement dans deux cases à la fois. Ca c'est un point pour lequel il faut absolument que tu sois convaincu du fait. Vectorisation ou pas, le parallélisme au niveau processeur ne prend un intérêt qu'à l'intérieur du processeur.

De ce constat, l'optimisation la plus importante vient du fait que tu dois tenter de faire le moins de travail possible pour atteindre toutes les cibles du crible.

Le crible (d'Erathostène) est un mécanisme qui prend pour principe d'éliminer les composites. Parce que tout simplement il est impossible de faire le contraire.

Pour faire ce travail le seul moyen est de pointer les "multiples de ...". Quel que soit le raisonnement que tu fais sur la manière de gérer les sauts tu devras atteindre autant de composites.

Dans la méthode que j'ai choisi, je sais que je tape un certain nombre de cases plusieurs fois. Dans toute autre méthode on tapera aussi des cases plusieurs fois. Tu peux essayer ce que tu veux comme approche, ça tapera toujours les cases plusieurs fois à certains endroits. Ce n'est pas divinatoire ce que je dis, mais jusqu'au jour où on aura une méthode qui peut prédire qu'un nombre est premier avant de l'avoir vérifier, on ne saura pas faire autrement que de pointer les composites autant de fois qu'ils ont de diviseurs entiers.

Dans mon écriture je limite le nombre de pointages aux diviseurs entiers premiers dans une plage de 2 à racine(nmax) pour une plage d'entiers testés allant de nmin à nmax. Peut pas faire mieux. A la main, au tableau, dans l'ordi, peut pas faire mieux. Je fais des plages nmin-nmax assez petites pour permettre au système de travailler au maximum en mémoire cache et pour faire en sorte que le 2 à racine(nmax) soit toujours au plus juste (plus la plage nmin-nmax est grande, plus la perte est importante en opérations inutiles pour les valeurs de n "loin" de nmax).

Je ne crois pas, pour l'instant en tout cas, que des sauts plus larges permettent de paralléliser concrètement quoi que ce soit. En tout cas, je ne parviens à voir comment si je me mets en tête le fonctionnement d'un CPU face à sa mémoire vive.

Le parallélisme qui fonctionne est celui qui consiste à mettre plusieurs CPU en jeu au même moment, mais pas des nombres en parallèle dans une même unité arithmétique et logique.

Pour la vectorisation d'un calcul, ce qui peut fonctionner correctement consiste à mettre plusieurs données en parallèle et à lancer une même opération sur chaque donnée. On obtient effectivement le résultat en parallèle en presque un seul cycle (pas tout à fait d'ailleurs). Ceci s'applique bien si on utilise le test de primalité par modulo ou divisions. Et cette approche ne donne pas des résultats intéressants parce qu'elle est trop longue dans le cas d'un traitement effectué par une machine ne disposant pas de centaines de processeurs ou plus (le rendement est vraiment très pauvre en fait et il faut utiliser des centaines de cœurs pour arriver à aller aussi vite qu'un crible dans le cas de calculs effectués sur des longues plages).

Si l'écart entre deux nombres premiers successifs était un élément prédictible, ou si il était constant, on pourrait imaginer paralléliser le calcul des pointeurs pour marquer le tableau (mais de fait on aurait pas besoin de faire ça puisqu'on connaitrait le résultat du test de primalité par avance). Or et justement les gaps entre nombres premiers, sujet principal de mon programme, ne sont pas prédictible de manière exacte, ni même approximative parce que jusqu'à maintenant les nombres premiers sont "imprévisibles". Donc on ne peut pas améliorer une technique de pointage par vectorisation.

Ce qu'on peut espérer faire avec une vectorisation est d'utiliser un crible statistique ou autre, qui permet d'éliminer des nombres dont on sait par le raisonnement qu'ils ne seront pas premiers. Sauf que les cribles de ce type ne donne pas une réponse au test de primalité, et qu'ils sont coûteux. Ils permettent de bien répondre à l'accélération d'un test de primalité ponctuel pour un nombre très grand. Ce n'est pas approprié pour tester une plage de nombres importante.

Optimiser le crible revient donc à chercher les solutions les plus économiques en instructions CPU, minimiser autant que possible les cycles de criblage inutiles.

Voilà, j'espère que tout ça éclaire un peu la réflexion.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 10:55
par Ollivier
Si le crible était une voie ferrée et l'instruction AVX OU logique d'un pack de plusieurs quad un aiguillage pour fusionner les états logiques normalement multiples, il va falloir tester en mémoire alignée, quelle est la fréquence maximale de traitement. Je pense que cette valeur sera effectivement ta limite locale.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 11:52
par Ollivier
Maintenant, pour le reste, "heureusement" que je ne suis pas d'accord avec toi !
Je te dis et je t'explique qu'en prolongeant une logique mathématique (ou arithmétique), tu obtiens un système qui ne crible que le strict nécessaire.

C'est très important à comprendre, car cela t'indique que ta limite de traitement va tendre vers la vitesse du "hard-copy" matériel.

Toi, tu as conçu un super système qui crible. Mais, en cherchant l'optimisation, tu as amputé ce système de son grossissement d'échelle numérique.

Pourtant, je tente (et je vais réussir !) de te faire revenir à la raison (j'exagère, au temps pour moi !), par tes propres armes que tu connais mieux que moi.

Tu sais que mathématiquement, les nombres premiers se raréfient.
A priori, les multiples à cribler s'accumulent.
Mais, maintenant, tu "connais" un système mathématique qui ne crible quasiment que ce qu'il y a à cribler (dans le même code source Pif7() tu as la variable nn qui comptabilise les exceptions : je crois que c'est autour de 29 000 exceptions pour un total de 55 millions de nombres premiers détectés, soit moins de 0.1% !! Et Pif11, ça diminue, Pif13 ça diminue encore, pif17 ça diminue encore et toujours, et, je pense que ça sera notre limite "humaine" : la fameuse période de 30030 ou pFact(13) étant là, ça nous fera un stock de gabarit de cribles pré-calculés d'une soixantaine de kilo-octets)
Ce n'est pas un système logiciel, mais un système mathématique. Donc il demande à être ultérieurement appliqué en tant que logiciel.
Vu que tu as déjà conçu une virtualisation, tu vas retrouver un algo assez proche du tiens.

Ce système mathématique se base sur les nombres premiers qu'il détecte pour cribler. Comme ceux-ci se raréfient, le criblage strictement nécessaire n'augmente pas exponentiellement : au contraire, il ralentit son augmentation !!

En réalité, c'est le "hard-copy" (instruction native CopyMemory) qui va cravacher et, la fusion AVX par logique OU aussi : ce sont tes 2 1ères limites matérielles.

La 3ème limite c'est la succession des quelques 3 000 instructions

Code : Tout sélectionner

! mov [ebp], 1
! mov [ebp + 124], 1
! mov [ebp + 310], 1
! mov [ebp + 534], 1
etc...
Il faut mesurer la vitesse de compilation et la vitesse d'exécution.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 17:50
par Ollivier
@Djes

Je ne comprends pas ton dernier code ASM !

Il donne l'impression que tes instructions de changement d'état de bit se moquent que tu dépasses la taille en bits de l'opérande destination.

Je ne retrouve pas de masque ni de décalage : il n'y a pas besoin?

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 18:41
par djes
Ollivier a écrit :@Djes

Je ne comprends pas ton dernier code ASM !

Il donne l'impression que tes instructions de changement d'état de bit se moquent que tu dépasses la taille en bits de l'opérande destination.

Je ne retrouve pas de masque ni de décalage : il n'y a pas besoin?
Je ne suis pas étonné de ta question, moi aussi j'ai été surpris ! En fait, non, quand on fait un adressage mémoire, l'instruction BTS s'occupe elle-même du calcul si le bit dépasse le mot pointé. Par contre, elle est lente cette instruction (normal), bien plus que quand on travaille sur un registre.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 19:32
par Ollivier
On n'a pas l'air très fin avec nos manipulation de bits !
Attends, je vais "tenter" de faire quelquechose un poil plus rapide sinon on va se faire surnommer "Jacquouille" qui joue avec l'interrupteur ("jour... nuit... jour... nuit... ") !!!

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 19:51
par Starwolf20
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é.

Re: A propos de nombres premiers

Publié : sam. 22/oct./2016 20:03
par fweil
La page que tu signales Starwolf20 est bien ... c'est un bon point de référence pour se plonger dans le crible.

L'approche permet de comprendre les niveaux d'optimisation.

Les exemples de code en C permettent aussi de voir et comparer si besoin le traitement de la compression en utilisant des bits.

La performance indiquée est sans doute meilleure aujourd'hui sur les PC plus récents en 4core.

A l'occasion si vous jouez avec le code généré en C et le code généré en PureBasic vous pourrez normalement constater que PureBasic n'est pas mauvais du tout au jeu des performances induites.

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.