Programme qui plante à 257.

[MihoAzuki]

Bonjour!

J'avais essayé de créer un programme qui calcule le n-ième premier, et je suis arrivé à ça:

Code : Tout sélectionner

n = int(input())
L = [2,3,5,7]
i = 9
while len(L) is not n:
    j = i
    for k in L:
        if k <= int(i**(0.5))+1:
            if i%k == 0:
                i += 2
                break
    if j == i:
        L.append(j)
        i += 2
print(L[-1])

Le programme marche très bien pour n allant de 4 à 256, pour n = 256 il fait d'ailleurs le calcul en quelques centièmes de seconde, et pour n = 257, il.. plante complètement.
Alors, si on modifie le programme de cette manière:

Code : Tout sélectionner

def npremier(n):
    L = [2,3,5,7]
    i = 9
    while len(L) < n:
        j = i
        for k in L:
            if k <= int(i**(0.5))+1:
                if i%k == 0:
                    i += 2
                    break
        if j == i:
            L.append(j)
            i += 2
    return(L[-1])

ça marche très bien (et relativement vite, mais si vous avez mieux je suis preneur. :p :finduHS:) pour n >= 257, mais là n'est pas la question:
Qu'est ce qui fait que mon premier programme plante complètement pour n=257 et plus?
Merci d'avance pour votre aide.

[loupi]

il faut utiliser "!=" et non "is not" dans ton while pour la comparaison, car tu compares 2 objet différents len(L) et n.

Par contre pourquoi ça fonctionne quand même pour n<=256, j'en sais rien, surement une histoire d'octet 2**8 (256), mais je ne vois pas très bien le rapport.
A moins que len(L) change de type de donnée quand sa valeur est >256.

[fakbill]

Pas le temps de lire ton code maintenant mais qui t'a montré "is / is not"??
Qu'as tu compris de "is / is not"? Ca teste quoi exactement??

Il plante quoi? des choux? As tu essayé de debugger? Sais tu comment commencer à débugger?

A moins que len(L) change de type de donnée quand sa valeur est >256.

Ben voyons...

[loupi]

A moins que len(L) change de type de donnée quand sa valeur est >256.


Ben voyons...

Comment expliques-tu que "len(L) is not n" renvoie true pour une valeur de n>256 lorsque len(L)==n, et renvoie false pour une valeur de n<=256 lorsque len(L)==n ?

[np*]

Bonjour,

Les entiers étant immuable en python, dans certaines implémentations de python, les "petits" entiers sont tous stockés au même endroit, ce qui est plus efficace en terme de mémoire. Vous pouvez vérifier par exemple que leur identifiant est le même :

Code : Tout sélectionner

for i in [225, 256, 257]:
    j = len(range(i))
    print(i, id(i), j, id(j), i == j, i is j)

En gros, is va vérifier que les identifiants sont les mêmes, ceux-ci étant uniques pour un objet donné pendant toute la vie du programme (en CPython c'est l'adresse de l'objet en mémoire par exemple). Pour des raisons d'optimisation, ce n'est pas le cas pour tous les entiers. Remarquez que la plage d'entiers concernés dépend de la version de python et de son implémentation.

Voici ce que dit la doc:

The current implementation keeps an array of integer objects for all integers between -5 and 256, when you create an int in that range you actually just get back a reference to the existing object.

Dans tous les cas, il s'agit là de détails d'implémentation, desquels ne doit pas dépendre le résultat de vos programmes. Il faut donc bien tester l'égalité de deux entiers avec l'opérateur d'équivalence == et non avec celui d'identité is.

Le seul cas que vous rencontrerez nécessitant l'identité (en dehors de cas tordus pour des programmes plus avancés) est celui de la comparaison au singleton None.

Code : Tout sélectionner

if object is None:

Dans ce cas, il n'y a qu'un seul objet None au monde et mieux vaut tester l'identité. Les cas d'égalité avec None qui ne renvoient pas le résultat escompté surviennent lorsque l'on définit ses propres objets avec leur opérateur __eq__, probablement chose que vous ne ferez pas tout de suite. Mais mieux vaut prendre de bonnes habitudes.

Si vous voulez en savoir plus:

http://stackoverflow.com/questions/3063 ... h-integers

[loupi]

ok, merci np*, pour l'info.
Je n'étais pas si loin que ça avec l'hypothèse de changement de type de donnée pour les entiers >256 (petits entiers => gros entiers), n'est-ce pas fakbill ?

[fakbill]

Heu conceptuellement si...tu en étais ultra loin.
Le type d'une variable, c'est une étiquette qu'on lui colle pour savoir si c'est une string ou un entier ou je ne sais quoi.
En python, ce n'est pas exactement ça si on veut être précis :
Python est basé sur le duck typing donc on ne regarde pas tant le nom sur l'étiquette que la capacité ou non de l'objet à faire ce qu'on lui demande. Si l'objet possède une méthode qui correspond à la demande alors accepte d’exécuter la demande. Par exemple, a.append(b) fonctionne du moment que a implémente une méthode append qui aime les objets du genre de b (il y aura probablement peu de contraintes sur ce que b est/ sait faire). "Duck typing" car "In other words, don't check whether it IS-a duck: check whether it QUACKS-like-a duck, WALKS-like-a duck, etc, etc, depending on exactly what subset of duck-like behaviour you need to play your language-games with."')

Ça c'est le typage façon python (ca et le fait qu'il soit dynamique).
Le "is" c'est totalement autre chose. C'est "parle-t-on du même objet **physiquement à la même place en mémoire**". Il est rare (en dehors de None) que ce soit ce que tu veuilles tester.

[loupi]

Heu conceptuellement si...tu en étais ultra loin.

Heu conceptuellement, non, pas tant que ça.
Il y avait bien une différence dans la façon de gérer la donnée en fonction de son type "petit entier" ou "gros entier", ce qui provoquait la différence d’exécution en fonction de la valeur et donc de son type, peu importe comment le type est implémenté.
De plus, pour moi, ça relève presque d'un bug de python, d'un point de vue exécution, il ne devrait pas y avoir de différence entre la comparaison IS de 2 objets quelque soit la taille. La comparaison IS donne des résultats différents si on compare un entier supérieur ou non à 256, ce qui ne devrait pas être le cas.

[fakbill]

non et le fait que tu penses que c'est presque un bug prouve que tu confonds deux choses qui n'ont rien à voir:
1) le typage
2) les détail, **non spécifiés**, d'implémentation du langage.

Le fait que python fasse ca:
https://docs.python.org/2/c-api/int.html
"the current implementation keeps an array of integer objects for all integers between -5 and 256, when you create an int in that range you actually just get back a reference to the existing object."
est un détail d'implémentation/optimisation. I se peut très bien que ça change dans une version future de python et ça ne pose aucun problème puisque ce comportement n'est PAS dans la spécification de python. La spécification de python n'impose PAS ce que "is" doit renvoyer ou pas. Tu es libre de recoder un interpréteur python qui gère les petits entiers autrement.

Ca n'a rien à voir avec la définition du langage. "is" ne compare *************PAS************ deux entiers au sens "ont ils la même valeur" mais il teste le fait que deux objets soient (ou non) stockés au même endroit en mémoire et donc le fait que ce ne soit qu'un seul et même objet.

Le bug c'est d'utiliser "is" au lieu de "==".

Si tu veux parler de typage des entiers alors prenons python2.7 (pas 3.X) et regardons ca:
import sys
type(sys.maxsize)
<type 'int'>

type(sys.maxsize+1)
<type 'long'>

Hé oui, les entiers change de type (int devient long) en python2. Ca s'explique car les entiers sont des entiers machine 62bits en mémoire. En C, c'est tout ce qu'on a. Si on dépasse la valeur max qu'on peut stocker dans un entier 64bits, ca ne fait pas ce qu'on veut
En python, +1 sur sys.maxsize transforme ***automatiquement*** l'entier de type int en un entier de type long. Ca change tout en interne. Prenons l'exemple de l'addition. Tant que les valeurs tiennent dans un entier 64bits, c'est une instruction CPU qui s'en charge.
Quand on dépasse cette valeur, il faut déjà commencer par stocker le nombre dans autre chose que 64bits. On peut penser à le stocker comme une list de ses chiffres (nul niveau perfo mais possible...). Faire un "+" est alors un algo qui doit faire une additions sur des nombres représentés sous forme de list. Ca coute beaucoup plus de temps que le + 64bits du CPU....et c'est la même tisane pour toutes les opérations arithmétiques. Il est donc normal d'avoir deux types différents....mais c'est un peu étrange pour l’utilisateur donc, en python3, TOUS les entiers ont le même type. Sous le manteau, python traite les petits entiers différemment des grands pour des raisons de performances MAIS tous les entiers ont le même type. Ca montre encore une fois la différence entre l'implémentation d'un langage et sa spécification. SI la spec n'interdit pas tel ou tel comportement dans tel ou tel cas alors l'implémentation est libre de faire ce qu'il y a de mieux pour la performance.

"is" te permet d'aller voir dans le détail de python et de sa façon de gérer la mémoire. Ça n'a RIEN À voir avec le "=" des mathématiques.

[loupi]

Ca n'a rien à voir avec la définition du langage. "is" ne compare *************PAS************ deux entiers au sens "ont ils la même valeur" mais il teste le fait que deux objets soient (ou non) stockés au même endroit en mémoire et donc le fait que ce ne soit qu'un seul et même objet.

Le bug c'est d'utiliser "is" au lieu de "==".

Euh, ça je l'ai compris depuis plusieurs années... c'est d'ailleurs ce que j'ai dit dans le 1er post.
J'essayais juste de comprendre pourquoi le programme de notre ami MihoAzuki se comportait différemment en fonction de la valeur de n et de lui apporter un début d'explication, ce que tu n'as pas fait, à mon humble avis avec tes réponses, surtout dans la première qui n'apportait aucune aide à notre ami, à part jouer au prof. La réponse valable et utile, c'est celle de np*.

Et désolé de te dire, mais un interpréteur qui se comporte différemment en donnant des résultats différents en fonction de la valeur d'un entier pour la même opération, c'est un bug que tu le veuilles ou non, même si évidemment ce n'était pas la bonne opération à utiliser.