Question de LEG : temps mis pour divisions par pi

LEG · 08-01-2014 19:38:48

je pense que la taille de la roue ne peut être augmenter car c'est impossible dans le programme nbpremierWin 32, car li s'agit de cribler avec un groupe multiplicatif de 8 premiers " toujours les mêmes {7,11.....31} par contre on doit incrémenter un tableau virtuel ou une ligne de 1,
représentant les entiers 30k+1 et 30k+p ; P[7;29],
par exemple on incrémente au maximum 15 000 000 000 de 1 , ce qui va représenter le crible des premiers < 450 000 000 000. on multiplie par 30, ou si tu préfères. cela représente 450 000 000 000 / 3,75 =120 000 000 000 d'entiers non multiple de 2; 3 ou 5.

Pour le crible en question tu ne peux pas changer la roue car tu dois cribler chaque multiple de 30
sans faire de doublon car cela alourdirai et saturerai le programme
par exemple tu ne peux pas avancer par pas de 90, ou 300...etc c'est logique

le nombre de divisions ou de calcul des restes de 30k par P_i est défini par la raine carrée de 30k.
et le nombre de P' à tester et de 8 , si tu en met 50, et bien tu ferras des divisions inutiles car cela serra des doublons...donc inutile...!

si tu as 50 P_i tu ne vas quand même pas tester et faire 8 * 50 divisions pour savoir si P' est congrus à 30k modulo P_i; c'est à dire vérifier si P' est congru R_i;j modulo P_i;j ; où R_i;j est le reste de 30k par p_i;j...

donc le programme avancera par pas de 30...pour extraire l'ensemble des nombres premiers consécutifs, par famille pour une limite de 30k fixée, c'est à dire de 930 à 30k = 120 000 000 000 000 par exemple tu avances par pas de 30.

donc tu es déjà obligé d'écrire les premiers q de 7 à racine carrée de 30k au fur et à mesure par le programme, ensuite à partir de cette limite, tu peux ne mettre que des 1 à la place des premiers q
et chaque fois le programme sauvegarde la ligne de ces P' marqués 0 ou 1suivant que leur complémentaire q est premier...! C'est l'exemple qui est donné ligne 279..

voici ce que cela donnerait à partir de 930 si 930 est racine carrée de 30k: normalement 31 et 29 serait ligne L0; les deux colonnes sont décalées à cause des deux P' 29 et 31 , car chaque ligne augmente de 30, et j'ai commencé à 90. pour gagner du temps on incrémente à partir de racine carrée de 30k = 31,... mais comme on a 8 termes, on aura toujours un décalage des deux dernière colonne, pour calculer la valeur de 1 ; ce qui donnera 1 =(Ln - 1)*30 + 29 ou +31 ...etc

23 19 17 13 11 7
53 0 47 43 41 37 31 29

1 0 1 0 1 1 0 1
1 0 1 0 1 1 0 0
1 1 0 0 0 1 1 0
0 1 0 1 1 0 1 1
0 1 0 1 1 0 1 1
1 0 1 1 1 1 0 0
0 1 0 1 0 1 0 1
1 0 0 1 1 0 0 0
1 0 1 0 1 0 1 0
1 0 1 1 0 0 1 0
0 1 0 0 0 1 1 1
1 1 1 0 0 0 0 1

Dernière modification par LEG (08-01-2014 19:56:32)

LEG · 09-01-2014 12:20:11

Bonjour
à vous
en définitive la différence entre les deux cribles nbpremierW32 réside dans le fait que pour cet algorithme P modulo 30, on fixe au départ la taille du tableau des entiers que l'on va cribler, (sans les 2m;3m et 5m)avec le groupe multiplicatif Gm comportant 8 premiers P'[7;31]; et on crible par famille 3k+1 ou 30k +p; soit 8 familles
le lien en exemple pour ce crible nbpremierW32 est :
http://www.cjoint.com/?0AjkYGPspd7

alors que le crible g, lui, il s'alimente tout seul on peut aussi cribler par famille mais aucun gain de temps, car on est obligé de tester le p' de la famille en question avec tous les [tex]P_i<\sqrt 30k[/tex], donc on crible les 8 familles.

l'avantage, c'est que l'on a pas besoin de créer un tableau fixe que le programme à besoins dans sa mémoire, et il peut dupliquer les lignes des 8 termes, 0 et 1 au fur et à mesure que 30k augmente par pas de 30; mais il serra plus lent par contre il ira plus loin lentement, car il peut utiliser une mémoire externe pour stocker les lignes...[tex]P_i >\sqrt 30k[/tex]

miq · 10-01-2014 01:45:37

bonsoir,
merci yoshi pour ton accueil ! (ça a l'air intéressant ton lien, j'y jetterai un œil).
leg, je suis désolé, mais je ne comprends pas grand chose à tes posts, à part l'idée générale du crible par roue. Oui, il est impossible de changer la taille de la roue en utilisant un stockage ultra optimisé comme nbPremierW32. Mais en utilisant un stockage en liste, ça ne devrait pas être un pbm. (sauf propriété de la répartition des premiers ? mais dans ce cas on devrait quand même pouvoir généraliser le principe de crible de taille n.)

bon, de mon côté, je sèche. J'ai fait le programme avec une roue qui progresse en taille, au départ de la taille 2, puis 2*3, puis 2*3*5, mais à partir de la taille 2*3*5*7 les problèmes commencent : j'ai des combinaisons (13*17) qui dépassent taille de la roue et qui du coup ne sont pas filtrées par elle...

voilà comment je procède :
A) Je commence avec [2,3,5] comme premiers connus. les premiers qui sont la base de la roue sont [2], donc la roue est de longueur 2 et le point de départ de la roue est 3.
B) De ça je déduis que le pas de la roue sera [+2] (4 n'est pas premier, donc un tour de roue partant de 3 arrivera à 5 en une étape de 2)
C) Puis je prépare la liste des premiers que je devrait connaitre pour la taille de roue suivante :
C1) cette taille sera (2*3) au départ de 5, donc il me faut la liste des premiers jusqu'à 11.
C2) je précalcule les produits possibles de premiers de la roue actuelle dans cet intervalle. En l'occurrence j'ai 3*3. (inutile de chercher avec 2, ils seront flitrés par la roue en cours.
C3) j'applique la roue jusqu'à 11, en éliminant les pas précalculés non premiers, et j'obtient [(2,3,5,)7,pas 9,11]
----------------
D) et on reprends en A en augmentant la taille de la roue du premier suivant, soit base de la roue [2,3], taille 2*3=6, point de départ 5.
E) comme en B : je déduis le pas de la nouvelle roue : 7-5=2, 11-7=4, j'ai ma taille de 6 et mes pas sont [2,4]
F) comme en C : je prépare les prochains premiers connus nécessaire pour calculer les pas de la prochaine roue (de taille 2*3*5, au départ de 7)
j'ai donc besoin d'aller calculer jusqu'à 37. Je précalcule ceux qui ne seront pas premiers dans cet intervalle [5*5, 5*7] puis j'applique la roue actuelle et obtient la liste des premiers [(2,3,5,7,11,)13,17, 19,23,pas 25,29,31,pas 35,37]
----------------
G) on reprends comme en A avec la roue suivante : [2,3,5], taille 2*3*5=30, point de départ 7.
H) comme B et E : le pas de la nouvelle roue : [11-7, 13-11, 17-13, 19-17, 23-19, 29-23, 31-29, 37-31] soit [4,2,4,2,4,6,2,6]
I) comme C et F : prochaine roue ira à 2*3*5*7+11=221, les non premiers dans l'intervalle sont [7*7,7*11,...7*31], [11*13,...11*19], [13*13,13*17]. et après application de la roue filtrée avec : [2, 3, 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]

et là, premier problème, relativement facilement résolu : 221, mon dernier premier de la liste nouvellement générée, n'est pas premier, c'est 13*17, donc je vais devoir travailler sans borne au prochain départ de la roue... (bon, c'est une roue, on peut décaler le départ d'un pas, pbm résolu)...

mais surtout, après 3 cycles complet de calcul et d'application de nouvelle roue sans problèmes, un des premiers crans de la nouvelle roue foire : 247 = 13*19 tombe sur un cran vérifié pour 2,3,5,7 ! (normal, vu les valeurs) mais du coup c'est toute la question du calcul de la taille de la roue qui est à reprendre, pour cette roue là, 210 n'est pas suffisant pour assurer une roue valable. Comment déterminer cette taille ?
C'est là que je sèche.

ci-joint mon code jusque là :

include itertools

def getCycle(Pi, iCycle, size):

    """Calcule les crans d'une roue avec:

    -la liste des premiers connus (de la taille exacte d'un tour de roue),

    -son point de départ (indice),

    -sa taille désirée.

    Pour ce faire, mesure les crans un par un jusqu'à la taille objectif"""

    cycle=[]

    while size>0 and iCycle<len(Pi)-1:

        cycle.append(Pi[iCycle+1]-Pi[iCycle])

        iCycle+=1

        size-=cycle[-1]

    if size!=0: #si jamais la borne n'est pas un nombre premier

        cycle.append(size)  # on clos quand même la liste

        return True,cycle

    return False,cycle

def getExclude(Pi,limit):

    """retourne les produits possibles de successeurs de pcourant"""

    return {p*p:[p*np for np in Pi if p<np and p*np<=limit] for p in Pi if p*p<=limit} 

    #TODO optimiser en arrêtant les test dès le premier dépassement

def testn():

    size=1

    Pi=[2,3,5]

    iStart=1 # soit cran = Pi[iStart] = 3, et cycle = Pi[:iStart] = [2]

    limit=5

    while iStart<5:

        # taille de la roue = ancienne taille fois dernier premier ajouté

        size*=Pi[iStart-1] 

        # roue et caractère premier du dernier pas

        shifted,cycle=getCycle(Pi, iStart, size) 

        current=limit # on récupère le prochain current

        limit=size*Pi[iStart]+Pi[iStart+1] # cible pour calculer roue suivante

        exclude=getExclude(Pi[iStart:], limit) # liste d'exclusion

        if shifted: # si le dernier cran n'est pas premier on décale la roue

            cycle[-1]+=cycle[0]

            del cycle[0]

            current+=cycle[-1]

        step=itertools.cycle(cycle)

        while current<limit:

            current+=next(step)

            if current not in exclude: # soit on a un nouveau premier

                Pi.append(current)

            else: # soit on met à jour la liste d'exclusion

                if exclude[current]!=[]:

                    exclude[exclude[current][0]]=exclude[current][1:]

                del exclude[current]

        iStart+=1

    return Pi

dommage, parce que ça avait l'air environ deux fois plus rapide que la roue fixe de taille 30 (aucune division, pas de tri lourd vu que les exclusions sont ordonnées et gérées au fur et à mesure), déjà sur ces quelques premières valeurs.

Est-ce que 30 est une taille max pour cribler à la roue à cause de la proximité entre eux des premiers premiers ?
Si non, quelle est la formule correcte pour calculer le taille des cribles ? max(produit, autre-chose) ? quel autre chose ?

LEG · 10-01-2014 10:59:31

Bonjour miq
a) je t'ai envoyé le crible pour cribler la famille 30k+23. est ce que tu comprends le fonctionnement
pour en revenir à ce que tu fais,
il te faut partir de 7 et ne travailler que dans les entiers congrus à 1 modulo 30 et à P modulo 30, P premier appartenant à [7;29]
dans le crible 1 est remplacé par 31 bien entendu.
donc ta roue calcule la à partir de cet ensemble:
7 , 11, 13 , 17 , 19, 23, 29, 31
37, 41, 42, 47, 49 , 53, 59 ,61
...etc
et du par du carré 7:

7*7 , 7*11, 7*13 ;7*17 ; 7*19; 7*23; 7*29; 7*31 . Quelle différence tu trouves entre ces produits ?

11*11; 11*13 ; 11*17....etc..11*31. Même question

....

31*31 ; 31*37..............

tu vas t'apercevoir que tu as 8 roues ou 8 table de 8 termes
dont la première et :
T1 = 7: {12,7,4,7,4,7,12,3,} somme des sauts = P₁ * 8 = 56
T2 = 11: {18,12,6,11,6,12,18,5} somme des 8 saut : P₂*8= 88

T8 = 31 :etc
*****************************************
table des différence D pour incrémenter la table T37
tD = {48.32.16.32.16.32.48.16} dont la somme vaut 240,

ce qui est la somme des différences entre 2 lignes:
7 , 11, 13 , 17 , 19, 23, 29, 31
37, 41, 42, 47, 49 , 53, 59 ,61
*******************************
pour T.37:
{12,7,4,7,4,7,12,3,}
+
{48.32.16.32.16.32.48.16}

pour T41:
T.11 + tD; c'est à dire:

{18,12,6,11,6,12,18,5}
+
{48.32.16.32.16.32.48.16}

*****************************
En revenant cet aprèm, je te mettrai le crible Eratosthène mod 30 qui n'est pas nbpremierW32
mais qui fonctionne avec une table ou roue de 8 termes ; cela devrai t'expliquer pourquoi tu as ces problèmes de produits, dans les nombres premiers.

miq · 10-01-2014 11:37:47

Est tu en train de me dire que les roues ont 2 dimensions ?

C'est la piste sur laquelle je suis pour résoudre mon problème. Appliquer la première dimension mécaniquement après sa détermination, mais filtrer mes produits sur la seconde dimension aussi. Ça à l'air de prendre sens pour ma méthode...

LEG · 10-01-2014 18:02:34

Est tu en train de me dire que les roues ont 2 dimensions ?

pas du tout , mais le principe que tu utilises est lourd inutilement d'après ce que je pense comprendre, tu changes la taille de ta roues puis du cribles dans cet intervalle...
déjà que vient faire ce 221 (2*3*5*7 + 11...? pourquoi, que vient faire cette roue de 221...
De plus pour cribler dans l'intervalle de 221, tu n'as besoin que de 7
je ne comprends pas pourquoi tu travailles avec et encore des multiples de 2,3 et 5

si tu pars de ta roue 7*11: 77 les tests sont 7*7,7*11 point barre donc
tes crans sont {4.2.4.2.4.6.2.6} dont la somme = 30.
7+4; 11+2; 13+4, 17+2, 19+4, 23+6, 29+2, 31+6; on réitère 37+4; 41+2; 43+4; 47+2 filtré par 7*7,49+4; 53+6, 69+2 ;71+6 filtré par 7*11. fin de cette roue;
si j'ai compris ce que fait ton programme.
il faudrait passer ensuite à
{7*11*13} racine carrée =36; donc tous les premiers P_iappartenant à [7;31] et toujours avec une roue à 8 crans....{4.2.4.2.4.6.2.6}? mais je n'en vois pas l'intérêt à première vue...

car il est plus simple de faire ou d'écrire les entiers <(7*11*13) = 1309
ce qui te fais 8 suites arithmétique de raison 30 et tu cribles dans cet intervalle 7;1309. avec les premiers [7;31]
mais en utilisant d'autre pas ou cran..

je part de (7) comment tu barres les multiple de 7 sans calculer les produits < ou = à 1309 par exemple:
7*7,7*11 qui on déjà été trié et après que fais tu.....?

moi dans un crible d'Eratosthène modifié, je fais ça:

T1 =7; {12,7,4,7,4,7,12,3,}
je part de 7, je compte 12 et je barre le douzième qui n'est autre que 49, puis je barre le 7ème =77; puis je barre le 4ème = 91..........etc je barre le 3ème qui est le dernier cran ce qui donne 217, et je réitere , 12, 7;4;.....3; je réitère 12,7,....3 jusqu' 1309 et 7 sort du crible pour cet intervalle,

puis je passe à T2 = 11: {18,12,6,11,6,12,18,5}
(11) je barre le 18ème , (qui serra 121), puis le 12ème........puis le 5ème qui est le dernier cran et je réitère, 18,12,....5

et idem pour les premiers [7;31], tu auras criblé sans erreur, les premiers < 1309......non ?

dans ton programme il te faut les 8 tables de 8 termes, la table D pour indexer {48.32.16.32.16.32.48.16}, à chaque changement de ligne
et par famille

ce qui veut dire que lorsque tu arrives sur P_i > 31, donc 37, tu as changé de ligne tu es dans la famille 30k+7, donc tu indexxe la table ou roue T1 = 7 avec tD
ce qui donne:
{12, 7, 4 , 7, 4 , 7, 12 , 3,}
+{48.32.16.32.16.32.48.16}

T₃₇= 60;39;20;39;20;39;60;19 dont la somme et bien égale à 37*8;
Ce qui veut dire que la table 37, parcourt 296 entiers par itération, et ne marque que 8 produits par itération et uniquement 1 par colonne ou famille....!

ton programme peut par exemple connaître le format de la table des 8 terme et faire un copier collé par itération, ce qui accélère et évite de compter les nombres, en positionnant bien la table P lignes en dessous de la ligne de départ....etc

Exemple la table 1; T₇: 7 lignes sous la premières ligne qui contient 7 , première colonne. Puisque l'itération se fait toujours même colonne de départ , P_i lignes en dessous.

Pour la table 11, serra 11 lignes en dessous de la ligne de départ 11, et 2ème colonne .
car 11*30+11 = 341 positionné colonne 2, ligne 11, en numérotant ligne 0 la première ligne des 8 premiers P_i : [7;31];

il est évident que dans ce cas, tu peux directement écrire ou représenter les valeurs 30k+1 et 30k+P, dans une taille de tableau à cribler par exemple 100 000 000 000.
sauf la première ligne N° 0 où la tu écris les 8 premiers pour identifier les 8 colonnes [7;31]

Est ce difficile à programmer ?

LEG · 10-01-2014 18:20:27

I) comme C et F : prochaine roue ira à 2*3*5*7+11=221,

j'ai quand même une grosse question concernant tes tailles de roues :
qu'est ce qui te permet de croire que : {p1;p2;p3 + p4} est un nombre premier...?
réponse rient...! sauf si te le teste..!
dans ton exemple :
2*3*5*7 = 210 qui est le produit, tu rajoutes 11 pourquoi pas ..., mais un entier n = 221 est premier si et seulement si , il n'est pas divisible par [tex]P_i <\sqrt{221}[/tex] autrement dit par

LEG · 10-01-2014 18:25:56

re
donc 7,11, ou 13.

pourquoi rajouter 11 , dans ce cas il fallait t'en tenir à 210.
puis à
2*3*5*7*11
etc..
de plus tes crans 6.4.2.4.2.4.6.2 servent uniquement à éliminer les multiple de 2,3 et 5 si tu pars au départ de 1....! et tu reboucle sur 31,37,41.....etc

miq · 10-01-2014 19:11:04

la roue de taille 2 et cran 2 permet d'éliminer les multiples de 2, à partir de 3
la roue de taille 2x3 et crans 2,4 permet d'éliminer les multiples de 2,3, à partir de 5
la roue de taille 2x3x5 et crans 6.4.2.4.2.4.6.2 permet d'éliminer les multiples de 2,3,et 5 à partir de 7
la roue de taille 2x3x5x7 et crans ... permet d'éliminer les multiples de 2,3,5,7 à partir de 11
Si on ajoute la correction calculée en N*log(N) multiplications et autant de tri, on peut peut-être étendre cette roue pour qu'elle filtre aussi les multiples de 11 inférieurs à 2 tailles de roue au dessus, et de 13 inférieurs à 3 tailles de roue au dessus....etc.

Si on peut itérer le processus à l'infini et calculer des roues de tailles de plus en plus grande en n*log(n) opérations, penses-tu qu'une roue de taille "produit des 20 premiers nombres premiers", mettra plus de temps qu'une roue de taille fixe, comme 30 ?

C'est ça que je cherche, pourquoi se limiter à une taille donnée, si on peut calculer une taille immense de roue ?

L'idée n'est pas de dire qu'on veut tester une quantité donnée de nombres, qu'on initialise et qu'on crible, non, l'idée est de créer le crible complet au fur et à mesure qu'on détermine chaque nombres premiers. Et je cherche par pas de tailles de roues successives.

Dernière modification par miq (10-01-2014 19:18:18)

LEG · 10-01-2014 21:34:28

la roue de taille 2x3x5x7 et crans ... permet d'éliminer les multiples de 2,3,5,7 à partir de 11

tu peux me dire quel sont les crans....?je ne pense pas, et pour moi c'est impossible; sauf peut être si tu utilises les crans dont je t'ai parlé ci dessus: roue à 8 cran avec; 7; {12,7,4,7,4,7,12,3,} tu élimines les multiples de 7 en partant de 7,
puis en partant de 11 : {18,12,6,11,6,12,18,5} tu élimine les multiples de 11 en partant de 11 ;
...etc , mais ce serra obligatoirement 8 crans , en plus il est simple de vérifier qu'il s'agit d'une boucle itérative , comme la boucle :
6.4.2.4.2.4.6.2, qui élimine les multiple de 2, 3 et 5...

et TU NE PEUX pas changer cette boucle sans sauter des multiples

mais tu peux t'apercevoir que la taille de l'ensemble des entiers parcourus par ces boucles augmente.
7*8 =56 ;tu parcours 56 entiers et tu marques 8 multiples de 7 par itération...
11*8 =88 ; tu parcours 88 entiers et tu marques 8 multiples de 11 par itération...
13*8 = 104 ; tu parcours 104 entiers et tu marques 8 multiples de 13...

P_n * 8 = X ; tu parcours X entiers et tu marques 8 multiples de P_n par itération

tu n'as donc nul besoins de faire des multiplication uniquement de compter en partant de Pn et par rapport aux 8 termes de ta "table de 8 crans ou de 8 sauts..." que tu réitères..
ce que toi tu penses, serait d'avoir une taille de plusieurs crans , en rapport avec la table = intervalle que tu cribles; et bien non.

c'est très simple
fait un petit tableau d'entiers 30k +1 et 30k+p :

et crible comme Eratosthène en partant de 7, avec la roue de 8 cran :{12,7,4,7,4,7,12,3,}

taille de l'intervalle 7*11*13 = 1001

7. 11. 13. 17. .19. 23. 29. 31.
37. 41. 43. 47. .49. 53. 59. 61.
67. 71. 73. 77. .79. 83. 89. 91.
97. 101. 103. 107.109.113.119.121.
.........................................................
etc jusqu'à 1001
tu verras bien que ta roue de 8 crans se répète comme une boucle ou cycle tous les 7*8 entiers, si tu préfères toute les 7 lignes, et crible bien
tous les multiples de 7, change un cran ou modifie ces 8 crans et c'est le fiasco...garantie...!

tu va boucler à: 7+210 = 217
puis à 427; puis à 637, c'est à dire 7*30 + 7.

pour 11 idem tu boucles tous les 330, [11*30 + 11 = 341] avec la table {18,12,6,11,6,12,18,5} , jusqu'à 1001,
puis avec 13...etc; et quand tu arrives à la deuxième ligne, en partant de 37, tu indexes avec la roue TD {48.32.16.32.16.32.48.16} que tu rajoute à la table de 7, car c'est la même famille 30k+7
idem pour la table 41, tu part de 41 car il est premier, il n'a pas été marqué, donc tu rajoutes la table TD à la table de 11; car même famille 30k+11....etc
si tu veux les tables pour 13,1;19,23,29 et 31 soit tu les calculs ou je les mets sur le forum...de cette discussion..tu auras les 8 tables et la table d'indexation TD.

Mais est ce que tu comprends la différence avec ta façon de cribler...
dans cette méthode pas de multiplications quelque soit la tailles des entiers de cet ensemble 30k+1, 30k+p....

Don le produit de 20 nombres premiers ne modifiera en aucun cas la taille du nombre de cran : 8 termes point barre,
par contre la taille de la roue se calcule P_n*8
par exemple pour 7 en partant de 7 et bien ta taille est 56 entiers parcourus toutes les 7 lignes par itération
et la taille de ton crible et bien c'est toi qui le fixe .

100 000 000 000.
donc il te faut un tableau de (100 000 000 000 /3,75 = 26 666 666 666 entiers congrus à 1 ou P modulo 30 ; P :[7;29]
que tu dois établir...avant de cribler
c'est pour cela que je les remples par des 1, ou des bits ...des point....des x...ce qui prend le moins de mémoire...
sauf comme je l'ai dit, la première ligne des 8 premiers , et Ligne numéroté: N° 0.

car supposons que tu attaque la ligne 100, il faut bien que ton programme connaisse la valeur du 1 = prime et qui puisse indexer l'une des 8 première Table : T₇ à T₃₁ . avec TD

ce qui donnera TD * 100 + T_p avec p de 7 à 31...est ce clair....?
car à chaque fois que tu marques un 1 il se transforme en 0 donc = produit...!

LEG · 10-01-2014 21:43:49

Sinon par taille successive cela serra par taille P_n * 8

56
88
104
et ensuite tu ré incrémentes comment tes tables.
tu recommences ce que tu as déjà fait....

le seul crible que je connaisse qui se crée lui même est le crible g, dont il est le sujet avec les congruences....!
car la, au fur et à mesure les nombres premiers vont s'établir..!
mais tu n'as pas le choix; c'est par pas de 30; donc couteux en terme de divisions
pour trouver un premier parmi 8 termes P' : [7;31] criblés...par pas de 30...
mais tu connais:
chi va piano, va sano e va lontano....LOL

miq · 10-01-2014 22:25:18

oui je peut te dire quels sont les crans. je les calcule en appliquant avec la roue précédente et jusqu'à la taille prévue pour la roue courante, c'est le principe que j'essaie de mettre en place. Ceux de la roue de taille 210 sont : [4,2,4,6,2,6,4,2,4,4,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,10,2,10,2,6,6,4,6,6,2,10,2,4,2,12,10] et elle commence en 11.

Mais on commence à avoir des non premiers genre 13*19 qui sont des calculs à ajouter en parallèle à l'application de la roue nécessaires à l'établissement de la roue suivante. Je pense que si je résous le problème que j'ai en faisant glisser les produits des ces autres premiers qui s'incrustent j'ai la méthode pour calculer toutes les roues de tailles successives.

Reste à connaître la complexité-temps de ce calcul et s'il fini par devenir plus rentable que les méthodes habituelles. À priori je pense que c'est le cas, mais ça demande finalisation et tests.

yoshi · 10-01-2014 22:26:48

B'soir,

[Mode HS on]
L'italianisant (LV2) que je suis, rajoute une suite
...Chi va forte va alla morte !

Je connaissais encore deux variantes :
Chi va piano, va sano ; chi va sano, va lontano...
Chi va piano, va sano ; chi va sano, va sicuro, chi va sicuro, va lontano...

[Mode HS off]

^_^

@+

LEG · 11-01-2014 00:37:10

4,2,4,6,2,6,4,2,4,4,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,10,2,10,2,6,6,4,6,6,2,10,2,4,2,12,10

je pense que cette roue a une erreur le 4 au lieu du 6 qui est la différence entre 47 et 53.
[2, 3, 5, 7, 11], 13,₄. 17,₂. 19, ₄.23,₆. 29,₂ 31,₆ 37,₄ 41,₂ 43,₄ 47,₆ 53,₆ 59...etc et à la fin ton 10, n'a rien à faire non...?
car la taille doit être 2*3*5*7, et tu part de 11 , tu n'as pas à rajouter 11,...non?
donc pour moi ta roue par de 13 et non de 11

ensuite 210*11, et tu pars de 13; intervalle des multiples à pré calculer serait [11*11,11*13....

mais tu as aussi des multiples de 7 donc pour les éliminer, tu as recalculé une roue cranté, .....?

est ce que tu peux détailler exactement, ce que tu fais pour la prochaine roue....

[2*3*5*7*11].13... ta roue devrai partir de 17....puisque l'autre est partie de 13 et non de 11; c'est le départ qui me pose un hic....?

probablement que tes roues comportent des erreur et donc te prenne des multiples; car si tu ré incrémente cette roue, étant donné qu'elle comporte une erreur, tu la répètes pour la taille suivante

Mais je ne comprend pas pourquoi répéter ce processus avec des cran qui sont l'écart entre les premiers...d'autant que tu calcul les produits dans l'intervalle 210*11
puis 210*11*13....tu vas calculer les multiples ...pour chaque intervalle...?

LEG · 11-01-2014 00:39:31

yoshi ....tout é hs....LOL
@+

miq · 11-01-2014 01:01:37

bon, ma roue ne marche pas, elle élimine au delà de ce qu'elle devrait.

il faut progresser par roues qui ne filtrent que leurs bases et pas les autres premiers de la liste, et filtrer les autres à côté. Pour ça il faut lister séparément les premiers et les crans de la roue. du coup, ça perds fortement en rentabilité...
À voir si je continue....

miq · 11-01-2014 01:05:35

oui leg, l'idée est de faire une roue toute petite, puis de l'appliquer et d'en déduire les pas de la suivante. mais là j'ai voulu aller trop vite, j'ai mangé des pas en comptant les multiples des entiers dans la taille de la roue, alors qu'il ne faut prendre que le premier d'entre eux. (Ça marchait bien jusqu'à la roue de taille 30.) Mais du coup je pense que les précalculs pour les produits d'autres premiers compris dans la taille de la roue vont exploser.

Dernière modification par miq (11-01-2014 01:08:19)

LEG · 11-01-2014 11:11:56

salut miq, tu bosses tard....

Mais du coup je pense que les précalculs pour les produits d'autres premiers compris dans la taille de la roue vont exploser.

oui , c'est bien pour ça que je ne voyais pas l'intérêt de répéter cette roue qui va saturer et sans intérêt des l'instant ou tu recalcules les multiples dans l'intervalle fixé [p₁*p₂*p₃...*p_n]

je pense que tu peux programmer à partir du tableau fixé, et les tables de 8 cran T₇,T₁₁,....et T₃₁ avec comme indexe la table TD lorsque ton programme passe à un entier de la ligne suivante.
Car la taille de l'intervalle criblé, devient automatique sans que le programme s'en occupe; puisqu'il n'a qu'à calculer les 8 nouveaux cran d'une table Tp_n+1.
et le programme comme dans Eratosthène il barre les multiple tous les n crans de la table de crible , qui agit comme une grille...et c'est itératif.

donc 8 multiples par intervalle de P*8, et par table...
Sachant que ton programme part du nouveaux premier P_n, matérialisé par 1 , Ligne n, colonne P_i : {7;11;13;17;19;23;29:31}

La dernière table bien entendu, et celle du dernier [tex]1 = P_n < \sqrt X[/tex] ou X représente le nombre d'entiers à criblé, représenté par des 1,
qui change de polarité , ou se transforme en 0, en fonction du choix de programme, lorsque ce 1 est marqué par un terme ou cran, de la table T_n

est ce que tu en comprends le fonctionnement ...?

LEG · 15-01-2014 11:04:00

Bonjour
@yoshi
est ce qu'il serait préférable de programmer en python ou en C++, ces types de programme, dont on vient de parler..?

crible g qui lui peut utiliser une mémoire externe pour stocker,

ou crible Eratosthène modulo 30 , qui lui on doit incrémenter un tebleau ou 8 colonnes d'entiers représenté par des 1 ou autres;
afin de cribler une taille de 600 000 000 000.

(pour nbpremier W32, lui il a été fait en C++ ; limite actuelle : 500 000 000 000 , et par famille.)

y'a t'il un bouquin pour apprendre le C++, relativement facile...et bien expliqué...dans tes connaissances...?

yoshi · 15-01-2014 11:36:57

Salut,

Pour apprendre le C++, je ne connais pas de bouquins...
Mais ici http://cpp.developpez.com/
tu trouveras plein de tutos, et de références de bouquins...

Je pense que déjà par exemple en Python, travailler avec un système d'exploitation 32 bits ou 64 bits change la donne : la taille des tableaux en mémoire n'est pas la même.
Python est plus agréable à apprendre même s'il est plus lent, il existe des variantes du Python "classique" qui disposent d'un compilateur et fonctions supplémentaires, tel pypy et donc plus rapides.

Si je ne me trompe pas, un programmeur qui maîtrise Python doit être capable d'adresser en parallèle les différents coeurs d'un processeur et donc répartir le travail pour gagner du temps : c'est toute la différence entre des pros et des amateurs comme moi...

@+

LEG · 15-01-2014 11:50:47

ok yoshi
effectivement, il faut travailler dans un système d'exploitation 64 bits.
ensuite je te remercie pour le lien, et je vais y jeter un coup d'oeil ...
a+

Forum de mathématiques - Bibm@th.net

#26 08-01-2014 19:38:48

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

#27 09-01-2014 12:20:11

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

#28 10-01-2014 01:45:37

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

#29 10-01-2014 10:59:31

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

#30 10-01-2014 11:37:47

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

#31 10-01-2014 18:02:34

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

#32 10-01-2014 18:20:27

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

#33 10-01-2014 18:25:56

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

#34 10-01-2014 19:11:04

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

#35 10-01-2014 21:34:28

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

#36 10-01-2014 21:43:49

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

#37 10-01-2014 22:25:18

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

#38 10-01-2014 22:26:48

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

#39 11-01-2014 00:37:10

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

#40 11-01-2014 00:39:31

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

#41 11-01-2014 01:01:37

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

#42 11-01-2014 01:05:35

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

#43 11-01-2014 11:11:56

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

#44 15-01-2014 11:04:00

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

#45 15-01-2014 11:36:57

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

#46 15-01-2014 11:50:47

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

Réponse rapide

Pied de page des forums