Big numbers και computers

[wooded glade]

The largest known prime number (as of December 2020) is 2^82,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.

Πως τα υπολογίζουν αυτά ;
Κάποιοι ενδιάμεσοι μαθηματικοί τύποι υπάρχουν οπωσδήποτε, αλλά η vb με double precision -που δεν παρέχει ακρίβεια- φτάνει μέχρι αριθμούς με 309 ψηφία. Δεν πάει παραπάνω.

Εγώ θέλω να υπολογίσω με ακρίβεια ακεραίους που να φτάνουν μέχρι το 10^18. Πως γίνεται ;

[klg]

http://www.numberworld.org/y-cruncher/

[nick]

The largest known prime number (as of December 2020) is 2^82,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.

Πως τα υπολογίζουν αυτά ;
Κάποιοι ενδιάμεσοι μαθηματικοί τύποι υπάρχουν οπωσδήποτε, αλλά η vb με double precision -που δεν παρέχει ακρίβεια- φτάνει μέχρι αριθμούς με 309 ψηφία. Δεν πάει παραπάνω.

Εγώ θέλω να υπολογίσω με ακρίβεια ακεραίους που να φτάνουν μέχρι το 10^18. Πως γίνεται ;

το primality test ειναι πολυ ευκολο

Given an integer n, choose some integer a coprime to n and calculate a^n − 1 modulo n. If the result is different from 1, then n is composite. If it is 1, then n may be prime.

https://en.wikipedia.org/wiki/Primality_test

δηλαδη αν 2^(n-1) mod n=1 τοτε πολυ πιθανο to n ειναι prime.
δοκιμαζεις και το 3^(n-1), 4^(n-1) ... να εισαι 99.999999... σίγουρος.
Αυτες οι πραξεις ειναι πολυ γρήγορες.
https://en.wikipedia.org/wiki/Modular_exponentiation

Σε πολλες γλωσσες υπαρχει η κλαση BigInteger που υποστηριζει αριθμους με εκατομμυρια ψηφια.

[Awesomatic]

Short version: Από ένα σημείο και μετά έχεις περιορισμό και από το σύστημα εκτός από τη γλώσσα. Η VB6 (που αν θυμάμαι καλά χρησιμοποιείς) δεν μπορεί να το κάνει αυτό. Αν θέλεις πολύ μεγάλους αριθμούς μπορεί να γίνει σε 64bit σύστημα με python ή Java (το τελευταίο για όσους έχουν ανώμαλες τάσεις)

[nick]

Short version: Από ένα σημείο και μετά έχεις περιορισμό και από το σύστημα εκτός από τη γλώσσα. Η VB6 (που αν θυμάμαι καλά χρησιμοποιείς) δεν μπορεί να το κάνει αυτό. Αν θέλεις πολύ μεγάλους αριθμούς μπορεί να γίνει σε 64bit σύστημα με python ή Java (το τελευταίο για όσους έχουν ανώμαλες τάσεις)

μιλαμε για πολυ μεγαλυτερους αριθμους απο 2^32 ή 2^64.

https://docs.oracle.com/javase/7/docs/a ... teger.html
https://docs.microsoft.com/en-us/dotnet ... ew=net-5.0
https://levelup.gitconnected.com/how-py ... db71f77a2f

[Navis]

Δε νομιζω οτι εχει να κανει με 32 η' 64 μπιτη αρχιτεκτονικη. Για τοσο μεγαλους αριθμους θα χρησιμοποιουνε ειδικες βιβλιοθηκες που κανουν τις πραξεις τμηματικα και οχι σε μια εντολη της ALU. Σε αυτη την περιπτωση ο μεγαλος αριθμος ειναι ενα μεγαλο bitstream χωρις περιορισμους 64 μπιτ αλλα οσο βασταει η μνημη σου. Και κατι τετοιο μπορει να γινει και σε ενα 8-μπιτο μηχανημα.

πχ και πολυ χοντρικα, η προσθεση δυο αριθμων 128 + 64, αντι να ειναι ενα και ενα μπαιτς , ειναι 3 και 3 strings "128", "64" και η πραξη της προσθεσης γινεται οπως καναμε στο δημοτικο.

[wooded glade]

Δε νομιζω οτι εχει να κανει με 32 η' 64 μπιτη αρχιτεκτονικη. Για τοσο μεγαλους αριθμους θα χρησιμοποιουνε ειδικες βιβλιοθηκες που κανουν τις πραξεις τμηματικα και οχι σε μια εντολη της ALU. Σε αυτη την περιπτωση ο μεγαλος αριθμος ειναι ενα μεγαλο bitstream χωρις περιορισμους 64 μπιτ αλλα οσο βασταει η μνημη σου. Και κατι τετοιο μπορει να γινει και σε ενα 8-μπιτο μηχανημα.

πχ και πολυ χοντρικα, η προσθεση δυο αριθμων 128 + 64, αντι να ειναι ενα και ενα μπαιτς , ειναι 3 και 3 strings "128", "64" και η πραξη της προσθεσης γινεται οπως καναμε στο δημοτικο.

Είπα έως 10^18.
Ας πούμε:

2234567890 x 345678901

Πως θα το κάνω ;
Σαν long integer βγάζει overflow. Σαν single precision ή και σαν double precision χάνεται η ακρίβεια.
Λες με εντολές όπως θα το κάναμε με το χέρι, προ slide rule και προ κομπιουτερακίων και να σχηματίζεται σιγά-σιγά το γινόμενο σαν string. Αυτό λες ;

[Navis]

ε ναι. Θα ειναι πιο αργο αλλα ισως οχι πολυ

[klg]

Και για να απαντήσω στο ερωτημά σου τώρα που έχω χρόνο, οι υπολογισμοί για τέτοιους αριθμούς γενικά πραγματοποιούνται με vector SSE. Οι πολλαπλασιασμοί, αναλογώς το μέγεθος του product, υλοποιούνται με διάφορους αλγόριθμους (karatsuba, FFT, NTT) και γενικά το πρόβλημα σου είναι ότι από ένα σημειο και μετά οι αριθμοί προφανώς δεν χωράνε ούτε στην ram, οπότε για τεράστιους πολλαπλασιασμούς χρησιμοποιείς το δίσκο και εκτελείς FFT ή κάποιο efficient NTT.

Με λίγα λόγια τα bottlenecks είναι 1) για μικρούς υπολογισμούς το throughput του SSE FPU και 2) για μεγάλους υπολογισμούς το bandwidth της ram και του δίσκου.

Πάντως γενικά υπάρχουν διάφορες βιβλιοθήκες που σου παρέχουν big number υλοποιήσεις με κλασσικό παράδειγμα (που μπορείς να δεις και εσύ) την GMP.

[NoMoreLice]

το πρόβλημα σου είναι ότι από ένα σημειο και μετά οι αριθμοί προφανώς δεν χωράνε ούτε στην ram

Υπάρχει κάποιος στον κόσμο που χρησιμοποιεί αριθμούς που δεν χωράνε στη ram; Και 100 GB να διαθέσεις για έναν αριθμό (δεν είναι τίποτα ας πούμε να έχεις έναν σέρβερ με 256 ή 512 gb μνήμη), μιλάμε μπορείς να υπολογίσεις αριθμούς έως 2^(80^11). Εξωπραγματικό. Δεν νομίζω ότι υπάρχει κανείς στον κόσμο που να αναγκάζεται να χρησιμοποιεί disk I/O για αριθμητικές πράξεις.

[klg]

το πρόβλημα σου είναι ότι από ένα σημειο και μετά οι αριθμοί προφανώς δεν χωράνε ούτε στην ram

Υπάρχει κάποιος στον κόσμο που χρησιμοποιεί αριθμούς που δεν χωράνε στη ram; Και 100 GB να διαθέσεις για έναν αριθμό (δεν είναι τίποτα ας πούμε να έχεις έναν σέρβερ με 256 ή 512 gb μνήμη), μιλάμε μπορείς να υπολογίσεις αριθμούς έως 2^(80^11). Εξωπραγματικό. Δεν νομίζω ότι υπάρχει κανείς στον κόσμο που να αναγκάζεται να χρησιμοποιεί disk I/O για αριθμητικές πράξεις.

Φυσικά και υπάρχει. Έτσι υπολογίζεις τα ψηφία του π για παράδειγμα.

http://www.numberworld.org/misc_runs/pi-12t/

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

[axilmar]

The largest known prime number (as of December 2020) is 2^82,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.

Πως τα υπολογίζουν αυτά ;
Κάποιοι ενδιάμεσοι μαθηματικοί τύποι υπάρχουν οπωσδήποτε, αλλά η vb με double precision -που δεν παρέχει ακρίβεια- φτάνει μέχρι αριθμούς με 309 ψηφία. Δεν πάει παραπάνω.

Εγώ θέλω να υπολογίσω με ακρίβεια ακεραίους που να φτάνουν μέχρι το 10^18. Πως γίνεται ;

Χρησιμοποιουν custom made types, και οι αριθμητικες πραξεις γινονται με κωδικα, οχι με εντολες προς την CPU.

Πολλες γλωσσες προγραμματισμου παρεχουν ειδικες κλασεις ακεραιων για μεγαλους αριθμους που ξεφευγουν της 32-μπιτ και 64-μπιτ αρχιτεκτονικης.

[NoMoreLice]

το πρόβλημα σου είναι ότι από ένα σημειο και μετά οι αριθμοί προφανώς δεν χωράνε ούτε στην ram

Υπάρχει κάποιος στον κόσμο που χρησιμοποιεί αριθμούς που δεν χωράνε στη ram; Και 100 GB να διαθέσεις για έναν αριθμό (δεν είναι τίποτα ας πούμε να έχεις έναν σέρβερ με 256 ή 512 gb μνήμη), μιλάμε μπορείς να υπολογίσεις αριθμούς έως 2^(80^11). Εξωπραγματικό. Δεν νομίζω ότι υπάρχει κανείς στον κόσμο που να αναγκάζεται να χρησιμοποιεί disk I/O για αριθμητικές πράξεις.

Φυσικά και υπάρχει. Έτσι υπολογίζεις τα ψηφία του π για παράδειγμα.

http://www.numberworld.org/misc_runs/pi-12t/

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

Ενδιαφέρον, θα το κοιτάξω. thanks.