Αριθμητική υπερχείλιση
Στα ψηφιακά ηλεκτρονικά και στην επιστήμη των υπολογιστών (κυρίως στον προγραμματισμό), αριθμητική υπερχείλιση ή απλούστερα υπερχείληση συμβαίνει όταν μια αριθμητική πράξη επιχειρεί να δημιουργήσει μια αριθμητική τιμή η οποία είναι πάρα πολύ μεγάλη για να αναπαρασταθεί εντός του διαθέσιμου χώρου αποθήκευσης (καταχωρητής ή μνήμη υπολογιστή). Δηλαδή όταν δύο αριθμοί, ο καθένας ν ψηφίων, προστίθενται και το άθροισμα καταλαμβάνει ν+1 ψηφία, τότε έχουμε υπερχείλιση.[1] Ένα πολύ συχνό σφάλμα που προκαλεί υπερχείλιση είναι υπολογίζοντας το αριθμητικό μέσο δύο αριθμών, προσθέτοντάς τους και μετά διαιρώντας τους με το δύο, όπως συμβαίνει στους περισσότερους αλγόριθμους αναζήτησης. Το σφάλμα υπερχείλισης προκαλείται στο άθροισμα (και όχι στον μέσο) το οποίο μπορεί να υπερβαίνει το μέγεθος της μνήμης.[2]
Υπερχείλιση[Επεξεργασία | επεξεργασία κώδικα]
Το μέγεθος του καταχωρητή ενός επεξεργαστή προσδιορίζει το εύρος των τιμών που μπορούν να αναπαρασταθούν. Τα συνήθη μεγέθη σε δυαδικούς καταχωρητές είναι:
- 8 bits: μέγιστη τιμή που μπορεί να αναπαρασταθεί 28 − 1 = 255
- 16 bits: μέγιστη τιμή που μπορεί να αναπαρασταθεί 216 − 1 = 65,535
- 32 bits: μέγιστη τιμή που μπορεί να αναπαρασταθεί 232 − 1 = 4,294,967,295 (το συνηθέστερο πλάτος στους προσωπικούς υπολογιστές μέχρι το 2005),
- 64 bits: μέγιστη τιμή που μπορεί να αναπαρασταθεί 264 − 1 = 18,446,744,073,709,551,615 (το συνηθέστερο πλάτος στους προσωπικούς υπολογιστές, αλλά όχι απαραίτητα και για τα λειτουργικά τους συστήματα, μέχρι και το 2014),
- 128 bits: μέγιστη τιμή που μπορεί να αναπαρασταθεί 2128 − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455
Επειδή μια αριθμητική πράξη μπορεί να έχει ως αποτέλεσμα έναν αριθμό μεγαλύτερο από την μέγιστη τιμή που μπορεί να αναπαρασταθεί, μπορεί να προκληθεί σφάλμα.
Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]
- ↑ Morris Mano. Ψηφιακή σχεδίαση. ISBN 960-7530-63-2.
- ↑ Google Research blog: Nearly All Binary Searches and Mergesorts are Broken, Joshua Bloch, 2 June 2006