Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#276 06-07-2018 10:36:14

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

Bonjour @Yoshi

Je ne sais pas si tu cherches toujours à amélioré , mais voila la partie du programme que j'ai "modifié" , mais qui crible faux...

par exemple pour n=240 j'ai 8 comme résultat et pour n = 24 300 000 000 j'ai 8 fois plus de premiers Mais , c'est le temps mis qui est intéressant 37 seconde au lieu de 131...Alors peut être que c'est dû au fait qu'il est faux ....?

voila la partie modifiée juste en dessous de la ligne r=nn%pi remplacé par j=nn%pi

en tenant compte que dans le programme j=r+pi*(1-r%2), qui correspond au début, on vérifie si j%30==1 , qui indique la fin sinon on incrémente par pas de ,pi*2... des que le j%30==1 est trouvé on passe au criblage


 debut,fin,pas=j+pi*(1-j%2),(j+pi*(1-j%2))%30==1,pi*2    # j'ai modifié (fin) afin qu'il s'arrête des que j%30==1
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:          # j'ai donc modifié  
              fam=Dico[1]
              testbit=(1<<fam)&temoin
              if not testbit:
                 temoin=(1<<fam)|temoin
                 debut_index=j//30
                 Nombres_fam=nombres[fam]
                 for index in range(debut_index, nbcell,pi):
                   Nombres_fam[index] = 0  
 

partie d'origine programme actuel :


j=nn%pi
 debut,fin,pas=+pi*(1-j%2),pi*30,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:
                fam=Dico[1]
                testbit=(1<<fam)&temoin
                if not testbit:
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0  
 

C'est donc cette partie, que je n'arrive pas à résoudre pour qu'il crible au fur et à mesure , et pour chaque pi en gagnant du temps et de la mémoire .


 debut,fin,pas=r+pi*(1-r%2),(r+pi*(1-r%2))%30==1,pi*2    # j'ai modifié (fin) afin qu'il s'arrête des que j%30==1 et qu'il crible.
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:          # j'ai donc modifié
 

Mais je patine dans la choucroute.....
@+

Dernière modification par LEG (07-07-2018 06:12:59)

Hors ligne

#277 06-07-2018 13:05:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 026

Re : crible en python

Salut,

Oui, je cherche toujours...
Mais je bute sur le remplacement du fichier final nombres qui ne contient que 1 ou 0.
Que ce soit 0, 1 ou 255 ça occupe 1 octet en mémoire...
Avec n=30 000 000 000
Ce fichier occupe 30 000 000 0000/30 *8 soit 8 000 000 000 octets, soit 8 Go...
Chez moi le test avec cette valeur de n plante : memory out...
Tous les essais de contournement se sont révélé prohibitifs en temps...
Je n'ai pas perdu tout espoir ...

Je vais me pencher sur ton pb...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#278 06-07-2018 15:32:17

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

moi j'ai tester 36 000 000 000, mais pour une famille soit : 1 200 000 000 octets....voila pourquoi il faut cribler uniquement par famille, il en est de même pour Eratosthène modulo 30 ...où je vais jusqu'à 15 000 000 000 octets par famille...

Par contre tu dis que 255 ou 1, ne prend qu'un octet.. donc un entier n compris entre 7 et n/30 , quelque soit cet entier il ne prendrait qu'un octet....? car si c'est le cas on a pas besoins du tableau de 1 pour une famille ....mais cela m'étonnerait...!

Dans cette hypothèse il suffit de cribler modulo pi*30 en partant de R = j tel que j est le reste de nn%pi

exemple n= 3600 soit, 3600/30 = 120 [1] ok...

donc :nn =7200 ; pi = 7 on veut cribler la fam, Dico={1:0} donc : fam=Dico[1]

j = 7200%7 == 4
on cherche j < 7*30 , congru a 1 modulo 30

  il faut que cette ligne soit modifiée 

debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2  

afin de ne s'occuper que de j%30==1
exemple :
4+7 = 11 qui correspond à j+pi*(1-r%2), 11 != 1%30 , on incrémente 11+14 = 25 ; 39 ; 53;  67; 81 != 1%30 ;95; 109; 123;137 ;
151 = 1%30 on passe à la phase criblage modulo pi*30 = 210

d'où :
151 +210+ 210 +210.....etc +210  jusqu'à <=3600 ce qui donne le nombre de [0] 16 +1 = 17 [0]   fin pour pi =7
et on stock les valeurs pour connaître les doublons afin de ne pas supprimer des [1] qui seraient marquer plusieurs fois ....autrement dit les valeurs sont les [0], une valeur qui apparaît plusieurs fois, ne vaut qu'un [0]
ce qui donne :
{151,361,571,781,991,1201,1411,1621,1831,2041,2251,2461,2671,2881,3091    ,3301,3511}
************************************
on passe à pi =11 on réitère 7200%11 == 6
6+11=17 on incrémente jusqu'à j%30==1 ; 17+22, +22 = 61 et 61%30 == 1 ok, on passe au criblage modulo pi*30 = 330

61 + 330 ....etc <= 3600

ce qui donne 10 [0] car il y a un doublon en rouge :

61,391,721    1051    1381    1711    2041    2371    2701    3031    3361  fin pour pi = 11
****************************************
on passe à pi =13 on réitère 7200%13 == 11
11+26 on incrémente jusqu'à j%30==1 ; 37+26, +26+26+26+26+26+26+26+26 = 271 et 271%30 == 1 ok, on passe au criblage modulo pi*30 = 390

271 ,661,1051,1441,1831,2221,2611,3001,3391
ce qui donne 7 [0] car il y a 2 doublons en rouge :
***************************************

etc....etc  jusqu'à pi = 83  il est clair que les derniers pi, ne vont pas marquer grand chose à part des doublons...

ensuite, à la fin comme tu l'as dit, on retranche le nombre de [0] de la somme des [1] = 120...

Est ce plus simple et plus rapide pour de grandes valeurs de n.....? est ce que l'on va à n = 30 mds....? car il faut trier les doublons....je doute que cela soit plus efficace....que de modifier cette partie , afin de chercher j=1%30 , et passer à la phase criblage , pour chaque pi:


  j=nn%pi
 debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2
        temoin=0
        for j in range(debut,fin,pas):    
            if j%30==1:
 

j'ai remplacer le r par j, et on aurait pas besoins d'aller jusqu'à pi*30 pour une majorité des pi , puisque la fin est ordonnée par j%30==1

il suffit ensuite de changer j%30==p8;  par l'une des 8 familles que l'on veut cribler...

Dernière modification par LEG (06-07-2018 15:34:55)

Hors ligne

#279 06-07-2018 17:06:55

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 026

Re : crible en python

Re,


J'ai questionné Python pour savoir quelle taille mémoire occupait la liste nombres pour n=300 000 000 .
Réponse : 6400000512 octets, soit 6,4 Go...

Je reprends.
1 octet c'est 8 bits.
1 en base deux c'est 00000001
2 en base deux c'est 00000010
3 en base deux c'est 00000011
............................
127 en base deux c'est 011111111
255 en base deux c'est 111111111

De gauche à droite, chaque bit vaut 128, 64, 32, 16, 8, 4, 2, 1 multiplié par 0 ou 1...
Avec 4 octets, soit 32 bis, on peut coder n'importe quel nombre entre  0 et 2**32-1 =  4294967295
Avec 8 octets, soit 64 bits, on peut coder n'importe quel nombre entre  0 et 2**64-1 = 18446744073709551615.

En binaire :
4294967295 = 11111111111111111111111111111111
Je vais reprendre mes essais parce que l'idée de départ était bonne, mais les durées sont - curieusement - invraisemblables par rapport à la construction d'une liste de 8000000000 de 1 !!!
La liste nombres, c'est au départ 8 lignes de nbcell nombres égaux à 1..
Pour n=30 000 000 000, on obtient nbcell= 1 000 000 000.
Soit pour la liste nombres 8 lignes de 1 milliard de 1...

