•  

    pokaż komentarz

    Świetny artykuł. Szkoda że po angielsku, bo nie dość że większość nie przeczyta bo matematyka, to części nie chce się po angielsku.

    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 zbliżyły się do n * log(n).
    Niedawno udowodniono (dokładnie nie wiem jak, ale to raczej skomplikowane) że da się zejść dokładnie do n * log (n), a teraz że nie da się niżej.
    Wiec teraz mamy prawie najlepsze algorytmy, z prędkością niżej nie zejdziemy niż "jeszcze max 3x szybciej".

    •  

      pokaż komentarz

      @deryt: Doceniam tldr, ale należy się kilka sprostowań

      Potem były kolejne algorytmy, ostatnie zbliżyły się do n * log(n).
      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).

      Niedawno udowodniono (dokładnie nie wiem jak, ale to raczej skomplikowane) że da się zejść dokładnie do n * log (n), a teraz że nie da się niżej.
      Niezupełnie. Nowy algorytm ma złożoność n * log(n) i sam w sobie stanowi dowód że się da. Udowodnienie że nie da się lepiej jest trudne i jeszcze się nie udało. Najlepszy do tej pory dowód opiera się na innym jeszcze nie udowodnionym twierdzeniu.

      Wiec teraz mamy prawie najlepsze algorytmy, z prędkością niżej nie zejdziemy niż "jeszcze max 3x szybciej".
      Niezupełnie. Chodzi o to że chociaż nowy algorytm jest dużym osiągnięciem w matematyce, to w praktyce jest nieprzydatny, bo może dać przyspieszenie max 3x (nawet dla bardzo dużych liczb)

    •  

      pokaż komentarz

      @deryt
      @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.

    •  

      pokaż komentarz

      @wcinaster: Trochę zgrabniejsza wersja

      Żona prosi męża informatyka:
      - Kup sześć bułek, a jak będą jajka, to kup dwanaście.
      Chłopina po wejściu do sklepu pyta:
      - Czy są jajka?
      - Tak - odpowiada sprzedawca.
      - To poproszę dwanaście bułek.

    •  

      pokaż komentarz

      @gre: @deryt:

      Nalezaloby jednak jeszcze dodac, ze o ile ten nowy algorytm jest istotny z punktu widzenia teorii matematyki, to niewiele zmieni w szybkosc odbliczen. Co najwyzej przyspieszy szybkosc mnozenia 3 razy.
      BTW: to skrociloby czas np. z wyzej uzytego przykladu monozenia dwoch liczb z miliardem cyfr z 30 do 10 lat.

      Co wiecej zamiana mnozenie na dodawanie (i odejmowanie) ktora miala przyspieszyc proces obliczeeniowy, wydaje sie bezcelowy bo dla niektorych wspolczesnych architektur procesorow mnozenie jest wykonywane szybciej od dodawania, co jest szalenstwem "where multiplication can be even faster than addition in some chip architectures. With some hardware, “you could actually do addition faster by telling the computer to do a multiplication problem, which is just insane,” Harvey said."

      pokaż spoiler Czyli jak zwykle, super odkrycie, ale w sumie to nie tak za super, bo zmienimy hardware i bedziemy miec to samo.

    •  

      pokaż komentarz

      @jeanpaul: Z tym hardware to poleciałeś. Cały problem jest dla liczb które nie mieszczą się w jednym rejestrze procesora.

      Oczywiście nowy hardware czasem przyspiesza, ale wynika to z implementacji w krzemie algorytmów które wcześniej były robione programowo. Czyli algorytmy są potrzebne choćby po to aby było jak aktualizować architekturę.

    •  

      pokaż komentarz

      @deryt: W O(n log n) już od dawna się dało mnożyć używając FFT wiec no, nie do końca masz rację. Tutaj jest info czemu FFT jednak nie jest aż takie cool:
      http://numbers.computation.free.fr/Constants/Algorithms/fft.html

    •  

      pokaż komentarz

      Z tym hardware to poleciałeś. Cały problem jest dla liczb które nie mieszczą się w jednym rejestrze procesora.

      Oczywiście nowy hardware czasem przyspiesza, ale wynika to z implementacji w krzemie algorytmów które wcześniej były robione programowo. Czyli algorytmy są potrzebne choćby po to aby było jak aktualizować architekturę.

      @Massad: dlatego umiescilem to poza tlumaczeniem. Po drugie w artykule jest napisane wyraznie ze procki wykonuja szybciej monozenie niz dodawanie. Wiec stosowanie algorytmu rozbijajacego mnozenie na dodawanie jest jakby bez sensu. I nigdy bym nie negowal potrzeby tworzenia i rozwiajania algorytmow, skomentowalem jedynie wniosek ktorym autorzy skonkludowali swoja prace.

    •  

      pokaż komentarz

      @jeanpaul: ale nie ma instrukcj mnozacych liczby 1024 bitowe albo dłuższe.

      Jak my mnozymy, to mnozymy cyfra po cyfrze. W nowoczesnych procesorach mozna mnozyc po 64 bity (chyba trzeba mniej, aby uniknac przepelnienia, musialbym sprawdzic jak wyglada uzycie bitu przepelnienia).

      A jak robisz po kawałku, to muszisz potem calosc dodawać.

    •  

      pokaż komentarz

      @crooner11: nie jestem pewny ale chyba było cos jeszcze z lodem i kakao( ͡° ͜ʖ ͡°)

    •  

      pokaż komentarz

      ale nie ma instrukcj mnozacych liczby 1024 bitowe albo dłuższe.
      Jak my mnozymy, to mnozymy cyfra po cyfrze. W nowoczesnych procesorach mozna mnozyc po 64 bity (chyba trzeba mniej, aby uniknac przepelnienia, musialbym sprawdzic jak wyglada uzycie bitu przepelnienia).
      A jak robisz po kawałku, to muszisz potem calosc dodawać.


      @Massad: obawiam sie obaj nie mamy wystarczajacej wiedzy na temat architektury wspolczesnych procesorow w superkomputerach. Jedyne co wywnioskowalem z tego wpisu to fakt ze czas wykonania instrukcji mnozenia jest krotszy od podobnej instrukcji dla dodawania:
      multiplication can be even faster than addition in some chip architectures. With some hardware, “you could actually do addition faster by telling the computer to do a multiplication problem

      Dlatego tez algorytm w ktorym wielokrotne mnozenie zastepujemy mnozeniem i dodawaniem lepiej byloby uproscic ograniczajac dodawanie i jedynie "kombinowac" z mnozeniem.

      To sa zajebiste sprawy, niestety lata temu odszedlem od architektury procesorow, PLA czy FPGA i mimo ze mam podstawy raczej dla wykopowej przyjemnosci nie bede nadrabial wiedzy z ostatnich 25 lat.

      Jesli chesz mozesz poszukac, cheetnie poczytam wnioski. Moge sobie wyobrazic kilka corow rozbijajacych proces monozenia na rownolegle procesy w ktorych sam process mnozenia jest realizowany jakims "sprytnym" microcodem, ktory stosujac pamiec podreczna potrafi przesuwac rejestry wieksze od 64 bitow, albo realizujac mnozenie w ramach 64 bitach szybciej od podobnej funkcji dla dodawania.

    •  

      pokaż komentarz

      W O(n log n) już od dawna się dało mnożyć używając FFT wiec no, nie do końca masz rację.

      @e_mati: Nie, to było takie uproszczenie dla programistów. ( ͡° ͜ʖ ͡°)
      W znalezisku podają O(n log(n) log(log(n)). W artykule który zalinkowałeś masz sekcję "More on the complexity of multiplication with FFT", gdzie wyprowadzona złożoność jest nawet większa, ale wspominają też o najlepszym wtedy wyniku: "The lowest known theoritical bound is obtained with the Schönhage multiplication, which generalizes the process by working in finite rings, and is O(N log(N) loglog(N)) "

    •  

      pokaż komentarz

      @jeanpaul: Mowię o rodzinie procesorów x86_64 które cały czas dominują w superkomputerach (Drugi filar to karty graficzne, które świetnie się nadają do obliczeń wektoryzowalnych). Standardowy rozmiar rejestru to 64 bity. Rozmiar rejestru dla obliczeń zmiennoprzecinkowych to 64 albo 80 bitów. Do tego sa specjalistyczne rejestry do operacji wektorowych. Najdłuższe o których wiem to 512 bitów. Być może są dłuższe rzędu 1024. Nawet zakłądając, że można potraktować 2 takie rejestry jako liczby i je pomnożyć przez siebie to cały czas jest to za mało. Te algorytmy są dla liczb dużo dłuższych.

      Problem mnożenia tych liczb jest tka rzadki, że wątpię aby się pojawiły optymalizację tego typu w procesorze.

      Natomiast w teorii złożoności obliczeniowej nie patrzy się ile dana operacja zajmuje na procesorze. Dodawanie i mnożenie pary rejestrów ma złożoność 1. Więc kluczowe jest ilość takich operacji. To o czym mówisz to jest walka o stałą.

      Załóżmy że mnożenie jest 4 krotnie szybsze. Ale algorytm wykorzystujący bardziej mnożenie ma złożoność k * n log^2(n) . Natomiast ten co wykorzystuje głównie dodawanie ma złożoność l * n log (n)). To zauważ że log(16) == 4. Stosunek czasu wykonania tych algorytmów to (k * log(n))/l. Czyli każdorazowe 16-krotne wydłużenia liczb do mnożenia powoduje 4 krotne pogorszenie stosunku na rzecz algorytmu wykorzystującego mnożenie. Więc zawsze algorytm który ma lepszą złożoność, nawet jak wykorzystuje bardziej czasochłonne operacje, będzie lepszy na odpowiednio dużych danych.

      Jeszcze niedawno pisałem kod pod superkomputery.

    •  

      pokaż komentarz

      Mowię o rodzinie procesorów x86_64

      @Massad: a ci panowie najwyrazniej mysla o jakis innych architekturach, moze o GPGPUs albo o power9 polaczonych z Nvidia Tesla GPUs - nie mam pojecia.

      Nie musisz mi przypominac teorii zlozonosci. Ona pozwala jedynie na teoretyczne wyliczynie i porownanie wydajnosci algorytmow zakladajac wykonanie na tej samej maszynie. Jeslii jednak dwa rozne algorytmy o takiej samej zlozonosci zostana wykonane na roznych maszynach wyniki beda rozne. Ponownie to ci kolesie twierdza (nie ja) ze metoda upraszczania mnozenia polegajaca na redukcji krokow mozenia i zastepowania ich dodawaniem moze okazac sie zla, jesli mnozenie kosztuje mniej czasu na procesorze niz dodawanie.

      Jesli uwazasz, ze sie myla, to moze warto przedyskutowac twoj punkt widzenia z nimi, a nie z kolesiem (ze mna) ktory przetlumaczyl 3 zdania.

    •  

      pokaż komentarz

      @crooner11:
      Żona do męża informatyka:
      - Idź kupić bułki.
      - Ile mam kupić?
      - No nie wiem, tyle kup, żeby starczyło na kolację i śniadanie.
      Mąż zirytowanym głosem:
      - Jak kupię za mało albo za dużo, to znów będzie awantura. Powiedz, ile mam kupić?
      Żona (z zalotnym spojrzeniem):
      - Kup tyle bułek, ile razy się wczoraj kochaliśmy.
      Mąż poszedł do sklepu. Staje przed ekspedientką i mówi:
      - Poproszę siedem bułek. Albo nie, pięć bułek, loda i kakałko

      ... a może to nie był mąż informatyk ( ͡° ͜ʖ ͡°)

    •  

      pokaż komentarz

      @e_mati: Dotychczas znane metody mnożenia przez FFT nie były O(nlogn), tylko O(n logn 2^(Θ(log*n)))

    •  

      pokaż komentarz

      @deryt: przy czym trzeba również pamiętać, że O(n log n) może być wolniejsze od O(n^2) (dla pewnych wartości n) i właśnie dla tego GMP zmienia algorytm w zależności od rozmiaru liczb.

    •  

      pokaż komentarz

      @deryt: jak by wiedzieli jeszcze o kolejnej kompresji hdd to mozna serwerownie na ebay wystawic

    •  

      pokaż komentarz

      @deryt: a tak na serio o co tu chodzi ? bo ta metoda nie jest najefektywniejsza to jest poczatek mozna tym odrazu dziabac duze liczby(faktoryzacja), zmiennoprzecinkowe, klucz

    •  

      pokaż komentarz

      faktoryzacja

      @Pira:
      Co ma faktoryzacja do tego? Nie da się faktoryzować liczb o miliardach cyfr.
      "ta" znaczy Karacuby?
      Jest efektowna, skoro ją stosują (znaczy stosuję inne, ale tak dużych liczb się nie mnoży cyfra po cyfrze).

      klucz
      Pisz jaśniej, bo nie wiadomo co chodzi. Wygląda jakbyś losowe słowo dopisał na końcu zdania ( ͡° ͜ʖ ͡°)

    •  

      pokaż komentarz

      @deryt: ano mozna robic cyfra po cyfrze z predkoscia 100/s(powiedzmy) ja w pomieci bym potrzebowal 1/5s (jesli sie nie myle) mozna spojrzec na liczbe wedlug klucza(nie bede sie jasniej rozpisywal bo z głupkami nie gadam a nie bede tego upublicznial) i da sie faktoryzowac liczby o miliardach (przynajnmiej powinno-w pamieci ;p) trzeba znac triki na sciagi(np w dlugopisie) na egzaminie nie same sciagi czy wiedze w glowie

  •  

    pokaż komentarz

    Klikooszczędzacz:

    źródło: media.wired.com

  •  

    pokaż komentarz

    Wystarczy wkleić do Excela i wpisać formułę.

  •  

    pokaż komentarz

    Kiedyś bawiłem się pisaniem własnego algorytmu mnożenia dużych liczb. Próbowałem właśnie szybkiej transformacji Fouriera, ale za głupi jestem na zaimplementowanie tego. Skończyło się na algorytmie Karacuby. I tak wystarczyło na zaliczenie, gdyż okazało się, że prowadzący nawet o metodzie mnożenia za pomocą Fouriera nie słyszał.

  •  

    pokaż komentarz

    Ten sposób jest tu ciekawie opisany ale nieuczciwe jest niewspomnienie, że już dawno mamy szybka transformatę Fouriera więc w zasadzie obecnie metoda z artykułu jest sztuką dla sztuki.