Wikipedia

Euklids algoritme: Forskelle mellem versioner

Gennemse historikken interaktivt
← Gå til forrige forskelGå til næste forskel →
Content deleted Content added
VisueltWikitekst
m lidt tegnsætning og sprog
→‎Division med rest: Anvender <math>
Tags: Mobilredigering Mobilwebredigering Avanceret redigering fra mobil
Linje 112:
 
=== Division med rest ===
Ved hvert trin ''k'' beregner Euklids algoritme en kvotient ''q''<submath>''k''q_k</submath> og resten ''r''<submath>''k''r_k</submath> fra to tal ''r''<submath>''r_{k''−1-1}</submath> og ''r''<submath>''r_{k''−2-2}</submath>
:<math>r_{k-2}=q_{k}r_{k-1}+r_k</math>
 
hvor ''r''<submath>''k''r_k</submath> er ikke-negativ og strengt mindre end [[Numerisk værdi|størrelsen]] på ''r'' <submath>''r_{k''−1-1}</submath>. Dette kaldes [[division med rest]]. Den matematiske sætning, der ligger bag division med rest, er, at en sådan kvotient og resten altid findes og er unikke.<ref>{{Cite book|title=Abstract Algebra|last=Dummit|first=David S.|last2=Foote|first2=Richard M.|publisher=John Wiley & Sons, Inc.|year=2004|isbn=978-0-471-43334-7|location=|pages=270-271}}</ref>▼
: {{Math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}
 
I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. ''r'' <submath>''r_{k''−1-1}</submath> trækkes fra ''r''<submath>''r_{k''−2-2}</submath>, indtil resten ''r'' <submath>''k''r_k</submath> er mindre end ''r'' <submath>''r_{k''−1-1}</submath> . Derefter byttes der om på ''r'' <submath>''k''r_k</submath> og ''r''<submath>''r_{k''−1-1}</submath> (så ''r''<submath>''k''r_k</submath> næste gang trækkes fra ''r''<submath>''r_{k''−1-1}</submath>), og processen gentages. Euklidisk opdeling reducerer alle trin mellem to opbytninger til et enkelt trin, hvilket er mere effektivt. Desuden er kvotienterne ikke nødvendige, så man kan erstatte division med rest med [[modulo]]operationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen▼
▲hvor ''r''<sub>''k''</sub> er ikke-negativ og strengt mindre end [[Numerisk værdi|størrelsen]] på ''r'' <sub>''k''−1</sub>. Dette kaldes [[division med rest]]. Den matematiske sætning, der ligger bag division med rest, er, at en sådan kvotient og resten altid findes og er unikke.<ref>{{Cite book|title=Abstract Algebra|last=Dummit|first=David S.|last2=Foote|first2=Richard M.|publisher=John Wiley & Sons, Inc.|year=2004|isbn=978-0-471-43334-7|location=|pages=270-271}}</ref>
:<math>r_k=r_{k-2}\bmod r_{k-1}</math>
 
▲I Euklids originale version af algoritmen findes kvotienten og resten ved gentagen subtraktion; dvs. ''r'' <sub>''k''−1</sub> trækkes fra ''r''<sub>''k''−2</sub>, indtil resten ''r'' <sub>''k''</sub> er mindre end ''r'' <sub>''k''−1</sub> . Derefter byttes der om på ''r'' <sub>''k''</sub> og ''r''<sub>''k''−1</sub> (så ''r''<sub>''k''</sub> næste gang trækkes fra ''r''<sub>''k''−1</sub>), og processen gentages. Euklidisk opdeling reducerer alle trin mellem to opbytninger til et enkelt trin, hvilket er mere effektivt. Desuden er kvotienterne ikke nødvendige, så man kan erstatte division med rest med [[modulo]]operationen, der kun giver resten. Således bliver hver iteration af Euklids algoritme simpelthen
 
: {{Math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>.}}
 
=== Implementeringer ===
Hentet fra "https://da.wikipedia.org/wiki/Euklids_algoritme"