Zum Inhalt springen

Datei:GCD through successive divisions.svg

Seiteninhalte werden in anderen Sprachen nicht unterstützt.
Zur Beschreibungsseite auf Commons
aus Wikipedia, der freien Enzyklopädie

Originaldatei (SVG-Datei, Basisgröße: 660 × 825 Pixel, Dateigröße: 4 KB)

Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.

Zur Beschreibungsseite auf Commons


Beschreibung

Beschreibung
English:
The  GCD  of  two  natural  numbers
is their common divisor,  multiple of all their common divisors.  To  calculate  it,
the Euclidean algorithm transforms gradually two positive integers into another pair
having  the  same  set  of  common  divisors.   After  each  euclidean  division,
the  divisor‑remainder  pair  becomes  a  possible  dividend‑divisor,   until  a
decisive  zero.   The  previous  remainder  is  then  the  wanted  GCD.
The   Euclidean   algorithm   finds
the  GCD  of  two  positive  integers
through  successive  divisions.
For  a  same  result,
each  euclidean  division
translated  into  an  iterated  subtraction.
 Flow  charts,   in  order  to  calculate  the  GCD  of  two  natural  integers 

Key of the proof:   if two integers are multiples of a certain integer k,  then their difference
or their sum is also a multiple of k
.  Consequence:  the set of common divisors of a given pair
of  integers  is  unchanged,   when  the  greatest  element  of  the  pair  is  replaced  with
the  positive  difference  of  the  two  elements,   like  in  the  second  flow  chart.
For  example,   72–20 = 52,  52–20 = 32,  32–20 = 12.   And  the  following  ordered  pairs
have  the  same  set  of  common  divisors:   (72,  20),  (52,  20),  (32,  20),  (12,  20). 
In short,  (72,  20)  and  (20,  12)  have the same common divisors.  When  72  and  20
enter  the  Euclidean  algorithm  as  initial  values  of  d  and  g,   12  appears  in  this
subsequenceof remainders:   (72,  20,  12),   returned  below  in  the  second  example.

20  is  the  remainder  of  the  euclidean  division of  20  by  72,
while  12  is the remainder when you divise  72  by  20.   In pseudo‑code,  the expression
20  mod  72  evaluates to  20,  while  72  mod  20  evaluates to  12.  Indeed  20 = 20 - 0 × 72,
while  12 = 72 - 3 × 20.   Each quotient like  0  or  3  falls into oblivion in the Euclidean algorithm.
In Python    like  in JavaScript,   20 % 72  returns  20,   and   72 % 20  —> 12,
where   %   means  modulo.


First  translation  in  JavaScript.
When  you  copy  the  following  line, 
and then paste it in the adress bar of your browser : 
JavaScript: g = 72; d = 20; s =" PGCD("+ d +", "+ g +") = "; while( g ){ r = d % g; d = g; g = r } s + d;
your  browser  executes  the  JavaScript code
when you type  Enter.   If it is not executed,
then  enable  JavaScript   in  your  browser.
And then by entering other positive integers
instead of  72 and 20,  you obtain their GCD.

Second  translation  in  JavaScript.
  Example  more  comprehensible,
  through  copious  comments  placed  between   /*  and  */
/*  To open  a  Firefox  window
 dedicated to JavaScript code:   Shift + F4   */

 d = 20; g = 72;
/*  Imperative:  two positive integers enter the calculation.
 These conditions could be automatically verified in a more
 developed function    GCD = function(… ){… },    which
 would return an alert message in a case of abnormal use.
 See  instruction  try  in
File:GCD_through successive_subtractions.svg
 Here an abnormal use is not anticipated.  Therefore take care
 to  replace   20  and  72   with positive integers,
 when you order the GCD of two other numbers.

 Why name  g  the second variable ?⸮      G   evokes   “Greatest”
 in acronym  GCD,   zero being the greatest (positive) integer
 for the partial order named  “divisibility”:
 zero is the mUlTiPlE of all integers.  */

mcd = "(" + d +", "+ g;
/*  Just after the values of type  Number  are assigned
 to  d  and  g,   a value of type  String  is attributed to the
 variable named  mcd.   “String”  means  “string of characters”.
 The first character  mcd.charAt( 0 )  is a parenthesis.   And
 then the sign   +   orders either   “add the numbers”  or
 “concatenate the strings”,  according to the context.  After
 a string,   +  orders a concatenation.  So the value Number of
 d  is tacitly converted into its writing in decimal numeration:
 a short‑lived string   (20.).toString( 10 )  comes after  "("
 of length 1.  The syntax that folllows has a similar meaning.

 The values   20  and  72   are stored in the initial value
 "(20, 72"  of  mcd,   before the loop below modifies the
 two values  Number  to obtain their GCD.  */


//  sqr = " Sequence of “all remainders”:\n " + mcd;
/*  Two slashes  //  marks a beginning of comment
 placed on the same line,   not executed by an interpreter
 of JavaScript.  The line above that begins with two slashes
 is a comment,  like here the text placed between its two
 particular pairs of characters  (like in CSS).

 But if this first pair of slashes is removed,
 then this line becomes an executable bit of code like the others,
 so the value  String   on this new code line is assigned to  sqr.
 The character  "\n"  of this string begins its second line,  equal
 to  mcd  for the moment.   Below the unique loop of the code will
 modify the initial value of  sqr,  if the second pair of slashes
 is also removed in this loop.  */


while( g ){
/*  beginning of the  loop.
 Between the brackets of  while,   the expression is implicitly
 translated for a short while into an object of type  Boolean,
 if necessary.   Its  value  is  true  or  false.
 Equivalent code:   while( Boolean( g ))
 For example,   Boolean( 72 )  returns  true:
 the required value to enter the loop.

 Other equivalent code:   while( g > 0 )
 You can verify,  of course:    ( 72 > 0 )  —> true
 ( 72 > 0 ).constructor  —> function Boolean() { [native code] }

 In a later case,   Boolean( 0 )  —> false.
 When  Boolean( g )  returns  false,   the entry into the loop
 is refused,  and the code after the loop is executed.  */

    r = d % g;
/*  %  is the operator  modulo.
 At the first instance of the variable name  r,
 a new variable named  r  is created,  of global scope.
 The remainder of the euclidean division of  d  by  g
 is assigned to the variable  r  (r like “remainder”).
*/

    d = g; g = r;
/*  possible  dividend-divisor  pair
 of a further division,   if  g  is not zero  */

//    sqr += ", "+ g;
/*  facultative code actually considered as comment,
 but executable if the slashes are removed.  An error
 is returned if this only pair of slashes is removed.
 Equivalent code:   sqr = sqr + ", "+ g;  */
}
/*  end of the  loop  while( g )  */


" GCD" + mcd +") = "+ d;  /*  returns a string with the wanted GCD
*/

//  sqr += ").";
/*  When the three pairs of slashes above are removed,
 the definitive value of  sqr  is returned:   the sequence
 of  “all remainders”  for the initial value of pair  (d, g).
 Anywhere in the sequence of remainders,  two successive
 integers have always the same set of common divisors.

 Keyboard shortcut in Firefox to execute the code:   Ctrl + L   */
Datum
Quelle Eigenes Werk
Urheber Arthur Baelde
Andere Versionen
SVG‑Erstellung
InfoField
 
Der SVG-Code ist valide.
 
Diese Vektorgrafik wurde mit einem Texteditor erstellt. Die Validierung hat sie für syntaktisch korrekt befunden.

Lizenz

Arthur Baelde, der Nutzungsrechtsinhaber dieses Werkes, veröffentlicht es hiermit unter der folgenden Lizenz:
w:de:Creative Commons
Namensnennung Weitergabe unter gleichen Bedingungen
Namensnennung: Arthur Baelde
Dieses Werk darf von dir
  • verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
  • neu zusammengestellt werden – abgewandelt und bearbeitet werden
Zu den folgenden Bedingungen:
  • Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
  • Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.

Kurzbeschreibungen

Ergänze eine einzeilige Erklärung, was diese Datei darstellt.
The algorithm transforms gradually two positive integers into another pair having the same common divisors.  After each euclidean division,  the divisor‑remainder ordered pair becomes a possible dividend‑divisor,  until a decisive zero.

In dieser Datei abgebildete Objekte

Motiv

image/svg+xml

Dateiversionen

Klicke auf einen Zeitpunkt, um diese Version zu laden.

Version vomVorschaubildMaßeBenutzerKommentar
aktuell14:10, 27. Aug. 2024Vorschaubild der Version vom 14:10, 27. Aug. 2024660 × 825 (4 KB)Arthur Baelde “modulo” in bold characters 
15:09, 22. Mai 2024Vorschaubild der Version vom 15:09, 22. Mai 2024660 × 825 (4 KB)Arthur BaeldeUploaded own work with UploadWizard

Keine Seiten verwenden diese Datei.

Globale Dateiverwendung

Die nachfolgenden anderen Wikis verwenden diese Datei:

Metadaten