Skocz do zawartości




Zdjęcie

Przyspieszenie mnożenia bardzo dużych liczb


  • Zaloguj się, aby dodać odpowiedź
Brak odpowiedzi do tego tematu

#1 nusZja

nusZja

    1

  • Members
  • PipPipPip
  • 115 postów

Napisano 10 styczeń 2013 - 11:48

Testuję mnożenie oparte na zmianie systemów pozycyjnych. W odpowiednio dobranym systemie KAŻDE mnożenie można sprowadzić do mnożenia przez 10, czyli dopisania zera jako cyfry najmniej znaczącej.

Trudność polega na algorytmie konwersji na odpowiedni system oraz z powrotem, na system dziesiątkowy lub binarny. Opracowałem taki, złożoności arytmetycznej kwadratowej.
Okazało się, że nie muszę przeprowadzać pełnej konwersji, przy powrocie stosuję bowiem konwersję odwrotną, która znosi działanie wcześniejszej, nie działając na dołączonej cyfrze. Zapewnia to też niezmiennik algorytmu konwersji: fragment liczby przed i po konwersji ma tę samą wartość liczbową.

Zatem, aby pomnożyć jakieś nie za duże liczby, np. 5.027.608.376 przez 1008, pierwszą dzielę na paczki oddzielone w/w kropkami, dopisuję paczkę zera '000', oraz używam konwersji o przyrost 1008-1000 = 8 dla każdej paczki.
Dla tego przykładu mam 4 mnożenia ósemki i liczby trójcyfrowej, cztery dodawania oraz parę nadmiarów.
Po uwzględnieniu nadmiarów uzyskuję wartość iloczynu 5.067.829.243.008.

I pytanie, czy można uzasadnić dopisanie paczki zer bez odwoływania się do historii powstania tego sposobu mnożenia? W jaki sposób?

Ta metoda sprowadza mnożenie gigantycznych liczb do znacznie prostszych działań na mniejszych wartościach, np. iloczyn liczb mających 380 oraz 400 bitów sprowadza się do pomnożenia dwu liczb mających około 380 oraz 20 bitów. Oraz kilka dodawań oraz przesunięć, jak zwykle w tym zakresie. To właśnie tak wielkie wartości powodują mniejszą krotność mnożeń niż w przykładzie.
Dlatego chciałbym umieć to przedstawiać jak najbardziej zrozumiale.






Użytkownicy przeglądający ten temat: 0

0 użytkowników, 0 gości, 0 anonimowych


Pozycjonowanie strony: Virtual Development