MATEMATYCY znaleźli idealny sposób MNOŻENIA WIELKICH LICZB
Złożoność wielu problemów obliczeniowych od kolejnych po przecinku cyfr liczby pi po odnajdywanie kolejnych liczb pierwszych sprowadza się do szybkości mnożenia ...
stanulam z- #
- #
- #
- #
- #
- #
- 57
- Odpowiedz
Komentarze (57)
najlepsze
tldr:
Mnożenie ogromnych (posiadających miliony, a nawet miliardy cyfr) jest bardzo czasochłonne. Normalnie mnożymy "cyfra po cyfrze" wiec wykonamy łącznie n^2 mnożeń gdzie n to ilość cyfr liczb mnożonych.
Okazało się że da się to zrobić w mniej mnożeń.
Udowodnił to Karacuba w 1960:
Niezupełnie. Kolejne opublikowane algorytmy zbliżały się do tej granicy, ale ostatnio opublikowany ma już złożoność dokładnie n * log(n).
@gre
Chciałem coś mądrego napisać ale widzę, że przy was zbłaźnię się.
Dlatego
@Verbatino: Tylko, że to nie jest algorytm nlog(n) :)
I jest po angielsku, a ludzie leniwi i nie chce im się czytać.
Ja tam jestem szybszy od tego fouriera i używam metody kalkulatora ))¯_(ツ)_/¯
No nie do konca, bo NASA uzywa 8 cyfr po przecinku zeby obliczac trajektorie orbit, a cos kolo 15 cyfr wystarczy by obliczyc srednice wszechswiata z dokladnoscia mniejsza niz srednica atomu
Co do wielkich liczb, próbowałem kiedyś sił we własnej implementacji algorytmu Gausa
@pies_harry: w artykule masz przebieg "całej" historii.
1: