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)
najnowsze
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:
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:
https://pl.wikipedia.org/wiki/Algorytm_Karacuby
Potem były kolejne algorytmy, ostatnie
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).
Niezupełnie. Nowy algorytm ma złożoność n
@gre
Chciałem coś mądrego napisać ale widzę, że przy was zbłaźnię się.
Dlatego zapodam suchar:
Żona prosi męża informatyka:
- Czy mógłbyś pójść za mnie na zakupy i kupić jeden karton mleka? Jeśli mają jajka, weź sześć.
Kilka minut później informatyk wraca ze sklepu z sześcioma kartonami mleka.
- Dlaczego kupiłeś sześć kartonów mleka? - pyta żona.
- Bo mieli jajka.