samedi 23 août 2014

Test de primalité d'un nombre entier.

Nous allons rechercher si un nombre impair supérieur ou égal à 3 est un nombre premier en utilisant l'algorithme de test élémentaire suivant:

K = 3
Début Test
{
    Si ( K > RacineCarrée(P) ) Alors ( P est Premier - Fin du Test )
    Si ( K divise P ) Alors ( P est non Premier - Fin du Test ) 
    K = K + 2
}
Retourne Début Test

Le programme suivant active le drapeau 1 (Flag 1) si le nombre testé est premier.

PGRM TOP
R001 LBL R
# Efface et désactive le drapeau 1 (Flag 1).
R002 CF 1
R003 STO P
R004 3
R005 STO K
R006 RCL P
# Racine carré de X.
R007 √(X)
R008 RCL K
R009 X > Y ?
R010 GTO R020
R011 RCL P
R012 X<>Y
R013 ÷
# FP signifie Fractional Part de P/K (Menu INTG choix 5).
R014 FP
R015 X = 0 ?
R016 GTO R023
R017 2
R018 STO + K
R019 GTO R006
# Active le drapeau 1 (Flag 1).
R020 SF 1
# CLSTK signifie vider les 4 niveaux du stack (Menu CLEAR choix 5).
R021 CLSTK
R022 RTN
R023 CLSTK
R024 RTN

Entrez votre nombre impair dans la ligne basse de l'écran de la calculatrice (registre X) et lancez le programme en faisant XEQ R ENTER.
Le drapeau 1 est activé si le nombre est premier, le chiffre 1 apparait alors sur la ligne d'indicateurs de la calculatrice.

Par exemple entrez 137 puis XEQ R ENTER. Le drapeau 1 s'active.
Voici quelques autres nombres à tester: 567 est non premier, 571 est premier, 2603 est non premier et 524287 est premier.
Vous pouvez faire chauffer le processeur en testant 2147483647 ;).

NB: Il ne sert à rien de tester les nombres pairs qui sont tous divisibles par deux et donc non premiers (Le seul nombre premier pair est 2).

Liens intéressants:
Les divers tests de primalité.
Test de primalité élémentaire.

A très bientôt :)

mercredi 13 août 2014

Calcul du PGCD de deux nombres entiers positifs.

Vous trouverez ci-dessous le programme qui calcule le PGCD de deux nombres entiers positifs non nuls en utilisant l'algorithme des soustractions que voici:

Tant que ( Y > 0 )
{
    Si ( X > Y ) Alors ( X = X - Y ) Sinon ( Y = Y - X) 
}
Retourne X

Le programme suivant est le plus minimaliste que l'on puisse écrire.

PGRM TOP
R001 LBL R
R002 X > Y ?
R003 GTO R007
R004 -
R005 LAST X
R006 GTO R010
R007 X<>Y
R008 -
R009 LAST X
R010 X > 0 ?
R011 GTO R002
R012 X<>Y
R013 RTN

Entrez Y puis entrez X, ou bien X puis Y (peu importe l'ordre de saisie) et lancez le programme en faisant XEQ R ENTER.
Le résultat est affiché sur la ligne basse de l'écran dans le registre X du stack.

Par exemple entrez 357 puis 561, le résultat sera 51.
Voici quelques autres exemples: PGCD(2001,78) = 3 ou bien PGCD(108,608) = 4.

Liens intéressants:
Algorithme des soustractions successives 1.
Algorithme des soustractions successives 2.

A bientôt :)

samedi 9 août 2014

Suite de Fibonacci.

Voici donc mon premier article sur la HP-35S, vraie calculatrice scientifique programmable avec le mythique stack RPN à 4 niveaux de HP ! Son look rétro façon HP-34C ou HP-41CV est très sympathique, tout comme son prix d'environ 50 euros en juillet 2014.

Soit F(n) la suite dite Suite de Fibonacci définie par:
  • F(1) = F(2) = 1
  • F(n) = F(n-1) + F(n-2) pour n > 2
Chaque terme de la suite est donc la somme des deux termes précédents.

Vous trouverez ci-dessous un petit programme qui calcule le n-ième terme de cette suite.

PGRM TOP
F001 LBL F
# Entrez ici l'indice du terme à calculer, par exemple 15 pour
# obtenir F(15) = 610.
F002 INPUT I
F003 -1
F004 RCL + I
F005 1000
F006 ÷
F007 3
F008 +
F009 STO I
# I vaut alors 3.014 et sera utilisé comme compteur avec ISG I: le
# compteur bouclera de 3 à 14, sera incrémenté avec un pas de 1 et
# sortira de la boucle à 15.
F010 1
F011 1
F012 +
# On enregistre les différentes valeurs calculées: STO(3) à ST0(14).
F013 STO (I)
F014 LAST X
F015 X<>Y
F016 +
# Le compteur boucle tant que I ne vaut pas 15.014.
F017 ISG I
F018 GTO F013
# On enregistre la dernière valeur calculée après sortie de la
# boucle: STO(15).
F019 STO (I)
F020 RTN

Lancez le programme en faisant XEQ F ENTER.
Entrez 15 à l'invitation I? puis continuez en tapant R/S.

Sur la ligne basse de l'écran sera alors affichée 610 soit la valeur de F(15).
(Sur la ligne du haut, on retrouve la valeur du compteur 3.014 telle que calculée ligne F008.)

Si à ce stade on entre tout simplement RCL I, on obtiens dans notre exemple 15.014 la valeur finale du compteur I en sortie de boucle. En entrant RCL (I) on retrouve bien 610.

Ainsi en fixant I entre 3 et 15 on retrouve avec RCL (I) la valeur de F(I) intermédiaire gardée en mémoire, par exemple 10 STO I puis RCL(I) donnera 55 soit F(10).

Prendre garde en quittant à désallouer les variables indirectes (I) addressées en les effacant avec CLEAR et CLVAR000.
Il reste la variable (0) à effacer en faisant 0 STO I STO (I).

Liens intéressants:
La Calculatrice HP-35S en détail.
HP-35S et Variables indirectes.
Working with Indirectly Addressed Memory.

A très bientôt :)