Ο Ευκλείδειος αλγόριθμος σε πολλές γλώσσες

[Morgul]

Μετά από μια πρόσφατη συζήτηση με τον Alan για τον πλουραλισμό και τις ομοιότητες/διαφορές των διαφόρων γλωσσών προγραμματισμού, αποφάσισα (μετά από πρότασή του) να ξεκινήσω ένα thread πάνω σ'αυτό. Η ιδέα είναι να φανούν όσο περισσότερες γλώσσες προγραμματισμού γίνεται σε σχετικά μικρό βάθος για να φανεί μορφολογία, σύνταξη και λίγη ιδιωματική χρήση σε σχέση με τον αλγόριθμο.

Ο αλγόριθμος του Ευκλείδη είναι ο μαθηματικά απλούστερος για την εύρεση μέγιστου κοινού διαιρέτη (ΜΚΔ ή Greatest Common Divisor — GCD στα αγγλικά). Ο αλγόριθμος ουσιαστικά είναι γεωμετρική μέθοδος, μια και οι αρχαίοι Έλληνες δούλευαν πάντα με λόγους και γεωμετρία. Ο σκοπός του είναι να βρει τη μεγαλύτερη δυνατή μονάδα μέτρησης της οποίας ακέραιο πολλαπλάσιο είναι τα μήκη δύο ευθύγραμμων τμημάτων ΑΒ και ΓΔ. Αφαιρούμε από το μεγαλύτερο τμήμα το μικρότερο κατ'επανάληψη μέχρι να εξαντληθεί ένα από τα δύο. Το μήκος του εναπομείναντος είναι η μονάδα που ψάχνουμε.

Και να'τος σε ψευδοκώδικα:

GCD.
INPUT: x, y φυσικοί αριθμοί.
OUTPUT: φυσικός αριθμός.

1. if x = 0
2.     return y
3. if x > y
4.     x = x - y
5. else:
6.     y = y - x
7. if y > 0
8.     go to step 3
9. return x

Στις απαντήσεις του thread θα βάλω υλοποιήσεις του απλού αυτού αλγόριθμου σε μερικές συνηθισμένες γλώσσες (και σε μερικές ασυνήθιστες). Μπορείτε να προσθέσετε κι εσείς τις δικές σας! Απλά κρατήστε το ύφος και τα ονόματα παρόμοια ώστε όσοι δεν ξέρουν τις γλώσσες να μπορούν (όσο γίνεται) να δουν τις ομοιότητες/διαφορές.

[Morgul]

Να ο αλγόριθμος σε C.

/* Calculate the greatest common divisor of two integers. Use Euclid's
 * algorithm. */
unsigned gcd (unsigned x, unsigned y)
{
        if (x == 0) return y;
        while (y) {
                if (x > y) x -= y;
                else y -= x;
        }
        return x;
}

Για να λειτουργήσει ως αυτόνομο πρόγραμμα, πρέπει να προσθέσουμε και τη συνάρτηση main() κατά το συνηθισμένο ANSI C πρωτόκολο:

int main (char argc, char * argv[])
{
        printf ("GCD = %u\n", gcd (1071, 1029));
        return 0;
}

[Morgul]

Έχω να γράψω Pascal σχεδόν 16 χρόνια. Δε μου λείπει τόσο πολύ, να πω την αλήθεια... Λόγω της σύνταξης της γλώσσας, παραθέτω τον αλγόριθμο ως αυτόνομο πρόγραμμα. Ευτυχώς, είναι εύκολο να διαχωριστεί η συνάρτηση από το πρόγραμμα. Όπως όλες οι γλώσσες του N. Wirth, είναι εξαιρετικά ευανάγνωστη.

program GCD;

{ Euclidean Algorithm in Pascal }
function GCD (x, y: integer): integer;

begin
   if x = 0 then begin
      GCD := y;
      exit;
   end;
   while y > 0 do begin
      if x > y then
     x := x - y
      else
     y := y - x;
   end;
   GCD := x;
end; { GCD }

begin
   writeln ('GCD = ', GCD (1071, 1029));
end.

[Morgul]

Η Python είναι η αγαπημένη μου γλώσσα προγραμματισμού εδώ και μερικά χρόνια για την εξαιρετική ισχύ της και το ευανάγνωστο του κώδικά της. Προσέξτε πόσο μοιάζει με ψευδοκώδικα!

def gcd (x, y):
    """
    Calculate the greatest common divisor of two integers.  Use Euclid's
    algorithm.
    """
    if x == 0:
        return y
    while y:
        if x > y:
            x -= y
        else:
            y -= x
    return x

Ενδιαφέρουσες αλλαγές σε σχέση με άλλες γλώσσες: κάθε συνάρτηση υποχρεούται (από το style guide) να τεκμηριώνει τον εαυτό της στην αρχή της. Το """...""" είναι πολύγραμμο string (προσβάσιμο μετά τον ορισμό της συνάρτησης ως gcd.__doc__), το οποίο χρησιμοποιείται για τη δημιουργία αυτόματης τεκμηρίωσης (γράφοντας, πχ, help(gcd) στον Python interpreter).

Επίσης, δεν υπάρχει ειδική σύνταξη ανάλογη του begin...end της Pascal ή του {...} της C. Τη λειτουργία τους την εκτελεί το indentation, που είναι μέρος της σύνταξης και υποχρεωτικό. Αυτό ξενίζει πολλούς νέους προγραμματιστές, αλλά στους περισσότερους τελικά αρέσει.

Για να γίνει αυτόνομο πρόγραμμα το παραπάνω, αρκεί να προσθέσουμε το εξής απλό:

print "gcd = %u" % gcd(1071, 1029)

Στην αναμενόμενη Python 3, το παραπάνω πρέπει να είναι:

print("gcd = %u" % gcd(1071, 1029))

Μια και η print άλλαξε επιτέλους από statement σε function.

[Morgul]

Έχω μια σχέση αγάπης-μίσους με τη Lisp. Την έμαθα για να γράφω αλλαγές/προγράμματα για το AutoCAD (το οποίο προγραμματίζεται σε AutoLisp). Τώρα θυμάμαι ελάχιστη, μόνο και μόνο για να γράφω μικροαλλαγές για τον Emacs.

Μου πήρε περισσότερο χρόνο να γράψω αυτό το τέρας απ'ότι σε άλλες γλώσσες.

(defun mygcd (x y) ; gcd is an existing function in Common Lisp.
  "Calculate the greatest common divisor of two integers. Use Euclid's
   algorithm."
  (if (zerop x) (return x))
  (loop
   (if (> x y)
       (setq x (- x y))
       (setq y (- y x)))
   (when (zerop y) (return x))))

Για να εκτελεστεί η παραπάνω συνάρτηση, αρκεί να πούμε:

(mygcd 1071 1029)

Ενδιαφέροντα χαρακτηριστικά της Lisp είναι ότι είναι η μόνη εν ζωή γλώσσα προγραμματισμού που γεννήθηκε από μαθηματική θεωρία και είναι μαθηματική θεωρία. Η γλώσσα δημιουργήθηκε κατά λάθος, και είναι από τις πιο μαθηματικά κομψές γλώσσες που υπάρχουν.

Δυστυχώς είναι εξαιρετικά δυσανάγνωστη, πράγμα που οφείλεται στην μεγάλη ηλικία της.

Είναι κοινή τακτική να μπαίνει ένα documentation string στην αρχή κάθε συνάρτησης Lisp. Αυτό δεν είναι ειδική σύνταξη: το string «εκτελείται» κανονικά (και αγνοείται), πράγμα που επιτρέπει σε εξωτερικό κώδικα να προσπελάσει την τεκμηρίωση κάθε τέτοιας συνάρτησης, όπως κάνει και η Python.

Κάθε πρόγραμμα Lisp είναι μία λίστα (Lisp = List Processing), τα μέλη της οποίας περικλείονται από παρενθέσεις. Το πρώτο μέλος κάθε λίστας είναι το όνομα μιας συνάρτησης, τα υπόλοιπα μέλη είναι οι παράμετροι της συνάρτησης. Τα πάντα στη Lisp είναι συναρτήσεις, ακόμα και βασικές λειτουργίες όπως η setq (variable assignment) και η if.

Το άλλο χαρακτηριστικό της Lisp είναι ότι, λόγω αυτής της σύνταξης, όλη η αριθμητική γίνεται «prefix» (infix: 10 + 20, postfix: 10 20 +, prefix: + 10 20). Αυτό είναι βολικό γιατί σε infix/prefix δε χρειαζόμαστε παρενθέσεις για να δηλώσουμε προτεραιότητα.

Οι παρενθέσεις στο τέλος ενός προγράμματος είναι κόλαση όμως.

[Morgul]

Η Scheme είναι η μικρή αδερφή της Lisp. Το «μικρή» είναι μάλλον παραπλανητικό, μια και το βιβλίο μου για τη Lisp είναι το μεγαλύτερο βιβλίο στη βιβλιοθήκη μου.

Η ιδέα ήταν να απλοποιηθεί η γλώσσα ώστε να μπορεί κάποιος να τη μάθει εύκολα. Η απλοποίηση δημιούργησε μια πολύ κομψή functional γλώσσα με παρόμοιο ύφος και σύνταξη με τη Lisp (Lambda calculus, S-expressions, κλπ).

Ο αλγόριθμος δεν είναι υλοποιήσιμος σε Scheme επειδή η γλώσσα είναι ανίκανη να εκτελέσει συμβατικά (iterative) loops — αντ'αυτού, αντικατέστησα το while με recursion, όπως επιβάλλει η γλώσσα.

(define mygcd ; Scheme has a built-in, optimal GCD function.
  (lambda (x y)
    (cond ((zero? x) y)
      ((zero? y) x)
      ((> x y) (mygcd (- x y) y))
      (else (mygcd x (- y x))))))

Ενδιαφέρουσες αλλαγές είναι η εισαγωγή της συνάρτησης lambda (που δημιουργεί closures ή ανώνυμες συναρτήσεις όπως λέγονται τελευταία). Επίσης άλλαξαν τα ονόματα των Lisp predicates (boolean functions) ώστε αντί να τελειώνουν σε p (predicate) τελειώνουν σε ? (zerop -> zero?). Παρόμοιες αλλαγές έχουν γίνει σε πολλές συναρτήσεις (ή μάλλον στις λίγες Lisp συναρτήσεις που έμειναν).

Όπως και στη Lisp, για να εκτελέσουμε τη συνάρτηση, δίνουμε:

(mygcd 1071 1029)

[Morgul]

Η Prolog έχει μια από τις πιο αμφισβητούμενες θέσεις στους καταλόγους γλωσσών προγραμματισμού, μια και είναι Turing Complete... κατά σύμπτωση. Σ'αυτή τη γλώσσα δεν περιγράφεις αλγορίθμους, αλλά στόχους. Η γλώσσα χρησιμοποιεί απλές τεχνικές έρευνας (depth-first-search) και δοκιμάζει κάθε δυνατή τιμή κάθε μεταβλητής μέχρι να φτάσει στο στόχο που θέλουμε. Συνήθως τη βοηθάμε περιορίζοντας τις δυνατές τιμές ώστε να τελειώσει την έρευνα πριν το τέλος του σύμπαντος.

Όπως και η Scheme, δεν έχει loops, και τα πάντα γίνονται με recursion. Δεν έχει επίσης συναρτήσεις, οπότε ο μόνος τρόπος να πάρεις αποτέλεσμα από κάτι είναι να περάσεις μια τρίτη παράμετρο (χωρίς τιμή), την οποία η Prolog θα κάνει «instantiate» αν όλα πάνε καλά.

% Calculate the greatest common divisor of two integers. Use Euclid's
% algorithm.

gcd(0, Y, Y).

gcd(X, 0, X).

gcd(X, Y, GCD):-
    X > Y,
    NewX is X - Y,
    gcd(NewX, Y, GCD).
    
gcd(X, Y, GCD):-
    NewY is Y - X,
    gcd(X, NewY, GCD).

Για να πάρουμε απάντηση, λέμε τα εξής στον Prolog interpreter:

gcd(1071,1029,Result).

Κι αυτός απαντάει με τις τιμές όλων των μεταβλητών μας.

Result = 21

Ενδιαφέρον είναι ότι οι μεταβλητές στην Prolog είναι ό,τι ξεκινάει με κεφαλαίο.

[Morgul]

Η Postscript, σε αντίθεση με την Prolog, δεν αμφισβητείται ως γλώσσα προγραμματισμού. Αυτό είναι γιατί ελάχιστοι γνωρίζουν ότι είναι γλώσσα προγραμματισμού! Το χαρακτηριστικό της είναι ότι τα πάντα λειτουργούν με stacks, και όλος ο προγραμματισμός είναι postfix (εξ'ου και το όνομα της γλώσσας): γράφουμε 10 10 + (ή μάλλον 10 10 add) αντί για 10 + 10.

Η Postscript είναι γλώσσα γραφικών, χρησιμοποιείται σχεδόν αποκλειστικά για να περιγράφει σελίδες ακριβών εκτυπωτών (γιατί είναι πανεύκολο να γραφτεί ένας Postscript interpreter, και είναι ελαφρύς και μικρός, ιδανικός για embedded συσκευές όπως και η Forth).

Η γλώσσα ήρθε σε κοινή χρήση με την έλευση του PDF, που είναι compiled, απλοποιημένη Postscript.

%!PS-Adobe-2.0

% Calculate the greatest common divisor of two integers. Use Euclid's
% algorithm.
/gcd {
    /y exch def
    /x exch def
    x 0 eq
    { y }
    {
        {
            y 0 eq {exit} if
            x y gt {/x x y sub def} {/y y x sub def} ifelse
        } loop
        x
    } ifelse
} def

Για να πάρουμε αποτέλεσμα, λέμε:

1071 1029 gcd

Το αποτέλεσμα θα είναι στην κορυφή του stack. Αν τρέχουμε gs (ghostscript), μπορούμε να το δούμε αυτό λέγοντας stack.

Ένα από τα κομψότερα χαρακτηριστικά της γλώσσας είναι ότι ο τύπος κάθε αντικειμένου είναι εμφανής από τον πρώτο χαρακτήρα του. Γι'αυτό το λόγο όλες οι εντολές και τελεστές ξεκινούν με αλφαβητικό χαρακτήρα (πχ add αντί για +, sub αντί για -).

[Morgul]

Αυτό το πρόγραμμα τρέχει σε διάφορα Unix shells, αλλά το έγραψα και το δοκίμασα στο de facto standard unix shell για Linux, το bash. Τα shells και οι scripting γλώσσες έχουν εξαιρετική ισχύ, αλλά έχουν και δυσανάγνωστο κώδικα και αναγκάζουν τον προγραμματιστή να καταφύγει σε τεχνάσματα (που κάνουν τον κώδικα πιο δυσανάγνωστο). Έχουν όμως την αδιάσειστη θέση τους στην «πρώτη γραμμή» μεταξύ του λειτουργικού συστήματος και του χρήστη.

# Calculate the greatest common divisor of two integers. Use Euclid's
# algorithm.

gcd() {
    x=$1;
    y=$2;
    [ $x == 0 ] && echo $y
    while [ $y -gt 0 ]; do
        if [ $x -gt $y ]; then
            x=$[ $x - $y ]
        else
            y=$[ $y - $x ]
        fi
    done
    echo $x
}

Για να το εκτελέσουμε:

gcd 1071 1029

[Morgul]

Αυτή είναι η γλώσσα Assembly (extended = macroassembly) του RISC επεξεργαστή MIPS R2000, και όλης της υπόλοιπης οικογένειας.

# MIPS R2000 Extended Assembly

# Subroutine to calculate the greatest common divisor of two integers. Uses
# Euclid's algorithm.
#
# Input: x in register $a0
# Input: y in register $a1
# Result: in register $v0 (standard use)

gcd:    beq     $a0, $0, rety   # if x = 0, return y.

while:  beq     $a1, $0, retx   # if y = 0, return x.
        sub     $t0, $a0, $a1   # Compare x and y
        bgtz    $t0, then       # if x > y, goto 'then'
else:   sub     $a1, $a1, $a0   # y = y - x
        b       gcd             # ... and loop all over again
then:   sub     $a0, $a0, $a1   # x = x - y
        b       while           # ... and loop all over again

retx:   or      $v0, $a0, $0    # return x ( $v0 <- $a0)
        jr      $ra

rety:   or      $v0, $a1, $0    # return y ( $v0 <- $a1)
        jr      $ra

Για να το εκτελέσουμε, χρησιμοποιούμε τις εξής εντολές:

        ori     $a0, $0, 1071   # $a0 = 1071
        ori     $a1, $0, 1029   # $a1 = 1029
        jal     gcd             # result is in $a0

Ο R2000 ήταν ένας από τους κομψότερους και ισχυρότερους 32-bit επεξεργαστές της δεκαετίας του 80, επεξεργαστής που «φορούσαν» αρχικά τα workstations της εταιρείας MIPS, αργότερα της Silicon Graphics, και μέχρι σήμερα μια τεράστια σειρά από hardware (routers, ψηφιακές φωτογραφικές μηχανές, RAID arrays, PDAs, κινητά, εκτυπωτές).

Είναι ένας επεξεργαστής με εξαιρετική απλότητα και orthogonality (υπάρχει ένας προφανής τρόπος να κάνεις τα πάντα): έχει 64 εντολές, και του λείπουν μερικές που θεωρούμε βασικές σε CISC assemblies. Πχ, αντί για MOVE πρέπει να χρησιμοποιήσουμε ADD ή OR με το μηδέν ως ένα από τους τελεστέους. Προσωπικά χρησιμοποιώ OR.

Ο Extended Assembler εξομαλύνει την κατάσταση ορίζοντας διάφορα macros (όπως πχ ένα MOVE A, Y που απλά υπολογίζει το A = Y + 0).

[jimm]

sub gcd
{
        my $x = $_[0];
        my $y = $_[1];

        if ($x == 0) { return $y; }
        while ($y) {
                if ($x > $y) { $x -= $y; }
                else { $y -= $x; }
        }
        return $x;
}

Και το τρέχουμε με:

print gcd(1071,1029);

(από το αρχείο που το περιέχει)
Άσκηση για τον αναγνώστη: Βρείτε τις διαφορές με το αντίστοιχο σε C.

Δ.


ΥΓ. Όχι μαμά δεν θέλω να το γράψω σε Java σε παρακαλώ.
ΥΓ2. Ίσως να ήταν καλό να παραθέταμε και footprints των παραπάνω προγραμμάτων.

EDIT: ΥΓ2. Μάλλον δεν είναι καλή ιδέα, δεν είναι και τόσο μεγάλα για να φανεί έντονα η διαφορά. Σε java βέβαια θα φανεί ακόμα κι αν τυπώσουμε Hello world
EDIT2: Όποιος το γράψει σε COBOL θα κερδίσει την Αντριάνα Σκλεναρίκοβα όπως είχαμε πει κάποτε στην megistos-based acro

[alan]

Αρχική Δημοσίευση από jimm EDIT2: Όποιος το γράψει σε COBOL θα κερδίσει την Αντριάνα Σκλεναρίκοβα όπως είχαμε πει κάποτε στην megistos-based acro

Θα κλείσεις σπίτια αν ξεκινήσω να γράφω DISPLAY και PERFORM

[alan]

Ευχαριστώ τον Αλέξη που ξεκίνησε αυτό το θέμα μιας και θα μας δοθεί η ευκαιρία να γράψουμε ένα απλό αλγόριθμο σε όσες γλώσσες έχει τύχει να προγραμματίσουμε.
Η αρχική μας συζήτηση ήταν να γίνει ένας απλός κώδικας τύπου counter 1..100 αλλά θεωρώ πως το πρόβλημα που διάλεξε ο Αλέξης για να το δούμε διεξοδικά είναι πολύ καλύτερο

Αποστόλης

[alan]

Στη ΓΛΩΣΣΟΜΑΘΕΙΑ θα μπορούσε να γραφεί κι έτσι (Θεωρώ έναν βελτιωμένο αλγόριθμο με βάση το mod κι όχι τη διαφορά).

ΠΡΟΓΡΑΜΜΑ ΕΥΚΛΕΙΔΗΣ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Χ, Υ, Ζ

ΑΡΧΗ
  ΔΙΑΒΑΣΕ Χ,Υ
  Ζ<-Υ
  ΟΣΟ Ζ<>0 ΕΠΑΝΑΛΑΒΕ
     Ζ<-Χ MOD Υ
     X<-Y
     Y<-Z
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "ΜΚΔ:",Χ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Η Γλωσσομάθεια διδάσκεται στη Γ'Λυκείου στο μάθημα ΑΕΠΠ (Ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον).
Βέβαια έχω δείξει στους μαθητές μου κι ένα απλό παράδειγμα σε assembly του Ζ80/Spectrum και σε γλώσσα μηχανής από τα 'θρυλικά' βιβλία του Αράπογλου ('80-'85 απ'τα νιάτα μου δηλαδή)

Αποστόλης

[alan]

Αλέξη υποθέτω ξέρεις τι περιμένω να δω...
Κάτι που αρχίζει από BE?????