Bonjour à tous !

J'ai ouï dire qu'il existait en Python des modules faits spécialement pour traiter des grands nombres. J'ai vu ça et là le mode decimal, mais je ne suis pas vraiment sûr que ce soit adapté à mes besoins, vu que je ne m'intéresse qu'aux entiers.

L'idéal serait de traiter des nombres jusqu'à 200 chiffres, mais je ne suis déjà pas sûr qu'il ne réalise pas d'approximation pour des nombres à seulement 20 chiffres...

Voilà le code en question :

from math import sqrt
import time

def isPrime(toTest, listToTest):

	component = []
	power     = []

	"""
	Renvoie la décomposition en facteurs premiers à partir d'une liste donnée.
	"""

	for prime in listToTest:

		if toTest % prime == 0:
			component.append(prime)
			power.append(1)
			toTest /= prime

			while toTest % prime == 0:
				power[-1] += 1
				toTest /= prime

		if prime > sqrt(toTest):
			component.append(int(toTest))
			toTest = 1
			power.append(1)
			break

	return [component, power, toTest]


def addPrime():

	"""
	Ajoute au moins un nombre premier à listPrime.
	"""

	global last
	last += 6

	while True:

		if isPrime(last - 1, listPrime)[0:2] == [[last - 1], [1]]:
			listPrime.append((last - 1))

			if isPrime(last + 1, listPrime)[0:2] == [[last + 1], [1]]:
				listPrime.append(last + 1)

			break

		elif isPrime(last + 1, listPrime)[0:2] == [[last + 1], [1]]:
			listPrime.append(last + 1)
			break

		else:
			last += 1

def decumpose(toTest):

	factors       = []
	valuations    = []
	decumposition = isPrime(toTest, listPrime)

	factors.extend(decumposition[0])
	valuations.extend(decumposition[1])
	toTest = decumposition[2]

	while decumposition[2] != 1:
		addPrime()
		decumposition = isPrime(toTest, [listPrime[-2],listPrime[-1]])
		factors.extend(decumposition[0])
		valuations.extend(decumposition[1])
		toTest = decumposition[2]

	return factors, valuations

listPrime          = [2,3,5,7]
last               = 6
toDecumpose        = 1235678900987654321
final              = ""
decumpositionFinal = decumpose(toDecumpose)

for i in range(len(decumpositionFinal[0]) - 1):
	final += str(decumpositionFinal[0][i]) + "^" + str(decumpositionFinal[1][i]) + " x "
final += str(decumpositionFinal[0][-1]) + "^" + str(decumpositionFinal[1][-1])

print(str(toDecumpose) + " = " + final)

J'ai commencé à le laisser tourner, mais quand je tape dans l'interpréteur Python, et que j'obtiens ça :

>>> a = 12345678900987654321
>>> a/2 == int(a/2)
True

J'ai quelques doutes sur l'efficacité de mon code...

Merci d'avance,

BunshinKage

-
Edité par BunshinKage 25 décembre 2015 à 0:52:05

Ce sont les nombres flottants qui sont limités et l'opérateur de division flottante convertie les opérandes en nombres flottants, ce qui peut fausser le résultat. C'est pour ça que l'on conseil d'utiliser le module decimal quand on désire de la précision avec des nombres flottants, mais tout comme la mémoire d'un ordinateur, la précision d'un nombre flottant n'est pas infinie, par exemple 1/3 est infini.

Les nombres entiers n'ont pour seul limite que l'espace mémoire que le systeme veut bien accorder au processus Python (2 Go maximum pour un Python en 32 bits et la totalité de la mémoire disponible pour un 64 bits).

Si tu veux savoir si un nombre entier est divisible par un autre, utilise le modulo (comme tu le fais dans ton code isPrime). Il donne le reste de la division euclidienne (division entière) :

reste = nombre % 2
if reste == 0:
    print(nombre, 'est paire (divisible par 2).')
else:
    print(nombre, 'est impaire.')

celthon a écrit:

Ce sont les nombres flottants qui sont limités et l'opérateur de division flottante convertie les opérandes en nombres flottants, ce qui peut fausser le résultat. C'est pour ça que l'on conseil d'utiliser le module decimal quand on désire de la précision avec des nombres flottants, mais tout comme la mémoire d'un ordinateur, la précision d'un nombre flottant n'est pas infinie, par exemple 1/3 est infini.

Les nombres entiers n'ont pour seul limite que l'espace mémoire que le systeme veut bien accorder au processus Python (2 Go maximum pour un Python en 32 bits et la totalité de la mémoire disponible pour un 64 bits).

Si tu veux savoir si un nombre entier est divisible par un autre, utilise le modulo (comme tu le fais dans ton code isPrime). Il donne le reste de la division euclidienne (division entière) :

reste = nombre % 2
if reste == 0:
    print(nombre, 'est paire (divisible par 2).')
else:
    print(nombre, 'est impaire.')

Donc en théorie, ce code tel qu'il est est censé me renvoyer un résultat correct, étant donné que je ne travaille qu'avec des entiers ? Et je n'aurai donc pas besoin de module supplémentaire pour travailler avec des nombres encore plus grands ?

Il n'y a pas d’approximation avec les nombres entiers. Mais, quand il s'agit de chercher de très grands nombres premiers, on est obligé d'utiliser des algorithmes probabilistes (voir l'algorithme de Miller-Rabin), qui rend les résultats plus incertains...

En Python l'algorithme déterministe de base (pour ne pas dire naïf) est celui-ci :

from math import ceil
from math import sqrt

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True:
    if not n % 2:
        return False
    for x in range(3, ceil(sqrt(n)), 2):
        if not n % x:
            return False
    return True

Il donnera un résultat sûr à 100%, mais plus les nombres premiers seront grand et plus il sera long, très long.

Il y a eu dernièrement un sujet sur les algorithmes de décomposition en facteurs premiers. Pour synthétiser, voici l'implémentation qui s'est trouvée être la plus rapide entre les 3 proposées:

def primeFactors(n):
    Decomp = []
    # 1 n'a pas de décomposition non plus parce que 1 n'est pas premier.
    if n <= 1:
        return Decomp
    # Tant que notre nombre est divisible par 2 (le dernier bit du nombre est un 0 <=> le nombre est divisible par 2):
    while not n & 1:
        Decomp.append(2)
        # Décaler sur la droite de 1 bit revient à diviser (division entière) par 2
        n >>= 1
     
    # Maintenant on est sur que notre nombre n'est pas divisible par 2 donc on n'a plus qu'à tester les nombres impairs:
    k = 3
    while n != 1:
        while not n%k:
            Decomp.append(k)
            n //= k
        k += 2
    # Ici on a trouvé tous les facteurs premiers, donc on retourne:
    return Decomp

Elle traite des nombres arbitrairement grands (tests effectués avec \( 10^{4096}\), soit un nombre à plus de 4000 chiffres), mais c'est un algorithme déterministe, donc à partir du moment où tu traites des nombres avec des facteurs premiers plutôt grands tu auras un temps d'exécution d'autant plus grand...

Sinon du côté des algorithmes non-déterministes, comme l'a dit celthon, l'algorithme de Miller-Rabin est le plus répandu car facile à implémenter et plutôt efficace.

BunshinKage a écrit:

Donc en théorie, ce code tel qu'il est est censé me renvoyer un résultat correct, étant donné que je ne travaille qu'avec des entiers ? Et je n'aurai donc pas besoin de module supplémentaire pour travailler avec des nombres encore plus grands ?

Python intègre par défaut des entiers de taille quelconque. Comme les opérations sur les entiers sont exactes, tu n'as pas à t'inquiéter de la précision des résultats, peut-importe leur ordre de grandeur. Par contre le temps d'exécution risque d'être un problème

PS:

n = 6483
if not n&1:
    # Equivalent n%2==0
    # Mais plus optimisé

Les opérateurs binaires ne sont pas assez performants en Python pour que leur utilisation soit réellement pertinente, en tout cas pas avec cet algorithme.

SI tu bases tes testes sur des puissance de 10, forcément il sera très légèrement plus rapide qu'un algorithme utilisant le modulo. En revanche si tu le testes avec un nombre premier, tu vas vite te rendre compte que... la vérité est ailleurs.

from math import ceil
from math import sqrt


def prime_factors(n):
    ls = []
    while not n % 2:
        ls.append(2)
        n //= 2
    x, m = 3, ceil(sqrt(n))
    while n != 1:
        while not n % x:
            ls.append(x)
            n //= x
            m = ceil(sqrt(n))
        x += 2
        if x > m:
            ls.append(n)
            break
    return ls

-
Edité par Anonyme 25 décembre 2015 à 13:09:41

celthon a écrit:

Les opérateurs binaires ne sont pas assez performants en Python pour que leur utilisation soit réellement pertinente, en tout cas pas avec cet algorithme.

Leur utilisation n'est peut-être pas totalement justifiable je te l'accorde car le gain apporté par l'introduction de ces opérateurs est négligeable par rapport à la perte d'expressivité du code. Néanmoins si tu recherches vraiment les performances, sans pour autant t'embêter avec des codes C (et tout le fatras pour l'introduire dans du Python), c'est une optimisation très simple et rapide à faire.

celthon a écrit:

SI tu bases tes testes sur des puissance de 10, forcément il sera très légèrement plus rapide qu'un algorithme utilisant le modulo. En revanche si tu le testes avec un nombre premier, tu vas vite te rendre compte que... la vérité est ailleurs.

from math import ceil
from math import sqrt


def prime_factors(n):
    ls = []
    while not n % 2:
        ls.append(2)
        n //= 2
    x, m = 3, ceil(sqrt(n))
    while n != 1:
        while not n % x:
            ls.append(x)
            n //= x
            m = ceil(sqrt(n))
        x += 2
        if x > m:
            ls.append(n)
            break
    return ls

Bien vu! Voici les points que j'ai pu remarquer:

• Ton algorithme ne marche pas pour de très grands entiers. La fonction sqrt attend en entrée un nombre flottant. Donc si tu passes en entrée un nombre du style \( 10^{512} \), ta fonction plante. Mais bon, c'est un choix d'implémentation tout à fait acceptable vu les performances
• Par contre le fait d'introduire la borne en cas de grand nombre premiers dans la décomposition... c'est une super idée C'est très efficace et je n'avais pas pensé au cas des grands nombres premiers dans la décomposition

Du coup je vais changer mon algorithme de décomposition en facteurs premiers en faisant un petit mix entre ton algorithme et le mien