Comparaison de grands nombre avec fonction ln

[Robic]

Je m'étais donné un petit TP à faire en Python pour utiliser les listes et les fonctions : calculer la liste des nombres premiers de 2 à un nombre donné. Voici le programme (j'ai fait quelques essais, ça a l'air juste) :

Code: Tout sélectionner

# Calcul de la liste des nombres premiers de 2 à un nombre donné

from math import sqrt

def prem( n ) :      # teste la primalité de n
   stop = int( sqrt( 1.*n ))
   a = True          # vrai si n est premier
   i = 1             # n° dans la liste - on commence à liste[1] = 3
   p = 3             # premier diviseur premier potentiel à tester
   while (a & (p <= stop)) :
      if ( n%p == 0 ) :
         a = False   # on a trouvé un diviseur premier
      i += 1
      p = liste[ i ] # diviseur premier potentiel suivant
   return a

print('N = ', end='')
nfin = int( input() )
liste = [2]          # initialisation de la liste des nombres premiers
k = 3                # on va parcourir de 3 à nfin
while (k <= nfin) :
   if prem( k ) :
      liste.append( k )
   k += 2
print('Liste des nombres premiers :', liste)


Remarques :
- j'ai utilisé une liste, bien adaptée au problème puisqu'on construit pas à pas la liste des nombres premiers ;
- ainsi qu'une fonction pour tester la primalité ;
- laquelle renvoie un booléen, d'où le test « if prem( k ) » ;
- la liste des nombres premiers est une variable globale et peut donc être utilisée dans la fonction, ainsi le test de primalité utilise les nombres premiers précédemment trouvés (on ne perd pas de temps à tester des diviseurs non-premiers).

[paquito]

Bonsoir Robic,

j'ai fait ça sur TI 82, la calculatrice des lycéens: il faut être maso pour faire ça et enfin ça ne sert à rien!
Plusieurs minutes pour P 100 et pour P1000, je n'ai pas chronométré,je me suis endormi avant!Sinon, on trouve un algorithme (pas facile)qui tient la route, mais la TI que j'ai est la même que celle que j'avais il y a 20 ans, le microprocesseur est le même et si on veut simuler une expérience aléatoire et qu'on fait N=100 000, ça va durer au moins 2 jours alors qu 'Algobox fait ça en 2 secondes. si tu veux l'algorithme, pas de problème: par contre, je veux bien des tuyaux sur le langage Python. Merci! :ptdr:

[Robic]

Argh, les calculatrices n'ont donc pas évolué ? :doh:

[chombier]

bien d'accord avec toi ....

un langage souple et puissant ... vive la liberté ...

