Αυτή είναι η παρουσίαση της λύσης μου για το collatz conjecture, ως μέρος της εργασίας_0 στα πλαίσια του μαθήματος Εισαγωγή στον Προγραμματισμό του τμήματος Πληροφορικής και Τηλεπικοινωνιών του Εθνικού και Καποδιστριακού Πανεπιστημίου Αθηνών. Στην παρουσίαση αυτή περιέχονται διάφορα μεγάλα ή μικρά optimizations τόσο μαθηματικά όσο και αλγοριθμικά που έκανα στην πορεία μου για τον περιορισμό των χρόνων εκτέλεσης.
Στην πορεία μου αυτή πέρασα από μια σειρά διαφορετικών προγραμμάτων των οποίων οι τεχνικές και ο τρόπος λειτουργίας παρατείθονται παρακάτω.
- Πρόγραμμα με while
- Πρόγραμμα με recursion
- Πρόγραμμα με recursion και memoization
- Enhanced πρόγραμμα με while και memoization <== Τελική Υποβολή ~2.9sec στο μέγιστο εύρος [1 , 100.000.000]
Πρωτoύ γίνει παρουσίαση των διάφορων τρόπων λύσης είναι αναγκαίο να γίνουν ορισμένες μαθηματικές παρατηρήσεις και παραδοχές
- Προκειμένου να φτάσει ένας αριθμός n της ακολουθίας στο 1 είναι απαραίτητο να μπεί στην κυκλική ακολοθία 1->2->4 και 4->2->1, η οποία μάλιστα είναι και η μόνη κυκλική ακολουθία που έχει μέχρι πρότινως εντοπισθεί για το Collatz Conjecture
- Δεν μπορούμε να έχουμε δύο διαδοχικούς περιττούς αριθμούς σε ακολουθία Collatz. Kάθε αριθμός 3n+1 είναι άρτιος για nεN, ιδιότητα που μας βοηθάει να μειώσουμε τον αριθμό των υπολογισμών και των βημάτων
- Οι αριθμοί εκείνοι που είναι δυνάμεις του 2 έχουν μήκος ακολουθίας log2(N)+1 (λογάριθμος του 2 +1)
Ουσιαστικά ο απλούστερος τρόπος επίλυσης του προβλήματος. Επιλέγοντας κάθε αριθμό n ανάμεσα στο lower_bound και το upper_bound που δίνοται ως ορίσματα από το command line με ένα απλό iteration με for loop εφαρμόζουμε τον αλγόριθμο του Collatz σε κάθε αριθμό n. Όσο ο αριθμός n δεν γίνεται 1 κρατάμε έναν μετρητή για το πλήθος των βημάτων που απαιτούνται για να φτάσουμε στον άσσο. Μετά από κάθε υπολογισμό των βημάτων και τερματισμό της ακολουθίας συγκρίνουμε τον μετρητή με την τρέχουσα μεγαλύτερη σε μήκος ακολουθία collatz, η οποία συμβολίζεται με max. Αξίζει να σημειωθεί πως ως αρχική τιμή για την μεταβλητή max ορίζεται η τιμή -1, πριν την έναρξη του κύριου for loop. Έπειτα από κάθε υπολογσιμό ακολουθίας Collatz, ο μετρητής των βημάτων μηδενίζεται για τον επόμενο αιρθμό. Η προσέγγιση αυτή, αν και χρονικά περίπλοκη αποτελεί σε γενικές γραμμές την ραχοκοκαλιά και των παρακάτω προσεγγίσεων
Σύντομα παρατίθεται ο κώδικας της πρώτης υλοποίησης
for(i=lower_bound; i<=upper_bound; i++)
{
count=0;
while(num!=1)
{
if(num%2==0)
{
num=num/2;
}
else
{
num=3*num+1;
}
count++;
}
if(count > max)
{
max=count;
}
} Η ακολουθία του Collatz αποτελεί κλασσικό παράδειγμα προβλημάτος που η επίλυση του μπορεί να προέλθει από την επίλυση επιμέρους απλούστερων προβλημάτων και του συνδυασμού των λύσεων αυτών. Άλλωστε στην ίδια κατηγορία συμπέφτουν και άλλα προβλήματα όπως ο υπολογισμός αριθμών Fibonacci ή του παραγοντικού. Με παρόμοιο τρόπο λοιπόν που υλοποιήθηκε ο υπολογισμός παραγοντικού μέσω αναδρομής στην δεύτερη διάλεξη με τον κύριο Αυγερινό, μπορούμε και εμείς να προσεγγίσουμε το Collatz Conjecture. Έτσι δημιουργούμε μια αναδρομική συνάρτηση που παίρνει ως όρισμα έναν αριθμό num. Ως base case ορίζουμε πως εάν num==1 τότε return 1. Για κάθε άλλη περίπτωση πριν προσεγγίσουμε το 1 εφαρμόζουμε την ακολουθία Collatz. Συγκεκριμένα εάν num%2==0 δηλαδή ο αριθμός num είναι άρτιος κάνουμε return 1+ collatz(num/2). Στην άλλη περίπτωση που ο αριθμός είναι περιττός απλά κάνουμε return 1 + collatz(3*num+1)
int collatz(long long int num){
if(num==1)
{
return 1;
}
else if(num%2==0)
{
return 1+collatz(num/2);
}
else
{
return 1+collatz((3*num+1));
//return 2+collatz((3*num+1)/2);
}
}Και η αναδρομική συνάρτηση collatz καλείται μέσω της main ως εξής:
for(i=lower_bound; i<=upper_bound; i++)
{
count=collatz(i);
if(count > max)
{
max=count;
}
}Αξιοποιώντας την δεύτερη παρατήρηση που παρατίθεται στην αρχή της σελίδας παρατηρούμε ότι μπορούμε να μειώσουμε δραστικά της κλήσεις της συνάρτησης collatz, εάν όταν συναντάμε περιττό αριθμό δεν καλούμε την συνάρτηση collatz με όρισμα το 3*num+1, αλλά με το (3*num+1)/2. Παραλείποντας δηλαδή ένα βήμα που ήταν δεδομένο ότι θα έπρεπε να διασχίσουμε. Εφαρμόζοντας αυτή την τεχνική θα πρέπει όμως να επιστρέφουμε 2+recur((3*num+1)/2),αντί για 1+collatz((3*num+1)); , που το +1 προκύπτει από το επιπλέον εκείνο βήμα που προσπεράσαμε.
Μετά την εφαρμογή της ακολουθίας Collatz με το χέρι σε διάφορα παραδείγματα συνειδητοποίησα το εξής: Συνέχεια ασχολούμαστε με τους ίδιους αριθμούς. Οι ίδιοι αριθμοί και ακολουθίες επανεμφανίζονται συνεχώς κατά των υπολογισμό των βημάτων ενός αριθμού προς τον άσσο. Γι' αυτό και θα πρέπει προκειμένου να μην κάνουμε περιττούς υπολογισμούς να δημιουργήσουμε μια δομή δεδομένων, στην περίπτωση μας ένα array που θα υπολογίζει πόσα βήματα χρειάστηκε ο αριθμός num να φτάσει στο 1 και θα συμβολίζεται ως memo[num]. Έτσι εάν γνωρίζω ότι το 100 χρειάζεται x iterations μέχρι να φτάσει στο 1 είναι προφανές ότι το 200 θα χρειάζεται x+1 iterations. Και έτσι καταφέρνουμε να υπολογίσουμε το πλήθος βημάτων του 200 χωρίς καν να κάνουμε πράξεις!(σχεδόν). Πρόκειται λοιπόν για την χρήση δυναμικού προγραμματισμού, προκειμένου να επωφεληθούμε απο προηγούμενες τιμές που υπολογίσαμε. Η υλοποίηση είναι η ίδια με μόνη διαφορά πως κάθε φορά που καλούμε την αναδρομική συνάρτηση collatz το τελικό αποτέλεσμα της συνάρτησης αποθηκεύεται στην θέση i του πίνακα, όπου i ο αριθμός πάνω στον οποίο ξεκινήσαμε να εφαρμόζουμε την ακολουθία Collatz. Ακόμη τροποποίησης χρήζει και η συνάρτηση collatz έτσι ώστε να μπορεί να καταλαβαίνει εάν μπορεί η όχι να ανακτήσει μια προηγουμένως υπολογσμένη τιμή του πίνακα. Στο πρόγραμμά μας ορίζουμε έναν global πίνακα memo 100.000.000 θέσεων με όλες τις αρχικές τιμές μηδενισμένες.
Σύντομα παρατίθεται ο κώδικας της τρίτης υλοποίησης
int collatz(long long int num)
{
if(num%2==0)
{
if(num<=100000000 && memo[num]!=0)
{
return memo[num];
}
else
{
return 1+collatz(num/2);
}
}
else
{
if(num<=100000000 && memo[num]!=0)
{
return memo[num];
}
else
{
return 2+collatz((3*num+1)/2);
}
}
}Και η αναδρομική συνάρτηση collatz καλείται μέσω της main ως εξής:
for(i=lower_bound; i<=upper_bound; i++)
{
count=memo[i]=collatz(i);
if(count > max)
{
max=count;
}
}Σημαντικό μειονέκτημα αυτής της λύσης είναι το εξής: Κατά την δημιουργία του πίνακα memoization ξεκινάμε να βάζουμε τιμές από την θέση lower_bound και μετά.Αυτή η προσέγγιση κάνει το πρόγραμμα εκπληκτικά αργό σε περιπτώσεις όπου το lower_bound είναι μεγάλος αριθμός. Παραδείγματος χάρην το συγκεκριμένο πρόγραμμα απαιτεί σχεδόν δεκαπλάσιο χρόνο να βγάλει αποτέλεσμα για το case [50.000.000 , 100.000.000] από ότι για το case [100 , 100.000.000]. Αυτό συμβαίνει διότι δεν γεμίζουμε τον πίνακα memo από την βάση του με αποτέλεσμα να είναι partially γεμάτος και όχι ιδιαίτερα λειτουργικός.
Λύση σε αυτό το παραπάνω πρόβλημα έδωσε η τελευταία έκδοση του προγράμματος, που αποτέλεσε και την τελική μου υποβολή, αφού δεν μπόρεσα να βρω καμία επιπλέον βελτιστοποίηση.
Το πρόγραμμα σε γενικές γραμμές ακολουθεί περίπου την ίδια φιλοσοφία με τα προηγούμενα, πλην μερικών μικρών αλλά χρονικά σημαντικών αλλαγών. Καταρχήν η αναδρομική συνάρτηση collatz υλοποιήται πλέον μέσω βρόχου while, ο οποίος φαίνεται να είναι πιο γρήγορος και να έχει μικρότερες απαιτήσεις μνήμης από την αναδρομική προσέγγιση. Ακόμη η συνθήκη της while είναι το 1 και συνεπώς είναι πάντοτε αληθής, οπότε βασιζόμαστε σε συγκεκριμένα break statements που τερματίζουν αυτόν τον φαινομενικά ατέρμων βρόχο. Συγκεκριμένα το πρόγραμμα τερματίζει μόλις βρει έναν άρτιο αριθμό του οποίου τα βήματα προς το 1 έχουν ήδη υπολογιστεί. Επιπλέον σημαντική βελτιστοποίηση αποτελεί το γεγονός ότι σε αυτή την έκδοση του προγράμματος τα βήματα Collatz υπολογίζονται από το 1 μέχρι και το upper_bound, αντί για από το lower_bound μέχρι το upper_bound, όπως στην προηγούμενη έκδοση. Επειδή αυτή η προσέγγιση δεν θα μπορούσε να ενσωματώσει την εύρεση των μέγιστων βημάτων λόγω διαφορετικού εύρους αριθμών εντός του βασικού βρόχου for, η διαδικασία αυτή πραγματοποιείται εκτός του κύριου βρόχου for. Τέλος καίριας σημασίας είναι και η αλλαγή των συνθηκών υπό τις οποίες το πρόγραμμα αντλεί προηγούμενες τιμές βημάτων. Στην τελευταία έκδοση βλέπουμε ότι χρησιμοποιείται η εντολή num μικρότερο i αντι για num μικρότερο ή ίσον 100.000.000 και memo[num]!=0. Αυτός ο νέος έλεγχος αρκεί για την περίπτωση μας διότι γνωρίζουμε ότι για κάθε θέση του array που είναι μικρότερη από το i πρέπει ήδη να έχει καταχωρηθεί ένας αριθμός βημάτων, αφού τρέχουμε την ακολυθία Collatz σειρακά σε όλους τους αριθμούς από το 2 και μετά!(Να σημειωθεί πως πριν τους βρόχους γίνεται η εντολή ανάθεσης memo[1]=1; και έτσι έχουμε το δικαίωμα να ξεκινήσουμε από το 2).
Ακόμη βλέπουμε πως παραλείπεται ο έλεγχος για την χρήση του πίνακα memo στις περιπτώσεις όπου έχουμε περιττό αριθμό. Αυτό γίνεται αντιληπτό αν αξετάσουμε τις 2 ακόλουθες περιπτώσεις.
1η Περίπτωση: Έστω ότι ξεκινάμε από έναν αριθμό num και τυχαίνει να είναι περιττός, τότε μέσω της μαθηματικής παρατήρησης που κάναμε ο επόμενος αριθμός θα είναι ο (3*num+1)/2 ο οποίος θα είναι σίγουρα μεγαλύτερος του αρχικού num και οπότε δεν θα έχει νόημα να ανατρέξουμε στο memo[num] αφού σίγουρα θα είναι μηδέν. Αν πάλι ο αριθμός που παίρνουμε ως αποτέλεσμα του προηγούμενου βήματος είναι περιττός τότε ο αλγόριθμος σίγουρα θα μας επιστρέψει μεγαλύτερο αριθμό, οπότε πάλι δεν χρειάζεται να ελέγξουμε για τον πίνακα memo και ούτο καθεξής. Βέβαια εάν ο αντίστοιχος καινούριος αριθμός είναι άρτιος τότε στο επόμενο itεrration θα μπούμε στο else και θα ελέγξουμε για την ύπαρξη του memo[num], γιατί μόνον τότε υπάρχει η πιθανότητα να είναι το num μικρότερο από το i.
2η περίπτωση:Έστω ότι ο αριθμός που εξετάζουμε είναι από την αρχή άρτιος, τότε δεν θα χρησιμοποιηθεί καν το τμήμα του αλγορίθμου που αφορά τους περιττούς αφού ο νέος αριθμός num/2 θα είναι μικρότερος του αρχικού num και συνεπώς θα μπορούμε να αντλήσουμε από τον πίνακα τα βήματά του, ανεξαρτήτως εάν ο num/2 είναι άρτιος ή περιττός.
for(i=2; i<=upper_bound; i++)
{
count=0;
num=i;
while(1)
{
if(num & 1)
{
num=(3*num+1);
num>>=1;
count=count +2;
/*
if(num<i)
{
count=count+memo[num]+1;
break;
}
*/
}
else
{
num>>=1;
if(num<i)
{
count=count+memo[num]+1;
break;
}
count++;
}
}
memo[i]=count;
}Η εύρεση του μέγιστου αριθμού βημάτων πραγματοποιείται μέσω του κατώθι βρόχου. Προσέξτε πως εάν κρατούσαμε την διαδικασία εύρεσης max μέσα στο βασικό for loop, τότε θα υπήρχε η πιθανότητα να λάβουμε λάθος αποτέλεσμα στην σπάνια αλλά όχι απίθανη περίπτωση που υπάρχει ένας αριθμός μικρότερος του lower_bound που παράγει μεγαλύτερη σε μήκος ακολουθία Collatz από κάθε άλλο αριθμό εντός του εύρους [lower_bound,upper_bound].
for(i=lower_bound; i<=upper_bound; i++)
{
if(max<memo[i])
{
max=memo[i];
}
}- Κατά την δημιουργία του πίνακα για να εφαρμόσω το memoization παρατήρησα το εξής: Πολλοί αριθμοί και μάλιστα διαδοχικοί είχαν ακριβώς τον ίδιο αριθμό βημάτων προκειμένου να φτάσουν στο 0. Πιθανώς να υπάρχει κάποιο μοτίβο ανάμεσα στους αριθμούς και τις ακολουθίες που δημιουργούν για να μην κάνουμε τζάμπα παραπάνω υπολογισμούς
- Οι αριθμοί στα βήματα της ακολουθίας Collatz αυξάνονται εκθετικά μετά από έναν βαθμό με αποτέλεσμα να γίνεται overflow στην μεταβλητή int που αποθηκεύουμε αυτούς τους αριθμούς. Για να αποφύγουμε αυτό το πρόβλημα μία γρήγορη λύση είναι να να χρησιμοποιούμε long long int μεταβλητή για να καρατάμε τους αριθμούς. Ωστόσο η χρήση μεταβλητών 64 bit καθυστερεί το πρόγραμμα αισθητά ~1 sec λόγω της μεταγλώττισης με -m32. Πιθανώς να μπορούσαμε να αποθηκεύαμε το τους αριθμούς collatz μέσα σε 2 32bit μεταβλητές και να προσομοιάζαμε τις πράξεις της διαίρεσης κατά 2 και πολλαπασιασμού επί 3 +1 μέσω bitwise τελεστών.
- Πιθανώς σε ακραίες περιπτώσεις, όπως αυτή όπου για input δίνοται οι αριθμοί 90.000.000 και 90.000.001 το πρόγραμμα με το while να εκτελείται πολύ πιο γρήγορα από το πρόγραμμα με το memoization. Αυτό συμβαίνει διότι στην περίπτωση του memoization πρέπει να υπολογίσουμε την ακολουθία collatz για όλους τους αριθμούς μέχρι το upper_bound, ενώ στο while υπολογίζουμε μόνο για αριθμούς num που βρίσκοται στο εύρος [lower_bound,upper_bound]. Ίσως σε μια επόμενη έκδοση του προγράμματος να μπορούσαμε ανάλογα με τις εισόδους να έχουμε μια δυναμική προσέγγιση του αλγορίθμου που θα ακολουθήσουμε.