Forum de mathématiques - Bibm@th.net

DrStone

Membre

Inscription : 07-01-2024

Messages : 273

Re : crible en python

PS.

>Encore une fois , avant de juger balaie devant ta porte ...

    ton côté paresseux

Bien entendu que j'ai moi aussi un côté paresseux ! Comme tout le monde. Je ne nie pas cette vérité. En revanche, lorsque j'utilise quelque chose j'apprends à m'en servir.

De fait, je n'utilise pas de fusées ni ne refait de charpentes. Donc je n'ai pas appris à faire des fusées ou à refaire de charpentes. Néanmoins, si demain je dois faire refaire ma charpente eh bien j'apprendrais : que ça me gonfle ou non ! (ça risque d'être un peu beaucoup moins vrai pour des fusées… en effet, il y a peu de chance que j'en ai jamais moi-même l'utilité)
Même si je deviens un vieux de 90 ans ! Je m'en sortirais alors peut-être pas tout seul pour ces travaux physiques à un âge aussi canonique ; mais ça c'est accessoire selon moi ! Le plus important est d'apprendre à faire.

Dernière modification par DrStone (11-11-2024 17:30:01)

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

toi qui je cite dans une de tes interventions :

    les gens sans informatique et mathématique il en serait encore entrain de cultiver , faire de l'élevage .!

..  mon pauvre crétin , c'est pourtant grâce à eux si tu peux te nourrir , te loger , etc etc , car le travail manuel pour toi , tu es bien trop fainéant , pour t'y résoudre

On entre dans la diffamation.

Non , ce n'est pas de la diffamation, contrairement à toi qui traites les gens de paresseux sans rien connaître de leur vie

je reprend donc ta phrase au complet

Le commun des mortels ne semblent pas se rendre compte que leurs vies gravitent entièrement autour des mathématiques et que sans elles, ils seraient encore, pour 90% d'entre eux, à biner à la main des champs, planter des fruits et légumes, etc… dans l'espoir d'avoir en retour de bonnes récoltes afin de ne pas, littéralement, mourir de faim durant l'hiver.

Ah oui ? 90% des gens sont des manuels , pour te permette de te nourrir , de t'habiller , de te loger , de conduire , te permettre de voyager , de faire tes course etc etc.. de construire un PC , pour y  faire fonctionner un programme...

Avant de faire de l'informatique ou des >Maths pour transformer les objets ou en construire , il faut te nourrir , te loger , t'habiller ...etc etc ,

et 90 % de ces gens, n'ont nul eut besoin de ton informatique pour vivre ni des maths ... Quand bien même elles sont utiles pour transformer la sté dont on voit le résultat ... Pour gagner ma vie  et monter ma sté, je n'en ai eut nul besoin . Contrairement à toi , pour gagner ta vie ... c'est ça le résultat ???

Ta phrase : c'est uniquement pour te faire mousser et te croire important vis à vis de 90% de ces gens .. et rien d'autre ..! 

Il me semble qu'il serait bon de s'arrêter là.

bien sûr quand on allume le feu , il faut savoir l'éteindre ...
D'ailleurs Yoshi  pourrait te dire comment je m'appel ... Loll...

Eh oui, initialement, tout part de ces deux mots.

Entièrement faux , et tu le sais ... relis un peu tes post après le post #415 , ou je me suis présenté , indiquai le matériel que j'avais ... ("afin qu'il n'y ai pas une mauvaise interprétation de mes possibilités") , ou sans me connaître , ni même connaitre ma vie, tu te permets  de dire que je profite de la gentillesse des gens..que je suis trop fainéant ... etc ..

si tu avais pris la peine de lire le sujet , au lieu de ta paresse en invoquent le prétexte que tu as une vie et de refiler des conseils inutiles , alors qu'il t'était simple de les installer dans le programme ... mais non ! Et  les autres , ils n'en ont pas de vie , c'est quoi cette excuse bidon...??
Tu as appris à réparer ton véhicule ou tes appareils ménagers dont tu te sers .
Arrête de te vanter s'il te plait, car je doute que tu sois en mesure de remplacer ta charpente même à ton âge actuel ... Avant de construire une fusée , apprends déjà à réparer un moulin à café électrique ou un aspirateur ...!

Qu'est ce que tu crois que j'ai fais dans ma vie et pas avec la g..., si ce n'est apprendre pour évoluer...

Non mais ...pour qui te prends ? tu es Alzheimer ?? Tu plantes la bouse et ensuite tu t'étonnes ... au lieu de sortir gentiment et de retourner à tes études ... ou à ta vie!
Qu'elle te soit profitable . bonne soirée et j'en reste là .

Dernière modification par LEG (11-11-2024 18:08:51)

DrStone

Membre

Inscription : 07-01-2024

Messages : 273

Re : crible en python

Tu n’as pas compris la phrase que tu cites. Celle-ci dit, en substance, que sans mathématiques pas de sciences, sans sciences pas de voitures, pas de médicaments, pas de cathédrales (oui, oui, même ça alors que c’est trèèèèès très ancien par rapport au reste), pas de vaccins, pas d’ordinateurs et pas de crible de monsieur LEG sur bibmath.net.

C’est la raison pour laquelle, 90% des gens qui ne comprennent pas que les mathématiques sont au cœur de leurs vies en seraient encore à biner les champs : car pas de tracteurs non plus ! Mais cela n’exclut aucunement que j’y serais moi-même entrain de biner les champs : je ne suis pas héritier de noble famille.

C’est tout. Cette phrase ne dit rien de plus. Rien de moins.

Dernière modification par DrStone (11-11-2024 18:51:02)

DrStone

Membre

Inscription : 07-01-2024

Messages : 273

Re : crible en python

ou sans me connaître , ni même connaitre ma vie, tu te permets  de dire que je profite de la gentillesse des gens..que je suis trop fainéant ... etc ..

Je n’ai pas écrit explicitement que tu profitais de la gentillesse des gens. J’ai écrit que si tu ne fais rien et tu te contentes (dans le cadre de ce programme C++ j’entends) d’attendre que le chaland arrive alors, selon moi, ça s’apparente à profiter de la gentillesse des gens. Nuance. Je sais, les nuances c’est énervant. Je n’y peux rien. Les mots ont un sens.
C’était peut-être maladroitement provocateur de ma part (ça je le reconnais) mais le but était que tu aies un sursaut qui te fasse te dire « tien il a peut-être raison sur le fait que je devrais au moins apprendre les rudiments pour implémenter moi-même ce qui m’intéresse. » non pas que tu te sentes attaqué de tous les fronts.
D’ailleurs si c’était aussi violent et méchant de ma part, nulle doute que yoshi qui est plutôt impartial m’aurait fait quelconque remontrance, voire m’aurait banni.

ne s'agit pas que de ça. Il s'agit aussi d'être capable d'apporter des modifications ou des améliorations par toi-même. Tu le dis toi-même, tu aimerais avoir la possibilité d'imprimer un tableau criblé (donc avec un résultat qui s'apparente à ce qu'on trouve dans ce post, j'imagine ?).
Mettons que je décide de ne pas le faire et de simplement réécrire le programme tel qu'il est en l'état simplement en le modernisant. Tu comptes faire quoi ? Attendre que quelqu'un d'autre débarque et le fasse pour toi ?
Ça s'apparente légèrement à profiter de la gentillesse des gens, non ? Alors même que, pourtant, cette idée d'imprimer le tableau comme dans le post mis en lien ci-dessus, ne demande presqu'aucune connaissance : juste les bases. Particulièrement en C++ moderne. Et nul besoin d'apprendre l'anglais pour apprendre les rudiments de la programmation. Il existe une littérature française fort bien fournie sur ces sujets — y compris des traductions d'ouvrages anglo-saxons.

Puis tu remarqueras que j’avais, encore, doucement réitéré ma proposition de te fournir des ressources pour apprendre toi-même (bien que j’avais compris à ce moment là, déjà que ce ne servirait sûrement à rien) ; et je n’aurais pas manqué de t’aider dans les moments difficiles.

Dernière modification par DrStone (11-11-2024 19:35:30)

DrStone

Membre

Inscription : 07-01-2024

Messages : 273

Re : crible en python

D’ailleurs si c’était aussi violent et méchant de ma part, nulle doute que yoshi qui est plutôt impartial m’aurait fait quelconque remontrance, voire m’aurait banni.

Nonobstant, je commence à croire qu’il le devrait, notre bon modérateur, me bannir (définitivement ?) même si je ne vois pas trop pour quel motif. Cela permettrait, eeeeeeeeenfin, de passer définitivement à autre chose !

Dernière modification par DrStone (11-11-2024 18:59:14)

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Il n' a aucune raison de te bannir , et il ne le fera pas , mais je pense que tu n'as vraiment pas besoins de ça , pour passer eeeeeenfin à autre chose ... Tu oublies que tu as le programme en C++ à refaire ... non ? La programmation je te la laisse... si cela avait été ma tasse de thé depuis des années  ... peut être , que je n'aurai pas payé pour faire modifier ce programme ... Je ne suis pas: Sensei (先生) Yoshi...

DrStone

Membre

Inscription : 07-01-2024

Messages : 273

Re : crible en python

Même si sans doute, pour le moment on verra.

Pour l’heure je suis juste dépité de la tournure qu’à prise cette discussion pour quelques mots aussi mal choisis que mal interprétés.

Quoi qu’il en soit, comme annoncé plus tôt, maintenant que les malentendus semblent à peu près dissipés, je vais faire une pause d’internet.

Dernière modification par DrStone (11-11-2024 19:44:04)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

RE,

Avant les 2 posts précédents, j'avais pondu une longue réponse.
Puis j'ai voulu me tenir au courant de la teneur exacte du manuscrit de Ibn Yasin...
J'ai jonglé entre les fenêtres pour revenir à ma réponse quasi terminée et paf, mauvaise combinaison de touches, qui a fermé la fenêtre de ma réponse en cours qui a été perdue, voilà ce que c'est que de confondre vitesse et précipitation !

Pourquoi bannirais-je l'un ou l'autre (ou inclusif) ?
Oui, il y a eu prise de becs et alors ? On n'est pas dans le monde des bisounours et elle (la prise de becs) n'avais dépassé  les limites de la bienséance...
De plus à vous relire, j'ai eu la nette impression que tout était parti d'une mauvaise interprétation des mots et de malentendus ; le Canard enchaîné met en exergue sur sa page 1, cette maxime dont j'ai oublié l'auteur (et j'ai la flemme de chercher) :
<< Sans la liberté de blâmer, il n'est pas d'éloge flatteur ! >>

LEG je vais continuer ma traduction, même si j'ai reçu un choc (je le digère lentement) et je chercherai le pourquoi à la fin de la traduction...
L'autre soir, dans ma période de tests de vitesses, j'ai extrait du programme Python les 2 fonctions Candidate_range(n) et Eratostene(n) d'origine qui peuvent fonctionner seules et les ai mises dans un fichier Python indépendant.
Puis j'ai fait la même chose avec ces fonctions revues en numpy (en fait, seule erato doit être modifiée) dans un autre fichier.
J'ai ensuite relevé les vitesses en appelant Erato.. et en lui passant en paramètre n=10**9...
J'ai failli tomber de ma chaise :
Python pur : 0,5 s et Python numpy : 25 s !!!
J'ai dû déconner quelque part... Où, je ne sais pas, j'y réfléchirai à la fin...
Parce que un tel os dans le potage, ce n'est pas banal : pour chacune des constructions de liste Python vs tableaux de numpy : numpy , rassemblées au sein de la fonction Erato : Python pur vainqueur par ko au 1er round. Invraisemblable, illogique !
Je trouverai !!!

Sensei (先生) Yoshi ? Il me semble qu'on dit plutôt Yoshi Sensei (先生). De toutes façons, Maître, c'est trop ! Monsieur si tu veux : Yoshi san...
Dans mon club de Kendo, j'étais parfois le Sempaï mais je n'ai fini que 1er kyu (équivalent de ceinture marron), j'ai tenté une fois le 1er dan, mais j'ai perdu le combat final...

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Bonjour  @Yoshi

^..^ ,En général , on dit seulement Senseï , on ne cite pas le nom... Du moins , c'est comme cela que je l'ai appris pendant des années , même dans le Bushido ^.^

Pour ce qui est de ton test, sur la rapidité d'exécution  entre Python pur : 0,5 s et Python numpy : 25 s !!!

Ben, c'est comme pour le programme C++ , dont je t'ai mis les résultat en temps, entre les deux limite n = 9*10¹⁸  et  2⁶⁴ , pour cette deuxième valeur , le programme indique une valeur trop grande pour être signée ... Mais il met 1,02 seconde pour cribler les trois familles ...???

Alors que pour la première valeur il met 124 secondes ???

La seul chose que je sais , en essayant de changer la valeur du slice : de 1 500 000 , en l'augmentant , 3 000 000 , puis 4 500 000 , et 6 000 000 , il va de plus en plus vite.. pour cribler jusqu'à la racine carrée de $n$ ... car je suppose qu'il n'a pas besoin de créer autant de tableaux de slices ...
Ce qui n'est pas le cas pour cribler jusqu'à la valeur n = 9000 000 000 000, si on ne descend pas la valeur du slice , il bug ... résultat : appuyer sur entrée pour continuer et Nada ^..^

Ce que je ferai des que possible, j'éditerai le résultat du tableau criblé pour n = 2⁶⁴ et je vérifierai les premiers $p'\not\equiv{2n}[P]$ représenté par 1, ou encore, plus simple si cela est possible , le résultat des deux programmes pour cette valeur $n$ , criblée jusqu'à racine de $n$, ce que j'ai déjà essayé jusqu'à 10¹⁷

à nouveau avec c++ et n = 10¹⁹  +24 temps 0,332 s , Fam 7 , nbr p' criblés < sqrt de 10 000 000 000 000 000 024 = 90 350 791 ;
nbr couples (p'+q) = 75 292 326 , j'ai paramétré le programme c++ en conséquence , tu pourras comme ça, faire une comparaison de teste avec cette valeur n et la fam 7 une fois ta modification faîte...

j'ai lancé python , pour la même valeur , cela fait trois plus de 2 heure qu'il mouline, je verrai le résultat..
je l'ai stoppé hier soir, car il moulinait toujours .
@+

Dernière modification par LEG (13-11-2024 08:54:04)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Salut LEG,

Une petite idée du pourquoi du paradoxe des temps ayant fait son chemin, j'ai voulu en avoir le cœur net et sachant quoi demander à Google, j'ai eu une réponse confirmant mes soupçons :
En cas de manipulation des tableaux numpy, il faut impérativement bannir l'emploi des boucles for...
la fonction eratostène(n), si j'ai transformé toutes les listes en tableaux, j'avais conservé les boucles boucles for en me disant : Bah  ! Pour une fois...

    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_E.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False

Si je veux modifier la fonction, j'ai besoin de comprendre précisément ce qui se passe dans ce morceau :
j'ai demandé l'affichage, pour différentes valeurs de n, de
- sieve_list
  avant et après la boucle for multiple
- de Prime_E
   avant et après la boucle for multiple

Je dois être fatigué et aveugle, parce que je'n'ai remarqué que la présence (en très très petite quantité) de False au lieu de True dans sieve_list.
Cette fichue Boucle en ai-je conclu, passe en revue un True après l'autre et en cas de multiple, opère le changement...
Là plusieurs questions se posent :
- Comment un True pourrait-il être le multiple d'un autre ?
- Multiple de quoi alors ? d'un nombre premier ? comment un nombre premier pourrait-il être le multiple d'un autre ?
  D'ailleurs Prime_E ne contient que des nombres premiers...
- Que signifie : if sieve_list[each_number] ?-->  Si l'élément stocké dans sieve list en position valeur de each_number est égal à True,
   alors... ?
   Comment pourrait-il en être autrement puisqu'on vient de remplir sieve_list de True ?

Tant que je ne comprends pas tout ça, je ne peux pas avancer, contrairement à ce que je pensais...
Il y a longtemps, j'ai pu rassembler deux morceaux en un seul, là, pour l'instant, je nage complètement...

Surtout que, ensuite, il a été introduit des noms de variables, de listes en anglais... et que ça ne facilite ni ma lecture, ni ma compréhension...
Que les mots-clés de Python soient en anglais, ça ne me dérange pas, c'est normal, c'est le cas de la majorité des langages courants de programmation puisque créés par des anglophones de naissance (ou de très longue date),
Qu'un programmeur anglophone, voire vivant dans un pays anglophone en dehors des mots-clés (où là il n'a pas le choix), s'exprime en anglais dans sa programmation, ma foi c'est naturel, mais moi je parle français, su je programme pour des francophones je m'exprimerai en français, si je dois programmer pour un non francophone et si je connais la langue ou que j'aie un bon dictionnaire, je ferai l'effort de m'exprimer dans sa langue, ou à défaut en anglais, mais qu'un francophone s'exprime en anglais dans un programme à destination des francophones, àa, ça ne passe pas !

J'ai déjà eu ce débat avec mon neveu, brillant cerveau, qui travaille actuellement pour Micro$oft et l'IA...
Lui en tient pour le tout en anglais : le langage de programmation étant en anglais, il trouvait (trouve ?) normal, logique, pour garder une forme d'unité, de cohérence, de s'y exprimer en anglais..
Quand je lui avais répondu que, moi, je n'y voyais qu'une forme de snobisme, d'affectation, ça l'avait beaucoup surpris...

Bon, ah !!!... ça y est, ça va mieux : j'ai vidé mon sac. ^_^

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Bonjour @Yoshi

Le souci,pour ce morceau :

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n = int((2*n)**0.5)
    prime_list = [2, 3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]
 

C'est toi qui l'a introduit  lors des modification , C'était plus rapide que les deux autres ci-dessous ; car si tu regardes , à la base je ne pense pas qu'il était écrit comme ça... dans le crible d'Ératosthène , pour cribler et extraire uniquement les nombres premiers de 7 à racine carrée de 2n , par rapport à la limite n fixée .  Nombres premiers, qui ensuite vont servir pour le crible d'ÉRATOSTHÈNE MODULO 30 avec cette fonction :

def E_Crible(premiers, n, fam):
    start_crible = time()
    n1 = int(n**0.5)
 

Puis ensuite, que pour le crible de Goldbach modulo 30  avec cette fonction :

def GCrible_2n(premiers, crible, lencrible, n, fam):
    start_crible = time()
    # On calcule les restes: r = 2*n/P
    nbpremiers = len(premiers)
 

c'est un petit crible d'Ératosthène dont on a besoin...afin d'extraire les nbr premiers qui vont être utilisés...

Voilà ci dessous comment cette première partie était écrit en 2018 : Tu dois avoir au début page 1 ta modification...

 V. 6.1 ## du 16.06.2018

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]
 

cette première version date de mars 2018 il n'y a pas  la limite =1+n : à été supprimée...

import os
import math
import time

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    b = [True]*m
    i = 0
    p = 3
    premiers = [2]
    while p*p < n:
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i += 1
        p += 2
    while i < m:
        if b[i]:
            premiers.append(p)
        i += 1
        p += 2
    return premiers[3:]
 

Donc je suppose que tu sais pourquoi ... mais il s'est passé du temps...
quelque soit l'une de ces trois fonctions, pour la première partie du crible Ératosthène , elle fonctionne... je viens de les tester avec le programme en référence ci dessus ...

je viens de regarder le début ,de nos échanges qui ont été modifiés mais  voici le post# 19 et 23

Post # 19 : je t’avais répondu :

La fonction Eratosthène doit extraire les nombres premiers Pi⩽√2n donc Pi⩽√2000=44
c'est tout ce qu'elle doit faire, pour utiliser ces Pi⩽44 dans la fonction du crible _G...ci dessous

post #23  une autre réponse suite à ta modification sur la première partie Ératosthène,,,:

j'ai copié ceci à la place de la mienne jusqu'à return premier :

def eratosthene(n):
    nombres, premiers = [],[]
    # n=int((2*n)**0.5)
    for i in range(2,n+1):
        nombres.append(True)
    for i in range(2,n+1):
        if nombres[i-2]:
            premiers.append(i)
            for j in range(2*i,n+1,i):
                nombres[j-2] = False
    return premiers
 

celle modification, par contre je ne l'ai pas testée , sur notre programme actuel en référence...

En espérant que cela t'aide à y voir plus clair... Dommage que Jeanne d'arc , n'est pas fait le ménage car les programmes serait en langue Française... ("loll")

Dernière modification par LEG (18-11-2024 09:21:19)

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Bonjour @Yoshi :

Là ou le programme python cité en référence , perd le plus de temps , c'est bien dans la première partie, def eratosthene(n):

Je  pense qu'il n'y a rien à y faire car c'est logique , si ce n'est que ta modification en numpy

Pour info : voila le résultat et le temps mis pour n = 6*10¹⁶

===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 60000000000000000
Nombre premiers prime_list  : 57.2
Nombre premiers criblés famille 19 : 1676915 ----- 17.38
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 60000000000000000 famille 19 : 150259 ----- 16.8

------------------------------------------------------------- n = 6*10^¹⁷

===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 600000000000000000
Nombre premiers prime_list  : 201.22
Nombre premiers criblés famille 19 : 4987802 ----- 55.9
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 600000000000000000 famille 19 : 420564 ----- 56.95
 

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Re,

Bah... J'ai fait une pause et je suis résolu maintenant à démonter pièce par pièce ce morceau de la def eratostene (n) et de tester les morceaux un par un pour savoir de quoi il retourne exactement...

for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False

Le problème c'est qu'il y a 2 boucles dont la 2e dépend de chaque élément de la première...
Tant que je n'ai pas compris ce qu'il s'y passe, si je sais par remplacer une boucle par une instruction numpy qui remplace le remplissage élément par une instruction globale, remplacer 2 boucles imbriquées, je n'ai aucune idée de la façon de procéder...
Tout ce que j'avais réussi à faire avec mon mix Python pur & numpy c'est de multiplier le temps Python pur par 50 !!! Brillant résultat...

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Oui effectivement , .. donc je te laisse , car moi je ne peux en aucun cas , émettre une idée..

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

RE,

Le point central de mon souci, c'est tout ce qui tourne autour de la variable multiple...
J'ai quelques idées sur le traitement des deux boucles imbriquées, mes tests m'aideront à y voir plus clair...

Je ne lâche pas l'affaire, no pb !

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

RE
C'est vrai que tel qu'il est le programme python , jusqu'à la racine carrée de 6* 10¹⁷ , ça va relativement vite ... Mais par contre 6*10¹⁸ ...là il galère un peu
pour la première partie def eratosthene  je n'ai pas pu aller jusqu'au bout ...8 heures après il moulinait encore...
Alors qu'il y a 98 222 287 nombre premiers P à extraire ...Au lieu de 39 905 625...
il est vrai que l'on passe du simple au double ..
Mais en C++ actuellement il ne met que quelques secondes pour les extraire et exécuter les deux autres parties du programme...
....Patience et longueur de temps font plus que force ni que rage ....
@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Re,

J'ai compris maintenant...
Dans un post précédent, je te disais ne pas comprendre, que c'était impossible qu'il y ait des multiples de nombres premiers à traiter...
J'ai identifié la source...
Dans ma mémoire, la 1ere version de candidate_range (peut-être sous un autre nom ?) version sans yield, était sans faille et ne fournissant que des nombres premiers...
Quelle n'a pas été ma surprise de constater (avec n=1000) que parmi les candidats premiers figuraient des multiples de 5 : 15, 25, 35, 55, 95, 115, 125
des multiples de 7 : 49, 91, 119, 133....
etc...
Je ne suis pas surpris qu'à un moment, ton prog se mette à patiner s'il doit repasser après la construction des nombres premiers et traiter ceux qui, en fait, ne le sont pas...
Si ma mémoire me trahit, je vais devoir me mettre en chasse d'une construction des nombres premiers plus performante en vitesse

Donc maintenant, je vais devoir vérifier si l'ancienne version était bien sans faute...

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Re tu en es sûr

Car je viens de regarder : avec la def candidate_range , il n'y a pas d'erreur , qu'il y a dans le programme en référence...

from time import time
from os import system

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    start_crible = time()
   
    n = int((2*n)**0.5)
    prime_list = [2, 3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])

pour n = 300000

