Τετάρτη 11 Ιουλίου 2018

Ακολουθία Φιμπονάτσι με μεγάλους ακέραιους.

Ενα πρόγραμμα που δημοσίευσα στο www.rosettacode.org
Δείχνει την ακολουθία Φιμπονάτσι από το 1 έως το 4000. Δουλεύει γρήγορα γιατί αποθηκεύει τις τιμές σε μια Κατάσταση (Inventory). Χωρίς την χρήση του αντικειμένου BigNum δεν θα μπορούσαμε να βγάλουμε πάνω από το 139, ενώ τώρα μπορούμε να δώσουμε όσο θέλουμε το όριο. Το αντικείμενο Bignum  προσθέτει αριθμούς χωρίς όριο ψηφίων! Το πετυχαίνει με την χρήση ενός σωρού τιμών (Stack) όπου κάθε τιμή σε αυτόν έχει 14 ψηφία, εκτός από το τελευταίο που μπορεί να έχει λιγότερα. Το τελευταίο στοιχείο έχει τα πιο σημαντικά νούμερα, ενώ το πρώτο έχει τα πρώτα δεκατέσσερα.
Ο σωρός αυξάνεται καθώς προσθέτουμε περισσότερα ψηφία. Έχουμε ορίσει έναν τελεστή "+" που παίρνει δυο αντικείμενα BigNum και εξάγει ένα άλλο.
Επειδή οι σωροί είναι αντικείμενα με δείκτες, το μέλος a κρατάει δείκτη σε αυτό, και στην αντιγραφή αντιγράφεται ο δείκτης. Έτσι όταν εκτελείται η πρόσθεση, το τρέχον (αριστερά του + αντικείμενο) έχει αντιγραφεί, αλλά ο δείκτης στο σωρό πρέπει να αλλαχθεί και να δείχνει ένα αντίγραφο του σωρού. Αυτό το κάνουμε στην αρχή του κώδικα του τελεστή "+".



Η δομή Class (Κλάση) είναι δυο πράγματα:  Περιέχει έναν ορισμό ομάδας, και είναι ταυτόχρονα και συνάρτηση που επιστρέφει την ομάδα που ορίζει. Η δομή αυτή είναι γενική (δηλαδή τη συνάρτηση μπορούμε να την καλέσουμε από οπουδήποτε), εκτός αν βρίσκεται σε ορισμό ομάδας, οπότε είναι μέλος ομάδας (και αυτή μπορεί να είναι γενική ή τοπική).
Δείτε στον ορισμό ότι υπάρχει μια ετικέτα Class: και η οποία διαχωρίζει τα στοιχεία του ορισμού, με το στοιχεία μετά από αυτήν την ετικέτα να χρησιμοποιούνται μόνο μέσα στην συνάρτηση. Στην επιστροφή της ομάδας από τη συνάρτηση γυρνάνε όλα τα μέλη εκτός από αυτά που δόθηκαν μετά την Class: (ή Κλάση:).
Όταν καλούμε την συνάρτηση BigNum() ο διερμηνευτής φτιάχνει πρώτα την βασική ομάδα, και μετά καλεί το τμήμα (module) με το ίδιο όνομα, με την ιδιαιτερότητα ότι κάθε νέο πράγμα που θα κάνουμε εκεί, για την ομάδα, θα μείνει στην ομάδα, και για το λόγο αυτό λέμε το τμήμα αυτό "κατασκευαστή". Όσες τιμές περάσουμε στην συνάρτηση BigNum() θα πάνε σε αυτό το τμήμα στο σωρό τιμών. Αν αφήσουμε τιμές στο σωρό τιμών στο τμήμα, αυτές θα διαγραφούν μετά την επιστροφή της ομάδας. Εδώ αφήνουμε μόνο ένα αλφαριθμητικό με του χαρακτήρες που δηλώνουν τον μεγάλο αριθμό. Η κατασκευή του εσωτερικού σωρού a, γίνεται σε αυτό το σημείο.

Στη Μ2000 τα ονόματα με κεφαλαία-πεζά δεν ξεχωρίζουν (δηλαδή δεν είναι σημαντικό να διατηρούμε τα κεφαλαία ως κεφαλαία, και τα πεζά ως πεζά στις μεταβλητές και στα τμήματα). Επίσης οι τόνοι αφαιρούνται στα ελληνικά γράμματα, και έτσι ονόματα με ίδια γράμματα με ή χωρίς τόνους αναγνωρίζονται ως ίδια. Σε ετικέτες που χρησιμοποιούμε για διακλαδώσεις, έχει σημασία να κρατάμε ως έχει την ετικέτα (με τους τόνους). Οι ετικέτες μετά την πρώτη αναζήτηση και για όσο τρέχει ένα τμήμα βρίσκονται σε χρόνο Ο(1) με ειδική δομή με πίνακα κατακερματισμού. Τα ονόματα τμημάτων/συναρτήσεων/μεταβλητών επίσης βρίσκονται άμεσα. Ουσιαστικά το μέγεθος των ονομάτων παίζει ρόλο, γιατί μικρό μέγεθος δίνει μικρό χρόνο επιστροφής από την συνάρτηση κατακερματισμού. Ο διερμηνευτής εκτελεί άμεσα (ως κείμενο) το κώδικα, γιατί λόγω του εκπαιδευτικού σκοπού για τον οποίο γράφτηκε, έχει την δυνατότητα να δείχνει τον κώδικα όπως τον εκτελεί. Γράψτε το παρακάτω σε ένα τμήμα έστω Α, με την Σ Α ή Edit a, και μετά την έξοδο από το διορθωτή, με Esc, δώστε αντί για το Α ή a το Δοκιμή Α ή Test a. Η φόρμα ελέγχου έχει τρια αριστερά και τρια δεξιά "πλήκτρα". Τα αριστερά δεν φαίνονται ως πλήκτρα γιατί είναι απλά ενδεικτικά για το ποιο τμήμα τρέχει, ποια εντολή και τη συνέχεια της εντολής. Αν επιλέξουμε τη συνέχεια της εντολής διαδοχικά θα εμφανίζεται πότε ο κώδικας και πότε ο σωρός τιμών (κάθε γραμμή κώδικα βλέπει έναν τρέχον σωρό τιμών).


Προσθήκη 21-05-2021
Στην λάμδα συνάρτηση fib() μπορούμε να αλλάξουμε μια γραμμή σε αυτό:
Ret=If(x>1->Lambda(x-1)+Lambda(x-2), Κ(0))
το Κ(0) δίνει το BigNum(0)..Το όνομα BigNum δηλώνεται ως γενική συνάρτηση BigNum(). Αν όμως τερματίσει το τμήμα στο οποίο δημιουργήθηκε η κλάση τότε θα διαγραφεί και ο ορισμός της. Το αντικείμενο της κλάσης όμως μπορεί να υπάρχει ακόμα και αν διαγραφεί ο ορισμός! Νέα αντικείμενα γίνονται και με αντιγραφή. Ο a είναι δείκτης σε σωρό, οπότε το K(0) δίνει τον ίδιο δείκτη στην αντιγραφή, ενώ το BigNum(0) δίνει νέο δείκτη στο a. Παρά αυτή την διαφορά όταν κάνουμε προσθέσεις παράγουμε αντίγραφο του a με την Stack(.a) (που είναι το Stack(This.a), δηλαδή παράγουμε νέο δείκτη με στοιχεία που έχουν αντιγραφεί από το παλιό a. Έτσι το άθροισμα θα έχει νέο δείκτη, διαφορετικό a/
Οι λάμδα συναρτήσεις έχουν δυο ονόματα, εδώ το fib και το fib(). Το πρώτο όνομα είναι η μεταβλητή που κρατάει την λάμδα συνάρτηση, και το δεύτερο είναι η κλήση της συνάρτησης, Με το πρώτο μπορούμε είτε να αλλάξουμε συνάρτηση πχ fib =  αλληλάμδα ή να την επιστρέψουμε πχ =fib  σε μια συνάρτηση, ή να την βάλουμε σε μια άλλη λάμδα όπως βάλαμε το Κ ή να την βάλουμε σε ένα σωρό (stack) ή  σαν τιμή σε ένα στοιχείο πίνακα πχ Πιν(3)=fib οπότε το Πιν(3)(10) είναι ίδιο με το fib(10) ή να το βάλουμε σε μια κατάσταση (inventory ή list ή queue) και να το καλέσουμε πχ Κατ("αβγ")(10).
 


Class BigNum {
      a=stack
      Function Digits {
            =len(.a)*14-(14-len(str$(stackitem(.a,len(.a)) ,"")))
      }
      Operator "+" (n) {
            \\ we get a copy, but .a is pointer
             \\ we make a copy, and get a new pointer
            .a<=stack(.a)
            acc=0
            carry=0
            const d=100000000000000@
                  k=min.data(Len(.a), len(n.a))
                  i=each(.a, 1,k )
                  j=each(n.a, 1,k)
                  while i, j {
                        acc=stackitem(i)+stackitem(j)+carry
                        carry= acc div d
                        return .a, i^+1:=acc mod d
                  }
                  if len(.a)<len(n.a) Then {
                        i=each(n.a, k+1, -1)
                        while i {
                              acc=stackitem(i)+carry
                              carry= acc div d
                              stack .a {data acc mod d}
                        }
                  } ELse.if len(.a)>len(n.a) Then {
                        i=each(.a, k+1, -1)
                        while i {
                              acc=stackitem(i)+carry
                              carry= acc div d
                              Return .a, i^+1:=acc mod d
                              if carry else exit
                        }     
                  }
                  if carry then stack .a { data carry}
      }
      Function tostring$ {
            if len(.a)=0 then ="0" : Exit
            if len(.a)=1 then =str$(Stackitem(.a),"") : Exit
            document buf$=str$(Stackitem(.a, len(.a)),"")
            for i=len(.a)-1 to 1 {
                  Stack .a {
                        buf$=str$(StackItem(i), "00000000000000")
                  }
            }
            =buf$
      }
      class:
      Module BigNum (s$) {
            s$=filter$(s$,"+-.,")
            if s$<>""  Then {
                  repeat {
                        If len(s$)<14 then Stack .a { Data val(s$) }: Exit
                        Stack .a { Data val(Right$(s$, 14)) }
                        S$=Left$(S$, len(S$)-14)
                  } Until S$=""
            }
      }
}

Inventory K=0:=BigNum("0"),1:=BigNum("1")
fib=Lambda K (x as decimal)-> {
      If Exist(K, x) Then =Eval(K) :Exit
      Ret=If(x>1->Lambda(x-1)+Lambda(x-2), bignum(str$(x,"")))
      Append K, x:=Ret
      =Ret
}
\\ Using this to handle form  refresh by code
Set Fast!
For i=1 to 4000 {
      N=Fib(i)
      Print i
      Print N.tostring$()
      Refresh
}

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.