Czy mnożenie dwóch liczb jest algorytmem o stałym czasie?

Question

Załóżmy piszę,

int a = 111; 
int b = 509; 
int c = a * b; 

Więc co jest złożoność czasu do obliczenia 'A * B'? W jaki sposób wykonywana jest operacja mnożenia?

Answer 1

Kompilacja tę funkcję:

int f(int a, int b) { 
    return a * b; 
} 

Z gcc -O3 -march=native -m64 -fomit-frame-pointer -S daje mi następujący montaż:

f: 
    movl %ecx, %eax 
    imull %edx, %eax 
    ret 

Pierwsza instrukcja (movl) ładuje pierwszy argument, druga instrukcja (imull) ładuje sekundę argument i pomnożyć go z pierwszym - wtedy wynik zostanie zwrócony.

Faktyczne mnożenie odbywa się za pomocą imull, która - zależnie od typu procesora - zajmie określoną liczbę cykli procesora.

Jeśli spojrzysz na Agner Fog's instruction timing tables, zobaczysz, ile czasu zajmie każda instrukcja. Na większości procesorów x86 wydaje się być małą stałą, jednak instrukcja imul na AMD K8 z 64-bitowym argumentem i wynikiem wyświetla się jako cykle procesora 4-5. Nie wiem jednak, czy to kwestia pomiaru, czy naprawdę zmienny czas.

Należy również zwrócić uwagę na inne czynniki niż czas wykonania. Liczba całkowita musi być przeniesiona przez procesor i dostać się w odpowiednie miejsce, aby uzyskać pomnożenie. Wszystkie te i inne czynniki powodują opóźnienie, co odnotowano również w tabelach Agner Fog. Istnieją inne problemy, takie jak problemy z pamięcią podręczną, które również utrudniają życie - nie jest łatwo po prostu powiedzieć, jak szybko coś będzie działało bez uruchamiania go.

---

x86 nie tylko architektura, a to nie jest właściwie nie do pomyślenia są CPU i architektur, które obecnie nie mają zakaz stałą czasową mnożenia. Jest to szczególnie ważne w przypadku kryptografii, w której algorytmy wykorzystujące mnożenie mogą być podatne na ataki czasowe na tych platformach.

Answer 2

Mnożenie samo w większości typowych architektur będzie stałe. Czas ładowania rejestrów może być różny w zależności od lokalizacji zmiennych (L1, L2, RAM, itp.), Ale liczba wykonywanych operacji cyklicznych będzie stała. Jest to sprzeczne z operacjami takimi jak sqrt, które mogą wymagać dodatkowych cykli w celu osiągnięcia określonej dokładności.

można dostać koszty instrukcji tutaj AMD, Intel, VIA: http://www.agner.org/optimize/instruction_tables.pdf

Answer 3

void myfun() 
{ 
int a = 111; 
int b = 509; 
int c = a * b; 
} 

De zebrać część:

movl $111, -4(%ebp) 
movl $509, -8(%ebp) 
movl -4(%ebp), %eax 
imull -8(%ebp), %eax 

Więc jak widać wszystko zależy od imull instrukcją, a konkretnie pobieranie, dekodowanie i wykonywanie cyklu procesora.

Answer 4

Według złożoności czasowej, zakładam, że masz na myśli to, czy zależy od liczby cyfr w aib? Tak więc, czy liczba cykli zegara procesora byłaby różna w zależności od tego, czy pomnożyłeś, powiedzmy 2 * 3, czy 111 * 509. Sądzę, że tak, byłyby różne i zależałoby od tego, w jaki sposób architektura ta implementuje operację mnożenia i jak przechowywane są wyniki pośrednie. Chociaż istnieje wiele sposobów na zrobienie tego, jedną prostą/prymitywną metodą jest zaimplementowanie mnożenia za pomocą obwodu binary adder/subtractor. Mnożenie a * b dodaje do siebie b razy używając n-cyfrowych adderów binarnych. Podobnie podział a/b to odejmowanie b od a aż do 0, chociaż zajmie to więcej miejsca, aby zapisać iloraz i resztę.

Answer 5

W przykładzie kompilator zrobi mnożenie i Twój kod będzie wyglądać

int c = 56499; 

Jeśli zmieniłeś przykład wyglądać

int c = a * 509; 

następnie kompilator może zdecydować się przepisać kod taki jak

int c = a * (512 - 2 - 1); 
int c = (a << 9) - (a << 1) - a; 

Powiedziałem, że może, ponieważ kompilator porówna koszt używając koszulki do kosztu wielokrotnej instrukcji i wybierz najlepszą opcję. Biorąc pod uwagę szybką instrukcję wielokrotną, zwykle oznacza to, że tylko 1 lub 2 przesunięcie będzie szybsze.

Jeśli twoje liczby są zbyt duże, aby zmieścić się w liczbie całkowitej (32-bitowe), to arbitralna precyzja procedur matematycznych wykorzystuje czasy między O (n^2) i O (n log n), gdzie n jest liczbą 32 -bitowe części potrzebne do przechowywania liczb.