Złożoność algorytmu

0

Witam. Jestem w trakcie tworzenia dużego typu liczbowego, który jest reprezentowany przez tablicę Dword w systemie pozycyjnym o podstawie 10^9. Mój problem dotyczy algorytmu mnożenia. Ten, który wymyśliłem, działa tak (w pseudokodzie):

tmp = 0;
while (mnożnik > 1)
{
  if (mnożnik podzielny przez 2)
  { // mnożną pomnóż przez 2, mnożnik podziel na 2
    mnożna <<= 1;
    mnożnik >>= 1;
  }
  else
  {
    tmp += mnożna;
    --mnożnik;
  }
}
mnożna += tmp;

Mam pytanie dotyczące złożoności obliczeniowej tego algorytmu. Przesunięcia bitowe, dodawanie i dekrementacja działają w czasie liniowym. Porównanie zarówno w warunku pętli, jak i wewnętrznym zachodzi w czasie stałym.

Wg. moich rozważań, zakładając rozmiary obu liczb równe n, optymistyczna złożoność (mnożnik jest potęgą dwójki) wynosi O(nlg(n)). Jeśli chodzi o przypadek pesymistyczny, to w połowie przebiegów wykonywane jest dzielenie+mnożenie, a w połowie dodawanie+dekrementacja, wobec tego złożność powinna wynosić O(n/2lg(n/2) + (n/2)*n), co asymptotycznie daje O(n^2).

Teraz proszę o sprawdzenie, czy nie mylę się w szacowaniu złożoności - mam wrażenie, że mogłem się pomylić, jakoś zbyt szybki ten algorytm mi się wydaje. :D

0

Zaraz, nie rozumiem. Co robią w kodzie "dzielna" i "dzielnik" skoro to mnożenie?

Jeśli Ci wyszła złożoność O(n^2) to nie jest wcale tak szybko. Mnożenie dużych liczb można zrobić w O(n log n), niezależnie od danych wejściowych.

0

Oczywiście chodziło o mnożną i mnożnik, już poprawiłem błąd. Nie twierdzę, że jest to szybki algorytm, ale jestem dość zdziwiony tym, że średnio jest szybszy od algorytmu "szkolnego", który ma złożoność O(n^2) dla każdych danych.

0

Po pierwsze - szybkość, to nie to samo co złożoność.

Po drugie - wyciągasz błędne wnioski z obliczeń. We wzorze O(n2) w algorytmie szkolnym, n oznacza długość liczb. W Twoim algorytmie n oznacza wartość mnożnika (pesymistyczny przypadek) lub logarytm tej wartości (optymistyczny). Ponieważ długość liczby ~ log jej wartości, to Twój algorytm w optymistycznym przypadku ma złożoność O(n2), w pesymistycznym zaś O(n a^n), gdzie n = długość liczb, "a" jakaś stała > 1. Oczywiście jest to paskudna złożoność w porównaniu z nawet algorytmem szkolnym.

Mnożenie przez FFT ma złożoność O(n log n), gdzie n długość obu liczb i n jest potęgą dwójki.

0

Rzeczywiście, dzięki za pokazanie błędu. Faktycznie, pesymistyczny przypadek to duża złożoność względem długości liczby. Chyba więc zastosuję algorytm szkolny - O(n2) to dość dużo, ale przy podstawie systemu równej 109 raczej nie będą się trafiały na tyle duże długości liczb, żeby się babrać z FFT.

0

zobacz, jak to jest zaimplementowane w vlong.

0

Dzięki Wam za pomoc, już się uporałem z algorytmem oraz dodałem dzielenie i resztę z dzielenia. Gdy to zrobiłem, pomyślałem, że może bardziej skutecznie i efektywnie będzie wykorzystywać jako podstawę systemu całego inta, zamiast poprzedniej, mniejszej podstawy. Zmiana wszystkich algorytmów była łatwa, a testy wykazują spory wzrost wydajności. :)

Jednak znowu pojawił się problem: w jaki sposób można wypisywać i wczytać taką liczbę ze stringa w systemie dziesiętnym? [???] Innymi słowy: Jak dokonać zamiany podstawy systemu z 2n na podstawę 10k (bo do tego sprowadza się mój problem)? Prosiłbym o namiary na jakiś prosty (albo nawet całkiem skomplikowany, ale dobrze wytłumaczony) algorytm takiej zamiany. Googlałem na ten temat, ale wszystko, co znalazłem, to zamiana na system dziesiętny w rodzaju "brute-force" - obliczyć wartość wielomianu a0 + a1p + a2p^2 + ... etc. A ze zrozumiałych względów taki algorytm mi nie pomoże. :| (A może jednak? Nie wiem, może mam chwilową zaćmę, ale nie mogę sobie z tym poradzić.)

0

a stary, dobry, tradycyjny sposob div-mod-przez10 nie bedzie odpowiedni?

na przykladzie uint 128bit: 0xDA3ADF4CCEE58CE8

0xDA3ADF4CCEE58CE8 % 0xA = 2
0xDA3ADF4CCEE58CE8 /= 0xA -> 15D2AFEE14B08E17

0x15D2AFEE14B08E17 % 0xA = 5
0x15D2AFEE14B08E17 /= 0xA -> 22EAB3168780E35

0x22EAB3168780E35 % 0xA = 9
0x22EAB3168780E35 /= 0xA -> 37DDEB573F349E

37DDEB573F349E % 0xA .....
.....
....

624 % 0xA = 2
624 /= 0xA -> 9D

9D % 0xA = 7
9D /= 0xA -> F

0xF % 0xA = 5
0xF /= 0xA -> 1

0x1 % 0xA = 1
0x1 /= 0xA -> 0 (koniec)

wniosek:
0xDA3ADF4CCEE58CE8 w (2) to
15725126569899166952 w (10)</b>

jedyny minus, to fakt, ze wymaga ciaglego dzielenia calej liczby, a dzielenie jej przez 10 wymaga przetworzenia wszystkich jej bitow.

wlasciwie mozna to przyspieszyc rozszczepiajac liczbe na fragmenty dajace sie obrabiac niezaleznie - dzielenia co prawda trzeba bedzie wykonac w tej samej albo i wiekszej ilosci, ale --- te dzielenia juz nie beda wymagaly obrobki wszystkich bitow, a jedynie czesci.

zakladajac rejestry unsinged 32bit mozna wstepnie duza liczbe podzielic na segmenty rzedu 10^9 [najwyzsza potega 10tki mieszczaca sie w 32bit] i potem obrabiac te kawalki osobno .na w/w przykladzie:

0xDA3ADF4CCEE58CE8 % 10^9 = 0x359832E8
0xDA3ADF4CCEE58CE8 /= 10^9 = 0x3A94A63A9

0x3A94A63A9 % 10^9 = 0x2B388DA9
0x3A94A63A9 /= 10^9 -> 0xF

0xF % 10^9 -> 0xF
0xF /= 10^9 -> 0 [koniec]

i teraz majac { [0x000000F] [0x2B388DA9] [0x359832E8]}

0x0000000F -> -> 15
0x2B388DA9 -> -> 725126569
0x359832E8 -> -> 899166952

dodatkowy plus: po takim 'połamaniu' liczby da sie koncowe operacje wykonac rownolegle

0

Cóż, div/mod jest dość powolny, ale po wspomnianym "połamaniu" liczby do przyjęcia. Bardzo dziękuję wszystkim za pomoc, jestem bardzo wdzięczny.

1 użytkowników online, w tym zalogowanych: 0, gości: 1