π
<-
Chat plein-écran
[^]

fonction isprime et crible d'ératosthène

Pour le TI-Basic sur Nspire

fonction isprime et crible d'ératosthène

Message non lude kadtexas » 05 Sep 2018, 11:04

Bonjour
Je voulais savoir, si possible, si la fonction isprime(entier) est indépendante du crible d'ératosthène ou bien elle l'utilise ?
Merci pour le renseignement.
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: fonction isprime et crible d'ératosthène

Message non lude Adriweb » 05 Sep 2018, 16:41

Pas de crible ("sieve" en anglais) : d'après http://www.technicalc.org/tiplist/en/fi ... ip6_55.pdf, des détails sur l'algo utilisé sur les TI-68k donc vraisemblablement la même chose sur TI-Nspire :

[6.55] Algorithms for factor() and isPrime()

The following description of the algorithms for factor() and isPrime() was obtained from TI by Bhuvanesh Bhatt. It is included with TI's permission.

TI a écrit:The algorithms used in the TI-92, TI-92 Plus, and TI-89 are described in D. Knuth, The Art of Computer Programming, Vol 2, Addison-Wesley, but here is a brief description:

The TI-92 simply divides by successive primes through the largest one less than 2^16.1: It doesn't actually keep a table or use a sieve to create these divisors, but cyclically adds the sequence of
increments 2, 2, 4, 2, 4, 2, 4, 6, 2, 6 to generate these primes plus a few extra harmless composites.

TI-92 Plus and TI-89 start the same way, except that they stop this trial division after trial divisor 1021, then switch to a relatively fast Monte-Carlo test that determines whether the number is certainly composite or is almost certainly prime. (Even knowing the algorithm, I cannot construct a composite number that it would identify as almost certainly prime, and I believe that even centuries of continuous experiments with random inputs wouldn't produce such a number).

The isPrime() function stops at this point returning either false or (almost certainly) true.

If the number is identified as composite, the factor() function then proceeds to the Pollard Rho factorization algorithm. It is arguably the fastest algorithm for when the second largest prime factor has less than about 10 digits. There are faster algorithms for when this factor has more digits, but all known algorithms take expected time that grows exponentially with the number of digits. For example, the Pollard Rho algorithm would probably take centuries on any current computer to factor the product of two 50-digit primes. In contrast, the isPrime() function would quickly identify the number as composite.

Both the compositivity test and the Pollard Rho algorithm need to square numbers as large as their inputs, so they quit with a "Warning: ... Simplification might be incomplete." if their inputs exceed about 307 digits.
Image

MyCalcs: Help the community's calculator documentations by filling out your calculators info!
MyCalcs: Aidez la communauté à documenter les calculatrices en donnant des infos sur vos calculatrices !
Inspired-Lua.org: All about TI-Nspire Lua programming (tutorials, wiki/docs...)
Avatar de l’utilisateur
AdriwebAdmin
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Prochain niv.: 80.1%
 
Messages: 14606
Images: 1216
Inscription: 01 Juin 2007, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: adriweb
GitHub: adriweb

Re: fonction isprime et crible d'ératosthène

Message non lude kadtexas » 05 Sep 2018, 17:52

Merci pour la lecture.
Je ne pensais pas qu'il y avait tous ces algorithmes et surtout ils peuvent mettre des siècles pour factoriser un entier produit de deux nombres premiers (50 chiffres chacun).
Mon petit programme est du niveau "primaire" juste pour générer les nombres premiers entre n et m.

Code: Tout sélectionner
Define LibPub fpremiers(n,m)=
Func
:Local p
:For p,n,m
: If isPrime(p) Then
:   Disp p
: EndIf
:EndFor
:Return "ok"
:EndFunc
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: fonction isprime et crible d'ératosthène

Message non lude Bisam » 06 Sep 2018, 10:30

Il n'y a aucun rapport entre les 3 problèmes suivants :
1) Déterminer si un entier donné est premier ou non (ce que fait la fonction "isprime")
2) Déterminer la liste de tous les entiers premiers inférieurs ou égaux à un entier donné (ce que fait le crible d'Ératosthène)
3) Factoriser un entier donné.

Dans le premier cas, on connait des algorithmes très efficaces, capables de décider en quelques millièmes de secondes si des nombres de quelques centaines de chiffres sont premiers ou non.
Dans le 2ème cas, on ne connaît pas grand chose de mieux que le crible d'Ératosthène lui-même... mais il permet déjà d'établir une telle liste en quelques secondes pour des entiers ayant moins de 10 chiffres.
Dans le 3ème cas, on connaît plein d'algorithmes, la plupart étant plus ou moins efficaces suivant le champ d'application, c'est-à-dire suivant la forme des nombres auxquels on les applique. C'est un problème bien plus complexe que les deux précédents... et c'est justement sur le fait que ce soit complexe que se basent une grande partie des systèmes de cryptage.
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: fonction isprime et crible d'ératosthène

Message non lude kadtexas » 06 Sep 2018, 11:16

Merci Bisam pour tes explications.
Donc il faudra que j'applique le crible d'Ératosthène pour être en "conformité"
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: fonction isprime et crible d'ératosthène

Message non lude Bisam » 06 Sep 2018, 12:31

