Test de carré et cube...

[Vertforever]

Bonjour,
Je me pose le problème suivant :

Dans les exos sur Python/maths apparaissent de nombreuses questions revenant à tester si un nombre entier est un carré ou un cube.

Depuis un certain temps je faisais comme je l'ai vu dans des corrigés :

int(sqrt(n))==sqrt(n)

qui me laissait un petit gout amer mais bon cela marchait.

Ensuite j'ai eu à le faire pour des cubes et là : problème car

64**(1/3)=3.999999999999997

.

On peut rusé et mettre un

round(n**(1/3))**3==n

qui semble bien marcher.

Néanmoins je me demande si il ne faudrait pas rester dans le type entier pour toutes ces questions et tester avec une boucle :

for k in range(0,n):
if k**2==n:
return True
return False

Qu'en pensez vous ?

[darklol]

Alors le problème de ta solution avec une boucle c'est que pour un entier $ n $, tu vas effectuer dans le pire cas $ n $ multiplications et $ n $ comparaisons (pire cas atteint si $ n $ n'est pas un carré). Et même dans le meilleur cas, ce sera de l'ordre de $ \sqrt n $ multiplications et comparaisons. Pour un très grand entier, c'est inacceptable en pratique.

La solution:

Code : Tout sélectionner

round(n**(1/3))**3==n

est la meilleure. En effet, à supposer que tu puisses obtenir la racine k-ième d'un nombre $ n $ avec une précision strictement meilleure que 0.5, alors tu es sûr que l'expression

Code : Tout sélectionner

round(n**(1/k))**k==n

sera évaluée à vrai si et seulement si $ n $ est une puissance k-ième.

Or, calculer la racine k-ième d'un entier $ n $ peut se faire par exemple avec la méthode de Newton, et on peut alors s'assurer que cette méthode permet d'obtenir une précision strictement meilleure que 0.5 très vite. Quoi qu'il en soit, tu peux être sûr qu'en pratique, la fonction **(1/k) de Python te donnera toujours une précision strictement meilleure que 0.5.

[Vertforever]

Oui, merci cela me déculpabilise un peu
mais cela ne semble pas très moral de tabler sur le fait que Python va faire les bons calculs, sachant que 0.3-0.1*3==0 donne False

On peut quand même avoir des beaux écarts :
In [25]: n=12345678910111213**5
In [26]: round(n**(1/5))
Out[26]: 12345678910111238

[darklol]

En effet dans ce cas, il faudrait utiliser une fonction qui te permette de calculer à une précision meilleure que 0.5 dans tous les cas. Tu peux écrire la tienne, basée sur la méthode de Newton (autre possibilité: une dichotomie). J'ai vérifié, et il n'y a en effet pas de fonction builtin qui permette de calculer la racine k-ième d'un entier avec une précision arbitraire, je m'attendais à mieux de la part de Python...

[bullquies]

au pire tu fais par dichotomie... ça fera au grand maximum log2(n) tentatives.

grillé

[left_shift]

Si tu veux manipuler des entiers aussi grands, il faut impérativement proscrire l'usage du type float puisque la conversion int -> float induit une perte irrémédiable de précision. Dans ce cas, plutôt qu'une dichotomie, une méthode de Newton est préférable car plus rapide (ou mieux encore, débuter par une dichotomie et finir par la méthode de Newton).

Plus exactement, il faut remplacer la division présente dans la méthode de Newton par une division euclidienne. On peut alors démontrer que si on choisit pour condition d'arrêt la condition x**n <= b on obtient une fonction qui calcule la partie entière de la racine n-ième :

Code : Tout sélectionner

def root(b, n):
    x = b
    while x**n > b:
        x = ((n-1) * x**n + b) // (n * x**(n-1))
    return x

Illustration :

Code : Tout sélectionner

In [6]: b = 123456789123456789123456789 ** 5

In [7]: root(b, 5)
Out[7]: 123456789123456789123456789

Le code ci-dessus peut être amélioré : il est facile de le modifier pour éviter par exemple de calculer deux fois x**n, mais je l'ai laissé comme ça pour en faciliter la lecture.
Une autre amélioration consiste à partir d'une valeur initiale plus proche du résultat final (plus on est proche plus la méthode de Newton est efficace). Si k est le nombre de décimales de b, on a b < 10**k donc b**(1/n) < 10**(k/n). On peut donc débuter avec x = 10**(k // n + 1) au lieu de x = b.

[fakbill]

mais cela ne semble pas très moral de tabler sur le fait que Python va faire les bons calculs, sachant que 0.3-0.1*3==0 donne False

python FAIT les BONS calculs
C'est juste qu'il ne travaille pas sur R (il aurait du mal...) mais avec d'autres nombres.
Les floatant en python sont des nombres IEEE754 https://de.wikipedia.org/wiki/IEEE_754
C'est LA norme en vigueur pour les floats (il y en a d'autres mais c'est celle là qu'on trouve un peu partout...mais pas partout partout )
Le fait qu'on ne soit pas sur R n'a rien à voir avec python. TOUS les softs qui utilisent des floats ne calculent pas sur R.
Avec ces floats, on perd presque toutes les propriétés de R:
En toute généralité:
a+b-c n'est pas égal à a-c+b
a*(b+c) n'est pas égal à a*b+a*c
a+1-1 n'est PAS égal à a
a/2.*2. n'est pas égal à a

Il faut bien voir que ce n'est PAS un problème avec python...c'est juste la façon dont les nombres sont représentés dans un CPU.
Par exemple, IEEE754 peut représenter exactement 1/5. mais pas 1/2. Pourquoi

https://docs.python.org/3/tutorial/floatingpoint.html

[left_shift]

Par exemple, IEEE754 peut représenter exactement 1/5. mais pas 1/2.

C'est plutôt le contraire

[fakbill]

Oui! je me suis emmêler les pinceaux.
0.5 c'est 2 puissance -1 donc ca admet une représentation exacte en IEE754.

[Vertforever]

Tu joues sur les mots fakbill, puisqu'il te faut une traduction :

"Python va faire les bons calculs" signifie "Python va donner la réponse attendue".

On sait très bien ce qu'est un réel.