Fonction isPrime

[pierrotdu18]

Bonjour à tous,

Déjà, je voulais savoir, y a t-il un moyen de connaître le code des fonctions déjà présentes dans la calculatrice?
Ensuite, je voudrais me pencher sur la fonction isPrime.
Récemment, j'essaye de trouver plein de façons différentes en TI-basic de tester la primarité d'un nombre... Toutes celles que j'ai déjà essayé sont beaucoup beaucoup plus lentes que la fonction native de la calculatrice...
Est-ce qu'ils ont trouvé un algorithme révolutionnaire? Si oui quel est celui utilisé, et sinon, peut être que ce n'est pas le même langage? Les fonctions natives seraient donc codées en ASM ou en C/C++ ?

Merci à vous!

[Lionel Debroux]

Est-ce qu'ils ont trouvé un algorithme révolutionnaire?

Non. Pas mal d'algorithmes pour ceci ont été trouvés par les mathématiciens et les informaticiens au fil du temps. Il y a des algorithmes déterministes, des algorithmes probabilistes, chacun ayant sa zone d'utilisabilité (les algorithmes naïfs deviennent vite très lents quand la taille augmente). Wikipedia, et des sites/forums plus spécialisés, seront des ressources plus complètes et plus pédagogiques
Notons que déterminer la primalité, et factoriser un composé, sont deux choses très différentes. La première est beaucoup plus facile que la deuxième, surtout avec une détermination probabiliste de primalité. On connaît un algorithme polynômial de détermination de primalité (AKS), même s'il est rarement utilisé; la factorisation est une autre paire de manches (NP-complet, au mieux), rapidement pénible pour des particuliers (factoriser RSA-512 est trivial, mais factoriser RSA-640 l'est déjà nettement moins pour des particuliers; l'état de l'art est à 768 bits, sachant que 896 ou même 1024 est probablement en cours).

Si oui quel est celui utilisé, et sinon, peut être que ce n'est pas le même langage?

Seul TI pourrait indiquer sans trop d'effort quels algorithmes sont utilisés par le CAS de la Nspire. Même si on sait comment s'y prendre pour trouver en gros les blocs de code qui s'occupent du test de primalité (trouver primary_tag_list et descendre - c'est exactement pareil que sur TI-68k, les structures de données au coeur du CAS de la Nspire restent très similaire à celles utilisées par le CAS des premières TI-92 de 1995-1996), il faudrait reconnaître les algorithmes à partir du désassemblage, ce qui peut être désagréable.
J'avais lu une fois que les TI-68k utilisaient un algorithme déterministe au début, puis probabiliste pour des nombres plus grands, mais je serais bien en peine de retrouver la référence, si tant est qu'elle existe encore (l'endroit où je pense l'avoir lu ayant été partiellement détruit par un cracker).

Les fonctions natives seraient donc codées en ASM ou en C/C++ ?

Bien entendu - toutes les fonctions natives du BASIC sont codées en C (sur TI-68k, c'est clairement du C, parce que même un programmeur ASM relativement incompétent ne produirait jamais certaines conneries que le compilo de merde utilisé par TI a commis - et puis de toute façon, développer en ASM pur prend beaucoup trop de temps et coûte donc beaucoup trop cher)
Et puis le BASIC est implémenté de façon lente, ce qui n'aide pas à l'implémentation d'algorithmes de test de primalité...

[pierrotdu18]

D'accord merci...
Et donc actuellement, quel est l'algorithme le plus rapide en TI-Basic pour tester la primarité d'un nombre?

[Laurae]

D'accord merci...
Et donc actuellement, quel est l'algorithme le plus rapide en TI-Basic pour tester la primarité d'un nombre?

Essaies l'algorithme de Sieve of Atkin pas sûr que ce soit le plus rapide mais c'est déjà pas trop mal.

[pierrotdu18]

Ok... Et donc l'algorithme qui consiste à incrementer de deux et tester la divisibilité jusqu'àla racine du nombre, faut oublier ?

[Levak]

Ok... Et donc l'algorithme qui consiste à incrementer de deux et tester la divisibilité jusqu'àla racine du nombre, faut oublier ?

Pourquoi ? Tu as mieux ?

[pierrotdu18]

Ah, c'est que c'est ça le truc de Sieve of Atkin ?
Je n'ai pas été me renseigner, mais si c'est ça alors j'ai rien dit

[Laurae]

Ah, c'est que c'est ça le truc de Sieve of Atkin ?
Je n'ai pas été me renseigner, mais si c'est ça alors j'ai rien dit

Bien plus différent.

http://en.wikipedia.org/wiki/Sieve_of_Atkin

Pseudocode selon Wikipedia :

Code: Select all

// arbitrary search limit
limit ← 1000000         

// initialize the sieve
for i in [5, limit]: is_prime(i) ← false

// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
for (x, y) in [1, √limit] × [1, √limit]:
    n ← 4x²+y²
    if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):
        is_prime(n) ← ¬is_prime(n)
    n ← 3x²+y²
    if (n ≤ limit) and (n mod 12 = 7):
        is_prime(n) ← ¬is_prime(n)
    n ← 3x²-y²
    if (x > y) and (n ≤ limit) and (n mod 12 = 11):
        is_prime(n) ← ¬is_prime(n)
 
// eliminate composites by sieving
for n in [5, √limit]:
    if is_prime(n):
        // n is prime, omit multiples of its square; this is
        // sufficient because composites which managed to get
        // on the list cannot be square-free
        for k in {n², 2n², 3n², ..., limit}:
            is_prime(k) ← false

print 2, 3
for n in [5, limit]:
    if is_prime(n): print n

[Bisam]

Le crible d'Atkin est une version améliorée du crible d'Ératosthène.
Son but n'est pas de tester si un nombre donné est premier ou non, mais de renvoyer la liste de tous les nombres premiers inférieurs ou égaux à une limite donnée.

On peut éventuellement s'en servir pour déterminer ensuite si un nombre est premier ou non... mais ce ne sera efficace que si on doit le faire un grand nombre de fois.

Il ne répond donc pas vraiment à la question posée par pierrotdu18.

Pour ce qui est des autres algorithmes de tests de primalité, la quasi-totalité nécessitent de solides connaissances mathématiques post-bac pour être compris et parfois encore plus pour être implémentés !

[Laurae]

t'as plein de choses ici compréhensibles : http://en.wikipedia.org/wiki/Primality_test