π
<-
Chat plein-écran
[^]

Le classement des Pythonnettes : la récursivité

Le classement des Pythonnettes : la récursivité

Message non lude critor » 31 Jan 2019, 21:56

A la rentrée 2019 le Python sera le seul langage de programmation préconisé pour l'enseignement de l'algorithmique au lycée en Seconde et Première.

Plusieurs calculatrices graphiques intègrent déjà une implémentation Python officielle dans leur dernière mise à jour, plus ou moins complète, fidèle et réussie selon le cas :
  • NumWorks avec MicroPython 1.9.4
  • Casio Graph 90+E avec MicroPython 1.9.4
  • HP Prime avec l'écriture Python de Xcas
  • le module externe TI-Python pour TI-83 Premium CE avec CircuitPython (dérivé de MicroPython)
À côté de cela nous avons aussi plusieurs implémentations communautaires, qui à la différence ne fonctionneront pas en mode examen en 2020 :

Ces diverses implémentations ne sont toutefois pas équivalentes.

C'est notamment le cas pour les fonctions récursives (fonctions qui se rappellent dans leur propre code), où certaines "Pythonnettes" nous avaient paru assez mauvaises.

Aujourd'hui, creusons donc les possibilités de nos Pythonnettes en récursivité à l'aide du script suivant :
Code: Tout sélectionner
def prodr(n):
  if n<=0:
    return 1
  else:
    return n*prodr(n-1)

def maxr(fct):
  n=0
  try:
    while True:
      fct(n)
      n=n+1
  except Exception as ex:
    print(ex)
  return n

La fonction prodr(n) effectue ici récursivement le produits des facteurs 1 à n, c'est la fonction factorielle.

La fonction maxr(fct) va appeler fct(n) avec des valeurs de n croissantes jusqu'à déclenchement d'une erreur, et nous indiquer alors la description de l'erreur et la profondeur de récursion atteinte.

Sur TI-Nspire l'appel maxr(prodr) atteint une profondeur de 130 avant de nous renvoyer l'erreur "maximum recursion depth exceeded". La profondeur maximum spécifiée lors de la compilation de l'interpréteur Python a donc ici été atteinte, impossible d'aller plus loin.

10209La calculatrice NumWorks quant à elle déclenche la même erreur à seulement 27 niveaux de profondeur.

Mais sur la version web de la calculatrice NumWorks ce n'est particulièrement pas joyeux, avec une limite à seulement 10 niveaux de récursion.

Sur Casio Graph 90+E, le script atteint une profondeur de 82 mais en renvoyant une erreur différente, "pystack exhausted", et la limitation n'a donc pas la même raison technique.

Avec l'application KhiCAS, la Graph 90+E fait un peu mieux avec une profondeur de 98. Mais ici la gestion de l'instruction except semble apparemment incomplète puisque la variable ex n'est pas affectée avec le message d'erreur.

La HP Prime qui utilise elle aussi un portage de GIAC, cœur du logiciel Xcas, atteint également une profondeur de récursivité de 98. Nuance toutefois, ici elle continue au-delà mais nous avertissant avec le message "Exécution en mode d'évaluation non récursive". Il semble donc que la calculatrice optimise le code en convertissant les appels récursifs en itératif au-delà de 98 niveaux de profondeur.

Si cela n'a pas été corrigé depuis octobre dernier, le module externe TI-Python pour TI-83 Premium CE que les types de base, soit les flottants uniquement en simple précision, et également les entiers uniquement courts, soit jusqu’à
$mathjax$2^{30}-1=1073741823$mathjax$
. La fonction factorielle produisant rapidement de longs entiers, l'appel maxr(prodr) devrait nous renvoyer :
TI-Python a écrit:>>> from recur import *
>>> maxr(prodr)
small int overflow
13
>>>

Mais ici la limite n'a donc rien à voir avec le fonctionnement de la récursivité. Afin de mieux évaluée ce dernier, contentons-nous donc plutôt de la somme récursive des termes de 0 à n :
Code: Tout sélectionner
def sumr(n):
  if n<=0:
    return 0
  else:
    return n+sumr(n-1)

L'appel maxr(sumr) devrait alors nous renvoyer :
TI-Python a écrit:>>> from recur import *
>>> maxr(sumr)
max recursion depth exceeded
21
>>>

L'application CasioPython sur Graph 35+E/75+E et anciens modèles Graph 35+USB/75/95 à processeur SH4 nous atteint des sommets avec l'appel maxr(prodr), plus exactement 674 de profondeur ! L’ascension est ici avortée par l'erreur "memory allocation failed, allocating 672 bytes".

Mais là encore, si c'est une limite de mémoire cela n'a rien à voir spécifiquement avec la récursivité. Passons donc à l'autre fonction qui mettra beaucoup plus de temps avant d'arriver sur des entiers longs, et consommera donc beaucoup moins de mémoire.

Extraordinaire, l'appel maxr(sumr) atteint maintenant une profondeur de 5351. Le message d'erreur "maximum recursion depth exceeded" nous confirme bien cette fois-ci qu'il s'agit de la limite finale.

Toutefois, si l'on installe l'application CasioPython sur les premières Casio Graph 35+USB/75/95 à processeur SH3 ainsi que sur les Graph 85, les résultats sont différents. maxr(prodr) n'atteint que 213 de profondeur avec l'erreur "memory allocation failed, allocating 170 bytes".

Et avec maxr(sumr) l'erreur "maximum recursion depth exceeded" se déclenche à seulement 644 de profondeur.

L'explication de la différence en est simple. Depuis la version 1.6, CasioPython dispose d'un nouveau code d'allocation mémoire lui permettant d'exploiter 256Kio au lieu de 32Kio. Mais hélas, pour le moment ce code n'est activé que sur les machines à processeur SH4, alors que les anciennes calculatrices à processeur SH3 disposaient pourtant déjà de ces mêmes 256Kio.

Petit classement donc de nos Pythonnettes basée sur la profondeur maximale de récursion :
  1. application CasioPython sur Casio Graph 35+E/75+E et Graph 35+USB/75/95 à processeur SH4 avec 5351
  2. application CasioPython sur Casio Graph 35+USB/75/95 à processeur SH3 et Graph 85 avec 644
  3. TI-Nspire avec 130
  4. HP Prime avec 98 (conversion automatique en itératif au-delà)
  5. application KhiCAS sur Casio Graph 90+E avec 98
  6. Casio Graph 90+E avec 82
  7. NumWorks avec 27
  8. module externe TI-Python pour TI-83 Premium CE avec 21
  9. NumWorks pour navigateur avec 10
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Le classement des Pythonnettes : la récursivité

Message non lude Lephe » 31 Jan 2019, 22:07

J'ai découvert à la tournée pédagogique que les Graph 90+E avec Python avaient plus de tas, essentiellement 3 Mo au lieu de 128 ko. Il n'est pas impossible que la pile soit affectée aussi.

Peux-tu visiter le menu constructeur de ta Graph 90+E et indiquer ce que tu as as sans la section Heap/Stack Remain ? :)
Avatar de l’utilisateur
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Prochain niv.: 67.7%
 
Messages: 386
Inscription: 15 Juin 2018, 19:53
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Le classement des Pythonnettes : la récursivité

Message non lude Noury » 31 Jan 2019, 22:09

Très intéressant.
J'ai essayé sur un Mac en python3, le max est de 997.
Bravo donc pour la Casio qui atteint 5351 !
Avatar de l’utilisateur
NouryVIP++
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Prochain niv.: 52.5%
 
Messages: 287
Inscription: 07 Sep 2018, 09:19
Localisation: Sceaux, France 92
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Le classement des Pythonnettes : la récursivité

Message non lude critor » 31 Jan 2019, 22:15

Oui. Tu te souviens à peu près dans lequel des nombreux menus de l'écran en question ça se trouve ?
Merci.
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Le classement des Pythonnettes : la récursivité

Message non lude critor » 31 Jan 2019, 22:25

Désolé, mal compris.

Je cherchais dans le menu de diagnostics, or ce que tu décris est dans l'autre menu secret, le menu de tests 5963.

Bref, voici :
10210
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Le classement des Pythonnettes : la récursivité

Message non lude darthvader » 01 Fév 2019, 01:58

Hello critor ;)
petite faute de frappe ici :
CasioPython dispose d'un noveau code d'allocution mémoire lui permettant lui permettant d'exploiter 256Kio
La théorie c'est quand on sait tout et que rien ne fonctionne ,
La pratique c'est quand tout fonctionne et que personne ne sait pourquoi ;)
Avatar de l’utilisateur
darthvaderVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 45.5%
 
Messages: 45
Images: 0
Inscription: 06 Déc 2011, 19:53
Localisation: Moselle
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: R&D robotique
YouTube: darthphysics

En ligne

Re: Le classement des Pythonnettes : la récursivité

Message non lude parisse » 01 Fév 2019, 18:30

critor a écrit:Désolé, mal compris.

Je cherchais dans le menu de diagnostics, or ce que tu décris est dans l'autre menu secret, le menu de tests 5963.

Comment on accede a ce menu? La je lis 128K ce qui correspond a l'ordre de grandeur de la memoire a laquelle j'accede avec le malloc systeme avec KhiCAS. S'il est possible d'acceder de maniere robuste a plus, ca serait evidemment interessant (j'avais essaye un malloc maison, mais ce n'etait pas robuste, j'ai laisse tomber puisque le malloc systeme suffit pour faire des calculs normaux).
Sinon, sur la Prime, quand on depasse la limite du nombre d'appels recursifs, l'evaluateur non recursif est appele, ce qui est plus lent et necessite des ressources dans le tas, pas de problemes sur la pile mais pas sur la Casio.
Avatar de l’utilisateur
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 77.1%
 
Messages: 3497
Inscription: 13 Déc 2013, 16:35
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Le classement des Pythonnettes : la récursivité

Message non lude critor » 01 Fév 2019, 19:03

parisse a écrit:Comment on accede a ce menu?

Voici la procédure valable pour toutes les Casio Graph USB/SH3/SH4 à ma connaissance, ainsi que leurs équivalents internationaux.

Je conseille de lire jusqu'au bout, car il y a un timeout. Si on met trop de temps à faire certaines manipulations, il faudra recommencer au début.

  1. éteindre la calculatrice
  2. maintenir les 2 touches
    OPTN
    et
    x10^x

    (ou
    OPTN
    et
    EXP
    si le clavier n'est pas francisé)
  3. sans relâcher ces 2 touches, maintenir la touche
    AC/ON
  4. la calculatrice doit s'allumer et afficher un popup :
    =DIAGNOSTIC MODE=
    Factory Use only!"
  5. relâcher alors rapidement les 3 touches
  6. puis au choix, rapidement :
    • taper
      F1
      puis
      9
      pour le menu de diagnostics
    • taper
      5
      puis
      9
      puis
      6
      puis
      3
      pour le menu de tests
      (besoin peut-être de taper alors
      EXIT
      si la touche
      3
      a été maintenue trop longtemps et a déjà validé le choix n°3)

Dans les deux cas il n'y a rien de dangereux à ma connaissance, pas possible de casser la calculatrice.
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

En ligne

Re: Le classement des Pythonnettes : la récursivité

Message non lude parisse » 01 Fév 2019, 20:18

Merci.
J'ai bien 128K de tas. C'est quand meme dommage qu'il n'y ait pas plus...
Avatar de l’utilisateur
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 77.1%
 
Messages: 3497
Inscription: 13 Déc 2013, 16:35
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Le classement des Pythonnettes : la récursivité

Message non lude Lephe » 01 Fév 2019, 20:45

critor a écrit:Bref, voici :
10210

Tu as donc 128k, comme les anciens modèles, et non 3M comme j'avais sur la machine utilisée lors de la tournée pédagogique. C'est curieux, car j'ai immédiatement associé l'augmentation du tas avec l'arrivée de Python. On a donc deux possibilités :

  • Ou bien la mise à jour vers l'OS 3.20 n'a pas débloqué la mémoire ;
  • Ou bien elle n'est physiquement pas présente, et seules les calculatrices avec Python pré-chargé l'ont.
Note que, même si le tas de l'add-in est plus gros, ça ne veut pas forcément dire que la pile va grandir, ça dépend de ce que MicroPython choisit de faire. Par contre ton script pour calculer la quantité de mémoire disponible devrait le sentir passer.

parisse a écrit:Comment on accede a ce menu? La je lis 128K ce qui correspond a l'ordre de grandeur de la memoire a laquelle j'accede avec le malloc systeme avec KhiCAS. S'il est possible d'acceder de maniere robuste a plus, ca serait evidemment interessant (j'avais essaye un malloc maison, mais ce n'etait pas robuste, j'ai laisse tomber puisque le malloc systeme suffit pour faire des calculs normaux).

Je pense qu'il y a certaines machines qui auront 3M, mais je ne connais pas de méthode pour les distinguer depuis un add-in, à part allouer 256k et regarder si ça marche. Je ne sais pas non plus dans quel endroit de la mémoire virtuelle c'est mappé puisque je n'ai pas pu lancer d'add-in dessus pendant la tournée pédagogique !

J'espère que des détails sur ce point arriveront avec le temps. :)
Avatar de l’utilisateur
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Prochain niv.: 67.7%
 
Messages: 386
Inscription: 15 Juin 2018, 19:53
Genre: Homme
Calculatrice(s):
MyCalcs profile


Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 13 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
855 utilisateurs:
>845 invités
>5 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)