HP 39g-Grafenberechner - Handbuch (Seite 147)

Exakte Berechnungen und Mathematik mit HP40G
Arithmetische Programme 147
8 Arithmetische Programme
8.1 PGCD Euklids Algorithmus
A und B sind zwei ganze positive Zahlen, zu denen wir NSD suchen.
Der euklidische Algorithmus basiert auf die rekursive (unendlich wiederholte)
Definition NSD:
NSD(A,0) = A
NSD(A,B) = NSD(B,A mod B) wenn B
¹ 0
wo A mod B den Rest der euklidischen Division kennzeichnet, A wird durch B
dividiert.
Beschreibung dieses Algorithmus:
Man führt eine folgende euklidische Division durch:
A = B
´ Q
1
+ R
1
0
£ R
1
< B
B = R
1
´ Q
2
+ R
2
0
£ R
2
< R
1
R
1
= R
2
´ Q
3
+ R
3
0
£ R
3
< R
2
Nach der beendeten Zyklen-Anzahl, existiert eine ganze Zahl n wie zum
Beispiel: R
n
= 0.
Man hat also:
NSD(A,B) = NSD(B, R
1
) = …
NSD(R
n – 1,
R
n
) = NSD(R
n – 1
,0) = R
n – 1
8.1.1 Algorithmische Erläuterung
Wiederholte (iterative) Version
Wenn B
¹ 0, rechnet man R=A mod B, dann speichert man B in A und R in B,
dies wiederholt man ständig bis B=0, und NSD A ist.
Funktion NSD(A,B)
Lokale (lokale) R
Wenn B
¹ 0 durchführen
A mod B -
>R