L'idée m'était venue de remplacer par exemple [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] par le nombre binaire 1111111111111111 soit en décimal :
65635 et donc remplacer la liste de 8 listes de 1 000 000 000 de 1 par un seul nombre dont la représentation binaire était composée de 1 milliard de 1, mais le temps de calcul de ce nombre exact est vraiment vraiment prohibitif : il comprend, en base dix, 125 000 000 de chiffres, il vaut très exactement [tex]2^{1\,000\, 000\, 000}-1[/tex].
J'avais trouvé comment remplacer un bit dans n'importe quelle position de  n'importe quel nombre et le mettre à 0 quand il vaut 1 et le laisser à 0, sinon.
Dommage ! (mais je n'ai pas renoncé à l'idée même si je ne vois pas trop comment m'en sortir)

donc un entier n compris entre 7 et n/30 , quelque soit cet entier il ne prendrait qu'un octet....?

J'ai dit :
avec 1 octet on peut représenter n'importe quel nombre entre 0 et 255 (=[tex]2^8-1[/tex])  --> 8  = 8 * 1
avec 2 octets on peut représenter n'importe quel nombre entre 0 et 65535 (=[tex]2^{16}-1[/tex])  --> 16 = 8 * 2
avec 3 octets on peut représenter n'importe quel nombre entre 0 et 16777215 (=[tex]2^{24}-1[/tex]) --> 24 = 8 * 3
avec 4 octets on peut représenter n'importe quel nombre entre 0 et 4294967295 (=[tex]2^{32}-1[/tex]) --> 24 = 8 * 4
............................................
avec 8 octets on peut représenter n'importe quel nombre entre 0 et 18446744073709551615 (=[tex]2^{64}-1[/tex]) --> 64 = 8 * 8

Donc l'idée est économique, mais le temps de calcul du nombre est lui inacceptable.
Pourtant, j'ai la sensation de rater quelque chose...

Je vais essayer de regarder ce que tu racontes...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#280 06-07-2018 18:49:51

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

donc ce n'est pas énorme en mémoire car prenons n = 30 000 000 000 soit 1 de nombre en progression arithmétique de raison 30, que l'on ne va pas écrire en totalité, et au pire chaque nombre prendrait en moyenne 2 octets soit au maximum 20 000 Pi qui cribleront modulo Pi*30 .
d'où plus Pi est grand, moins on écrit de nombres en progression Pi*30 entre 7 et n/30, et cela en partant de j = 1%30 si on crible la famille p8 = 1.
dans l'exemple du post ci-dessus avec Pi<= 83 . cela donne :

{151,361,571,781,991,1201,1411,1621,1831,2041,2251,2461,2671,2881,3091 ,3301,3511}

61,391,721    1051    1381    1711    2041    2371    2701    3031    3361  fin pour pi = 11

271 ,661,1051,1441,1831,2221,2611,3001,3391

première colonne sont les débuts index puis criblage modulo pi*30

451    ;961    1471    1981    2491    3001    3511
                       
151    ; 721    1291    1861    2431    3001    3571
                       
1    ;691    1381    2071    2761    3451   
                       
211    ;1081    1951    2821           
                       
721    ;1651    ,2581    3511           
                       
1021    ;2131,    3241               
                       
271    ;1501    ,  2731               
                       
1051    ;2341                   
                       
1231    ;2641                   
                       
151    ;1741,    3331               
                       
61    ;1831                   
                       
1771    ;                   
                       
31    ;2041                   
                       
1591    ;                   
                       
1141    ;3331                   
                       
1591    ;                   
                       
1141    ;

ce qui donne bien 52 nombres premiers de 3600 à 7200 , congrus à 29 [30]

Dernière modification par LEG (06-07-2018 18:51:09)

Hors ligne

#281 07-07-2018 10:12:42

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 026

Re : crible en python

Salut,

Dans un premier temps je repars de ton post #276...
Et j'ai retouché (très peu) la v. 6.3...
Pour n =2.400.000.000 je gagne 1 s...
Voilà la partie modifiée :


    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2
        temoin=0
        for j in range(debut,fin,pas):
            j30=j%30                                            #ici
            if j30 in [1, 7, 11, 13, 17, 19, 23, 29]:    #ici
                fam=Dico[j30]                                  #ici
                if not ((1<<fam)&temoin):
 

Maintenant, je vais regarder de plus près ta motif  du #276 et chercher pourquoi elle plante...
Quand je saurai, je me pencherai sur ton dernière suggestion...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#282 07-07-2018 11:03:25

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

Maintenant, je vais regarder de plus près ta motif  du #276 et chercher pourquoi elle plante...
Quand je saurai, je me pencherai sur ton dernière suggestion...

De ce que j'ai pu comprendre ça ne criblerait pas; du fait que pour (fin,) j'ai mis (j+pi*(1-j%2))%30==1, en croyant que des l'instant où il y a j%30==1 cela terminait le processus des j , donc inutile d'aller jusqu'à pi*30.... et que l'on passerait à la phase criblage....

Je vais essayer ta modif pour la fam=Dico [1]

Hors ligne

#283 07-07-2018 12:06:31

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

voici les tests pour la fam=Dico[1] avec ta modif:

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 21000000000
Phase d'initialisation: 1.9968032836914062 seconds ---
Bloc S2_s3 : 103.94298267364502 seconds ---
Extraction des premiers n à 2*n : 5.3196094036102295 seconds ---

**  108685478 nombres trouvés en 111.25939536094666 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.3088040351867676 seconds ---
Bloc S2_s3 : 121.43061327934265 seconds ---
Extraction des premiers n à 2*n : 6.130810499191284 seconds ---

**  125009260 nombres trouvés en 129.8702278137207 secondes **

ensuite j'ai re modifié :


debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2  # ici
       temoin=0
       for j in range(debut,fin,pas):
           if j%30==1:                     # ici            
             fam=Dico[1]    # modifier la valeur de la fam à cribler [1,7,11,....,29]
             if not ((1<<fam)&temoin):
 

voici les tests
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 21000000000
Phase d'initialisation: 1.9968035221099854 seconds ---
Bloc S2_s3 : 103.35018134117126 seconds ---
Extraction des premiers n à 2*n : 5.304009199142456 seconds ---

**  108685478 nombres trouvés en 110.6509940624237 secondes **
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 24300000000
Phase d'initialisation: 2.3400039672851562 seconds ---
Bloc S2_s3 : 122.10141444206238 seconds ---
Extraction des premiers n à 2*n : 6.146410703659058 seconds ---

**  125009260 nombres trouvés en 130.5878291130066 secondes **
>>>

Comme tu peux le voir, cela ne change pas grand chose...

C'est pour cela que je voulais modifier cette ligne afin qu'elle s'arrête des que j%30 ==1 est trouvé, puisque ensuite on va les tester à la ligne en dessous ("for j in range(debut,fin,pas):")

debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2

Hors ligne

#284 17-07-2018 15:22:24

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

Bonjour
j'ai laissé tourner un peu le cribleG4Y pour n = 29 970 000 000 , car je pensais qu'il "beuguait" et ben non:

Donnez la valeur de n = 30k : 29 970 000 000
Phase d'initialisation: 3.6816067695617676 seconds ---
Bloc S2_s3 : 5224.839176654816 seconds ---
Extraction des premiers n à 2*n : 31.137654781341553 seconds ---

**  152859833 nombres trouvés en 5259.658438205719 secondes **
Appuyez sur une touche pour continuer...

******************************
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 29 100 000 000
Phase d'initialisation: 4.321207523345947 seconds ---
Bloc S2_s3 : 173.519104719162 seconds ---
Extraction des premiers n à 2*n : 7.363212823867798 seconds ---

**  148600698 nombres trouvés en 185.20352506637573 secondes **


c'est quand même curieux la différence de temps qu'il y a pour n = 29 100 000 000 pour une différence relativement faible

sqrt de 2*29970000000 et sqrt de 2*29100000000 :  ce qui représente environ un écart de 300 nombres premiers pi en plus, qui vont cribler très peu de nombres...

Hors ligne

#285 19-07-2018 10:49:50

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

Bonjour @Yoshi
D’après tes explications au post # 258, page 11 . Pour chacun des Pi tu vides les Pfam à chaque tour pour ne pas les stocker…
A_) Mais est-ce que cela concerne aussi les j… de la ligne de programme

 debut,fin,pas=j+pi*(1-j%2),pi*30,pi*2