Un langage qui ne gère malheureusement pas la récursivité terminale (http://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale)
Un langage où a=0, selon les cas, modifiera la valeur d'une variable a déjà définie ou créera une nouvelle variable.

En python True+True=2... :ptdr:

C'est un bon langage de prototypage, ou pour programmer un petit truc vite fait, c'est tout.

http://sucre.syntaxique.fr/doku.php?id=python

/HS

[Robic]

ou pour programmer un petit truc vite fait

Tout à fait, et c'est justement de cela qu'on parle (s'en servir pour s'initier à la programmation au lycée plutôt qu'utiliser une calculatrice).

Je le trouve moi aussi souple (en tout cas à mon niveau - faire de petits programmes) et puissant (on peut calculer 2015 ! directement).

Quant à True + True, c'est de toute façon une opération qui me paraît stupide (si on veut faire "ou", on utilise "ou").

[chombier]

Tout à fait, et c'est justement de cela qu'on parle (s'en servir pour s'initier à la programmation au lycée plutôt qu'utiliser une calculatrice).

Je le trouve moi aussi souple (en tout cas à mon niveau - faire de petits programmes) et puissant (on peut calculer 2015 ! directement).

Quant à True + True, c'est de toute façon une opération qui me paraît stupide (si on veut faire "ou", on utilise "ou").

Ce qui est stupide c'est que l'interprete Python ne renvoie pas une erreur. Que le langage soit peu typé, ok, mais de là à ce qu'il autorise l'addition de deux booleens...

Évidemment si on lit "true + true" dans un programme, c'est stupide, mais si on lit a=b+c, que b est entier et c un booléen, on aimerait bien que l'interprete Python prévienne le programmeur qu'il a sans doute fait une bêtise.

[Robic]

OK, je vois ce que tu veux dire. Comme c'est le genre de reproche qu'on fait aussi au langage C (par exemple si on écrit « if (x=2) » le compilateur ne détecte aucune erreur : ah, le type veut tester si l'affectation x=2 retourne 1, ben non, elle retourne 2) j'en conclus que tous les langages ont les défauts de leurs qualités.

[chombier]

OK, je vois ce que tu veux dire. Comme c'est le genre de reproche qu'on fait aussi au langage C (par exemple si on écrit « if (x=2) » le compilateur ne détecte aucune erreur : ah, le type veut tester si l'affectation x=2 retourne 1, ben non, elle retourne 2) j'en conclus que tous les langages ont les défauts de leurs qualités.

Oui, le C a ses défauts aussi, mais ce que je reproche le plus à python personnellement c'est qu'il ne gère pas la récursivité terminale.

Exemple d'un programme qui calcule f(a, n) = a * n!

Méthode 1 (itérative) :

Code: Tout sélectionner

def f(a, n) :
  r := a
  Pour i variant de 1 à n faire :
    r := r * i
  Renvoyer r

Méthode 2 : (récursive)

Code: Tout sélectionner

def f(a, n) :
  si n<=1
    renvoyer a
  sinon
    renvoyer f(a*n, n-1)

Python, avec la deuxième méthode, ne saura pas calculer 1002! = f(1, 1002)
- Parce qu'il ne gère pas la récursivité terminale
- Parce que la pile d'appel est limitée à 1000 appels imbriqués

Cette deuxième méthode est pourtant, pour un matheux, beaucoup plus intuitive. Et elle a la beauté d'un langage procédural, il n'y a pas d'affectation ni de boucle.
Elle utilise simplement le fait que :
si n<=1, f(a, n) = a * n! = a*1 = a
sinon f(a,n) = a * n! = a * n * (n-1) ! = f(a*n, n-1)

Et c'est beau

[nodjim]

Sur ma calculette, si j'écris un nombre à 11 chiffres, divisé par 3, on me renvoie un entier systématiquement.
111 111 111 11/3=3703703703
111 111 111 12/3=3703703703
111 111 111 13/3=3703703703
111 111 111 14/3=3703703703
....

[Robic]

Personnellement je ne suis pas fan de récursivité. Je me considère pourtant comme matheux, mais j'ai l'impression de ne pas maîtriser le truc. En fait, je soupçonne que ça prend plus de temps ou plus de mémoire à se mettre en place. L'ordinateur gère une pile et passe son temps à créer des variables locales puis à les détruire, ça me paraît être une sacré machine à gaz à côté d'une simple itération. L'autre défaut, c'est que l'écriture plus concise me paraît plus difficile à lire. C'est peut être une question d'habitude, mais si on me donne un programme en me disant « devine ce qu'il calcule », j'ai l'impression que j'aurais plus de mal s'il est récursif.

[takezo]

Bonjour,

Non, votre doyen n'est pas un C84, c'est probablement moi : ME66...
Et en ce temps-là, j'avais 9 h de maths par semaine et 5 h 30 de Physique-Chimie, de quoi faire saliver bien des "jeunots"...

Bon, passons...

Alors, moi non plus je n'aime pas trop la récursivité ...

Python, avec la deuxième méthode, ne saura pas calculer 1002! = f(1, 1002)
- Parce qu'il ne gère pas la récursivité terminale
- Parce que la pile d'appel est limitée à 1000 appels imbriqués

"Why is tail recursion optimisation not implemented in languages like Python, Ruby, and Clojure? Is it just difficult or impossible ?" Lien :
http://www.quora.com/Why-is-tail-recursion-optimisation-not-implemented-in-languages-like-Python-Ruby-and-Clojure-Is-it-just-difficult-or-impossible

MAIS :

Code: Tout sélectionner

def f(a,n):
    if n<=1:
        return a
    else:
        return f(a*n,n-1)

print (f(5,1966))

Et je vous fais grâce des 5625 chiffres de la réponse (à la louche 1 s de calcul). :zen:
Bien sûr, je cache quelque chose (deux lignes)...
Quelqu'un veut-il savoir quoi ?

Deux atouts de Python parmi d'autres :
* la taille des nombres entiers ne dépend "que" de la quantité de RAM disponible.
En tablant là dessus, et en "rusant", je peux calculer le nombre d'or avec 20000 (oui, vingt mille) décimales en une quinzaine de secondes... Bon, d'accord, ça ne sert à rien ! :lol3:
* il dispose en natif d'un module nommé "decimal" qui permet - notamment - de préciser le nombre de décimales souhaité dans un calcul. Bien sûr, il y a ralentissement... Bien sûr, il est exclu de réaliser la même chose qu'au point précédent...

je veux bien des tuyaux sur le langage Python.

Volontiers (même si la demande ne m'étais pas adressée - et pour cause ! -), comme quoi par exemple ? Mais il faudrait ouvrir une autre discussion, parce que je contribue à faire dévier la discussion de son sujet originel...

Bye

[zygomatique]

je ne pensais pas que ça allait délirer autant sur le sujet (dans le bon sens bien sur) ....


j'avoue que je ne connais pas très bien tous ces nouveaux langages ... mais il semble donc que ça n'est guère mieux que si c'était plus pire ... :ptdr:

avec les progrès de ces 20 dernières années ben je trouve que c'est bien triste ... mais que signifie le mot progrès ....



pour en revenir à al récursivité ... et bien c'est beau, bref, concis ....

elle s'applique naturellement à tous les produits du modèle factorielle ... mais plus généralement à par exemple toutes les sommes où f est une fonction

puisque

et moi je veux pouvoir faire cela sans m'occuper de la pile , ou la face ou je ne sais quoi d'autre ... mais si à 1000 ça stoppe ... ben mede alors !!!!

que un coup ça me sorte peut-être un "memory overflow" parce que je pousse un peu trop ok ... j'accepte bien ...

mais donc il semble bien qu'on n'est pas fait avancé réellement le schmilblick ...(enfin j'exagère un peu)

en arrivant à la fac on était en plein dans TURBOPASCAL que je trouvais très pédagogique car très rigoureux et structuré .... avec tout de même ce défaut de déclaration de variable très lourd ...

mais si on n'a plus de déclaration de variable mais que le langage "ne reconnaît" pas true + true c'est un peu dommage ....



à Robic ::: il me semble qu'il faudrait commencer à tester la divisibilité par 2 et non par 3 pour éliminer tout nombre pair ... ?


un modeste et humble programmeur ....

:lol3:

[Robic]

à Robic ::: il me semble qu'il faudrait commencer à tester la divisibilité par 2 et non par 3 pour éliminer tout nombre pair ... ?

Pas besoin car je ne parcours pas les nombres pairs. Quand j'ai initialisé la liste des nombres premiers, j'ai mis 2 dedans. Du coup il n'y a plus besoin de tester les autres nombres pairs, aussi ma boucle principale va de 3 à Nfin en incrémentant de 2 en 2 : je teste 3, 5, 7, 9, etc.

Code: Tout sélectionner

k = 3                # on va parcourir 3, 5, 7, 9, etc. jusque nfin
while (k <= nfin) :
   if prem( k ) :
      liste.append( k )
   k += 2            # on passe au nombre impair suivant

[takezo]

Voilà pour prouver que je plaisante pas :

Code: Tout sélectionner

#!/usr/bin/env python
# -*- coding: UTF8 -*-

from time import process_time

def rac5(prc):
    reste,md,finbcl,L=100,4,prc+1,["2"]
    for j in range(finbcl):
        md=10*md
        i=5*(1-((md+5)*5>reste))
        while (md+i)*i>> print (True+True)
2
>>>

D'autre part, quand j'écris :
i=5*(1-((md+5)*5>reste)) j'utilise bien True et False :
(md+5)*5>reste est soit True, soit False, et True et False sont automatiquement remplacés selon le cas par 1 ou 0 et le calcul effectué...
Précision : l'algorithme d'extraction de la racine carrée de 5 est basé sur la méthode de calcul à la main que j'ai apprise en classe de 4e et que bien peu de nouveaux profs connaissent...

Et voilà les 2 lignes que j'avais gardées cachées :

Code: Tout sélectionner

from sys import setrecursionlimit
setrecursionlimit(100000)

[paquito]

Si on utilise un programme qui reconnait un nombre premier, il n'y a rien à faire! Aucun intérêt!Restons dans le cadre lycée!
Ces langages sont à placer dans le supérieur d'une part et d'autre part c'est trop facile; il n'y a pas de quoi se vanter.

[Robic]

Paquito : si tu parles de mon programme (celui de Takezo calcule des racines carrées avec plein de décimales), il utilise une fonction qui reconnaît les nombres premiers, mais c'est moi qui ai écrit cette fonction, bien sûr (c'était le but du jeu). Je pense que c'est ambitieux mais faisable en terminale par des élèves ayant vu tout le cours d'arithmétique, du moins ceux qui ont déjà une petite habitude de la programmation (et qui en ont le goût).

[chombier]

Personnellement je ne suis pas fan de récursivité. Je me considère pourtant comme matheux, mais j'ai l'impression de ne pas maîtriser le truc. En fait, je soupçonne que ça prend plus de temps ou plus de mémoire à se mettre en place. L'ordinateur gère une pile et passe son temps à créer des variables locales puis à les détruire, ça me paraît être une sacré machine à gaz à côté d'une simple itération. L'autre défaut, c'est que l'écriture plus concise me paraît plus difficile à lire. C'est peut être une question d'habitude, mais si on me donne un programme en me disant « devine ce qu'il calcule », j'ai l'impression que j'aurais plus de mal s'il est récursif.

C'est une grave erreur, un langage qui gère la récursivité terminale gerera récursion, dans le cas où c'est le dernier appel de la fonction exactement comme une boucle et la pile d'appel ne grandira pas.

C'est pourquoi une fonction comme celle ci :

Code: Tout sélectionner

def f(n)
  afficher n
  f(n+1)   ;;ceci est un appel récursif terminal

f(0)

va s'arrêter à 1000 en python (car la pile d'appel est pleine) mais tournera ad vitam aeternam dans un vrai langage.

D'autre part, quand on a l'habitude, la récursion est bien plus claire. On n'a plus à se demander "dois-je incrémenter ici avant ou après telle instruction", "au fait, la boucle s'arrête-t-elle à n, n-1 ou n+1" ou "et cette variable, sa valeur a-t-elle changé ou pas ?". Il n'y a pas non plus de choses pas très belles comme "a := a * 7 + 10"

Les vrais langages, les langages fonctionnel, permettent aussi de manipuler les fonction comme des objets (tout comme en maths on se permet de faire f+g ou f o g). Et ainsi on peut faire une fonction qui calcule le nième terme d'une suite définie par récurrence et qui marche pour n'importe quelle suite :

nieme(u0, f, n) :
si n=0 alors
retourner u0
sinon
retourner nieme(f(u0), f, n-1) ; ceci est un appel récursif terminal

nieme(1, x->2x, 10) --> 1024
nieme(0, x+7, 10) --> 70

Exercice cadeau : que calcules ce code, sachant que u est une suite numérique ?

Code: Tout sélectionner

def devine(a, u, n)
  if n=0 then
    return a
  else
    return devine(a+u(n), u, n-1)   ; ceci est un appel récursif terminale

devine(777, u, 10)


[Robic]

Ah OK, le défaut que je prêtais à la récursivité n'est pas présent avec la récursivité terminale, que justement le langage Python ne gère pas.

Concernant le code surprise, n'y aurait-il pas une erreur dans cette ligne :

Code: Tout sélectionner

return devine(a+u(n), n-1)

--> il manque un paramètre.

[chombier]

D'autre part, quand j'écris :
i=5*(1-((md+5)*5>reste)) j'utilise bien True et False :

C'est horrible ce code !! La dernière version de python a ENFIN ajouté un opérateur ternaire :

python : "a if condition else b"

En C, en 1970, ça existait déjà, ça s'écrivait : "condition?a:b"

Je t'invite à modifier ton code "5*(1-((md+5)*5>reste))" par "0 if (md+5)*5>reste else 5"

Ce sera beaucoup plus lisible

[chombier]

Ah OK, le défaut que je prêtais à la récursivité n'est pas présent avec la récursivité terminale, que justement le langage Python ne gère pas.

Concernant le code surprise, n'y aurait-il pas une erreur dans cette ligne :

Code: Tout sélectionner

return devine(a+u(n), n-1)

--> il manque un paramètre.

Exact, j'ai corrigé !

Un autre, avec une fonction interne (loop) et une fonction anonyme (x->x^2) :

La fonction interne a une double fonction :
- permettre de ne pas repasser "u" à chaque appel
- assurer la récursion terminale
le "a" est un accumulateur

Code: Tout sélectionner

def devine2(u, n) :
  def loop(a, n) :
    si n = 0 alors
      retourner a
    sinon
      retourner loop(a+u(n), n-1)
  loop(0, n)

devine2(x->x^2, 5)