[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773]
Nombre premiers prime_list[3:] : 0.0
 

Il n'y a bien que les nombres premiers > 5...

Il suffit même d'éditer le total des nombres premiers ,afin de voir qu'il correspond bien ...à la réalité ,  (inférieur à racine carrée de 2n.= 774)

sinon il ne patine que pour la limite n = 6*10¹⁸ mais pas en dessous

Dernière modification par LEG (19-11-2024 20:20:18)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

RE,

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n = int((2*n)**0.5)  ##(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E =[2]
    sieve_list=[True for _ in range(n+1)] # (que des True (n+1 fois)
    for each_number in candidate_range(n):
        print (each_number)
        if sieve_list[each_number]:
            print("-",each_number)
            prime_E.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
       return prime_E[2:]
 

n=10000
eratostene(n)
J'ai 25,35,49,55,77,95,115,125...
Si ton crible est sûr, alors, pourquoi tester s'il y a des multiples et passer sieve_list[multiple] de True à False (ce qui me dérange depuis le début):

for multiple in range(each_number*each_number, n+1, each_number):
    sieve_list[multiple] = False

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Re :

Effectivement cette instruction ne sert à rien

for multiple in range(each_number*each_number, n+1, each_number):
    sieve_list[multiple] = False
 

Mais à l'origine lorsque tu essayais de modifier le programme , pour gagner du temps , il "" me semble "" que c'est toi qui avait modifié la première partie du programme , ou à moins que tu es repris le programme python d'origine de mon petit fils... en 2019 ...

car effectivement il suffit simplement d'utiliser cette partie ci dessous , mais cela n'explique pas pourquoi ton programme fait apparaître la ligne verticale avec des multiple de 5 etc  etc .?
Car même en supprimant ces deux lignes de programme , ces multiples apparaissent toujours ligne verticale du résultat ... Or il faut justement les supprimer , ce que fait ensuite la fonction :
for multiple in range(each_number*each_number, n+1, each_number):
    sieve_list[multiple] = False