Ou bien, est-ce que cette ligne, met en cache tous les j <= pi*30 , relatif à leurs pi, pour être traité ensuite par la ligne de programme en dessous, (« que j’ai modifiée post #258, pour ne travailler que par Fam»).

 
for j in range(debut,fin,pas):
           if j%30==1:
             fam=P8[1]

etc…ensuite rien ne change.

B_) Ma question est : Puisque l’on a besoin que d’un j %30==1 (« en criblant uniquement par Famille en exemple, fam=P8[1] ») ; peut-on modifier la ligne debut,fin,pas= , afin de limiter les j jusqu’à j%30==1 qui correspond à fin. .. ? Pour chaque Pi , et que l’on vide à chaque tour de criblage pour passer au Pi suivant …. ?
Ce qui sous-entend , que cette ligne vérifiera au fur et à mesure les j%30…
Et la ligne

 
for j in range(debut,fin,pas):
           if j%30==1:

devra surement être modifiée afin de ranger j%30==1 dans fam=P8[1]….
Et continuer la fin du programme sans rien changer…Ensuite on passe au Pi suivant…. Non ?

A moins que cela ne change pas grand chose....

Hors ligne

#286 20-07-2018 07:58:43

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 026

Re : crible en python

Salut,

Tout est dit là :


    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2
        temoin=0
        for j in range(debut,fin,pas):
            if j%3!=0 and j%5!=0:
                fam=Dico[j%30]

