Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Question de LEG : temps mis pour divisions par pi

Bonjour

Bonsoir
sans perturber, est ce l'on peut connaître le temps mis par un bon ordinateur pour effectuer environ 2 160 500 000 divisions par Pi ;  afin d'en déduire les restes Ri de chaque division...? en gros....

Voilà mon test :

from math import pi
from time import time

def duree(hr,mnt,sec,tot):
    tot=int(tot)
    hr=tot/3600
    tot=tot%3600
    mnt=tot/60
    sec=tot%60
    return hr,mnt,sec,tot

i=0
q,r=0,0

deb=time()
while i<2160500001:
    i+=1
    q,r=i/pi,i%pi

terme = time()
temps = terme - deb
hr,mnt,sec,tot=0,0,0,temps
hr,mnt,sec,temps=duree(hr,mnt,sec,temps)
print 'Temps de fonctionnement du module',hr,'h',mnt,'min',sec,'s'

Python réputé lent
Mon proc AMD Phenom III X3 710 Black Edition : milieiu de gamme d'il y a 3 ans
4 Go DDR3
XP
24 min 50 s

@+

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Question de LEG : temps mis pour divisions par pi

Bonsoir,

#Python 3.2
from time import localtime, strftime
print(strftime("%a, %d %b %Y %H:%M:%S +0000", localtime()))
pp=3.1415926535
i=0
while i<2160500001:
    i+=1
    q=i/pp
print("fin",i)
print(strftime("%a, %d %b %Y %H:%M:%S +0000", localtime()))

Temps passé :
Processeur    Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz sous Windows 7
12 minutes 40 secondes

La même boucle en Visual Basic, pi, i et q déclarés "double" : 17 secondes

miq

Invité

Re : Question de LEG : temps mis pour divisions par pi

Bonsoir,

En python, un while ? avec une affectation de variable incrémentée ???

Sans utiliser les résultats des divisions le plus efficace en python3 sera 

import timeit
import math
def test():
  for i in range(2160500001):
    i%math.pi

timeit.timeit(test, number=1)

Si on fait quelque chose des valeurs, et qu'il y a besoin de les stocker il vaut mieux utiliser les listes en intention

restes=[i%math.pi for i in range(2160500001)]

et s'il n'y a pas besoin de les conserver mais juste de faire un calcul sur chacun il vaut mieux utiliser un générateur 

restes=(i%math.pi for i in range(2160500001))

Ces deux dernier sont plus rapides que la boucle for pour ce qui est des calculs en eux mêmes (surtout le générateur, qui calculera la valeur suivante uniquement quand le code en amont en aura besoin et évitera donc le stockage intermédiaire des valeurs) mais leur syntaxe n'existe qu'avec une utilisation des valeurs calculées.

miq

Invité

Re : Question de LEG : temps mis pour divisions par pi

Edit du post ci-dessus :

-la boucle for met 20% de temps de moins que la boucle while sur ma bécane. La liste en intention, tout en créant l'objet liste, perd 10% par rapport à la boucle for, mais est quand même plus rapide que la boucle while...

-il faudrait tester en c aussi, ça devrait dépotter, mais là je vais me coucher, bonne nuit :)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Bonjour,

En python, un while ? avec une affectation de variable incrémentée ???

1. J'ai un système 32 bits
2. Mon essai avait une raison : je sais quand même écrire ce que miq a écrit....
    Voilà ce que j'obtiens avec une boucle for
   

for i in range(2600000001):
             OverflowError: range() result has too many items

3. miq et totomm on fait leurs essais avec Python 3.2 : moi avec Python 2.6.
   Je vais essayer le 3.2 pour voir.

@+

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

En fonction de vos réponses donc; pour cribler les premiers jusqu'à 10²⁸ cela risque de prendre du temps...
mon crible comporte un avantage, on peut à partir de la racine carrée de 10²⁸, stocker uniquement les premiers représentés par 1
par ligne, une ligne comporte au maximum 8 termes P.

par contre le programme avance par pas de 30....

et le nombre de divisions pour calculer le reste de 30k par P_i va nécessairement prendre du temps...à chaque pas , sauf si il reste en mémoire la formule pour chaque itération de 3(k+1), puisque les modulos P_i restent les mêmes, en gros par rapport à 30(k-1) le nombre de P_i augmente en fonction de la racine carrée de 30k.

le crible est en lui même très simple à programmer pour un informaticien bien sur..

dommage que je ne puisse  joindre le fichier excel..pour vous en faire une idée.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Bonjour,

dommage que je ne puisse  joindre le fichier excel..pour vous en faire une idée.

Comment ça ?
Si c'est le fichier lui-même, ok...
Mais tu peux le mettre à dispo en le posant sur
http://www.cjoint.com/
tu nous donnes le code, et on va le chercher...

En ce qui concerne la v. 3.3, elle accepte effectivement l'instruction
for i in range(2160500001):
je n'ai plus d'overflow...

Euh, attends...
J'ai un doute là...
Voulais-tu tester les divisions par Pi --> [tex]\pi[/tex]    ou... P_i soit [tex]P_i[/tex]  (P indice i) ???
Parce que les tests sur des entiers (et non sur des nombres en virgule flottante comme 3.1415926535897...) c'est bien plus rapide...

@+

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

cellule A 246 = 930, qui va varier par pas de 30    ; racine carrée de la cellule:[tex]\sqrt930 = 30,49590136    [/tex]pour déterminer le dernier
[tex]P_i [/tex]à ajouter si besoins.                           
                                   
tableau des Restes R_i : 30k modulo P_i. Formule à incrémenter en début de programme                                    
afin de ne pas recommencer pour toute nouvelle valeur de 30k cellule A246, le calcul du reste.                                   
ie: l'égalité [tex]P' = n*P_i + R_i[/tex] , revient à vérifier si [tex]P'\equiv R_i [P_i][/tex] ou [tex]P'\equiv 30k[P_i][/tex]                                    

----------------------------------------------------                                    
6; 6 ;7 ; 12 ; 18 ; 10 ;  2 ;  0 .       
13 ;17; 20; 29; 37; 33;31;31       
20 ;    28 ; 33                           
27 ;                                   
34 ;                                   
------------------------------------------------
                                   
Pour tout nouveau [tex]P_i > 31[/tex],on vérifie simplement:
si le reste = P' appartenant à [tex][7;31][/tex]
ligne des [tex]R_i[/tex] de 930 par P_i > 31
---------------------------------------------------------                                   
[tex]5 ; 28 ; 27 ; 37 ; 61 ; 29; 45    ;15[/tex]
-----------------------------------------------------------       
                                   
                                   
lorsque l'on arrive sur le dernier P_i de cette ligne , on incrémente une nouvelle ligne de P_i en dessous,                                   
en calculant le reste de 30k cellule A246. Ou bien on le fait au fur et à mesure.                                   
                                   
[tex]P'\neq R_i[/tex] ; ou [tex]P\neq n*Pi + R [/tex],
marquer [tex]P'= n*P_i + R_i [/tex] si il figure dans le tableau des Restes ci-dessus                                    
7 ; 11 ; 13 ; 17 ; 19; 23; 29; 31

voila un exemple de ce que je fais sur Excel.

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

voila le lien:
   
http://cjoint.com/?3Ahl1gIwFfE
http://cjoint.com/?3Ahl1gIwFfE

effectivement yoshi il ne s'agissait pas de [tex]\pi[/tex] mais des premiers [tex]P_i[/tex]

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Salut,

Désolé d'être si bouché, mais je ne vois pas instantanément ce que tu fais...
Donc, ton propos est-il bien ici :
Recherche de tous les nombres premiers inférieurs à 930 ?
Ou
Test de primalité d'un nombre quelconque n (ici 930) ?
Je penche pour la 2e solution puisque tu recherches la racine carrée de n : s'il n'y a pas eu de quotient entier exact avant cette racine, il n'y en aura pas après.
[tex]\sqrt n[/tex] est ton test d'arrêt.
C'est ça ?

En relisant ton post#6, je vois que non, tu veux rechercher les premiers jusqu'à [tex]10^{28}[/tex]...
Que vient faire le 90 là-dedans.
Je vais aller voir ce que tu avais expliqué dans la discussion ouverte par madgel.
Tiens j'ai trouvé un message sur un forum où sévissait madgel

Re: Répartition des nombres premiers et multiple de 5