Tu peux sans doute utiliser ta méthode pour de petites valeurs de n et m.
Tu peux simplifier ainsi :
Code: Tout sélectionner
Define Libpub fpremiers(n, m)=
Func
Return delvoid(seq(when(isPrime(p),p,_),p,n,m))
EndFunc
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: fonction isprime et crible d'ératosthène

Message non lude Heneos » 01 Fév 2021, 12:18

Bisam a écrit:Il n'y a aucun rapport entre les 3 problèmes suivants :
1) Déterminer si un entier donné est premier ou non (ce que fait la fonction "isprime")
2) Déterminer la liste de tous les entiers premiers inférieurs ou égaux à un entier donné (ce que fait le crible d'Ératosthène)
3) Factoriser un entier donné.

Dans le premier cas, on connait des algorithmes très efficaces, capables de décider en quelques millièmes de secondes si des nombres de quelques centaines de chiffres sont premiers ou non.
Dans le 2ème cas, on ne connaît pas grand chose de mieux que le crible d'Ératosthène lui-même... mais il permet déjà d'établir une telle liste en quelques secondes pour des entiers ayant moins de 10 chiffres.
Dans le 3ème cas, on connaît plein d'algorithmes, la plupart étant plus ou moins efficaces suivant le champ d'application, c'est-à-dire suivant la forme des nombres auxquels on les applique. C'est un problème bien plus complexe que les deux précédents... et c'est justement sur le fait que ce soit complexe que se basent une grande partie des systèmes de cryptage.


Yep, you are right. I am trying to find the code behind the isPrime() function in TI Nspire CX-CAS, I made my own isPrime function with Miller-Rabin prime testing but it is not enough because it is slow with large numbers (>2^64), and I also see that a numbertheory library uses a for and isPrime() as a condition to enumerate all prime numbers in a range and it is faster than Erastosthenes sieve, but this does not make sense because the sieve has a complexity of O (nlog(log(log(n)))) and a for has a complexity of O (n*isPrime_complexity) then, isPrime has a complexity less than O(log(log(n)))!? Is this the reason why Miller-Rabin prime testing is slow compared to isPrime? But at the same time, isPrime is a really powerful and efficient algorithm. I looked for some algorithms to solve this task, but Miller Rabin is one of the most efficient in smaller numbers and isPrime is beating it. Is there any way to look at the code of this function?
Avatar de l’utilisateur
Heneos
Niveau 1: MD (Membre Débutant)
Niveau 1: MD (Membre Débutant)
Prochain niv.: 60%
 
Messages: 4
Inscription: 18 Juil 2018, 10:17
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: University
GitHub: HeNeos

Re: fonction isprime et crible d'ératosthène

Message non lude parisse » 01 Fév 2021, 13:01

Before calling Miller-Rabin, you should run trial division for a list of small primes (I'm using myself all primes<10^4). And of course this will be much faster if compiled vs interpreted. If you want to really compare speeds for not too small values of n, you should try to write your code in C with ndless (and compare to GMP builtin function).
Avatar de l’utilisateur
parisseVIP++
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 77.2%
 
Messages: 3500
Inscription: 13 Déc 2013, 16:35
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: fonction isprime et crible d'ératosthène

Message non lude Heneos » 01 Fév 2021, 13:32

Thanks, good answer, I remember that I tried with C and ndless, but it was a really headache (I feel more comfortable with C++ and STL), so maybe my implementation was not efficient. This is my code for sieve:
Code: Tout sélectionner
Define sieve(n)=
Func
:Local i,j,primes,ss
:ss:=newList(n)
:primes:={}
:For i,2,n
:  If ss[i]=0 Then
:    primes:=augment(primes,{i})
:    For j,i*i,n,i
:      ss[j]:=1
:    EndFor
:  EndIf
:EndFor
:Return primes
:EndFunc


And this is with isPrime:

Code: Tout sélectionner
Define naive(n)=
Func
:Local i,j,primes
:primes:={2}
:For i,3,n,2
:  If isPrime(i) Then
:    primes:=augment(primes,{i})
:  EndIf
:EndFor
:Return primes
:EndFunc

For 20000, sieve runs in around 5 seconds and naive runs in 1.4 second :(
Dernière édition par Heneos le 01 Fév 2021, 23:09, édité 1 fois.
Image
Avatar de l’utilisateur
Heneos
Niveau 1: MD (Membre Débutant)
Niveau 1: MD (Membre Débutant)
Prochain niv.: 60%
 
Messages: 4
Inscription: 18 Juil 2018, 10:17
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: University
GitHub: HeNeos

Re: fonction isprime et crible d'ératosthène

Message non lude Bisam » 01 Fév 2021, 17:44

I bet it runs faster doing like this :
Code: Tout sélectionner
Define sieve(n)=
Func
Local i,j,len,primes,ss
ss:=newList(n)
primes:={}
len:=0
For i,2,n
  If ss[i]=0 Then
    len:=len+1
    primes[len]:=i
    For j,i*i,n,i
      ss[j]:=1
    EndFor
  EndIf
EndFor
Return primes
EndFunc

It's based on an undocumented fact : if you put something just after the end of a list, the lists grows automatically.
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Suivante

Retourner vers Nspire-Basic

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 16 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.
1064 utilisateurs:
>1041 invités
>19 membres
>4 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)