Pour chaque pi issu de la def eratostene sont créées
- la valeur d'entrée de boucle : debut
- la valeur de fin de boucle : fin. En fait, en Python, comme beaucoup de langages de programmation, la sortie se fait à fin-1
- le pas (pi*2) : l'écart entre un j donné et le suivant.
Moyennant quoi  je rentre dans la boucle et je ne vais conservé un j donné que s'il n'est ni multiple de 3, ni de de 5 : if j%3!=0 and j%5!=0.
Dans ce cas, je range Dico[j%30] dans fam....

Mais je ne stocke aucun j : je traite leur cas à la volée, l'un après l'autre...

Les deux seules listes, plus ou moins conséquentes, qui sont conservées en mémoire sont :
* Primes_init : ensemble des premiers issus de la def eratostene
* nombres qui est - au départ - une liste de 8 listes comprenant nbcell nombres 1 : c'est cette liste qui est mise à jour dans la dernière boucle (et ce pour chaque j) en remplaçant des 1 par des 0...

Ma dernière version fonctionnelle :

from time import time
from os import system


## V. 6.3.1 ##

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:]

def Crible_mod30(n):
    global nombres,nbcell
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    debut=time()
    for i in range(8):
        nombres.append([1]*nbcell)
    P8=[1, 7, 11, 13, 17, 19, 23, 29]
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2
        temoin=0
        for j in range(debut,fin,pas):
            if j%3!=0 and j%5!=0:
                fam=Dico[j%30]
                if not ((1<<fam)&temoin):
                    temoin=(1<<fam)|temoin
                    debut_index=j//30
                    Nombres_fam=nombres[fam]
                    for index in range(debut_index, nbcell,pi):
                        Nombres_fam[index] = 0
    s_23=time()-start_time
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total=0
    for sous_liste in nombres:
        total+=sum(sous_liste)
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s


n=2400000
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
#system("pause")

Si tes questions sont toujours d'actualité j'y regarderais alors de plus près...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#287 20-07-2018 10:21:41

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

Bonjour @Yoshi

Ben.... tu viens de répondre à mes questions, je n'étais pas sûr que les j été traités un après l'autre et qu'ils étaient en mémoire cache d'après cette  ligne :

debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2

,
pour ensuite être rangé  Dico[j%30]dans fam..afin de calculer l'index de départ puis criblage par pas de pi...dans liste nbcell pour remplacer les 1 par des 0 .

je travail avec ta dernière version par famille uniquement... ce qui fait qu'effectivement pour chaque pi je ne travail qu'avec un j%30==1 que je range Dico[1] dans fam...

ce qui m'a fait posé cette question, c'est que lorsque j'édite les j, il m'édite le dernier j relatif au dernier pi