Messagepar Francky » Lundi 07 Octobre 2013, 22:45
À part 2 et 3, tous les nombres premiers sont congrus à ±1 mod 6.
En partant de 5, on fait en boucle +2 +4 pour chercher de nouveaux candidats.
Je me sers de cette propriété pour écrire mon programme de crible d’Ératosthène avec une roue à 6 dents.

Pour une roue à (2×3×5 =) 30 dents, le schéma, c'est de partir de 7, et de faire :
+4 +2 +4 +2 +4 +6 +2 +6, puis boucler.:

@+

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

[qote]En relisant ton post#6, je vois que non, tu veux rechercher les premiers jusqu'à 1028 ...
Que vient faire le 90 là-dedans.[/qote]

est ce que tu as ouvert le fichier EXcel joint par le lien du post #9
tu verras que je crible...
le 90 c'est le départ du crible
dans le fichier excel:
à partir de la ligne A246 la cellule 930 veut dire que j'ai criblé de 90 à 930; il te suffit d'ailleurs de changer la valeur et de la passer à 960
tu verras que le tableau des reste en dessous les valeur vont changer
il te suffit ensuite de relever ceux qui son égaux à P' [7;31] de la ligne 277, qui actuellement comporte des 0 et des 1 au lieu des 8 premiers [7;31], le tableau d'à côté te dis à quoi correspondent les 1...
@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Re,

Dans la discussion en question, tu avais écrit à madgel :

je vais te donner un ex tout simple.

jusqu'à 100

je part de 1: je construit un tableau de 6 sur 6 soit 36 cellules représentant des entiers 6n+1.

je positionne 5*5 dans sa cellule = 25, et 7*7 dans sa cellule=49

les deux premiers qui servent de base pour cet algorithme, sont donc 5 et 7 pour ces entiers 6n+1.

le programme permet d'identifier à coup sur, si le complémentaire de 5 ou 7 est un nombre premier.

le complémentaire de 5 ou de 7 est le dernier entier utilisé, augmenté de 6 à chaque saut...

ie: le complémentaire de 5, serra 11, 6n+1 < ou = à la racine carrée de 211... donc 13 dans cet exemple précis
le complémentaire de 7 serra 13  soit 6n+1 < racine carrée de 211

si le complémentaire est premier alors il marque tous ses multiples jusqu'à la limite fixée uniquement en comptant les cellule...sinon il est éliminé du crible....et on réitère.

les bases 5 et 7 sont positionnées au départ et ensuite elles comptent au fur et à mesure leur cellule par pas de 5 ou de 7 ...etc

ce que tu fais en faisant des multiplications  de p par 4 et 2 et en rajoutant n multiple de p

tu peux facilement vérifier que toutes les cellules marquées p, est bien un nombre premier de la form 6k+1 et cela en partant de 1:

je positionne 5*5 dans sa cellule = 25, et 7*7 dans sa cellule=49
Sa cellule ? Laquelle ?
Comme dans un tableur, je note les colonnes A, B, C, D, E, F  et les lignes de 1 à 6.
Qu'inscris-tu dans la cellule A1 ? 1 ? dans quelle cellule inscris-tu 25 ? en A4 et 49 en B3 ?
Ce qui positionne 211 en F6 ?
Pour ton système à base de 30k+1, ton carré de base fait donc 30*30 ? Tu pars de 1 en A1 et tu incrémentes de 30 en 30...
Non, je ne crois pas, je n'obtiens que des nombres terminés par 1...

@+

[EDIT]
Non, je n'avais pas vu tes liens...
Je vais faire un tour chez un pote.
Je reprends quand je reviens.

Dernière modification par yoshi (07-01-2014 14:26:10)

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

re yoshi

1)la racine carrée de n détermine la limite des premiers [tex]P_i[/tex]à utiliser pour cribler et en même temps la limite du crible par exempl [tex]10^28[/tex]...

2) je n'ai besoin pour cribler les premiers [tex]P'[/tex] que ceux appartenant à [tex][7 ; 31][/tex]

pour éviter les doublons, et limiter le nombre d'opération tel que pour un premier [tex]q = 30k - P'[/tex] si et seulement si P' n'est pas congru à 30k modulo [tex]P_i[/tex], ce qui est triviale

3) pour éviter d'avoir à répéter les divisions de 30k par [tex]P_i[/tex], j'utilise le principe Eratosthène pour le petit tableau ligne :252 à 256 du fichier
a)
il me faut quand même les 8 premiers restes [tex]R_i[/tex] de [tex]30k[/tex] par [tex]p_i[/tex] avec [tex]P_i ;[7;31][/tex]
mais ensuite j'utilise le principe d'Eratosthène
Pour [tex]P_i = 7[/tex] et [tex]R_i = 6[/tex] dans le cas de [tex]30k= 930[/tex] il me faut bien vérifier qu'aucun des 8 [tex]P'\not\equiv930 [P_i][/tex] c'est à dire que [tex]P'[/tex] appartenant à[tex][7;31] \not\equiv R_i {(mod P_i)} [/tex] donc je remplace dans le petit tableau
par la formule équivalente et qui m'évite les division[tex]R_i + n * 7[/tex] infér ou = à 31 pour cet exemple; et ce, pour les 8 premiers modulo [tex]P_i [/tex]
que tu peux constater en cliquant sur les cellules...
b)
et la ligne 259 c'est lorsque la [tex]\sqrt30k\geqslant37[/tex] les 8 [tex]P_i >31[/tex] suivant, appartenant à[37 ; 61]...ou j'ai déjà la formule des restes incrémenté;  donc en changeant la valeur de la cellule A246, les valeurs des restes de ces 8 premiers sur cette ligne, change aussi...
la ligne 270 c'est simple c'est cellule A246 - P' non marqués, de la ligne 266
ligne que l'on stock dans le tableau à côté, comme ça on les a par famille. Et si il n'y avait que des 1 pour connaître la valeur 1, et bien:
[tex]L*30k + P_i[/tex] avec [tex]P_i;[7;31][/tex] L étant le N° de la ligne....

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

ton post #12

je positionne 5*5 dans sa cellule = 25, et 7*7 dans sa cellule=49
Sa cellule ? Laquelle ?

je te répond ("mais il vaut mieux travailler sur le fichier joint, tu vas comprendre de suite même si ce n'est pas le même crible")
sa cellule:
on crible les entiers 6k+1
donc on part de 1 ;7; 13; 19 ; 25 ; 31 ; 37 ; 43 ; 49
donc les cellules étant numéroté de 0 à n
cellule 4 = 5*5 ; soit 6*4 +1
cellule 8 = 7*7 ; 6*8 + 1
mathématiquement c'est l'entier de rang n , "ou cellule N° n" c'est une suite arithmétique....[tex]U_o = 1[/tex] de raison 6
mais oublie cette discussion car on n'est pas dans le même crible..@+

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

re post #12

Comme dans un tableur, je note les colonnes A, B, C, D, E, F  et les lignes de 1 à 6.
Qu'inscris-tu dans la cellule A1 ? 1 ? dans quelle cellule inscris-tu 25 ? en A4 et 49 en B3 ?
Ce qui positionne 211 en F6 ?

on est pas dans le système 30k+1 mais 6k+1
donc suivant ton carré de 6 sur 6
A1 = 1 et E1 = 25
49 lui est positionné en C2 car (9-1) * 6 + 1 = 49 c'est pour cela que la cellule A1 est numéroté 0 ensuite tu fais un saut de 5 cellules et de 7cellules...etc et tu obtiens 5*11 et 7*13 à chaque saut le complémentaire de 5 ou 7, augmente de 6.....
tu as bien 55 en D2 et 91 en D3....voila pour l'info sur ce sujet.

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

re post #12
attention que le crible en question n'a rient avoir avec le crible modulo 30 dans Eratosthène

Pour ton système à base de 30k+1, ton carré de base fait donc 30*30 ? Tu pars de 1 en A1 et tu incrémentes de 30 en 30...
Non, je ne crois pas, je n'obtiens que des nombres terminés par 1...

car dans cet discussion il s'agit de l'algorithme P modulo 30, ou P modulo 6; et les nombres que tu viens de citer, sont les entiers de la forme [tex][30k+1[/tex]
donc les premiers congrus à 1 modulo 30..
cela ne fonctionne pas comme le crible g....! dont il est question dans ce fichier Excel..
@+

miq

Invité

Re : Question de LEG : temps mis pour divisions par pi

Parce que les tests sur des entiers (et non sur des nombres en virgule flottante comme 3.1415926535897...) c'est bien plus rapide...

Oui mais attention, on change la complexité du problème, on est plus en N, mais quelque part entre N et NN.

sinon pour revenir aux premiers,
le problème du crible, c'est la taille en mémoire. Le code suivant va planter à cause de l'espace mémoire.

crible = [i for i in range(3,10000000,2)]

La solution est peut être effectivement de passer par une roue de taille différente.
voilà comment je fait rapidement pour calculer les premiers nombres premiers (c'est sans doute largement améliorable, en évitant par exemple de tester 17 (soit le premier newPi de la boucle du 16) avec 13 (qui est le dernier de la liste Pi à ce moment là, et bien supérieur à [tex]\sqrt{17}[/tex])) :

import math
import timeit

def premier(Pi,n):
    for i in Pi:
        if not n%i:
            return False
    return True

def test():
    Pi=[3]
    for limit in [16,256,65536]:
        Pi+=[newPi for newPi in range(int(math.sqrt(limit)+1),limit,2) if premier(Pi,newPi)]
    Pi.insert(0,2)
   
timeit.timeit(test,number=1)
 

avec une taille de roue croissante. Cette boucle me prends 8 secondes sur une machine moyen de gamme d'il y à 4 ans. Si je rajoute le cran suivant, ça tourne pendant plusieurs minutes et je n'ai pas la patience d'attendre.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Bonjour,

Alors je vois que tu ponds des cribles comme d'autres enfilent des perles...
Là, c'est le flou le plus total : je suis complètement à la ramasse.
C'est tout juste si je sais encore où j'habite.
Savoir pour soi etr savoir pour les autres, ça fait deuxn je l'ai toujours dit.

On efface tout et on recommence.
Je prends ton fichier Excel que j'ouvre averc OpenOffice Calc (désolé, moi je travaille autant que faire se peut, avec des logiciels libres et ce n'est pas le cas d'Excel.
Ligne 1

On ne tient pas compte des multiples de 2 ; 3 et 5. ce qui donne le nombre d'entiers ≡ 1 ou P (mod 30) avec P appartenant à [7 ; 29] a : 9540 / 3,75 = 2544

           
De 2 à 29, il reste 7, 11, 13, 17, 19, 23, 29
Pourquoi étends-tu jusqu'à 31 dans ton encadré ? Où tu écris : Tableau des P' extraits par le crible jusqu'à 30(k-1) donc < 9540 et limité à 4770. Mais j'y reviendrais.
Donc, j'ai cité ta première ligne, j'ai pu identifier les 7 nombres premiers suivant 2, 3 et 5...
Et là, paf, le lecteur censé découvrir ta méthode en partant de zéro se ramasse : 9540 / 3,75 dans la figure.
9540 ? Boufre ! Il vient d'où ce 9540 ?
[tex]9540 = 2^2\times 3^2\times 5\times 53[/tex]
Et alors ?
J'en reviens donc à 9540... Choix arbitraire ?
Et 3.75 ?
[tex]e^{3.75}\approx 42.521082000062783[/tex]C'est quoi ce 42 rt des brouettes ? our l'instant je ne dépasse pas la ligne 1...
J'irais voir ce que raconte (racontait ?) Goldbach plus tard.
Je vais mettre du temps à comprendre sûrement : j'ai le cerveau lent (par jour de grand vent, je lui attache deux poids de 200 daN de chaque côté ^_^)...

@+

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

Yoshi la ligne 1 à 232, concerne  le criblage de 9540 simplement c'est à dire le nombre de couples q+p = 9540 point barre,
effectivement j'aurais dû le préciser avant que tu n'ouvre ce fichier.
pour en revenir à [tex]\frac{9540}{3,75}[/tex]  c'est le rapport entre les entiers naturels multiple de 2,3 et 5 et les autres de la forme [tex]30k + 1[/tex] ou [tex]30k + P [/tex] avec [tex] P: [7;29][/tex].

pour cribler les premiers, jusqu'à 9540, je n'ai besoin effectivement des premiers P' [7;31] lors que je met 1 ou P [7;29] 1 n'est pas un nombre premier donc les 8 premiers P' [7;31]

pourquoi on limite les P' à [tex]\frac{30k}{2} [/tex] parce que le complémentaire q premier est compris entre [30k/2 ; 30k] tel que :
[tex]q + P' = 30k[/tex]
dans le crible g on utilise les congruences...les multiples de 30 et les premiers [tex]P_i <\sqrt30k [/tex] et ainsi que les 8 P' [7;31]
pourquoi on à besoin que de ces 8 premiers P' c'est pour éviter les doublons < 30k - 31.

les premiers P' compris entre 31 et 30k/2 donnent des doublon q extrait par 30(k-1) donc il faut uniquement les premiers q appartenant à:
[tex][30(k-1) -1 ; 30k -1][/tex]

si [tex]30k - 1[/tex]  est un nombre premier;  tu es bien d'accord que [tex]1 + (30k - 1)[/tex] n'est pas un couple [tex]p' + q[/tex]

si je ne fais pas cela en exemple voila ce qui se passerai:
je crible 60; qui est congru à 4 (mod 7)
[tex]P_i = 7[/tex] donc [tex]R_i = 4[/tex]
les [tex]P' [7;30][/tex]
ce qui donne P'{7,11;13,17;23;29}
on marque les [tex]P' = R_i + n*P_i[/tex]
4+7 =11
11+14 = 25
25 +14 > 30 fin
seul P' = 11  à pour complémentaire q non premier divisible par [tex]P_i[/tex]
on obtient bien:
60 - 7; 60 -13; 60 - 17; 60 - 19 ; 60 -23 , et  60 -29.

je crible 90 qui est congru à 6 (mod 7) ; [tex]\sqrt 90 < 8[/tex]
[tex]P_i = 7[/tex] donc [tex]R_i = 6[/tex]
les [tex]P' [7;45][/tex]
ce qui donne P'{7,11;13,17;23;29;31;37;41;43}
on marque les [tex]P' = R_i + n*P_i[/tex]
6+7 =13
13+14 = 27
27 +14 = 41
41 +14 =  > 45 fin du crible
seul P' = 13 ; et 41 ont pour complémentaire q non premier divisible par [tex]P_i[/tex]
on obtient bien:

90 - 7; 90 -11; 90- 17; 90 - 19 ; 90 -23 ,  90 -29, 90 -31 ; 90 -37 et  90 - 43; sont des doublons
imagine la quantité de doublons pour une limite [tex]P' < 10^{10}[/tex]

donc:
pour le crible rapporte toi ligne 236

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

dans le criblage complet de 9540 pour déterminer les P' < 4770  qui n'ont pas un complémentaire q premier, je me sert des suites arithmétiques
de raison [tex] P_i * 30[/tex] en partant des 8 entiers [tex] n*p_i + R_i[/tex] qu'on est obligé de déterminer, ("et ce pour chaque modulo P_i")
ligne 17 à 199; et ensuite je marque en rouge les nombres premiers P' dans le tableau à côté

pour ne pas tester chaque P' avec les modulo [tex]P_i [7;97][/tex] c'est plus rapide.et on ne fait pas de division, sauf les premières relatives au modulo [tex]P_i [7;97][/tex] car on a pas le choix.. mais dans le cas d'une décomposition totale d'un 30k précis en l'occurrence 9540

miq

Invité

Re : Question de LEG : temps mis pour divisions par pi

bonsoir;

je pense avoir compris le criblage proposé par leg, mais je reste dubitatif quand à la complexité qu'il induit dans le codage par rapport au gain de temps de calcul escompté.

voilà mon dernier code :

import math
import timeit
import itertools

def premier(Pi,n):
    for i in Pi:
        if not n%i:
            return False
    return True

"""
-Création d'une liste qui contient tout les premiers jusqu'à 4, la liste Pi
  (sauf 2 qui est rendu inutile par le fait qu'on ne génère que des impairs dans la suite)
-Calcul de la liste des premiers entre 4 et 16, par tests avec tous les premiers < 4 (liste Pi)
-Ajout de cette nouvelle liste à Pi, qui contient donc tous les premiers < 16
-Calcul de la liste des premiers entre 16 et 256, par tests avec tous les premiers < 16 (liste Pi)
-Ajout de cette nouvelle liste à Pi, qui contient donc tous les premiers < 256
-Calcul de la liste des premiers entre 256 et 65536, par tests avec tous les premiers < 256 (liste Pi)
-Ajout de cette nouvelle liste à Pi, qui contient donc tous les premiers < 65536
"""
def test():
    Pi=[3]
    for limit in [16,256,65536]:
        Pi+=[newPi for newPi in range(int(math.sqrt(limit)+1),limit,2) if premier(Pi,newPi)]
    Pi.insert(0,2)
    return Pi

"""
On reprends l'idée précédente mais en limite glissante au lieu des puissances de 2.
La liste Pi contient les premiers inférieurs à la racine du nombre testé.
La liste Pnext contient les premiers suivants;
Elle est mise à jour en testant chaque division avec les membres de Pi.
Quand on détecte que le nombre testé dépasse le carré de la limite de la liste Pi, on ajoute un    
premier de Pnext dans Pi et on precalcule le prochain nombre qui dépassera son carré.
"""
def test2():
    Pi=[3]
    limit=9 #=3**2
    Pnexts=[]
    newPi=5
    while newPi<6553600:
        if newPi>limit:
            Pi.append(Pnexts[0])
            limit = Pnexts.pop(0)**2
        if premier(Pi,newPi):
            Pnexts.append(newPi)
        newPi+=2
    Pi.insert(0,2)
    return Pi+Pnexts

"""Roue à 6 dents, en partant de 5 et en augmentant cycliquement par 2 puis 4
 on vire les multiples de 2 et 3.
Pour le reste, fonctionnement similaire au test2"""
def test3():
    Pi=[5]
    limit=25 #=5**2
    Pnexts=[]
    iterator=itertools.cycle([2,4])
    newPi=5
    while newPi<6553600:
        if newPi>limit:
            Pi.append(Pnexts[0])
            limit = Pnexts.pop(0)**2
        if premier(Pi,newPi):
            Pnexts.append(newPi)
        newPi+=next(iterator)
    return [2,3]+Pi+Pnexts

"""Roue à 30 dents, en partant de 7 et en augmentant cycliquement par 4,2,4,2,4,6,2,6
 on vire les multiples de 2, 3, 5."""
def test4():
    Pi=[7]
    limit=49 #=7**2
    Pnexts=[]
    iterator=itertools.cycle([4,2,4,2,4,6,2,6])
    newPi=7
    while newPi<6553600:
        if newPi>limit:
            Pi.append(Pnexts[0])
            limit = Pnexts.pop(0)**2
        if premier(Pi,newPi):
            Pnexts.append(newPi)
        newPi+=next(iterator)
    return [2,3,5]+Pi+Pnexts
 

et voilà les résultats de mes chronos (unité en secondes):

>>> timeit.timeit(test2,number=1)
21.34194803237915
>>> timeit.timeit(test3,number=1)
20.885185956954956
>>> timeit.timeit(test4,number=1)
20.398810148239136
 

On constate qu'il y a effectivement une amélioration faible, mais il est vrai que je reste dans des valeurs faibles aussi. Il faudrait tester avec une meilleure machine et avec des roues plus grandes.
Si j'ai le courage je regarderais s'il est possible de faire varier la taille de la roue avec la profondeur de la recherche, les différences entre test3 et test4 étant minimes.

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

Bonjour
@miq
je ne programme pas ce n'est pas du tout mon domaine, ce que je peux te dire c'est que le programme "nbpremier win32" qui a été fait il y a un peu plus d'une dizaine d'année par un étudiant à l'essi de sophia antipolis crible les premiers jusqu'à 450 000 000 par famille [tex]30k + 1[/tex] ou [tex]30k + p[/tex] avec[tex]p, [7;29][/tex] en 4h

celui ci de programme  qui ne fonctionne pas comme "nbpremier win32" et que je n'ai pas encore fait faire, devrait permettre d'aller très loin environ [tex]10^{28}[/tex], car on a pas besoin d'avoir dans la mémoire "virtuelle" une liste de nombre que l'on trie : crible, comme dans Eratosthène, ou "nbpremier win32"

à partir de la racine carrée de [tex]10^{28}[/tex] on n'est plus obligé, de stocker les entiers premiers : [tex]30k - P'[/tex] mais les représenter par 1.
donc on stock que des 1, dans les 8 colonnes qui représentent les 8 familles modulo 30 :[tex]30k + 1[/tex] ou [tex]30k + p[/tex].
donc à partir de cette limite racine carrée on n'a plus besoin de soustraire P' à 30k pour connaître q premier
on teste tout simplement les 8 P'{7;11;13;17;19;23;29;31}
si un des reste [tex]R_i[/tex] de [tex]30k[/tex] par [tex]P_i[/tex] = [tex]P'[/tex]alors 0; sinon 1, puis on stock la lignes:
la ligne 277 dans le fichier Excel:

exemple : avec la ligne des P' relatif à 930.                           
0    1    0    0    1    1    0    0

mais je suppose que l'on ne peut pas garder en mémoire dans le programme tous ces 1 au delà de [tex]\sqrt10^{28}[/tex] pour ne pas saturer, mais de les stocker sur un disque externe de 10

le programme lui n'a besoin que des modulo premiers [tex]P_i <\sqrt10^{28}[/tex] pour calculer les restes de [tex]30k[/tex] par [tex]P_i[/tex]; afin de marquer le ou les 8 [tex]P'[/tex], ligne 277; que l'on stock au fur et à mesure que 30k augmente de 30.

donc la base de donnée première ie; les [tex]P_i[/tex] s'alimente d'elle même et le programme prend dans cette base de donnée, les [tex]P_i <\sqrt10^{28}[/tex] dont il à besoin pour le calcul du reste au fur et à mesure que 30k progresse.

ce qui implique: qu'au fur et à mesure que 30k passe à 30(k+1) les formules de calcul du reste de 30k restent; seul les reste [tex]R_i[/tex] vont changer, et peut être avec un[tex]P_i[/tex] en plus, donc un nouveau reste;

car la racine carrée de [tex]30k[/tex], augmente très peu par rapport à[tex]30(k+1)[/tex].

dans le fichier regarde ce qui se passe en partant de 90 cellule A246, dans le tableau des restes ligne 252 à 259, et tu augmentes de 30 la cellule, jusqu'à 930

il aurait fallu que j'automatise la ligne 266 des 8 P', pour que les P' = [tex]R_i[/tex]passent en rouge ; et donc je ne prend en compte que les P' non marqués, pour la ligne 270 [tex] 30k - P' = q[/tex]
un P' qui est candidat est : [tex]P'\not\equiv30k (mod P_i)[/tex]

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Question de LEG : temps mis pour divisions par pi

re
le programme nbpremierWin32 est en C++, je ne sais pas quel sont les différence de rapidité ou d'exécution entre les différentes programmations

miq

Membre

Inscription : 08-01-2014

Messages : 24

Re : Question de LEG : temps mis pour divisions par pi

C++ est beaucoup plus rapide que python, mais aussi beaucoup moins user friendly.

Ce que tu as l'air de décrire de nbPremierWin32 indique que les nombres premiers sont stockés par leur position dans un tableau de taille fixe au moins pour sa première dimension. Ça implique une taille de roue fixe (la roue représentant une ligne). C'est effectivement une approche très économe en mémoire.

L'idée d'augmenter la taille de la roue au fur et à mesure (ce vers quoi mes essais se dirigent) me plait bien aussi, reste à savoir si elle serait compatible avec un stockage par placement, mais ça me paraît à première vue beaucoup plus difficile, voire impossible.

Ce qu'il me reste à étudier pour suivre ma version tient pour l'instant en deux points :
-Comment déterminer les crans de la roue suivante;
-Comment sélectionner le moment du glissement d'une roue à l'autre.

J'ai des bonnes pistes de réponse à ces deux questions, mais il me reste à les formaliser rigoureusement, et à adapter le code en conséquence.

Après, une transcription de mon algo en c++ sera toujours possible, mais elle sera quand même infiniment moins efficace que nbPremierWin32 pour ce qui est du stockage des réponses (à moins qu'il ne soit possible d'intégrer l'idée du stockage binaire par position) et (à priori¹) aussi moins efficace pour les calculs.

¹:À priori, parce que la taille de roue augmentant à quand même tendance à accélérer les choses, donc ça reste à confirmer sur les très grands nombres (et c'est d'ailleurs tout l'intérêt de mon approche)

Dernière modification par miq (08-01-2014 14:59:26)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Question de LEG : temps mis pour divisions par pi

Re,

Au fait, miq, bienvenue à bord !
Un pythonien de plus, et un bon, voilà qui est chouette...
Quand tu auras pondu et que tu seras satisfait, jette un œil là-dessus, c'est bien plus coriace que ça en a l'air dans le cas, des sous-séries avec des nombres d'indices non-consécutifs...
Je finis une méthode, mais je n'apprécie pas du tout mon code !

@+