PureBasic

Forums PureBasic
Nous sommes le Mer 21/Aoû/2019 21:10

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 155 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6 ... 11  Suivante
Auteur Message
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Sam 08/Oct/2016 21:10 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3483
@Ar-S

Petite parenthèse sur ce qu'est le crible d'Erathostène visuellement. J'ai mis les cases des premiers en rouge et des flèches pour se déplacer : fonce vers la droite et tâche de tenir la "ligne rouge" au milieu de l'écran avec les flèches haut et bas.

Pas d'optimisation (thread, ASM), juste de la recherche de diviseurs premiers (attention ! Tu vois du Erathostène, mais ce n'est pas du Erathostène!)

(Ça me fait penser : on n'aurait pas perdu Huitbit?)
Code:
;********************************************************************************************************************************************
Procedure InitScreen()
        ExamineDesktops()
        Global Dw = DesktopWidth(0)
        Global Dh = DesktopHeight(0)
        Global Dd = DesktopDepth(0)
        InitSprite()
        InitKeyboard()
        OpenScreen(Dw, Dh, Dd, "")
EndProcedure

Global Dim CharFont.I(80)
Global Dim CharSprite.I(80, 255)
Global Dim CharW.I(80, 255)
Global Dim CharH.I(80, 255)

#BackColor = $406080
#CaseBackColor = $FFFFFF
#CaseTextColor = $000000

Procedure InitSpriteCharacter(SizeList.S)
        Define SizeSize = CountString(SizeList, ";")
        Dim Size.I(SizeSize)
        For K = 0 To SizeSize
                Size(K) = Val(StringField(SizeList, 1 + K, ";") )
        Next
        For K = 0 To SizeSize
                J = Size(K)
                CharFont(J) = LoadFont(#PB_Any, "Verdana", J)
        Next

StartDrawing(ScreenOutput() )
        For K = 0 To SizeSize
                J = Size(K)
        DrawingFont(FontID(CharFont(J) ) )
        For I = 1 To 255
                CharW(J, I) = TextWidth(Chr(I) )
                CharH(J, I) = TextHeight(Chr(I) )
        Next
        Next
StopDrawing()

        For K = 0 To SizeSize
                J = Size(K)
        For I = 48 To 57
                CharSprite(J, I) = CreateSprite(#PB_Any, CharW(J, I), CharH(J, I), #PB_Sprite_AlphaBlending)
                StartDrawing(SpriteOutput(CharSprite(J, I) ) )
                        DrawingFont(FontID(CharFont(J) ) )
                        DrawingMode(#PB_2DDrawing_AllChannels)
                        DrawText(0, 0, Chr(I), RGBA(0, 0, 0, 255), RGBA(255, 255, 255, 0) )
                StopDrawing()
        Next
        For I = 65 To 90
                CharSprite(J, I) = CreateSprite(#PB_Any, CharW(J, I), CharH(J, I), #PB_Sprite_AlphaBlending)
                StartDrawing(SpriteOutput(CharSprite(J, I) ) )
                        DrawingFont(FontID(CharFont(J) ) )
                        DrawingMode(#PB_2DDrawing_AllChannels)
                        DrawText(0, 0, Chr(I), RGBA(0, 0, 0, 255), RGBA(255, 255, 255, 0) )
                StopDrawing()
        Next
Next
EndProcedure

Procedure DisplayText(x, y, A$, Size, Color, Angle = 0)
        Define AngleRad.F = Angle * #PI / 180.0
        If Angle
                For I = 1 To Len(A$)
                        A = Asc(Mid(A$, I, 1) )
                        If Angle
                                RotateSprite(CharSprite(Size, A), Angle, #PB_Absolute)
                        EndIf
                        DisplayTransparentSprite(CharSprite(Size, A), X, Y, 255, Color)
                        X + (CharW(Size, A) * Cos(AngleRad) )
                        Y + (CharW(Size, A) * Sin(AngleRad) )
                Next
        Else
                For I = 1 To Len(A$)
                        A = Asc(Mid(A$, I, 1) )
                        RotateSprite(CharSprite(Size, A), 0, #PB_Absolute)
                        DisplayTransparentSprite(CharSprite(Size, A), X, Y, 255, Color)
                        X + CharW(Size, A)
                Next
        EndIf
EndProcedure

Macro GraphDrawExemple()
InitSpriteCharacter()
Repeat
        Lap0 = Lap
        Lap = ElapsedMilliseconds()
        Delay(16)
        ExamineKeyboard()
        ClearScreen(#BackColor)
        DisplayText(0, 0, Str(Lap - Lap0), 20, RGB(255, 0, 0) )
        FlipBuffers()       
Until KeyboardPushed(#PB_Key_Escape)
EndMacro

Macro AjoutePremier(X)
        Prim(PrimeQuantity) = X
        Prime2(PrimeQuantity) = X * X
        PrimeQuantity + 1
EndMacro

Macro IsPrime5(Nombre)
        bPremier = 1
        For Jprime = 2 To MostPrime2
                If Nombre % Prim(Jprime) = 0
                        bPremier = 0
                        Break
                EndIf
        Next
EndMacro

Macro TestPrime5(Pas)
        If Prime2(MostPrime2 + 1) <= Iprime
                MostPrime2 + 1
        EndIf
        IsPrime5(Iprime)
        If bPremier
                AjoutePremier(Iprime)
        EndIf
        Iprime + Pas
EndMacro

InitScreen()
InitSpriteCharacter("10;20")


nDebut = 5
nFin = 100000
Global Dim Prim.I(nFin)
Global Dim Prime2.I(nFin)
AjoutePremier(2)
AjoutePremier(3)
Iprime = nDebut
Repeat
        TestPrime5(2)
        TestPrime5(4)
Until Iprime > nFin

MaxPrime = PrimeQuantity - 1

BackColor = RGB(0, 0, 255)

CellW = 64
CellH = 24
FirstColumnW = 40
FirstRowH = 80

CribleSp = CreateSprite(#PB_Any, CellW, CellH, #PB_Sprite_AlphaBlending)
If StartDrawing(SpriteOutput(CribleSp) )
        DrawingMode(#PB_2DDrawing_AllChannels)
        W = OutputWidth()
        H = OutputHeight()
        Box(0, 0, W, H, RGBA(0, 0, 0, 255) )
        StopDrawing()
EndIf

Crible1er = CreateSprite(#PB_Any, CellW, CellH, #PB_Sprite_AlphaBlending)
If StartDrawing(SpriteOutput(Crible1er) )
        DrawingMode(#PB_2DDrawing_AllChannels)
        W = OutputWidth()
        H = OutputHeight()
        Box(0, 0, W, H, RGBA(255, 0, 0, 255) )
        StopDrawing()
EndIf

DecalYMax = (CellH * (MaxPrime + 1) ) - (Dh - FirstRowH)
Repeat
        Lap0 = Lap
        Lap = ElapsedMilliseconds()
        Delay(16)
        ExamineKeyboard()
        If KeyboardPushed(#PB_Key_Right)
                DecalAX + 2
        EndIf       
        If KeyboardPushed(#PB_Key_Left)
                DecalAX - 2
        EndIf       
        If KeyboardPushed(#PB_Key_Down)
                DecalAY + 2
        EndIf       
        If KeyboardPushed(#PB_Key_Up)
                DecalAY - 2
        EndIf       
        If DecalAX
                DecalX + DecalAX
                If DecalAX > 0
                        DecalAX - 1
                Else
                        DecalAX + 1
                EndIf
                If DecalX < 0
                        DecalX = 0
                        DecalAX = 0
                EndIf
        EndIf
        If DecalAY
                DecalY + DecalAY
                If DecalAY > 0
                        DecalAY - 1
                Else
                        DecalAY + 1
                EndIf
                If DecalY < 0
                        DecalY = 0
                        DecalAY = 0
                EndIf
                If DecalY > DecalYMax
                        DecalY = DecalYMax
                        DecalAY = 0
                EndIf
        EndIf
        ClearScreen(BackColor)
        DisplayText(0, 0, Str(Lap), 20, RGB(255, 0, 0) )
        Displaytext(200, 0, Str(Prim(MaxPrime) ), 20, RGB(0, 255, 255) )
        JDebutY = DecalY / CellH
        JFinY = JDebutY + ((Dh - FirstRowH) / CellH)
        For I = JDebutY To JFinY
                DisplayText(0, FirstRowH + CellH * I - DecalY, Str(Prim(I) ), 10, RGB(255, 255, 255) )
        Next
        JDebutX = DecalX / CellW + 1
        JFinX = JDebutX + ((Dw - FirstColumnW) / CellW)
        For J = JDebutX To JFinX
                DisplayText(FirstColumnW + CellW * J - DecalX, 40, Str(J), 10, RGB(255, 255, 255), -20)
        Next
        For I = JDebutY To JFinY
                For J = JDebutX To JFinX
                        X = FirstColumnW + CellW * J - DecalX
                        Y = FirstRowH + CellH * I - DecalY
                        If (J % Prim(I) ) = 0
                                If J = Prim(I)
                                        DisplaySprite(Crible1er, X, Y)
                                Else
                                        DisplaySprite(CribleSp, X, Y)
                                EndIf
                        EndIf
                Next
        Next
        FlipBuffers()       
Until KeyboardPushed(#PB_Key_Escape)

_________________
Juste la 4G pour Smartphone


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Sam 08/Oct/2016 22:32 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 16/Mai/2004 17:50
Messages: 505
Localisation: Bayonne (64)
Alors moi j'ai réussi à monter une marche d'escalier ...

Code:
Structure PACKED4D ; structure permettant de précharger des Doubles
  d0.d             ; le format est 4 x 64 = 256 bits.
  d1.d             ; Ce format correspond à un registre ymm
  d2.d
  d3.d
EndStructure

Structure PACKED8D ; structure en 512 bits correspondant à deux PACKED4D
  D4_0.PACKED4D    ; Ce format correspond à un registre zmm (ou 2 ymm)
  D4_1.PACKED4D
EndStructure

nTimes.q = 100000000

  If OpenConsole()
    ;
    ; On fait des presets
    ;
    packed_in.PACKED8D
    packed_in\D4_0\d0 = 120
    packed_in\D4_0\d1 = 121
    packed_in\D4_0\d2 = 122
    packed_in\D4_0\d3 = 123
    packed_in\D4_1\d0 = 7
    packed_in\D4_1\d1 = 7
    packed_in\D4_1\d2 = 7
    packed_in\D4_1\d3 = 7
    *packed_in = @packed_in
    packed_out.PACKED4D
    *packed_out = @packed_out
   
    ;
    ; Premier jeu de test en PB classique
    ;
    tz.q = ElapsedMilliseconds()
    For i.q = 1 To nTimes
      packed_out\d0 = packed_in\D4_0\d0 - packed_in\D4_1\d0 * Int(packed_in\D4_0\d0 / packed_in\D4_1\d0)
      packed_out\d1 = packed_in\D4_0\d1 - packed_in\D4_1\d1 * Int(packed_in\D4_0\d1 / packed_in\D4_1\d1)
      packed_out\d2 = packed_in\D4_0\d2 - packed_in\D4_1\d2 * Int(packed_in\D4_0\d2 / packed_in\D4_1\d2)
      packed_out\d3 = packed_in\D4_0\d3 - packed_in\D4_1\d3 * Int(packed_in\D4_0\d3 / packed_in\D4_1\d3)
      result.q = #True
      If packed_out\d0 = 0
        result.q = #False
      EndIf
      If packed_out\d1 = 0
        result.q = #False
      EndIf
      If packed_out\d2 = 0
        result.q = #False
      EndIf
      If packed_out\d3 = 0
        result.q = #False
      EndIf
    Next i
    Time.d = (ElapsedMilliseconds() - tz) / 1000
    PrintN("result = " + Str(result) + #TAB$ + StrD(Time, 3))
   
    ;
    ; Second jeu de test en PB classique mais en utilisant des
    ; variables directes (test de comparaison pour info sur le coût
    ; de l'utilisation d'une structure de preset
    ;
    tz.q = ElapsedMilliseconds()
    n0.q = packed_in\D4_0\d0
    n1.q = packed_in\D4_0\d1
    n2.q = packed_in\D4_0\d2
    n3.q = packed_in\D4_0\d3
    d0.q = packed_in\D4_1\d0
    d1.q = packed_in\D4_1\d1
    d2.q = packed_in\D4_1\d2
    d3.q = packed_in\D4_1\d3
    For i.q = 1 To nTimes
      r0.q = n0 - d0 * Int(n0 / d0)
      r1.q = n1 - d1 * Int(n1 / d1)
      r2.q = n2 - d2 * Int(n2 / d2)
      r3.q = n3 - d3 * Int(n3 / d3)
      result.q = #True
      If r0 = 0
        result.q = #False
      EndIf
      If r1 = 0
        result.q = #False
      EndIf
      If r2 = 0
        result.q = #False
      EndIf
      If r3 = 0
        result.q = #False
      EndIf
    Next i
    Time.d = (ElapsedMilliseconds() - tz) / 1000
    PrintN("result = " + Str(result) + #TAB$ + StrD(Time, 3))
   
    ;
    ; Même traitement en AVX (les tests à la fin seront en AVX
    ; quand je serai arrivé à trouver comment faire.
    ;
    tz.q = ElapsedMilliseconds()
    For i.q = 1 To nTimes
      !  mov      rax, [p_packed_in]
      !  mov      rbx, [p_packed_out]
      !  vmovupd  ymm0, [rax]
      !  vmovupd  ymm1, [rax+32]
      !  vdivpd   ymm2, ymm0, ymm1 ; D4_0 / D4_1
      !  vroundpd ymm2, ymm2, $01 ; INT() [round floor]
      !  vmulpd   ymm3, ymm2, ymm1 ; * D4_1
      !  vsubpd   ymm0, ymm0, ymm3 ; D4_0 -
      !  vmovupd  yword [rbx], ymm0
      result.q = #True
      If packed_out\d0 = 0
        result.q = #False
      EndIf
      If packed_out\d1 = 0
        result.q = #False
      EndIf
      If packed_out\d2 = 0
        result.q = #False
      EndIf
      If packed_out\d3 = 0
        result.q = #False
      EndIf
    Next i
    Time.d = (ElapsedMilliseconds() - tz) / 1000
    PrintN("result = " + Str(result) + #TAB$ + StrD(Time, 3))
   
    PrintN("")
    PrintN("Push any key to quit ...")
    While Inkey() = ""
      Delay(50)
    Wend
    CloseConsole()
  EndIf
 
End


Ca me dit en gros un ratio temps 7s sur le test 1, 5s sur le test 2 et 3s sur le test 3, très approximativement, et en valeur moyenne moyennée. Donc ce serait prometteur, mais il y a du boulot pour bien arriver à faire ça propre dans le programme.

_________________
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Sam 08/Oct/2016 22:34 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 16/Mai/2004 17:50
Messages: 505
Localisation: Bayonne (64)
J'ai utilisé un préchargement par une structure parce que c'est sans doute ça qui sera utilisé au final. Pour alimenter AVX il faut des données contigües en mémoire.

Ollivier c'est sympa la présentation en graphique ... et c'est du boulot à rédiger ^^

_________________
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Sam 08/Oct/2016 23:01 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3483
C'est mon Exzèleux en godeux zource bilingue!
Il te manque les flags... Tu peux "shifter"?

Les comparaisons en SSE&co, c'est bourrin : le résultat est dans l'opérande destination sous forme 0 (faux) ou -1 ($Ffff...ffffF) (vrai).

_________________
Juste la 4G pour Smartphone


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 8:57 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2053
@fweil :

tu fais comment pour faire tourner ton code ?

moi j'ai une erreur sur la ligne :
Code:
For i.q = 1 To nTimes

Citation:
'For' ne supporte pas les variables de type 'quad'.


ton code (le dernier posté avant ce message) ne tourne pas en Pb 5.50 !

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 9:11 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 02/Oct/2011 16:17
Messages: 2157
Localisation: 50200 Coutances
Code:
;For i.q = 1 To nTimes

nTimes = 10000000
i.q = 1

While i < nTimes
  i + 1
Wend

Debug i

_________________
Microsoft Windows 10 Famille 64 bits : Carte mère : ASRock 970 Extreme3 R2.0 : Carte Graphique NVIDIA GeForce GT 640 : Processeur AMD FX 6300 6 cœurs 12 threads 3,50 GHz PB 5.62, 5.70 LTS
Un homme doit être poli, mais il doit aussi être libre !


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 9:13 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3483
@Zorro

Teste avec une installation PB x64 si tu veux exécuter le code.

_________________
Juste la 4G pour Smartphone


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 9:15 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2053
arf .. oui bien sur , merci

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 9:23 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 16/Mai/2004 17:50
Messages: 505
Localisation: Bayonne (64)
Ah ba oui, j'avais pas dit, je fais tout en x64, alors si on veut faire tourner sur x86, il faut juste reprendre certain trucs, dont le fameux For / Next qui supporte pas qu'on l'embête.

Sur AVX, j'ai beau triturer ça dans tous les sens, j'arrive à sortir des vecteurs 4 x doubles qui contiennent le résultat de la division entière par ce que je veux, mais pour tester le pack, j'arrive pas à dire pour l'instant :

- trouve si il y a double à zéro dans le pack
- sors le produit des atomes du pack pour voir si ça fait zéro

(c'est les deux façons de dire la même chose, sauf que la seconde est plus lente mais si on pas le ouache, ça pourrait le faire, sauf que ça le fait pas si je sais pas le faire et que si t'as besoin de rien t'es tout de suite servi).

Donc je bute, provisoirement, mais ça va finir par y aller. Mais ... mais ... dans l'immédiat, j'ai déjà compris que je vais pas arriver à aller plus vite sur cette voie là. Sauf si en y repensant un moment je trouve mieux, la vectorisation ne sera pas plus rapide que la mise en application d'un crible comme celui que j'ai mis au point. A comparer des séries de déplacements de pointeurs avec tout ce qu'on veut, ben déplacer des pointeurs c'est quand même hyper rapide.

Bon je me concentre pour essayer de pouvoir me contredire.

_________________
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 9:40 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3483
Quand tu fais la somme de tes gaps pré-calculés, quel résultats tu obtiens ? (Exemple : dans "Exzel" c'est 6, car tu as TestPrime5(2 <<<<<) et TestPrime5(4 <<<<<<) et donc 2 + 4 = 6)

_________________
Juste la 4G pour Smartphone


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 12:04 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 09/Oct/2005 16:51
Messages: 8735
L'exemple graphique est sympa merci.
j'ai lu sur wikipedia ce que c'était mais j'aimerai tout de même comprendre les applicatifs possibles.
Concrètement ça vous sert à quoi.

_________________
~~~~Règles du forum ~~~~
.: Ar-S :. Tour + portable W10 x64 PB 5.4x / 5.6x
LDV MULTIMEDIA : Dépannage informatique & mes Logiciels PB
RESIZER GOLD : Mon logiciel de redimensionnement par lot 100% PB


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 15:05 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3483
@Ar-S

Si tu as un chat inconnu au bataillon qui semble s'être coincé sur une gouttière chez toi, et que tu fabriques une échelle pour mettre ce chat sur la terre ferme. Ce chat, une fois posée au sol, il s'enfuit. Résultat, excepté un très faible risque de sentir la charpille pourrie, s'il était resté condamné là, ça ne t'a quasi-strictement servi à rien de t'en occuper. Par contre, désormais, tu disposes d'une échelle pour faire des choses plus utiles : réparer une fuite, repeindre un volet, etc...

Je crois que l'utilité de l'étude des nombres premiers, c'est un peu pareil. L'utilité n'est pas dans le but peu probable, mais dans la création des moyens pour y parvenir.

_________________
Juste la 4G pour Smartphone


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 16:12 
Hors ligne
Avatar de l’utilisateur

Inscription: Dim 16/Mai/2004 17:50
Messages: 505
Localisation: Bayonne (64)
Il y a une chose qui tarabuste les gens qui sont fadas de nombres, c'est que toute chose découle des nombres entiers, et que tous les nombres entiers découlent des nombres premiers qui en font partie.

L'étude des nombres premiers est un peu comme la quête que l'on peut faire pour savoir répondre aux grandes questions existentielles : où vais-je ? où cours-je et dans quel état j'ère ? D'où venons-nous et pourquoi ?

Tout le monde ne goûte pas la poésie des nombres, en tout cas pas de la même manière, mais il y a quelque chose de constant chez ceux qui les aiment assez, savoir décrire les choses, celles qui nous entourent, celles qu'on ne voit pas, avec des nombres, agencés en partitions variées et parfois compliquées, parfois faciles à comprendre, parfois tout simplement superbes parce qu'elles sont simples.

L'étude des nombres premiers confrontent ceux qui s'y adonnent à l'infini, à l'infini dans l'infini, et à ces choses qu'on devine sans arriver à les démontrer parce que la magie des nombres est portée dans cette discrète pudeur qu'ils ont à exister, à être bien utiles, mais à ne pas nous permettre d'en comprendre toute l'essence.

Comment les nombres premiers peuvent-ils permettre à tous les autres d'exister ? Pourquoi ne sont-ils pas prévisibles lorsqu'on les cherche ? Combien y en a t-il qui ont telle forme ou telle autre ? Et combien de temps faut-il pour démontrer qu'un nombre est premier ? Comment doit-on s'y prendre ?

Au cours de l'histoire humaine (l'Histoire qui correspond en gros à la période qui s'écoule depuis qu'on conserve des traces écrites de nos élucubrations), pas mal de gens ont cogité à tout cela en apportant des réponses plus ou moins utiles, plus ou moins précises.

Pour ma part, le travail auquel je contribue consiste à affiner quelques hypothèses pour des mathématiciens sur la nature des nombres premiers parmi les nombres entiers, en ce qu'ils sont distribués de telle sorte qu'on en prévoit aujourd'hui à peu près la quantité (combien de nombres premiers se trouvent entre truc et bidule), mais qu'on est encore relativement peu capables d'en prédire la place (quels nombres sont premiers entre truc et dudule).

En gros, on a des systèmes et des formules qui permettent de dire pour une partie des nombres qu'ils n'ont aucune chance d'être premiers, ou au contraire que ça vaut peut-être le coup de calculer si ils le sont.

Le crible d'Erathostène, par exemple, n'est pas une méthode transcendante pour vérifier qu'un nombre quelconque est premier, mais c'est en quelque sorte la meilleure approche pour le vérifier.

Ceci étant posé, les nombres premiers ensuite nous servent à pas mal de choses qui nous échappent souvent dans le tumulte du quotidien. Il fut un temps où les humains ne connaissaient pas les nombres réels, et ils utilisaient les nombres entiers seulement. Pour trouver de justes mesures à un certain nombre de choses, ils utilisaient les quotients (divisions) entre nombres premiers.

Lorsqu'un quotient est fait entre deux nombres, il a le plus souvent pour résultat une partie entière, et un reste, que l'on peut représenter aussi comme la partie décimale de la division (c'est ce qui permettra aux humains d'invinter les nombres réels).

La connaissance des nombres premiers conduit à comprendre que les autres nombres peuvent être formulés à partir de ceux-ci. Ces autres nombres sont des nombres composites.

Cette connaissance, souvent intuitive, permet de faire fonctionner beaucoup de choses dans nos vies quotidiennes.

On multiplie et on divise les choses à l'envie pour faire toutes sortes d'objets ou de raisonnements, et quand ça tombe pas juste, ça peut poser des questions, ou des problèmes. Les nombres entiers, les quotients, et le reste des divisions entières sert à tout ça. C'est aussi bien ce qui permet de fabriquer un plat pour le repas à servir à 3 personnes, que pour dessiner puis construire une horloge ou un moteur à explosion.

A partir de là, on comprend bien qu'il n'est peut-être pas nécessaire d'en savoir plus sur quelque chose qui nous rend déjà service, mais on peut aussi comprendre facilement que si on on savait plus on se faciliterait peut-être la vie dans certains cas.

Le projet sur lequel je planche ici, aussi ésotérique qu'il puisse paraître, consiste à déterminer quelle est la nature mathématique de la courbe des écarts entre nombres premiers, ce qui permettrait d'en reformuler mieux la distribution. C'est à dire, indirectement, de proposer une piste, ou mieux encore, une nouvelle formule, permettant d'améliorer la prédiction de primalité d'un nombre (je n'imagine pas dans l'immédiat que l'on puisse prédire exactement qu'un nombre quelconque soit premier, dans la mesure où toutes les méthodes connues qui permettraient de le faire mettent en jeu des séries de calculs qui tendent vers l'infini quand les nombres eux-mêmes tendent vers l'infini.).

Ce point est important pour quelques personnes, en recherche appliquée, parce qu'on utilise les nombres permiers dans un certain nombre d'application de traitement de données ou il est toujours pratique de prédire la primalité d'un nombre en un temps record par exemple (et ce nombre pouvant être assez grand on peut préférer calculer sa primalité plutôt que de stocker tous les nombres premiers possibles et immaginables et chercher si le nombre qu'on regarde en fait partie).

Voilà un peu l'essence de la chose sur laquelle on pourrait en dire encore tant, mais je ne voudrais pas devenir chiant. C'est en en sciant que Léonard devint scie comme on dit dans mon Auvergne natale (avec l'accent, essayez, vous comprendrez).

_________________
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 18:15 
Hors ligne
Avatar de l’utilisateur

Inscription: Ven 11/Fév/2005 17:34
Messages: 4222
Localisation: Arras, France
Je ne sais pas si je dois te remercier, car même si tu partages avec talent et enthousiasme ta passion, ce type de problème m'embarrasse l'esprit au point que je prends souvent des chemins d'évitement ! Là, impossible de passer à côté, et j'ai encore passé deux heures ce matin à cogiter...

Allez, je te remercie quand même, car c'est passionnant, et très agréable à suivre à ce niveau ;-)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: A propos de nombres premiers
MessagePosté: Dim 09/Oct/2016 19:45 
Hors ligne
Avatar de l’utilisateur

Inscription: Mar 31/Mai/2016 9:06
Messages: 2053
exemple concret de l'utilité des nombres premier
la cryptographie !

exemple le systeme RSA :
voici l'algo :

source : https://sciencetonnante.wordpress.com/2 ... -premiers/
Citation:
Pour aller plus loin : le détail de l’algorithme RSA

Choisissez deux nombres premiers P et Q (que vous gardez pour vous), prenons par exemple P=5 et Q=11.

Fabriquez le produit des deux N=P.Q, dans notre cas N=55.

Choisissez un nombre E n’ayant pas de facteur premier commun avec (P-1).(Q-1) Dans notre cas puisque (P-1).(Q-1) = 40 = 2*2*2*5, on peut choisir par exemple E = 7.

La paire (E,N) constitue la clé publique, que vous donnez à votre ambassadeur

Choisissez ensuite un nombre D tel E.D mod (P-1).(Q-1) = 1 par exemple dans notre cas D = 23 fait l’affaire car 7*23 mod 40 = 1

La paire (D,N) constitue la clé privée, que surtout vous gardez pour vous.

Comment se passe la procédure d’encodage ? Tout d’abord il vous faut ramener votre message à un nombre. Vous pouvez le faire par le moyen que vous voulez comme A=01 ; B=02 ; … ;Z =26 par exemple. Une fois votre message traduit sous la forme d’un nombre M, vous allez encoder ce nombre avec la clé publique (E,N) de la manière suivante :

C = M^E modulo N

Pour décoder C (et donc retrouver M), il vous faut appliquer une opération différente, utilisant la clé privée (D,N) :

C^D modulo N.

Et c’est là que les maths des nombres premiers nous sont utiles, car elles permettent de prouver que ça marche c’est-à-dire que l’opération de décodage permet effectivement bien de retrouver le message M initial. On peut en effet démontrer que :

(M^E modulo N)^D modulo N = M

_________________
Image
Image
Site: http://michel.dobro.free.fr/
Devise :"dis moi ce dont tu as besoin, je t'expliquerai comment t'en passer"


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 155 messages ]  Aller à la page Précédente  1, 2, 3, 4, 5, 6 ... 11  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye