Send a PR on GitHub

progintro @ dit

Μέθοδος επίλυσης άσκησης 3 της εργασίας hw0

Για να επιλύσουμε το πρόβλημα, εργαζόμαστε ως εξής:

  1. Δημιουργούμε κώδικα για την εικασία του Collatz για έναν αριθμό.
  2. Τον τροποποιούμε, ώστε το αποτέλεσμα να είναι το μήκος της εικασίας.
  3. Τον τροποποιούμε, ώστε αυτό να γίνεται για ένα εύρος αριθμών.
  4. Βρίσκουμε το μεγαλύτερο από τα παραπάνω μήκη.

Έτσι, θα θεωρήσουμε δεδομένη μία συνάρτηση Collatz(N) που υλοποιεί την εικασία του Collatz για έναν αριθμό N και επιστρέφει το μήκος αυτής. Θα την κατασκευάσουμε αργότερα. Στη συνάρτηση main, δεχόμαστε έναν αριθμό N με χρήση argc/ argv, όπως μάθαμε στις διαλέξεις και καλούμε τη συνάρτηση Collatz για αυτόν τον αριθμό. Για να εκτελέσουμε τη συνάρτηση Collatz για ένα εύρος αριθμών, έστω από 1 μέχρι 10, δεν έχουμε παρά να καλέσουμε τη συνάρτηση για κάθε αριθμό από 1 μέχρι 10. Άρα θα χρησιμοποιήσουμε μία εντολή for ως εξής: for(int i=1; i<=10; ++i) (Το ++i είναι λίγο γρηγορότερο από το i++). Άρα, αν το εύρος ήταν από start μέχρι end θα γράφαμε: for(int i=start; i<=end; ++i). Πρώτα, όμως, θα πρέπει να έχουμε σιγουρευτεί πως οι αριθμοί μας είναι θετικοί: if (start<=0 || end<=0) printf(“0”);. Διαφορετικά, συνεχίζουμε τη for και το αποτέλεσμα της συνάρτησης, το αποθηκεύουμε σε μία μεταβλητή length:

if(start<=0 || end<=0) printf("0");
else{
    for(int i=start; i<=end; ++i){
        int length = Collatz(i);
    }
}

Εμείς θέλουμε να υπολογίζουμε το μέγιστο μήκος, έστω maxl. Τα μήκη δεν χρειάζεται να τα αποθηκεύσουμε κάπου, γιατί δεν μας χρειάζονται πουθενά, εκτός από το τελευταίο μήκος, το οποίο συγκρίνουμε κάθε φορά με το maxl, το οποίο αρχικοποιούμε ως 0, αφού πάντοτε το μήκος θα είναι τουλάχιστον 1 (και έτσι το maxl θα πάρει την τιμή του πρώτου length στην πρώτη επανάληψη) και έτσι έχουμε:

if (start<=0 || end<=0) printf("0");
else{
    int maxl = 0;
    for(int i=start; i<=end; ++i){
        int length = Collatz(i);
        maxl = (length>maxl) ? length : maxl;
    }
    printf("%d\n", maxl);
}

Μαζί με τις εντολές εισόδου, η main μας μοιάζει κάπως έτσι:

int main(int argc, char **argv){

    if(argc != 3){
        printf("Program needs to be called as `./collatz start end`\n");
        return 1;
    } 

    int start = atoi(argv[1]);
    int end = atoi(argv[2]);

    if(start<=0 || end<=0) printf("0");
    else{
        int maxl = 0;
        for(int i=start; i<=end; ++i){
            int length = Collatz(i);
            maxl = (length>maxl) ? length : maxl;
        }
        printf("%d\n", maxl);
    }

    return 0;
}

Τώρα, θα προσπαθήσουμε να φτιάξουμε τη συνάρτηση Collatz, που όπως είπαμε παραπάνω θα ξεκινάει ως εξής: int Collatz(int N){} Αρχικά σκεφτόμαστε πώς θα αλλάζει το N. Αν είναι περιττός (N%2==1 ή N%2==true ή N%2) N=3*N+1, αλλιώς N/=2. Αυτό θα επαναλαμβάνεται ώσπου το N να γίνει 1. Θα μπορούσαμε να χζρησιμοποιήσουμε do{}while() αλλά στην περίπτωση που N=1 δεν θέλουμε να κάνει καμία πράξη, δηλαδή να μην μπει στον βρόχο. Άρα θα χρησιμοποιήσουμε while. Η συνάρτηση επιστρέφει το μήκος, άρα χρησιμοποιούμε μία μεταβλητή length, που σε κάθε επανάληψη της while αυξάνεται κατά 1. Επειδή στο τέλος το length δεν έχει συμπεριλάβει το 1, θα αυξήσουμε το length κατά 1, καθώς το επιστρέφουμε. Σύμφωνα με τα παραπάνω, συνάρτηση μοιάζει κάπως έτσι:

int Collatz(int N){
    int length = 0;
    while(N!=1){
        N = (N%2) ? 3*N+1 : N/2;
        length++;
    }
    return length+1;
}

…και προκύπτει και η λύση:

#include <stdio.h>
#include <stdlib.h>

int Collatz(int N){
    int length = 0;
    while(N!=1){
        N = (N%2) ? 3*N+1 : N/2;
        length++;
    }
    return length+1;
}

int main(int argc, char **argv){

    if(argc != 3) {
        printf("Program needs to be called as `./collatz start end`\n");
        return 1;
    } 

    int start = atoi(argv[1]);
    int end = atoi(argv[2]);

    if(start<=0 || end<=0) printf("0");
    else{
        int maxl = 0;
        for(int i=start; i<=end; ++i){
            int length = Collatz(i);
            maxl = (length>maxl) ? length : maxl;
        }
        printf("%d\n", maxl);
    }

    return 0;
}

Η παραπάνω λύση, όμως, είναι πολύ αργή. Γι’ αυτό, θα χρειαστεί να “πειράξουμε” τη συνάρτηση Collatz. Μία σκέψη είναι η χρήση της αναδρομής για να αποφύγουμε τη while, με τη συνάρτηση να μοιάζει κάπως έτσι:

int Collatz(int N, int length){
    if(N==1) return length+1;
    else{
        N = (N%2) ? 3*N+1 : N/2;
        length++;
        return Collatz(N, length);
    }
}

*Να σημειώσουμε πως αναγκαστικά αλλάξαμε τα ορίσματα της συνάρτησης, γιατί ο τερματισμός της εξαρτάται από την τιμή του length. Όμως δημιουργήθηκε ένα πρόβλημα: Κάθε φορά που η συνάρτηση καλεί τον εαυτόν της, αυξάνεται μία στοίβα επιστροφής (call stack). Η στοίβα αυτή, φυσικά, έχει πεπερασμένο μέγεθος, επομένως μία συνάρτηση δεν μπορεί να καλεί τον εαυτόν της επ’ άπειρον. Στο πρόβλημά μας, η αναδρομή δεν δουλέυει, καθώς για αριθμούς της τάξης του 100,000,000 η στοίβα επιστροφής υπερχειλίζει με αποτέλεσμα να παίρνουμε “Σφάλμα κατάτμησης” (segmentation fault - segfault).

Άρα πρέπει να σκεφτούμε μία λύση, με την οποία θα γλυτώνουμε κάποιες επαναλήψεις από την αρχική while. Εδώ θα μας βοηθήσει ο Δυναμικός Προγραμματισμός και η τεχνική Memoization (https://en.wikipedia.org/wiki/Memoization). Με απλά λόγια, παρατηρούμε πως κάθε φορά που εξετάζεται το μήκος ενός νέου αριθμού στο ζητούμενο εύρος, υπολογίζεται ξανά η εικασία του Collatz για αριθμούς που έχουμε ξαναβρεί ήδη σε προηγούμενους αριθμούς. Π.χ. τα αποτελέσματα για N=5 θα ήταν τα εξής: {5, 16, 8, 4, 2, 1}, μήκους 6. Όμως η εικασία θα έχει ήδη υπολογιστεί προηγουμένως για τους αριθμούς 4, 2 και 1 οπότε θα μπορέσουμε να αποφύγουμε κάποιες επαναλήψεις, αποθηκεύοντας το μήκος κάθε αριθμού σε έναν πίνακα lengths, αρχικοποιημένο με 0 (θα αυξήσουμε το μέγεθος του προγράμματος για να βελτιώσουμε τον χρόνο). Η λογική είναι πως αν στη συνάρτηση προκύψει αριθμός που έχει υπολογιστεί ήδη (lengths[n]!=0), το συνολικό length αυξάνεται κατά το length αυτού του αριθμού (length+=lengths[n]) και η while τερματίζει (break). Στο τέλος, θα αποθηκεύουμε στον πίνακα το μήκος του αριθμού για τον οποίο κλήθηκε η συνάρτηση, ώστε να επαναχρησιμοποιηθεί σε μετέπειτα αριθμούς. Ο κώδικας θα διαμορφωθεί ως εξής:

int lengths[100000001];

int Collatz(int N){
    int length=0;
    long long n=N;
    while (n!=1){
        if (n<=N && lengths[n]!=0) {
            length+=lengths[n];
            break;
        }
        n = (n%2) ? 3*n+1 : n/2;
        length++;
    }
    lengths[N]=length;
    return length+1;
}

Περαιτέρω εξήγηση: Ο πίνακας έχει 100,000,001 θέσεις, δηλαδή από 0 έως 100,000,000, γιατί κάθε φορά αποθηκεύουμε στη θέση του αριθμού που υπολογίζουμε, ο οποίος μπορεί να είναι μέχρι και το 100,000,000. Επειδή θέλουμε να κρατήσουμε τον αρχικό αριθμό, μετά την τροποποίησή του, αυτή θα γίνει μέσω μίας άλλης μεταβλητής, τύπου long long, καθώς μπορεί να πάρει τιμές που υπερβαίνουν τα όρια του τύπου int. Στην if, δεν θα πρέπει να ξεχάσουμε να ελέγξουμε ο προκύπτων αριθμός να μην υπερβαίνει τον αρχικό, αφού εξετάζουμε μήκη στο εύρος των αριθμών που δόθηκε (<=N), ενώ το n μπορεί να πάρει τιμές μέχρι και 3*N+1 (>Ν). Σε αυτό το σημείο, να τονίσουμε πως στη C, σε έναν λογικό έλεγχο τύπου a&&b, αν a=false, ο compiler δεν μπαίνει καν στη διαδικασία να εξετάσει το b. Αν δεν γινόταν αυτό, θα ερχόμασταν αντιμέτωποι με ένα νέο πρόβλημα, πως ίσως το n να είναι μεγαλύτερο του 100,000,000, οπότε θα είχαμε segfault, καθώς θα επιχειρούσαμε πρόσβαση σε θέση του πίνακα που δεν έχουμε δεσμεύσει (>100,000,001).

Έτσι, καταλήγουμε στην τελική λύση:

#include <stdio.h>
#include <stdlib.h>

int lengths[100000001];

int Collatz(int N){
    int length=0;
    long long n=N;
    while (n!=1){
        if (n<=N && lengths[n]!=0) {
            length+=lengths[n];
            break;
        }
        n = (n%2) ? 3*n+1 : n/2;
        length++;
    }
    lengths[N]=length;
    return length+1;
}

int main(int argc, char **argv){

    if(argc != 3){
        printf("Program needs to be called as `./collatz start end`\n");
        return 1;
    } 
    int start = atoi(argv[1]);
    int end = atoi(argv[2]);

    if(start<=0 || end<=0) printf("0");
    else{
        int maxl = 0;
        for(int i=start; i<=end; ++i){
            int length = Collatz(i);
            maxl = (length>maxl) ? length : maxl;
        }
        printf("%d\n", maxl);
    }

    return 0;
}

Ταχύτερη λύση εκμεταλλευόμενοι κάποια “δοσμένα νούμερα”: Τροποποιώντας τον παραπάνω αλγόριθμο, μπορούμε να ελαχιστοποιήσουμε τις πράξεις που εκτελούνται. Συγκεκριμένα, σύμφωνα με το λήμμα της Βικιπαίδειας για την εικασία του Collatz (https://en.wikipedia.org/wiki/Collatz_conjecture#Empirical_data), μπορούμε εκ των προτέρων να γνωρίζουμε τον αριθμό που περιέχεται σε ένα εύρος αριθμών, που δίνει το μεγαλύτερο μήκος (ακολουθία A006877 στην OEIS - https://oeis.org/A006877/b006877.txt). Στην ακολουθία, μας ενδιαφέρουν μόνο οι 61 πρώτοι όροι, καθώς ο 61ος όρος είναι ο πρώτος που ξεπερνάει το όριου των 100,000,000.

int max_lengths[61]=
    {1,2,3,6,7,9,18,25,27,54,73,97,129,171,231,313,
    327,649,703,871,1161,2223,2463,2919,3711,6171,
    10971,13255,17647,23529,26623,34239,35655,52527,
    77031,106239,142587,156159,216367,230631,410011,
    511935,626331,837799,1117065,1501353,1723519,
    2298025,3064033,3542887,3732423,5649499,6649279,
    8400511,11200681,14934241,15733191,31466382,36791535,
    63728127,127456254}; //oi arithmoi me to amesos epomeno megalitero length (61 stoiheia)

Υπολογίζουμε και αποθηκεύουμε σε έναν ακόμα πίνακα τα μήκη του καθενός από τους παραπάνω αριθμούς.

int collatz[61]=
    {1,2,8,9,17,20,21,24,112,113,116,119,122,125,128,131,144,145,171,179,182,183,209,217,238,
    262,268,276,279,282,308,311,324,340,351,354,375,383,386,443,
    449,470,509,525,528,531,557,560,
    563,584,597,613,665,686,689,692,705,706,745,950,951}; //ta collatz ton parapano

Αν, λοιπόν, το εύρος μας περιλαμβάνει κάποιον από τους αριθμούς του max_lengths, βρίσκουμε τον μεγαλύτερο εξ αυτών και το μήκος του είναι και το μεγαλύτερο μήκος στο συγκεκριμένο εύρος και το ζητούμενο έπεται.

int max;
for(int i=0; i<61; ++i){
    if(end<max_lengths[i]){
        max=i-1;
        break;
    }
}
printf("%d\n", collatz[max]);

Αν, όμως, το εύρος μας δεν περιλαμβάνει κάποιον, τότε εκτελούμε κανονικά την εικασία όπως προηγουμένος, με memoization. Έτσι, προκύπτει ο κώδικας:

int max;
for(int i=0; i<61; ++i){
    if(end<max_lengths[i]){
        max=i-1;
        break;
    }
}
        
if(start>max_lengths[max]){
    int maxl = 0;
    for(int i=start; i<=end; ++i){ 
        int length = Collatz(i);
        maxl = (length>maxl) ? length : maxl;
    }
    printf("%d\n", maxl);
}
else printf("%d\n", collatz[max]);

Μία τελευταία τροποποίηση που μπορούμε να κάνουμε εκμεταλλευόμενοι κάποιους έτοιμους αριθμούς, είναι να βοηθήσουμε το memoization. Συγκεκριμένα, ο πίνακας lengths έχει τη χρήση να μη χρειάζεται να υπολογίσει κάποιο μήκος που έχει ήδη υπολογιστεί πρωτύτερα. Βάζοντας κάποια μήκη αυτούσια, ελαττώνουμε τις πράξεις που θα χρειαστούν. Στη βικιπαίδεια, συναντούμε επίσης και την ακολουθία A006577. Στο https://oeis.org/A006577/b006577.txt υπάρχουν έτοιμα τα μήκη (μειωμένα κατά 1) για τους πρώτους 10,000 αριθμούς. Επομένως, θέτουμε αυτόυς τους αριθμούς στις πρώτες 10,000 θέσεις του πίνακα lengths και πλέον έχουμε μία γρήγορη λύση χάρη στις ακολουθίες που χρησιμοποιήσαμε έτοιμες.