par exemple si je tape n=2400000
avec print (j) à la fin de # FAMILLES POUR CHAQUE Pi

il me donne :
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG4Y_modulo30.py =====
Donnez la valeur de n = 30k : 2400000
Phase d'initialisation: 0.0 seconds ---
65033
Bloc S2_s3 : 0.015600204467773438 seconds ---
Extraction des premiers n à 2*n : 0.0 seconds ---

**  19933 nombres trouvés en 0.015600204467773438 secondes **
>>>

Ce qui me fait penser qu'il traite les 15j  relatif à la boucle :

debut,fin,pas=r+pi*(1-r%2),min(1+r+pi*29,nn),pi*2

, Ce qui est normal puisqu'il travaille dans les 8 famille...

alors que ne travaillant que dans une seule  famille , je n'ai besoins que d'un j%30==1 que je range Dico[1] dans fam...
Donc je cherchai le moyen d'arrêter la boucle dès que j%30==1 était trouvé, sans aller jusqu'à fin = min(1+r+pi*29,nn)..

Ceci dit.... je ne pense pas que cela changerai grand chose....
@+

Hors ligne

#288 20-07-2018 12:07:38

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 026

Re : crible en python

Re,

je travaille avec ta dernière version par famille uniquement... ce qui fait qu'effectivement pour chaque pi je ne travaille qu'avec un j%30==1 que je range via Dico[1] dans fam...

Oui, fam ne contient toujours qu'une valeur en tout et pour tout...

Il n'y a que la liste de listes nombres qui est imposante après sa construction : pour n=30 000 000 000, elle contient en tout 8 000 000 000 de 1...

Python a une extension mathématique numpy qui elle gère de vrais tableaux et est censée aller plus vite que Python tout seul (elle est installée chez moi) : j'avais donc remplacé les listes par des tableaux et testé...
J'ai abandonné : c'était bien plus lent !

Le point faible maintenant c'est clairement nombres !
Je n'ai toujours pas trouvé comment s'en passer : en fait j'ai bien une idée depuis le début, mais les résultats sont faux...

Une solution serait de paralléliser les calculs et d'utiliser le fait que nos processeurs sont multicœurs et qu'on ne s'en sert pas : mais ça, je ne sais pas faire pour le moment...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#289 20-07-2018 15:42:25

LEG
Membre
Inscription : 19-09-2012
Messages : 280

Re : crible en python

je pense qu'au niveau du criblage lorsque l'on dépasse 29 700 000 000 ce n'est pas liste nombres = 1 000 000 000 par famille le point faible..
c'est bien le criblage par pas de Pi qui pose problème, car il faut compter les 1 ..... et ça on ne pourra s'en passer.

car regarde que je crible 29 100 000 000 le temps par famille pi et d'environ 3 secondes pour 29 910 000 000 il est de 4 secondes environ  et pour 29 940 000 000 quelques dixièmes en plus....
mais en criblage on passe de 180 seconde à 2800 secondes puis à 5600 secondes alors que le temps d'extraction ne varie pratiquement que de très peu de 7 à 10 seconde. justement grâce à ta partie 4 extraction...

or dans les trois cas la liste nombres est établie les Pi sont stockée...la boucle des j ne varierai que de très peu , même en limitant cette boucle la finà (while j%30 == 1).

c'est le même problème dans nbpremiers win 32 d'Eratosthène modulo 30 par famille..qui lui prend nombres = 15 000 000 000 de 1 mais le temps est d'environ 2h 20 avec mon pc, le programme est en c++.

par contre il est clair qu'il peut être amélioré par plusieurs points déjà la partie 4 de ton programme qui est très rapide par rapport au début où le temps est divisé au moins par 30....et d'autre point comme la racine carrée des premiers extraits par le GM ('Grupe Multiplicatif)..
Là probablement que l'utilisation d'un processeur multicœurs serait utile chacun prendrait une base il y en a 8...Mais c'est suffisant ...

Est ce que tu veux cet exécutable ? qui se présente sous la forme d'un calculateur sous Windows...

Dernière modification par LEG (21-07-2018 09:46:16)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante ?47 - 38
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums