nombres premiers : limites des technologies actuelles
seguiere :: sciences :: nombres Premiers
Page 1 sur 1
nombres premiers : limites des technologies actuelles
par Admin Mar 24 Sep 2013 - 10:33
Nombres Premiers (NP) et limitations des technologies actuelles 2013 xads
Ecrire et faire "tourner" suffisamment longtemps des programmes informatiques qui voudraient :
- Démontrer la conjecture forte de Goldbach (échec)
- Tenter de trouver un nombre Premier de UN milliard de chiffres (échec)
posent quelques soucis de stockages et de représentations.
J'ai exclu le nombre 2 de l'ensemble des NP et dès lors je considère que tout NP est nombre Impair.
Par la suite, je vais appeler NxF le nombre de chiffres (longueur) d'un nombre.
Ainsi 97 aura un NxF=2 et 95111 un NxF=5.
Il est évident que la différence entre un NxF de 4 et de 3, est une puissance de 10 en plus.
Il en va de même entre un nombre de NxF de un million et un nombre de NxF de (un million + 1)
sauf que cette puissance de 10 en plus, porte déjà sur un nombre gigantesque !
Le tableau ci-dessous [corriger] , donne une idée sur le nombre d'impairs que l'on peut rencontrer selon la longueur des nombres. Ex: combien d'impairs possibles pour un nombre de 3 chiffres ? (=450) .
Passer d'un nombre de 10.000.000 de chiffres à un nombre de 17.425.170 chiffres
implique une puissance supplémentaire de 10**7.425.170 , et c'est affolant.
Il est vrai que plus on avance dans des nombres avec des NxF importants
plus les Impairs ont des chances de se trouver être un multiple d'un Premier déjà rencontré.
déjà, éliminer tous les impairs multiples de 3, de 5, 7, 11, 13, 17 ..
Mais aussi, plus on avance dans des nombres avec des NxF importants ,
plus on va rencontrer des quantités d'impairs importantes !
A moins qu'au-delà d'un certain Impair de taille titanesque, il n'existe plus de nouveau Premier !
Autrement dit l'ensemble des Premiers serait borné. [le contraire a été démontré]
L'idée que, la conjugaison des multiples des Premiers déjà rencontrés pour tout Impair supérieur à une valeur titanesque, borne l'ensemble des Premiers, est intéressante en soi, mais cela s'arrête là.
"La théorie" des nombres Premiers, c'est aussi la théorie de la conjugaison des multiples des Premiers
déjà rencontrés dans un ensemble d' impairs* de taille colossale.
Si je savais décrire cette conjugaison de façon certaine, j'aurais fait un grand pas pour l'humanité [rire] .
Mais là n'est pas mon propos.
(*) ou pas
"Table" des NP (TNP)
Table des NP (TNP)
Je voudrais rappeler que la seule écriture d'un nombre de 10 millions de chiffres va occuper une "surface"
d'environ 5 millions d'octets (5 Mo) [avec compression].
Et il y a près de 4.5 fois 10 puissance 10 millions d' Impairs, dans ce cas, candidats à être Premier (ou pas) !
C'est l'objet de la TNP : on essaie de stocker le minimum de Premiers (dont ceux de très grande taille)
on se concentre plutôt sur les distances entre eux.
Exemple : voici à quoi pourrait ressembler la TNP avec des NP très, très petits : ici de NxF=5
[br]La distance entre 99551 et 99559 est de 8. J'utilise ici une distance "relative". [corriger]
Chaque ligne étant identifiée par un "Premier de base". Chaque ligne est une "tranche" de Premiers.
Je ne suis pas dans la précision absolue de l'arithmétique :
les grandeurs que j'évoque ici, se contentent souvent d'approximation, c'est suffisant pour ce que je veux en faire.
Je suis quand même obligé –de temps en temps- de stocker un Premier de Base sur "disque" pour alléger les calculs. Ainsi lorsque j'ai épuisé le parcours de la Tranche des "99401" il faut que je récupère celle des "99551"
(ce n'est qu'un exemple trivial, la réalité est bien plus complexe) .
Il me semble qu'un record (paquet de bytes sur disque) ne peut dépasser 2.147.483.647 bytes (2Go) ,
dans le meilleur des cas, avec le langage "Pascal".[corriger]
Pour une Tranche, j'ai tout intérêt à aligner la taille de mes records à leur plus grande capacité possible : 2Go.
Je vais tenter de rechercher le Premier de Base par un "indice" (référence à la position de cette tranche dans la TNP donc aussi sur "disque") et qui va me servir à retrouver les distances implémentées pour lui.
Cet "indice" va me permettre de retrouver la 1ére Tranche, la seconde, etc..
Avec le langage "Pascal" cet "indice" ne doit pas excéder [corriger] la taille d'un LongWord donc 4.294.967.295 d'indices : c'est dire que je ne peux pas "adresser" plus de 4.294.967.295 de Tranches,
à moins de complexifier fortement le système d'adressage.
Maintenant, dans UNE "Tranche" combien pourrais-je stocker de "distances" (donc de Premiers) ?
Une distance, sera représentée par un 4 bytes. Ainsi avec un LongWord la plus grande distance
que l'on peut stocker est 4.294.967.295 ce qui semble énorme.
Mais n'existe-t-il pas un Premier P1 et son successeur P2 tels que P2 moins P1 > 4.294.967.295 ?
C'est plus que probable, c'est même certain. Et ces premiers ont quels NxF ?
On va atteindre là, la limite de notre spécification informatique de la distance.
Notez que si je présente la distance avec un 8 bytes au lieu de 4, j'ai toujours la certitude de dépasser un jour, sa capacité ! Mais de quel NxF ?
Pour un "Premier de Base", dans la TNP, il est nécessaire de stocker le maximum possible de distances
dans sa Tranche de 2 Go (LongInt) [corriger].
Autrement dit, tout accès disque ne pourra pas restituer/stocker plus de 2Go par record. [corriger]
Et sur ces 2Go en théorie je pourrais stocker ½ milliard de distances, environ.
Est-ce à dire qu'il faut stocker comme "Premier de Base", UN Premier tous les UN demi milliard de Premiers environ ?
Dans ma "Table" TNP je ne peux donc stocker/retrouver que 4.294.967.295 Tranches avec mon indice,
qui chacune stocke 0.5 milliard de distances avec ses Premiers successeurs de sa Tranche.
Je peux donc stocker en tout un peu plus de 2*10**18 distances donc de Premiers environ.
Il faut voir que dans les nombres de NxF=10**7 chiffres il y a [ (9*10**9.999.999) / 2] nombres Impairs de 10**7 chiffres [corriger] mais combien de Premiers ?
Si je décrète que dans les impairs de NxF=10**7 chiffres il y a "seulement" 5% de nombres Premiers
cela me donne 5% de [ (9*10**9.999.999) / 2] soit environ 2*10**1.000.000 de Premiers de NxF=10**7 à découvrir. [corriger]
Comparé aux 2 * 10**18 (environ) Premiers "stockables" avec la technologie,
Ces 2*10**1.000.000 de Premiers de NxF=10**7 -et même s'ils sont 2 fois moins nombreux-
sont déjà infiniment plus nombreux que ce que peut supporter cette technologie !
La taille d'un record, la taille de mon "indice", la taille d'une Tranche, la taille d'une "distance", ..
ne sont pas spécialement adaptées à cette recherche via l'informatique, à ce jour.
Sans compter qu'il faut que j'arrive à stocker sur mes "disques" les quantités astronomiques
de bytes que cela représente, et que je n'explicite pas ici.
Technologies
Pourquoi le langage "Pascal" plutôt que C, ou tout autre ? Pourquoi Intel plutôt que Z/os ?
Si l'on veut travailler avec des nombres de 10**7 chiffres ou plus, finalement ils sont presque tous équivalents
quand à leurs capacités d'adressage et de stockage.
La technologie "binaire" (d'où découle le byte) n'est pas adaptée.
La taille de la mémoire, l'architecture, les supports externes (disques) non plus.
Les nombres de NxF >= 10 millions de chiffres sont inaccessibles avec les technologies actuelles.
Et pour trouver les 2*10**1.000.000 de Premiers de NxF=10**7 (et même s'ils sont 2 fois moins nombreux)
il faudrait que je complexifie fortement le système d'adressage
et que je trouve quelques téraoctets pour les disques et la mémoire .
L'informatique distribuée en réseau me semble efficace, que si et seulement si, on se pose comme question :
"le nombre (n) est-il premier ?". [corriger]
Il y a des limites où "ruser" devient impossible.
Là où on voudrait tenter de jouer dans la cour des Dieux, on n'y arrive pas (encore).
Il faut abandonner la recherche des nombres Premiers (par cette méthode)
ou alors s'arrêter aux possibilités des technologies actuelles.
Ecrire et faire "tourner" suffisamment longtemps des programmes informatiques qui voudraient :
- Démontrer la conjecture forte de Goldbach (échec)
- Tenter de trouver un nombre Premier de UN milliard de chiffres (échec)
posent quelques soucis de stockages et de représentations.
J'ai exclu le nombre 2 de l'ensemble des NP et dès lors je considère que tout NP est nombre Impair.
Par la suite, je vais appeler NxF le nombre de chiffres (longueur) d'un nombre.
Ainsi 97 aura un NxF=2 et 95111 un NxF=5.
Il est évident que la différence entre un NxF de 4 et de 3, est une puissance de 10 en plus.
Il en va de même entre un nombre de NxF de un million et un nombre de NxF de (un million + 1)
sauf que cette puissance de 10 en plus, porte déjà sur un nombre gigantesque !
Le tableau ci-dessous [corriger] , donne une idée sur le nombre d'impairs que l'on peut rencontrer selon la longueur des nombres. Ex: combien d'impairs possibles pour un nombre de 3 chiffres ? (=450) .
| NxF | Nombre min Pour ce NxF | Nombre max | Quantité de nombres avec ce NxF | Quantité de nombres IMPAIRS avec ce NxF |
| 2 | 101 = 10 | 102 -1 = 99 | 9*101 = 90 | |
| 3 | 102 | 103 -1 = 999 | 9*102 = 900 | (900/2)=450 |
| 4 | 103 = 1.000 | 104-1 = 9.999 | 9*103 = 9.000 | (9000/2) |
| 9 | 108=100.000.000 | 109 -1 | 9*108-1 | (9*108) / 2 |
| 10 | 109=1.000.000.000 | 1010 -1 | 9*1010-1 | (9*109) / 2 |
| 100 | 10(100)-1=1099 | 10100 -1 | 9*10100-1 | |
| 1000 | 10(1000)-1=10999 | 9*10999 | ||
| 106 (1 million | 10(10**6) -1 | 9*10999.999 | ||
| 107 (10 millions | 10(10**7) -1 | 1010**7 -1 | 9*10(10**7)-1 | (9*109.999.999) / 2 |
| 108 (100 millions | 10(10** -1 | 1010**8 -1 | 9*10(10**-1 | (9*1099.999.999) / 2 |
| 109 (1 milliard | 10(10**9) -1 | 1010**9 -1 | 9*10999.999.999 | (9*10999.999.999) / 2 |
implique une puissance supplémentaire de 10**7.425.170 , et c'est affolant.
Il est vrai que plus on avance dans des nombres avec des NxF importants
plus les Impairs ont des chances de se trouver être un multiple d'un Premier déjà rencontré.
déjà, éliminer tous les impairs multiples de 3, de 5, 7, 11, 13, 17 ..
Mais aussi, plus on avance dans des nombres avec des NxF importants ,
plus on va rencontrer des quantités d'impairs importantes !
A moins qu'au-delà d'un certain Impair de taille titanesque, il n'existe plus de nouveau Premier !
Autrement dit l'ensemble des Premiers serait borné. [le contraire a été démontré]
L'idée que, la conjugaison des multiples des Premiers déjà rencontrés pour tout Impair supérieur à une valeur titanesque, borne l'ensemble des Premiers, est intéressante en soi, mais cela s'arrête là.
"La théorie" des nombres Premiers, c'est aussi la théorie de la conjugaison des multiples des Premiers
déjà rencontrés dans un ensemble d' impairs* de taille colossale.
Si je savais décrire cette conjugaison de façon certaine, j'aurais fait un grand pas pour l'humanité [rire] .
Mais là n'est pas mon propos.
(*) ou pas
"Table" des NP (TNP)
Table des NP (TNP)
Je voudrais rappeler que la seule écriture d'un nombre de 10 millions de chiffres va occuper une "surface"
d'environ 5 millions d'octets (5 Mo) [avec compression].
Et il y a près de 4.5 fois 10 puissance 10 millions d' Impairs, dans ce cas, candidats à être Premier (ou pas) !
C'est l'objet de la TNP : on essaie de stocker le minimum de Premiers (dont ceux de très grande taille)
on se concentre plutôt sur les distances entre eux.
Exemple : voici à quoi pourrait ressembler la TNP avec des NP très, très petits : ici de NxF=5
| 99401 | 8 99409 | 32 99431 | 8 99439 | 30 99469 | 18 99487 | 10 99491 | 26 99523 | 4 99527 | 2 99529 |
| 99551 | 8 99559 | 4 99563 | 8 99571 | 6 99577 | 4 99581 | 26 99607 | 4 99611 | 12 99623 | 20 99643 |
Chaque ligne étant identifiée par un "Premier de base". Chaque ligne est une "tranche" de Premiers.
Je ne suis pas dans la précision absolue de l'arithmétique :
les grandeurs que j'évoque ici, se contentent souvent d'approximation, c'est suffisant pour ce que je veux en faire.
Je suis quand même obligé –de temps en temps- de stocker un Premier de Base sur "disque" pour alléger les calculs. Ainsi lorsque j'ai épuisé le parcours de la Tranche des "99401" il faut que je récupère celle des "99551"
(ce n'est qu'un exemple trivial, la réalité est bien plus complexe) .
Il me semble qu'un record (paquet de bytes sur disque) ne peut dépasser 2.147.483.647 bytes (2Go) ,
dans le meilleur des cas, avec le langage "Pascal".[corriger]
Pour une Tranche, j'ai tout intérêt à aligner la taille de mes records à leur plus grande capacité possible : 2Go.
Je vais tenter de rechercher le Premier de Base par un "indice" (référence à la position de cette tranche dans la TNP donc aussi sur "disque") et qui va me servir à retrouver les distances implémentées pour lui.
Cet "indice" va me permettre de retrouver la 1ére Tranche, la seconde, etc..
Avec le langage "Pascal" cet "indice" ne doit pas excéder [corriger] la taille d'un LongWord donc 4.294.967.295 d'indices : c'est dire que je ne peux pas "adresser" plus de 4.294.967.295 de Tranches,
à moins de complexifier fortement le système d'adressage.
Maintenant, dans UNE "Tranche" combien pourrais-je stocker de "distances" (donc de Premiers) ?
Une distance, sera représentée par un 4 bytes. Ainsi avec un LongWord la plus grande distance
que l'on peut stocker est 4.294.967.295 ce qui semble énorme.
Mais n'existe-t-il pas un Premier P1 et son successeur P2 tels que P2 moins P1 > 4.294.967.295 ?
C'est plus que probable, c'est même certain. Et ces premiers ont quels NxF ?
On va atteindre là, la limite de notre spécification informatique de la distance.
Notez que si je présente la distance avec un 8 bytes au lieu de 4, j'ai toujours la certitude de dépasser un jour, sa capacité ! Mais de quel NxF ?
Pour un "Premier de Base", dans la TNP, il est nécessaire de stocker le maximum possible de distances
dans sa Tranche de 2 Go (LongInt) [corriger].
Autrement dit, tout accès disque ne pourra pas restituer/stocker plus de 2Go par record. [corriger]
Et sur ces 2Go en théorie je pourrais stocker ½ milliard de distances, environ.
Est-ce à dire qu'il faut stocker comme "Premier de Base", UN Premier tous les UN demi milliard de Premiers environ ?
Dans ma "Table" TNP je ne peux donc stocker/retrouver que 4.294.967.295 Tranches avec mon indice,
qui chacune stocke 0.5 milliard de distances avec ses Premiers successeurs de sa Tranche.
Je peux donc stocker en tout un peu plus de 2*10**18 distances donc de Premiers environ.
Il faut voir que dans les nombres de NxF=10**7 chiffres il y a [ (9*10**9.999.999) / 2] nombres Impairs de 10**7 chiffres [corriger] mais combien de Premiers ?
Si je décrète que dans les impairs de NxF=10**7 chiffres il y a "seulement" 5% de nombres Premiers
cela me donne 5% de [ (9*10**9.999.999) / 2] soit environ 2*10**1.000.000 de Premiers de NxF=10**7 à découvrir. [corriger]
Comparé aux 2 * 10**18 (environ) Premiers "stockables" avec la technologie,
Ces 2*10**1.000.000 de Premiers de NxF=10**7 -et même s'ils sont 2 fois moins nombreux-
sont déjà infiniment plus nombreux que ce que peut supporter cette technologie !
La taille d'un record, la taille de mon "indice", la taille d'une Tranche, la taille d'une "distance", ..
ne sont pas spécialement adaptées à cette recherche via l'informatique, à ce jour.
Sans compter qu'il faut que j'arrive à stocker sur mes "disques" les quantités astronomiques
de bytes que cela représente, et que je n'explicite pas ici.
Technologies
Pourquoi le langage "Pascal" plutôt que C, ou tout autre ? Pourquoi Intel plutôt que Z/os ?
Si l'on veut travailler avec des nombres de 10**7 chiffres ou plus, finalement ils sont presque tous équivalents
quand à leurs capacités d'adressage et de stockage.
La technologie "binaire" (d'où découle le byte) n'est pas adaptée.
La taille de la mémoire, l'architecture, les supports externes (disques) non plus.
Les nombres de NxF >= 10 millions de chiffres sont inaccessibles avec les technologies actuelles.
Et pour trouver les 2*10**1.000.000 de Premiers de NxF=10**7 (et même s'ils sont 2 fois moins nombreux)
il faudrait que je complexifie fortement le système d'adressage
et que je trouve quelques téraoctets pour les disques et la mémoire .
L'informatique distribuée en réseau me semble efficace, que si et seulement si, on se pose comme question :
"le nombre (n) est-il premier ?". [corriger]
Il y a des limites où "ruser" devient impossible.
Là où on voudrait tenter de jouer dans la cour des Dieux, on n'y arrive pas (encore).
Il faut abandonner la recherche des nombres Premiers (par cette méthode)
ou alors s'arrêter aux possibilités des technologies actuelles.
Admin- Admin
- Messages : 7
Date d'inscription : 20/06/2013 -
Re: nombres premiers : limites des technologies actuelles
par zaduk Sam 19 Oct 2013 - 15:31
j'en ai mal à la tête
zaduk- Invité
seguiere :: sciences :: nombres Premiers
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum|
|
|