A propos de nombres premiers

[djes]

Non, ça c'est une réflexion pour un autre totalement différent.

[djes]

Comme je n'aurai pas le temps d'optimiser, voici le code de la méthode "sieve of Eratosthenes prime numbers lookup binary brute force" ( ) pas du tout optimisée, en version 8 bits et en version 64 bits. Les bits sont utilisés pour stocker les nombres premiers trouvés et le criblage. Evidemment, ça limite la portée de la recherche. Je voulais voir ce que ça donnait question vitesse, sans optimisation, pour voir si cet algo avait une chance. Je pense que non, même si on peut facilement multiplier la vitesse de la recherche avec les trucs connus et une bonne optimisation assembleur.

A enregistrer dans un dossier avec les droits en écriture, et compiler en version unicode.

Version 8 bits

Code : Tout sélectionner

;All rights reserved :)
#Max = 1000000

EnableExplicit

Procedure SetBit(*ptr, nb.i)
  
  *ptr + nb / 8
  nb = 1 << (nb % 8)
  PokeB(*ptr, PeekB(*ptr) | nb)
  
EndProcedure

Procedure BitNotSet(*ptr, nb.i)
  
  *ptr + nb / 8
  nb = 1<<(nb % 8)
  If (PeekB(*ptr) & nb ) = 0
    ProcedureReturn #True
  EndIf
  
EndProcedure

Procedure BitSet(*ptr, nb.i)
  
  *ptr + nb / 8
  nb = 1<<(nb % 8)
  If (PeekB(*ptr) & nb ) <> 0
    ProcedureReturn #True
  EndIf
  
EndProcedure

Procedure Sieve(*ptr, nb.i)
  
  Protected u.i = nb
  Protected *pos = *ptr + u/8
  
  While *pos < *ptr + #Max/8
    
    PokeB(*pos, PeekB(*pos) | (1 << (u % 8)))
    u + nb
    *pos = *ptr + u/8
    
  Wend
  
EndProcedure


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

OpenConsole()

file = CreateFile(#PB_Any, filename)
If file
  
  PrintN("Successfully created file " + filename)
  
  *pn = AllocateMemory(#Max / 8)
  If *pn
    
    PrintN("Successfully allocated prime numbers memory of " + Str(#Max / 8) + " bytes")
    
    *sieve = AllocateMemory(#Max / 8)   
    If *sieve
      
      PrintN("Successfully allocated sieve memory of " + Str(#Max / 8) + " bytes")
      
      time = ElapsedMilliseconds()
      
      For u = 2 To #Max - 1
        
        If BitNotSet(*sieve, u)
          SetBit(*pn, u)
          Sieve(*sieve, u)
        EndIf
        
      Next u  
      
      time = ElapsedMilliseconds() - time
      
      PrintN("Time elapsed : " + Str(time) + " ms")
      WriteStringN(file, "Time elapsed : " + Str(time) + " ms")
      
      For u = 2 To #Max - 1
        If BitSet(*pn, u)
          WriteStringN(file, Str(u) + ", ")
          counter + 1
        EndIf
      Next u
      
      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()

Version 64 bits

Code : Tout sélectionner

;All rights reserved :)
#Max = 1000000

EnableExplicit

Procedure SetBit(*ptr, nb.i)
  
  *ptr + (nb >> 3 ) & $FFFFFFFFFFFFFFF8 ;  *ptr + (nb / 64  ) * 8
  nb = 1 << (nb % 64)
  PokeI(*ptr, PeekI(*ptr) | nb)
  
EndProcedure

Procedure BitNotSet(*ptr, nb.i)
  
  *ptr + (nb >> 3 ) & $FFFFFFFFFFFFFFF8
  nb = 1 << (nb % 64)
  If (PeekI(*ptr) & nb ) = 0
    ProcedureReturn #True
  EndIf
  
EndProcedure

Procedure BitSet(*ptr, nb.i)
  
  *ptr + (nb >> 3 ) & $FFFFFFFFFFFFFFF8
  nb = 1 << (nb % 64)
  If (PeekI(*ptr) & nb ) <> 0
    ProcedureReturn #True
  EndIf
  
EndProcedure

Procedure Sieve(*ptr, nb.i)
  
  Protected u.i = nb
  Protected *pos = *ptr + (u >> 3 ) & $FFFFFFFFFFFFFFF8
  
  While *pos < *ptr + #Max/8
    
    PokeI(*pos, PeekI(*pos) | (1 << (u % 64)))
    u + nb
    *pos = *ptr + (u >> 3 ) & $FFFFFFFFFFFFFFF8
    
  Wend
  
EndProcedure


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 / 8)
  If *pn
    
    PrintN("Successfully allocated prime numbers memory of " + Str(#Max / 8) + " bytes")
    
    *sieve = AllocateMemory(#Max / 8)   
    If *sieve
      
      PrintN("Successfully allocated sieve memory of " + Str(#Max / 8) + " bytes")
      
      time = ElapsedMilliseconds()
      
      For u = 2 To #Max - 1
        
        If BitNotSet(*sieve, u)
          SetBit(*pn, u)
          Sieve(*sieve, u)
        EndIf
        
      Next u  
      
      time = ElapsedMilliseconds() - time
      
      PrintN("Time elapsed : " + Str(time) + " ms")
      WriteStringN(file, "Time elapsed : " + Str(time) + " ms")
      
      For u = 2 To #Max - 1
        If BitSet(*pn, u)
          WriteStringN(file, Str(u) + ", ")
          counter + 1
        EndIf
      Next u
      
      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()

[fweil]

@djes,

J'ai lancé la version 64 bits pour te donner le temps sur ma machine de référence, avec un 1e9. Il tient encore en mémoire avec ça. Le code est bien propre et reprend bien l'algo c qu'on peut trouver ici ou là. Je l'avais déjà testé. Là c'est pas optimisé du tout, bien sûr, et après un coup de clean il peut aller sans doute 10 fois plus vite. Je ferai une reprise optimisée pour l'évaluer sous un meilleur jour.

En l'état j'obtiens 104 secondes sur 1e9 ! C'est pas très pointu comme temps, mais c'est ce qu'on trouve dans pas mal d'ouvrages de référence alors ta rédaction mérite une bonne note.

Pour rappel, sur la même machine je fais 11,5 secondes en non optimisé monothread. On devrait être pas très loin avec cette mouture en optimisé qui souffre d'un inconvénient c'est le fait que le tableau de nombres n'est pas découpé en morceaux pendant le calcul, donc la porté serait limitée à 1e9 en l'état. Sinon le crible en lui-même est à peu de choses près identique, puisque c'est bien un Erathostène pur et simple.

[Ollivier]

@Djes

C'est magnifique de penser quelquechose et de voir apparaître le code, comme par magie.

C'est une très bonne idée l'usage des bits et c'est LE plus rapide, du moins, pour des premiers à 6 chiffres, plus gros, ça reste à prouver. C'est tellement rapide une fois bien usé que passer, ou non les multiples de 2 n'a que peu d'importance. Le paradoxe avec le crible d'Erathostène usé au bit près, c'est que cela nécessite l'usage d'une opération de division par nombre premier cribleur !

Vivement que je retrouve un peu de temps et un ordinateur.

[fweil]

Voilà le code préparé pour une optimisation plus basse (asm) ... enfin c'est une proposition ...

Par contre l'utilisation des bits n'est pas le plus efficace, franchement, je dois vous faire cet aveu à mon corps défendant, cela n'optimise que l'utilisation de la mémoire mais sûrement pas du processeur si cela oblige à faire des ou des et et des décalages à chaque échange avec le tableau. C'est intéressant comme approche, mais cela coûte en vitesse d'exécution.

La préparation à l'optimisation consiste en moyenne à prendre les chemins les plus efficaces pour les affectations et les adressages. Ici je n'ai pas touché à la partie bits justement, pour ne pas casser le principe du code. Par contre j'ai été réduire le code des procédures qui n'étaient utilisées qu' à une seule place dans le code du programme en replaçant les instructions des procédures et en minimisant les transferts de paramètres (et donc les push / pops de registres lors des appels de procédures). J'ai aussi ajouté des pointeurs typés pour remplacer les peeks et les pokes. Ces instructions sont performantes en PureBasic, mais si on vise la performances, elles restent moins rapides que des accès en adressage indirect.

Si on descend ça en assembleur ça doit pouvoir aller 2 ou 3 fois plus vite à la fin.

Là sur 1e9, mon PC de référence me donne déjà 10% d'économie de temps à la louche (et 1e9 doit pas être la meilleure tranche de test vu l'encombrement du tableau).

Code : Tout sélectionner

;All rights reserved :) All rights reversed :))
#Max = 10000000

EnableExplicit

Define u.i, time.i, counter = 0, file, filename.s = #PB_Compiler_FilePath + "primes64.txt"
Define *pn, *pn1.INTEGER, *ptr.INTEGER, *sieve, *sieve1.INTEGER, nb.i, u1.i, *pos.INTEGER, mask.i = $FFFFFFFFFFFFFFF8, max8.i = #Max >> 3

OpenConsole()

file = CreateFile(#PB_Any, filename)
If file
  
  PrintN("Successfully created file " + filename)
  
  *pn = AllocateMemory(max8)
  If *pn
    
    PrintN("Successfully allocated prime numbers memory of " + Str(max8) + " bytes")
    
    *sieve = AllocateMemory(max8)
    If *sieve
      
      PrintN("Successfully allocated sieve memory of " + Str(max8) + " bytes")
      
      time = ElapsedMilliseconds()
      
      For u = 2 To #Max - 1
        *sieve1 = *sieve + (u >> 3) & mask
        If (*sieve1\i & (1 << (u % 64))) = 0
          *ptr = *pn + (u >> 3) & mask
          *ptr\i = *ptr\i | (1 << (u % 64))
          u1.i = u
          *pos = *sieve + (u1 >> 3) & mask
          While *pos < *sieve + max8
            *pos\i = *pos\i | (1 << (u1 % 64))
            u1 + u
            *pos = *sieve + (u1 >> 3) & mask
          Wend
        EndIf
      Next u
      
      time = ElapsedMilliseconds() - time

      PrintN("Time elapsed : " + Str(time) + " ms")
      WriteStringN(file, "Time elapsed : " + Str(time) + " ms")
      
      For u = 2 To #Max - 1
        *pn1 = *pn + (u >> 3 ) & mask
        If (*pn1\i & (1 << (u % 64))) <> 0
          WriteStringN(file, Str(u) + ", ")
          counter + 1
        EndIf
      Next u
      
      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()

[djes]

Merci beaucoup de t'être donné la peine d'essayer d'optimiser un peu, et merci aussi bien sûr pour vos avis (à toi et à ollivier). Je suis entièrement d'accord avec tes conclusions, et je pense que c'est une impasse, même s'il est possible comme tu l'as fait dans ton code de partitionner et d'optimiser plus encore.

L'idée des bits m'était venue pour mettre de côté l'algèbre et revenir à quelque chose de plus fondamental, qui pourrait coller au plus juste aux capacités de l'ordinateur. Le bit représente l'unité, et la mémoire un immense boulier ! Mais pour des nombres gigantesques, il y a trop de données à traiter, même si, et c'est une autre possibilité d'optimisation, on remplace les multiplications et les divisions par des additions et des sauts binaires en s'aidant, pourquoi pas, des GPU et autres calculs parallèles.

Sinon, ma réflexion actuelle se porte sur le pourquoi des nombres premiers, et comment ils apparaissent. Le pourquoi est simple, c'est une histoire de dissymétrie, et l'univers n'existerait certainement pas s'il était symétrique ! Du coup je réfléchis à des comparaisons avec des nombres en bases symétriques, entre autres choses. Mais pour l'instant, rien de concret et de suffisamment rapide.

[Ollivier]

Par contre l'utilisation des bits n'est pas le plus efficace, franchement, je dois vous faire
cet aveu à mon corps défendant, cela n'optimise que l'utilisation de la mémoire mais
sûrement pas du processeur si cela oblige à faire des ou des et et des décalages à chaque
échange avec le tableau. C'est intéressant comme approche, mais cela coûte en vitesse
d'exécution.

Je n'ai pas compris l'une des phrases, sûrement à cause d'un oubli de frappe.

...si cela oblige à faire des ou des et et des décalages...

Je pense néanmoins, par déduction que cette obligation est suffisamment loin d'être nécessaire pour couvrir les besoins espérés.

[fweil]

Le coût des opérations logiques et des décalages pour lire ou fixer un bit dans un mot n'est pas bénin. Cela rend la technique économique en espace mémoire mais onéreuse en temps. Même si ces opérations sont rapides en soi, il y a un certain nombre de cycles d'horloge avant que la valeur d'un bit soit envoyée ou reçue dans le mot.

Il y a une chose intéressante à faire pour une optimisation fine du temps d'exécution, c'est d'utiliser la fonction /COMMENTED du compilateur pour lire le code assembleur généré. On peut ainsi compter les cycles d'horloge et évaluer le temps d'exécution réel d'une séquence de code.

[Ollivier]

Il existe aussi cet exemple http://www.purebasic.com/documentation/ ... embly.html qui use du désassembleur natif à la volée, au moins en 32 bits.

@fweil

Je ne suis vraiment pas sûr du tout de ce que tu avances dans le cadre du crible d'Erathos.

Si c'est "vraiment" plus lent dans ce cadre, c'est que l'expérience qui l'a prouvé n'a pas été mené avec la quantité de critères suffisants.

[fweil]

Je ne sais pas si ce que j'avance a quelque chose à voir pour le crible d'Erathostène, mais je sais que si je lance le même algorithme sans les opérations bits, en utilisant un tableau de mots au format natif (32 ou 64), je fais tourner le même truc 2 fois plus vite.

Ca me suffit pour penser que c'est plus rapide comme ça.

En même temps il y a une raison logique qui l'explique, c'est que lire et écrire à une adresse mémoire en faisant des opérations intermédiaires ou sans les faire, ce n'est pas la même chose ... c'est tout simple. Il ne faut pas y voir un sujet d'investigations profondes.

Le but de l'utilisation d'un tableau de bits ne sert que de moyen d'économiser de la place en "comprimant" la table de nombres d'un facteur significatif. Mais cela a un coût en termes de performances.

Il est assez élevé pour justifier la recherche d'une solution de "pagination" de la table, ce que j'ai proposé dans le code que j'utilise avec le programme que j'ai présenté. Et cette pagination est redoutablement plus efficace pour traiter une grande portée numérique.

[Ollivier]

@fweil

C'est important que tu précises ton contexte de pagination.

Ton système contient donc une virtualisation du crible d'Erathos.

A titre indicatif, j'en ai créé un tel système dans le code graphique. Cela n'a évidemment rien à voir, cependant, c'est bel et bien une virtualisation du crible d'Erathos : il s'affiche devant tes yeux mais n'existe pas réellement. (D'où mon expression à Ar-S : "Attention, tu vois du Erathostène, mais ce n'est pas du Erathostène.").

Il n'empêche que ce n'est pas forcément constructif de mettre à néant l'idée que travailler au bit près n'est pas avantageux par rapport à une cellule usuelle.

1) Parce que je vais te poster un code assez bref qui te prouve que c'est faux.

2) Parce que pour une sous-couche électronique interne au CPU (ou à la CPU), que tu travailles au bit près ou à une cellule booléenne près, ça lui est égal. (Je pense que tu es d'accord sur le fait que même notre petite fonction random est "digérée" par le processeur dans une absolue transparence au sein de la couche ASMx86)

3) Parce que si tu virtualises, c'est sûr c'est rapide, mais s'il faut transmettre en réseau, ce n'est plus virtuel : c'est réel.

Ma question : est-ce le crible d'Erathos au bit près et compressé est-il plus ou moins volumineux que la liste des nombres premiers compressés?

Ça peut sembler dénué de sens, mais c'est le genre de réponse qui, elle tranchera clairement l'utilisation du crible au bit près.

En attendant, dans un contexte vierge, voici un squelette d'expérience suffisamment viable pour obtenir la synthèse suivante :
Il existe 3 échelles de taille de tableau.
En 64 bits, les petits et les grands tableaux prônent le système général par bits plutôt que par cellule booléenne 64 bits. C'est significatif pour les petits tableaux. Il n'existe qu'un calibre restreint de tableaux de type "moyen" ou la cellule booléenne est avantagée par rapport au traitement de bit.

Code : Tout sélectionner

Ordonnee = 20
Abscisse = 25

TailleCellule = 64
TailleTable = 1 << Ordonnee
TailleTest = 1 << Abscisse

Total = TailleCellule * TailleTable
Max = Total - 1
Global Dim Gamma(Total - 1)
Global Dim Beta(TailleTable - 1)

Procedure SetCellule(Adresse)
Gamma(Adresse) = 1
EndProcedure

Procedure SetBit(Adresse)
Beta(Adresse >> 6) | (1 << (Adresse & 63) )
EndProcedure

A0 = ElapsedMilliseconds()
For I = 1 To TailleTest
SetBit(Random(Max) )
Next
A1 = ElapsedMilliseconds()
For I = 1 To TailleTest
SetCellule(Random(Max) )
Next
A2 = ElapsedMilliseconds()
MessageRequester(Str(A1 - A0), Str(A2 - A1) )

Je suis prêt à toute critique constructive.

Je rappelle juste que l'on est dans le cas général : un "random access". Je doute que le/la CPU reste indifférent à la contiguïté des accès.

[djes]

Je m'intercale dans la discussion pour dire que le tableau de bits permet de cribler rapidement des «mots» de la taille du bus, et en mode rafale, plusieurs mots d'un coup. Pour le criblage de 2 par exemple (inutile, je sais), un simple And $AAAAAAAAAAAAAAAAA me fait un sacré boulot... Ensuite, il faudrait pré calculer certains criblages, voire des combinaisons, voire réutiliser ce qui a déjà été criblé avec une copie. Bien sûr, l'intérêt est restreint aux «petits» nombres cribblants.

Une autre idée par rapport aux bits, évoquée par ollivier, est la compression. Un run-length pourrait peut-être limiter la consommation mémoire en remplaçant les bits par un codage des gaps ?

[fweil]

Bon, je vais tenter de clore la discussion sur les avantages et inconvénients de l'utilisation des tableaux de bits de manière très résumée.

Voici une approche "classique" du crible d'Erathostène, sans aucun ésotérisme, avec un tableau de nombres entiers au format de base (j'ai utilisé des .i pour tester en 32 ou en 64 indifféremment).

Je vous laisse regarder ce que ça donne pour vous, et en toute honnêteté vous noterez, si vous voulez, vos résultats ici.

Testez le avec un nMax en 1e8. Mon PC de référence me donne 3,7 s à 3,8 s. Vous comparerez ou pas avec d'autres algorithmes.

Pour la question de la pagination, si j'ai posté mon code, avec tous les commentaires que j'ai mis, c'est bien pour permettre de voir ce que je fais et comment ça fonctionne. C'est dedans.

On passe des sous-plages nmin-nmax à une procédure qui prend en charge le passage du crible en utilisant des valeurs de départ des compteurs de cribles qui sont calculées en fonction de la valeur nmin, et on fait sauter les compteurs chacun en fonction de leur valeur jusqu'à ce que nmax soit atteint. Une fois cela fait, on renvoie les résultats de cette sous-plage au prog principal et on passe à la sous-plage suivante. C'est la seule étrangeté de la chose, sans poudre aux yeux ni baguette magique. L'avantage c'est qu'on peut écouler toutes les sous-plages qu'on veut jusqu'à épuisement de la plage principale de départ, même si celle-ci est d'une taille qui ne peut pas tenir en mémoire, ni même sur disque.

Et je ne sais pas expliquer quoi de plus dans tout ça, mais une chose est certaine c'est qu'il n'y a pas de parallélisme ou de vectorisation à utiliser des bits au lieu d'entiers d'une part, et que par contre il y a des opérations en plus, et, ou, décalage, qui coûtent.

D'une manière ou d'une autre le code que je montre ici est le même que celui dans lequel on utilise des traitements au bit, et la mesure de temps est faite entre les m^mes instants du traitement. Sur le code en tableau de bits, j'obtiens 8 secondes. Je n'y peux rien, c'est peut-être mon processeur qui est construit avec une UAL anti-bit ?

Code : Tout sélectionner

nMax.i = 100000000
Dim Numbers.i(nMax)

OpenConsole()

  tz.i = ElapsedMilliseconds()
  Numbers(0) = 1
  Numbers(1) = 1
  For n.i = 4 To nMax Step 2
    Numbers(n) = 1
  Next
  dMax.i = Sqr(nMax)
  For d.i = 3 To dMax
    If Numbers(d) = 0
      For n.i = d << 1 To nMax
        Numbers(n) = 1
        n + d - 1
      Next
    EndIf
  Next
  nPrimes.i = 0
  For n = 0 To nMax
    If Numbers(n) = 0
      nPrimes + 1
    EndIf
  Next
  Time.d = (ElapsedMilliseconds() - tz) / 1000
  
  PrintN(Str(nPrimes) + " premiers trouvés en " + StrD(Time, 3) + " s")
  PrintN("")
  

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

[PAPIPP]

Bonjour à tous

Voila les résultats sur mon PC du prg d’ Olivier.
J’ai précisé ce à quoi ces temps correspondaient.

Temps sur Bit=3909
Temps sur mot=3009
Taille=33554432

Code : Tout sélectionner

Ordonnee = 20
Abscisse = 25

TailleCellule = 64
TailleTable = 1 << Ordonnee
TailleTest = 1 << Abscisse

Total = TailleCellule * TailleTable
Max = Total - 1
Global Dim Gamma(Total - 1)
Global Dim Beta(TailleTable - 1)

Procedure SetCellule(Adresse)
Gamma(Adresse) = 1
EndProcedure

Procedure SetBit(Adresse)
Beta(Adresse >> 6) | (1 << (Adresse & 63) )
EndProcedure

A0 = ElapsedMilliseconds()
For I = 1 To TailleTest
SetBit(Random(Max) )
Next
A1 = ElapsedMilliseconds()
For I = 1 To TailleTest
SetCellule(Random(Max) )
Next
A2 = ElapsedMilliseconds()
MessageRequester("Temps sur Bit="+Str(A1 - A0),"Temps sur mot="+ Str(A2 - A1)+#crlf$+"Taille="+str(Tailletest) )

A+

[djes]

Au niveau des bits, vous oubliez quand même que PB est peu fourni là-dessus, contrairement aux processeurs. Voici quelques instructions pour vous donner du grain à moudre :

0F BA 4 BT r/m16/32/64 imm8 o..szapc .......c o..szap. Bit Test
0F BA 5 L BTS r/m16/32/64 imm8 o..szapc .......c o..szap. Bit Test and Set
0F BA 6 L BTR r/m16/32/64 imm8 o..szapc .......c o..szap. Bit Test and Reset
0F BA 7 L BTC r/m16/32/64 imm8 o..szapc .......c o..szap. Bit Test and Complement
0F BB r L BTC r/m16/32/64 r16/32/64 o..szapc .......c o..szap. Bit Test and Complement
0F BC r D28 BSF r16/32/64 r/m16/32/64 o..szapc ....z... o..s.apc Bit Scan Forward
0F BD r D28 BSR r16/32/64 r/m16/32/64 o..szapc ....z... o..s.apc Bit Scan Reverse

Mais ! Est-ce vraiment à l'optimisation qu'il faut s'attacher, maintenant (je n'en reviens pas de dire ça...) ? Ce que je vois dans l'astuce de fweil, ce n'est pas la vitesse, c'est surtout le fait de pouvoir aller bien plus loin qu'avec un programme traditionnel, jusqu'aux limites d'un système. Il a eu une idée géniale et son implémentation est superbe !

Je pense qu'on devrait s'attaquer à l'après, des nombres plus grands, et je pense que nous sommes tous conscients que les limites de nos processeurs seront vites atteintes, et qu'à un moment il faudra jongler avec tout ce dont on dispose, les nombres, les mots et les bits. Moi j'ai proposé les bits tout de suite, parce que c'est l'unité incompressible, mais pour de très grands nombres, il faudra peut-être retourner dans l'algèbre, et la représentation... Je n'en sais rien !