-----------------------------------------------------------------------------------------------

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    start_crible = time()
   
    n = int((2*n)**0.5)
    prime_list = [2, 3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
           # #for multiple in range(each_number*each_number, n+1, each_number):
               # #sieve_list[multiple] = False
    print(prime_list[3:])
    print(f"Nombre premiers prime_list[3:] : {int((time()-start_crible)*100)/100}")        
    return prime_list[3:]
 

qui a le même résultat que ton post ci-dessus , en ne regardant le résultat de la ligne du bas horizontal du bas  :

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n = int((2*n)**0.5)  ##(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E =[2]
    sieve_list=[True for _ in range(n+1)] # (que des True (n+1 fois)
    for each_number in candidate_range(n):
        print (each_number)
        if sieve_list[each_number]:
            print("-",each_number)
            prime_E.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
       return prime_E[2:]
 

on ne peut pas supprimer cette fonction, qui supprime les multiples de 5 et autres, ce que je viens de tester

  # for multiple in range(each_number*each_number, n+1, each_number):
                #sieve_list[multiple] = False
 

je vais donc tester avec ta partie de programme , jusqu'à 6*10¹⁷ et voir le résultat... que je t'afficherai...

teste effectué :, il met 3 fois plus de temps , si on supprime la fonction :

for multiple in range(each_number*each_number, n+1, each_number):
    sieve_list[multiple] = False
 

voila le résultat du teste avec la fonction actuelle  :

Donnez n: 600000000000000000
Nombre premiers prime_list[3:] : 199.25
Nombre premiers criblés famille 7 : 4988801 ----- 55.75
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 600000000000000000 famille 7 : 422407 ----- 55.96
>>>
 

voici le résultat avec ta fonction def eratosthène n , ci-dessus,  il met 20 seconde de plus

===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 600000000000000000
Nombre premiers prime_E[2:] : 220.81
Nombre premiers criblés famille 7 : 4988801 ----- 55.28
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 600000000000000000 famille 7 : 422407 ----- 56.33
>>>
 

conclusion , il s'agit bien d'un petit crible d'Ératosthène  : on utilise bien et uniquement  dans les deux cas, les nombres premiers $P\leqslant\sqrt{2n}$ , pour cribler ensuite, par fam modulo 30, aussi bien pour :

def E_Crible(premiers, n, fam):

ainsi que pour:

def GCrible_2n(premiers, crible, lencrible, n, fam):

Jusqu'à la racine carrée des deux tableaux criblés...

Pour te donner une idée, en criblant les nombres $p'$ de la def Ératosthène inférieur à racine de $n=300 000$ puis ensuite,
tableau qui est re-criblé par la def GCrible 2n
voici le résultat :

===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 300000
Nombre premiers prime_list[3:] : 0.0
crible Ératosthène : [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]
Nombre premiers criblés famille 7 : 13 ----- 0.0
crible É ET G: [1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0]
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 300000 famille 7 : 7 ----- 0.0
 

Où tu peux vérifier que les premiers $p'\not\equiv{2n}[P]$ repésenté par [1] modulo 30, vérifient bien la conjecture de Goldbach . avec les p' = 7, 67, 157, 307 , 337, 397, et 487. ; qui ont pour complémentaire les nombres premiers $q$ appartenant à la famille 23 modulo 30

Contrairement à ce qui est dit...les nombres premiers $q$ dépendent bien de la congruence des nombres premiers $p'$ de 1 à n et on ne peut dire, qu'ils  sont indépendants ...!
Tout comme il est impossible de supposer que pour n +15 = 300015 , ou encore 300030 etc .. la conjecture pourrait être fausse  avec cette famille 30k+7.
car il suffit simplement de déplacer le vecteur du cible É ET G, d'un rang sur le vecteur du crible Ératosthène , pour voir jusqu'où elle est vérifiée...etc

Donc imagine avec un vecteur É ET G vérifié, jusqu'à la limite n=6*10¹⁷ ...Tu as une conjecture vraie sur plusieurs millier d'entiers pairs 2n consécutifs etc etc.
Tu va donc repousser la limite n du double à chaque vérification ... Jusqu'à ce que tu arrives à une grande limite, où la conjecture est vraie ... (^.i.^)

Actuellement il est efficace jusqu'à racine carrée de n=6*10¹⁷ , ce qui est pas mal du tout pour ton programme python que tu avais modifié et unifié, tu vas pouvoir vérifier ce que cela donne en numpy...

   
@+

Dernière modification par LEG (20-11-2024 11:38:48)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Ave,

Bon on avance...

Ça, j'avais bien vu... ce qu'elle faisait !
Mais je me pose deux questions existentielles (si ! si )...
1. D'abord, cette instruction :

if sieve_list[each_number]:

    J'ai pensé que ceci voulait dire : si l'élément de la liste sieve_list d'index each number est vrai alors....
    Pourquoi  cette  condition ne serait-elle pas vérifiée ? En effet 3 lignes au-dessus; sieve_list a été remplie de(n+1) fois  True.   
   

sieve_list=[True for _ in range(n+1)]

    Ligne suivante :
   

 for each_number in candidate_range(n):

    Là - en principe - tu ne fabriques que des nombres premiers.
    C'est ce que j'ai voulu savoir avec mes "mouchards" (les print() que j'ai rajoutés et qui ne servent à rien d'autre), donc arrive mon premier
    mouchard : print (each_number)
    Puis vient le fameux test qui m'intrigue :
   

if sieve_list[each_number]:

    _  La sieve_list à ce stade ne contient que des True, ok ?
    _  each_number est un nombre premier  qui sert d'index de position pour extraire l'élément sieve_list[each_number] et demander s'il vaut
        True.
    D'où ma question : est-il possible que l'élément sieve_list[each_number] ne soit pas True ? Si oui, alors pourquoi, puisque du premier élément au dernier, on ne l'a rempli qu'avec True ? et qu'à ce stade aucun élément de sieve list n'a été passé  à True...
    Ensuite, dès que cet élément est bien catégorisé True, et qu'il est en position de nombre_premier, tu passes tous les positions de ses multiples jusqu'à n à False.... et tu remontes en courant jusqu'au prochain each_number premier pour le tester...
    Voilà pourquoi....
    En fin de compte, à la sortie de la def eratostene, sieve_ list ne devrait contenir de False qu'aux positions de multiples de nombres premiers...
Voilà mon morceau test pour repérer les nombres issus de candidats(n) et qui ne seraient pas premiers :

from time import time
from os import system

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n = int((2*n)**0.5)  ##(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E =[2]
    sieve_list=[True for _ in range(n+1)] # (que des True (n+1 fois)
    for each_number in candidate_range(n):
        print ("Brut de sortie de candidate_range :",each_number) # mouchard_1
        if sieve_list[each_number]:
            print("each-number après questionnement True :",each_number) # mouchard_2
            print()
            prime_E.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_E[2:])
    return prime_E[2:], sieve_list

n=10000
P,S= eratostene(n)

Bruts de sortie (normaux) 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 43, 59
Faux : 35, 49, 55...

Et pourtant (rassurant), voilà la liste E :
[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139]
Pas d'erreurs...

Ton procédé de mise en évidence de l'exactitude de la conjecture de Goldbach ne porte que sur les nombres premiers et uniquement eux, s'pas ?
D'où ma 2e question (sûrement naïve) pourquoi traîner cette liste sieve_list, puisque disposant d'une liste de  nombres premiers ?

Pour finir :  non, non, l'écriture de cette fonction sous cette forme n'est pas de moi :100 % de certitude...

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Pour finir :  non, non, l'écriture de cette fonction sous cette forme n'est pas de moi :100 % de certitude...

ok .. Donc c'est le programme python que mon petit fils avait charger , pour extraire les nombres premiers $P\leqslant\sqrt{2n}$ dont on a besoins pour les deux fonctions suivantes de l'algorithme ...def Ecrible et def GCrible

Ton procédé de mise en évidence de l'exactitude de la conjecture de Goldbach ne porte que sur les nombres premiers et uniquement eux, s'pas ?

Tout à fait

Et pourtant (rassurant), voilà la liste E :
[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139]
Pas d'erreurs...

Exactement

D'où ma 2e question (sûrement naïve) pourquoi traîner cette liste sieve_list, puisque disposant d'une liste de  nombres premiers ?

  j'en ai :  Absolument aucune idée ...

Je suppose que je peux  supprimer  if sieve_list[each_number]:  et voir ce que cela donne....

Ce que je viens de faire ... désastre : il y a les multiple de P qui apparaissent donc on ne peut pas la supprimer ou faire autrement !
Donc je ne sais pas ce qu'il faut enlever, pour ne pas traîner cette liste sieve_list  ???  Sans altérer cette partie de programme...

Mais pourquoi ;    return prime_E[2:], sieve_list ...à quoi cela sert de retourner sieve_list , puisque cela fonctionne sans ça ?

@+

Dernière modification par LEG (20-11-2024 14:30:22)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Re,

Encore une scorie je voulais vérifier les False apparaissant dans sieve_list...
Bin je m'en vais doinc me concentrer sur l'intérêt de sieve_list :
1. Avec sieve_list, on dispose de  la position de tous les nombres non premiers parmi les entiers de 1 à n, et  par ricochet les autres sont premiers . Quel intérêt a-t-on de savoir où sont les premiers entre 1 et n ?
2. On dispose pourtant, aussi de la liste des nombres premiers...
    Si vraiment, je n'arrive pas  à trouver la réponse, alors je me concentrerais sur le contraire de ce qui est fait : construire sieve_list à partir
    de prime_E[2:] : je suis presque convaincu qu'il y a du temps à gagner : je devrais à pouvoir remplacer ces 3 boucles imbriquées (plus la
    toute première) par des instructions numpy globales...

@+

[EDIT]
1ers constats
Q. Que fait la def eratostene(n) ?
R. Elle construit sieve_list et Prime_E...

Q. D'où est-elle appelée sachant que d'origine elle ne retourne que la liste de nombres premiers ?
R. Depuis la def main() qui récupère la liste des premiers générés...

Q. A quoi sert alors la sieve_list ?
    Si candidate_range était fiable : à rien !!!
    En fait son seul boulot c'est d'expurger, prime_E des "quelques" non-premiers générés par candidate_range...

Il faut savoir qu'en Python tout ce qui se passe dans une fonction est de l'ordre du local : tout calcul, tout résultat, tous les noms de variables s'ils ne sont pas retournés en fin de def avec Return restent totalement inconnus à l'extérieur de ladite def...

Dernière modification par yoshi (20-11-2024 16:35:47)

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 738

Re : crible en python

Re

Quel intérêt a-t-on de savoir où sont les premiers entre 1 et n ?

Absolument aucun ...du moment que l'on a la liste des nombres premiers $P\leqslant\sqrt{2n}$ .
Sauf ...,  si cette fonction permet justement d'éliminer les multiples de $P$

Dernière modification par LEG (20-11-2024 16:22:06)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 223

Re : crible en python

Re,

J'ai testé candidate_range vs la  dernière version que j'avais retouchée...
Y a pas photo avec un n brut de 50000, le premier me fournit au moins une vingtaine (à la louche) de faux premiers (multiples) :
[5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 187, 191, 193, 197, 199, 203, 205, 209, 211, 215, 217, 221, 223, 227, 229, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265, 269, 271, 275, 277, 281, 283, 287, 289, 293, 295, 299, 301, 305, 307, 311, 313]

et l'ancien:
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313]

Pourquoi ? je ne sais pas. Je verrais ça plus tard
Le seul intérêt de sieve_list est était de corriger cette aberration.
J'ai donc prévu de t'aider à t'en passer et de tout ce qu'il y avait autour...

Ça va être à toi de jouer (mdifications minimalisées) :
1. Tu commences par charger ton programme.
2. Tu supprimes les def candidate_range(n) et eratostene(n)
3. Tu enregistres ton programme  sous un autre nom !!) impératif, hein...
4  Tu rajoutes la remplaçante:

def candidats(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    b = [True]*m
    i = 0
    p = 3
    premiers = [2]
    while p*p < n:
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i += 1
        p += 2
    while i < m:
        if b[i]:
            premiers.append(p)
        i += 1
        p += 2
    return premiers[3:] # 3 ou 2 . Si 3 --> 2, 3, 5 pas présents
 

5. Enfin, tu vas dans def main(n)
- tu mets un # devant premiers = eratostene(n)
- et dessous tu écris
premiers = candidats(n)

Questions :
1. Le plus important : ça fonctionne ?
2. Vitesse : beaucoup de perte ?
3. limite maxi de n : changement ?

Je pars du principe que ça va fonctionner...
Je vais redémarrer sur numpy et voir d'abord à modifier candidats, puis le reste...

@+

---

Arx Tarpeia Capitoli proxima...