Probleme de division de grands entiers.

Version imprimable

11/04/2017, 09h18
fred61

Probleme de division de grands entiers.
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:

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.
11/04/2017, 10h15
wiztricks

Salut,

Citation:

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
11/04/2017, 10h25
nekcorp
Citation:

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:

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.
11/04/2017, 10h52
memento80
Bonjour,

Citation:

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).

Citation:

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:

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

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).

J'ai essaye le code suivant :

Code:

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

Et j'obtient ca :

Code:

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.

11/04/2017, 11h37
wiztricks

Citation:

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

Citation:

Envoyé par fred61

J'ai essaye le code suivant :

Code:

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

Et j'obtient ca :

Code:

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:

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 ?

11/04/2017, 12h49
memento80

Citation:

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 ?

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

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

11/04/2017, 13h43
wiztricks

Citation:

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

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:

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

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.

11/04/2017, 14h55
fred61

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.
11/04/2017, 15h12
nekcorp

Citation:

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 :mouarf:
11/04/2017, 17h26
tyrtamos
Citation:

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:

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:

126372531954418782670747930963559908367043074176552978854728812339634981881297738186484473148885678679817250057381314722686293252256406164004406590313221431594658364724234232601401479859842407134408936812192579280935450252285976584619444811530638558312046094061538487405595898712527059751636380445254298891031

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