Probleme de division de grands entiers.

**fred61** · 11/04/2017, 09h18

Bonjour,

J'ai fait un programme pour factoriser les grands entiers, il fonctionne jusqu'a des nombres d'environs 20 decimales mais avec des nombres plus grands il tourne en boucle. Au debut je pensais que c'etait mon code qui avait un probleme, mais en debogan mon code je me suis appercu que Python fesait des erreurs lors de division de certains grands nombres. J'ai installe Python 3.6.1.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
n=18157405041894350
m=n/2
print("m=", m)

Normalement en executant le code ci-dessus le resultat devrait etre : 9078702520947175
Mais Python m'affiche 9078702520947176.

Est-ce que vous pouvez verifier si vous avez le meme probleme en executant mon code sur vos pc ? Et sinon savez-vous d'ou peut venir le probleme ?

Je vous remercie.

**wiztricks** · 11/04/2017, 10h15

Salut,

Envoyé par fred61

Et sinon savez-vous d'ou peut venir le probleme ?

n / 2 retourne le nombre flottant le plus proche du résultat.
n // 2 retourne l'entier inférieur (équivaut à floor).

Python fait ce que vous lui demandez (mais peut être pas ce que vous pensiez qu'il ferait).

- W

**nekcorp** · 11/04/2017, 10h25

Envoyé par fred61

Est-ce que vous pouvez verifier si vous avez le meme probleme en executant mon code sur vos pc ?

Salut fred61,

Pour ma part voilà ce que j'obtiens sous Python 2.7.3 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
>>> n=18157405041894350
>>> m=n/2
>>> print("m=", m)
('m=', 9078702520947175L)
>>>>>> print m
9078702520947175

Par contre je ne comprend pas ce que veux dire le L à la ligne 5.

**memento80** · 11/04/2017, 10h52

Bonjour,

Envoyé par nekcorp

Par contre je ne comprend pas ce que veux dire le L à la ligne 5.

De mémoire, c'est le type "long" (qui ne serait pas en Python3).

Envoyé par fred61

Est-ce que vous pouvez verifier si vous avez le meme probleme en executant mon code sur vos pc ? Et sinon savez-vous d'ou peut venir le probleme ?

J'utilisais le module Decimal pour gérer ce genre de problème. Inconvénient : il est très lent. Il y a probablement une meilleure solution... (?)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
from decimal import Decimal
n=Decimal(18157405041894350)
m=n/2
print("m=", m)
m= 9078702520947175

**fred61** · 11/04/2017, 11h05

Je vous remercie pour vos reponses mais je trouve quand meme ca etonnant, wiztricks tu me dis

"n / 2 retourne le nombre flottant le plus proche du résultat"

Le resultat de l'operation 18157405041894350/2 est 9078702520947175, et non 9078702520947176.0 comme le resultat obtenu avec Python, que ca soit un flottant ou non le resultat est faux, ce qui m'etonne pour un language utilise par des scientifiques.

memento80, meme en utilisant le module Decimal j'obtient le meme resultat. Ce qui est etonnant c'est que le calcul est jusque quand je divise d'autres nombres, ca bug que pour certains nombres.

(desole pour les accents, je suis a l'etranger avec un pc en qwerty).

**fred61** · 11/04/2017, 11h31

J'ai essaye le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i in range(18157405041894350, 18157405041894400, 2):
	print(i, "/2=", i/2)

Et j'obtient ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
18157405041894350 /2= 9078702520947176.0
18157405041894352 /2= 9078702520947176.0
18157405041894354 /2= 9078702520947176.0
18157405041894356 /2= 9078702520947178.0
18157405041894358 /2= 9078702520947180.0
18157405041894360 /2= 9078702520947180.0
18157405041894362 /2= 9078702520947180.0
18157405041894364 /2= 9078702520947182.0
18157405041894366 /2= 9078702520947184.0
18157405041894368 /2= 9078702520947184.0
18157405041894370 /2= 9078702520947184.0
18157405041894372 /2= 9078702520947186.0
18157405041894374 /2= 9078702520947188.0
18157405041894376 /2= 9078702520947188.0
18157405041894378 /2= 9078702520947188.0
18157405041894380 /2= 9078702520947190.0
18157405041894382 /2= 9078702520947192.0
18157405041894384 /2= 9078702520947192.0
18157405041894386 /2= 9078702520947192.0
18157405041894388 /2= 9078702520947194.0
18157405041894390 /2= 9078702520947196.0
18157405041894392 /2= 9078702520947196.0
18157405041894394 /2= 9078702520947196.0
18157405041894396 /2= 9078702520947198.0
18157405041894398 /2= 9078702520947200.0

C'est problematique, comment obtenir les bons resultats ?
Merci.

**wiztricks** · 11/04/2017, 11h37

Envoyé par fred61

Le resultat de l'operation 18157405041894350/2 est 9078702520947175, et non 9078702520947176.0 comme le resultat obtenu avec Python, que ca soit un flottant ou non le resultat est faux, ce qui m'etonne pour un language utilise par des scientifiques.

Si vous n'avez aucune notion de la représentation des nombres flottants en binaire, je comprends tout à fait votre surprise. Mais il y a une différence entre "je ne comprends pas trop comment çà fonctionne et comment je vais bien pouvoir faire pour obtenir ce que je cherche" - si vous expliquiez ce que vous cherchez à faire on pourrait vous aider à construire la solution - et l'arrogance de dire droit dans ses bottes "ce résultat est faux" - qui ne mérite que "aller troller ailleurs..." - d'autant que vous ne comprenez même pas les solutions qu'on vous indique ('//' ou module Decimal).

- W

**nekcorp** · 11/04/2017, 11h48

Envoyé par fred61

J'ai essaye le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i in range(18157405041894350, 18157405041894400, 2):
	print(i, "/2=", i/2)

Et j'obtient ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
18157405041894350 /2= 9078702520947176.0
18157405041894352 /2= 9078702520947176.0
18157405041894354 /2= 9078702520947176.0
18157405041894356 /2= 9078702520947178.0
18157405041894358 /2= 9078702520947180.0
18157405041894360 /2= 9078702520947180.0
18157405041894362 /2= 9078702520947180.0
18157405041894364 /2= 9078702520947182.0
18157405041894366 /2= 9078702520947184.0
18157405041894368 /2= 9078702520947184.0
18157405041894370 /2= 9078702520947184.0
18157405041894372 /2= 9078702520947186.0
18157405041894374 /2= 9078702520947188.0
18157405041894376 /2= 9078702520947188.0
18157405041894378 /2= 9078702520947188.0
18157405041894380 /2= 9078702520947190.0
18157405041894382 /2= 9078702520947192.0
18157405041894384 /2= 9078702520947192.0
18157405041894386 /2= 9078702520947192.0
18157405041894388 /2= 9078702520947194.0
18157405041894390 /2= 9078702520947196.0
18157405041894392 /2= 9078702520947196.0
18157405041894394 /2= 9078702520947196.0
18157405041894396 /2= 9078702520947198.0
18157405041894398 /2= 9078702520947200.0

C'est problematique, comment obtenir les bons resultats ?
Merci.

J'ai testé sur Python 2.7.3 (désolé je n'ai pas de version 3 d'installé sur ma machine).

voilà ce que j'obtiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
>>> for i in range(18157405041894350, 18157405041894400, 2):
	print(i, "/2=", i/2)
 
 
(18157405041894350L, '/2=', 9078702520947175L)
(18157405041894352L, '/2=', 9078702520947176L)
(18157405041894354L, '/2=', 9078702520947177L)
(18157405041894356L, '/2=', 9078702520947178L)
(18157405041894358L, '/2=', 9078702520947179L)
(18157405041894360L, '/2=', 9078702520947180L)
(18157405041894362L, '/2=', 9078702520947181L)
(18157405041894364L, '/2=', 9078702520947182L)
(18157405041894366L, '/2=', 9078702520947183L)
(18157405041894368L, '/2=', 9078702520947184L)
(18157405041894370L, '/2=', 9078702520947185L)
(18157405041894372L, '/2=', 9078702520947186L)
(18157405041894374L, '/2=', 9078702520947187L)
(18157405041894376L, '/2=', 9078702520947188L)
(18157405041894378L, '/2=', 9078702520947189L)
(18157405041894380L, '/2=', 9078702520947190L)
(18157405041894382L, '/2=', 9078702520947191L)
(18157405041894384L, '/2=', 9078702520947192L)
(18157405041894386L, '/2=', 9078702520947193L)
(18157405041894388L, '/2=', 9078702520947194L)
(18157405041894390L, '/2=', 9078702520947195L)
(18157405041894392L, '/2=', 9078702520947196L)
(18157405041894394L, '/2=', 9078702520947197L)
(18157405041894396L, '/2=', 9078702520947198L)
(18157405041894398L, '/2=', 9078702520947199L)

J'imagine que ce sont les résultats souhaités ?

**memento80** · 11/04/2017, 12h49

Envoyé par fred61

memento80, meme en utilisant le module Decimal j'obtient le meme resultat. Ce qui est etonnant c'est que le calcul est jusque quand je divise d'autres nombres, ca bug que pour certains nombres.

Etonnant que ça ne fonctionne pas avec Decimal.

Des exemples de nombres/résultats que tu obtiens et qui te sembleraient corrects ou incorrects ?

**fred1599** · 11/04/2017, 13h03

Utilises GMPY, il est fait pour ça...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
>>> import gmpy
>>> n = gmpy.mpz('18157405041894350')
>>> m = int(n/2)
>>> m
9078702520947175

**wiztricks** · 11/04/2017, 13h43

Envoyé par nekcorp

J'ai testé sur Python 2.7.3 (désolé je n'ai pas de version 3 d'installé sur ma machine).

Pour tester avec la division de Python3, il suffit de faire from __future__ import division.

- W

**tyrtamos** · 11/04/2017, 13h54

Bonjour,

Ce qui se passe n'est pas une erreur: Python fait exactement ce qui lui est demandé.

Les nombres flottants de Python (=type "double" du C) sont capables de conserver de 16 à 17 chiffres significatifs. Quand on essaie de diviser un nombre entier de 20 chiffres par 2 en utilisant le signe '/', on génère une conversion de ce nombre en flottant, ce qui fait perdre les derniers chiffres.

Mais si on veut obtenir un nombre entier après la division, ce n'est pas logique d'utiliser le signe '/': il faut utiliser le signe '//' de la division entière!

Appliquons avec le code donné en exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i in range(18157405041894350, 18157405041894400, 2):
    print(i, "//2=", i//2)

Cela donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
18157405041894350 //2= 9078702520947175
18157405041894352 //2= 9078702520947176
18157405041894354 //2= 9078702520947177
18157405041894356 //2= 9078702520947178
18157405041894358 //2= 9078702520947179
18157405041894360 //2= 9078702520947180
18157405041894362 //2= 9078702520947181
18157405041894364 //2= 9078702520947182
18157405041894366 //2= 9078702520947183
18157405041894368 //2= 9078702520947184
18157405041894370 //2= 9078702520947185
18157405041894372 //2= 9078702520947186
18157405041894374 //2= 9078702520947187
18157405041894376 //2= 9078702520947188
18157405041894378 //2= 9078702520947189
18157405041894380 //2= 9078702520947190
18157405041894382 //2= 9078702520947191
18157405041894384 //2= 9078702520947192
18157405041894386 //2= 9078702520947193
18157405041894388 //2= 9078702520947194
18157405041894390 //2= 9078702520947195
18157405041894392 //2= 9078702520947196
18157405041894394 //2= 9078702520947197
18157405041894396 //2= 9078702520947198
18157405041894398 //2= 9078702520947199

A noter qu'il s'agit d'une différence entre Python 2 et Python 3. Pour des raisons historiques, la division simple ('/') de Python 2.x entre 2 entiers donnait un entier! Ce n'est plus vrai avec Python 3.

**fred61** · 11/04/2017, 14h55

Je vous remercie beaucoup pour vos eclaircissements, effectivement ca fonctionne avec //
Pardonnez-moi d'avoir mis en doute les performances de Python

Encore une autre question au passage, est-ce que je risque d'avoir le meme genre de difficulte en utilisant l'operateur modulo (%) ?
Merci.

**nekcorp** · 11/04/2017, 15h12

Envoyé par fred61

Encore une autre question au passage, est-ce que je risque d'avoir le meme genre de difficulte en utilisant l'operateur modulo (%) ?
Merci.

J'ai envie de te dire fait le test et reviens nous voir si ça ne fonctionne pas

**tyrtamos** · 11/04/2017, 17h26

Envoyé par fred61

est-ce que je risque d'avoir le meme genre de difficulte en utilisant l'operateur modulo (%) ?

Tant que tu restes dans le monde des entiers, tu obtiendras ce que tu voudras:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
print(3333333333333333333333333333333333333333333333333333333333333%2)
1

Python a des capacités impressionnantes dans les calculs d'entiers. Voilà, par exemple, un nombre premier de 1024 bits calculé en Python en moins de 30 secondes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

126372531954418782670747930963559908367043074176552978854728812339634981881297738186484473148885678679817250057381314722686293252256406164004406590313221431594658364724234232601401479859842407134408936812192579280935450252285976584619444811530638558312046094061538487405595898712527059751636380445254298891031

Ce qui peut s'utiliser dans certains algorithmes de cryptographie.

Probleme de division de grands entiers.

Python

Discussions similaires

Partager

Partager