W miarę jak coraz bardziej angażuję się w teorię programowania, fascynują mnie i oszałamiają pozornie proste rzeczy. Zdaję sobie sprawę, że moje rozumienie większości podstawowych procesów jest uzasadnione poprzez logikę kołową

P : Jak to działa?

Odp . : Ponieważ tak jest!

Nienawidzę tej realizacji! Uwielbiam wiedzę, a ponadto uwielbiam uczyć się, co prowadzi mnie do mojego pytania (choć jest ono szerokie).

Pytanie:

Jak oceniane są podstawowe operatory matematyczne za pomocą języków programowania?

Jak ulepszono obecne metody?

Przykład

var = 5 * 5; 

Moja interpretacja:

$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
    $num3 = $num3 + $num1;
    $num2 = $num2 - 1;
}
echo $num3;

Wydaje się to bardzo nieefektywne. Przy wyższych czynnikach ta metoda jest bardzo wolna, podczas gdy standardowa metoda wbudowana jest natychmiastowa. Jak symulowałbyś mnożenie bez iteracyjnego dodawania?

var = 5 / 5;

Jak to się w ogóle robi? Nie mogę wymyślić sposobu, aby dosłownie podzielić go na 5 równych części.

var = 5 ^ 5; 

Iteracje iteracji dodawania? Moja interpretacja:

$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {

    $num2 = 5; $num3 = 0;
    while ($num2 > 0) {
        $num3 = $num3 + $num1;
        $num2 = $num2 - 1;
    }
    $num1 = $num3;
    $mod -=1;
}
echo $num3;

Ponownie, jest to BARDZO nieefektywne, ale nie mogę wymyślić innego sposobu na zrobienie tego. To samo pytanie dotyczy wszystkich funkcji matematycznych obsługiwanych automatycznie.

Aby naprawdę zrozumieć, jak działa arytmetyka wewnątrz komputera, musisz mieć zaprogramowany język asemblera. Najlepiej taki z małym rozmiarem słowa i bez instrukcji mnożenia i dzielenia. Coś jak 6502.

W 6502 praktycznie cała arytmetyka odbywa się w rejestrze zwanym akumulatorem. (Rejestr to specjalna pamięć w procesorze, do której można szybko uzyskać dostęp). Aby dodać dwie liczby, należy załadować pierwszą liczbę do akumulatora, a następnie dodać do niej drugą liczbę.

Ale to upraszcza. Ponieważ 6502 jest 8-bitowym procesorem, może obsługiwać liczby od 0 do 255. Przez większość czasu będziesz chciał pracować z większymi liczbami. Musisz dodać je we fragmentach po 8 bitów na raz. Procesor ma flagę Carry, która jest ustawiona, gdy wynik dodania dwóch liczb przepełni akumulator. Procesor dodaje to podczas dodawania, więc można go użyć do „przenoszenia 1”, zakładając, że zaczynasz od bajtu najniższego rzędu liczby. Wielobajtowy dodatek na 6502 wygląda następująco:

1. Flaga Clear Carry (CLC)
2. Załaduj bajt najniższego rzędu pierwszego numeru (LDA, ładuj akumulator)
3. Dodaj bajt najniższego rzędu drugiego numeru (ADC, dodaj z przeniesieniem)
4. Przechowuj bajt wyniku najniższego rzędu (STA, akumulator akumulatora)
5. Powtórz kroki 2–4 z kolejnymi bajtami wyższego rzędu
6. Jeśli na końcu przeniesienie jest ustawione, przepełniłeś się; podjąć odpowiednie działania, takie jak wygenerowanie komunikatu o błędzie (BCS / BCC, rozgałęzienie, jeśli przeniesienie ustawione / wyczyść)

Odejmowanie jest podobne, z tym wyjątkiem, że najpierw ustawisz przeniesienie, użyj instrukcji SBC zamiast ADC, a na końcu przeniesienie jest jasne, jeśli wystąpił niedopełnienie.

Ale poczekaj! Co z liczbami ujemnymi? Cóż, z 6502 są one przechowywane w formacie zwanym dopełnieniem dwóch. Zakładając liczbę 8-bitową, -1 jest zapisywane jako 255, ponieważ kiedy dodasz do czegoś 255, dostajesz o jeden mniej w akumulatorze (plus przeniesienie). -2 jest przechowywane jako 254 i tak dalej, aż do -128, która jest przechowywana jako 128. Tak więc dla liczb całkowitych ze znakiem, połowa zakresu 0-255 bajtu jest używana dla liczb dodatnich, a połowa dla liczb ujemnych. (Ta konwencja pozwala po prostu sprawdzić najwyższy bit liczby, aby sprawdzić, czy jest ona ujemna).

Pomyśl o tym jak o 24-godzinnym zegarze: dodanie 23 do godziny spowoduje godzinę wcześniejszą (następnego dnia). Zatem 23 jest modułowym odpowiednikiem zegara dla -1.

Jeśli używasz więcej niż 1 bajtu, musisz użyć większej liczby dla negatywów. Na przykład 16-bitowe liczby całkowite mają zakres od 0 do 65536. Tak więc 65535 jest używany do reprezentowania -1 i tak dalej, ponieważ dodanie 65535 do dowolnej liczby daje jedną mniej (plus przeniesienie).

W 6502 są tylko cztery operacje arytmetyczne: dodawanie, odejmowanie, mnożenie przez dwa (przesunięcie w lewo) i dzielenie przez dwa (przesunięcie w prawo). Mnożenie i dzielenie można wykonać przy użyciu tylko tych operacji w przypadku plików binarnych. Rozważmy na przykład pomnożenie 5 (binarne 101) i 3 (binarne 11). Podobnie jak w przypadku mnożenia dziesiętnego długiego, zaczynamy od prawej cyfry mnożnika i mnożymy 101 przez 1, dając 101. Następnie przesuwamy mnożnik w lewo i mnożymy 1010 przez 1, dając 1010. Następnie dodajemy te wyniki razem, dając 1111 lub 15. Ponieważ zawsze mnożymy tylko przez 1 lub 0, tak naprawdę nie mnożymy; każdy bit mnożnika służy po prostu jako flaga, która mówi nam, czy dodać (przesunięty) mnożnik, czy nie.

Podział jest analogiczny do ręcznego dzielenia długiego przy użyciu dzielników próbnych, z wyjątkiem binarnych. Jeśli dzielisz przez stałą, możesz to zrobić w sposób analogiczny do odejmowania: zamiast dzielenia przez X, mnożysz przez wstępnie obliczone odwzorowanie 1 / X, które daje pożądany wynik plus przepełnienie. Nawet dzisiaj jest to szybsze niż podział.

Teraz spróbuj wykonać matematykę zmiennoprzecinkową w asemblerze lub przekonwertować liczby zmiennoprzecinkowe na ładne formaty wyjściowe w asemblerze. I pamiętajcie, jest 1979 rok, a częstotliwość taktowania wynosi 1 MHz, więc musicie to zrobić tak efektywnie, jak to możliwe.

Rzeczy nadal działają podobnie do dzisiaj, z wyjątkiem większych rozmiarów słów i większej liczby rejestrów, i oczywiście większość matematyki jest teraz wykonywana przez sprzęt. Ale nadal odbywa się to w ten sam fundamentalny sposób. Jeśli na przykład zsumuje się liczbę przesunięć i sum wymaganych do zwielokrotnienia, koreluje to raczej dobrze z liczbą cykli wymaganych dla instrukcji zwielokrotnienia sprzętowego na wczesnych procesorach posiadających taką instrukcję, na przykład 6809, w której została wykonana w mikrokodzie w podobny sposób, jak robiłbyś to ręcznie. (Jeśli masz większy budżet tranzystora, istnieją szybsze sposoby wykonywania zmian i dodawania, więc nowoczesne procesory nie wykonują tych operacji sekwencyjnie i mogą wykonywać multiplikacje w zaledwie jednym cyklu).

Ostatecznie podstawowe operacje arytmetyczne są wykonywane sprzętowo. Mówiąc dokładniej, w procesorze (lub w rzeczywistości jego podsekcji)

Innymi słowy, są to układy elektroniczne. Ustaw odpowiednie bity jako dane wejściowe, a otrzymasz odpowiednie bity jako dane wyjściowe. Jest to połączenie podstawowych bramek logicznych.

http://en.wikipedia.org/wiki/Adder_%28electronics%29

http://en.wikipedia.org/wiki/Binary_multiplier

Wszystko to pokryte jest dokładną cierpliwością w sztuce programowania komputerowego Dona Knutha.

Wydajne algorytmy dodawania, odejmowania, mnożenia i dzielenia są opisane szczegółowo.

Możesz dobrze przeczytać takie rzeczy, które obejmują podział.

http://research.microsoft.com/pubs/151917/divmodnote.pdf

Odbywa się to w pikosekundach za pomocą obwodów elektronicznych. „Mnożnik sprzętowy” Google itp., Aby uzyskać szczegółowe informacje. Nowoczesne procesory to niezwykle złożony wynik dziesięcioleci ciągłego doskonalenia.

BTW, skoro nie mnożycie przez wielokrotne dodawanie, dlaczego wyobrażacie sobie, że komputer by to zrobił?

W żadnym wypadku nie jest to dokładna odpowiedź, ale powinna dać ci pojęcie, jak rzeczy są realizowane. Jak zapewne wiesz, liczby są reprezentowane w postaci binarnej. Na przykład komputer może oznaczać liczbę 5 jako 00000101. Bardzo podstawową operacją, którą może wykonać komputer, jest przesunięcie w lewo, co dałoby 00001010, który jest dziesiętny 10. Gdyby dwukrotnie przesunąć w prawo, byłby to 00010100 (dziesiętnie 20). Za każdym razem, gdy przesuwamy cyfry w lewo, 1 raz podwajamy liczbę. Powiedzmy, że mam liczbę x i chciałem ją pomnożyć przez 17. Mogłem przesunąć x w lewo 4 razy, a następnie dodać x do wyniku (16x + x = 17x). Byłby to skuteczny sposób na pomnożenie liczby przez 17. To powinno dać ci pewien wgląd w to, jak komputer może pomnożyć duże liczby bez konieczności wielokrotnego dodawania.

Podział może używać kombinacji dodawania, odejmowania, przesunięcia w prawo, przesunięcia w lewo itp. Istnieje również wiele sztuczek służących do podnoszenia liczb do wykładników.

Kiedy byłem dzieckiem, nauczyłem się rozmnażać i dzielić za pomocą długopisu i papieru, nie marnując czasu na zbyt wiele dodatków. Później dowiedziałem się, że pierwiastki kwadratowe są również obliczalne w ten sposób.

Na uniwersytecie nauczyłem się obliczać operacje trygonometryczne i logarytmiczne z kilkunastoma multiplikacjami, podziałami i dodatkami. Nazwali to serią Taylor.

Wcześniej mój ojciec dał mi książkę, w której te złożone operacje zostały już obliczone dla setek wartości i przedstawione w tabelach. Było także kilka wyjaśnień dotyczących szacowania błędu, gdy potrzebowano sinusa wartości między dwiema obliczonymi wartościami.

Jednostki całkowite, zmiennoprzecinkowe, GPU i DSP po prostu wdrażają wszystkie te stare techniki na krzemie.

Spróbuję dać ci wyobrażenie o tym, w jaki sposób obwody cyfrowe są zaprojektowane do rozwiązywania problemów z przetwarzaniem cyfrowym, wykorzystując postawione problemy: w jaki sposób procesory implementują dodawanie i mnożenie.

Po pierwsze, usuńmy bezpośrednie pytanie: w jaki sposób język programowania skutecznie ocenia mnożenia i uzupełnienia. Odpowiedź jest prosta: zestawiają je w mnożenie i dodają instrukcje. Na przykład następujący kod:

a = 1 + 1;
b = a * 20;

jest po prostu skompilowany do czegoś takiego jak:

ADD 1 1  a
MUL a 20 b

(zauważ, że powyższy zestaw jest dla wyimaginowanego procesora, który nie istnieje, dla uproszczenia).

W tym momencie zdajesz sobie sprawę, że powyższa odpowiedź po prostu przesuwa problem i rozwiązuje go za pomocą magii sprzętowej. Kolejne pytanie brzmi oczywiście, jak działa ta magia sprzętowa?

Najpierw spójrzmy na prostszy problem: dodanie.

Najpierw wykonujemy znany problem, dodając w regularnej bazie 10 liczb:

 17
+28

Pierwszym krokiem byłoby dodanie 7 i 8. Ale daje to 15, która jest więcej niż jedną cyfrą. Nosimy więc 1:

(1)
 17
+28
= 5

Teraz dodajemy 1, 1 i 2 razem:

 17
+28
=45

Z tego otrzymujemy następujące zasady:

1. gdy wynikiem dodawania jest więcej niż jedna cyfra, zachowujemy najmniej znaczącą cyfrę i przenosimy najbardziej znaczącą cyfrę do przodu

2. jeśli mamy cyfrę przeniesioną do naszej kolumny, dodajemy ją wraz z liczbami, które dodajemy

Teraz nadszedł czas, aby zinterpretować powyższe reguły w bazie 2 - algebra boolowska.

Tak więc w algebrze boolowskiej, dodanie 0 i 1 razem = 1. Dodanie 0 i 0 = 0. I dodanie 1 i 1 = 10, co jest więcej niż jedną cyfrą, więc przenosimy 1 do przodu.

Z tego możemy zbudować tabelę prawdy:

a b  |  sum  carry
-------------------
0 0  |   0     0
0 1  |   1     0
1 0  |   1     0
1 1  |   0     1

Na tej podstawie możemy zbudować dwa obwody / równania boolowskie - jeden dla wyniku sumy, a drugi dla wyniku przeniesienia. Najbardziej naiwnym sposobem jest po prostu wypisanie wszystkich danych wejściowych. Dowolna tabela prawdy, bez względu na to, jak duże i złożone można przekształcić w tej formie:

(AND inputs in first row) OR (AND of inputs in second row) OR ...

Jest to w zasadzie suma postaci produktów. Patrzymy tylko na wyniki, które dają 1 i ignorujemy 0:

sum = (NOT a AND b) OR (a AND NOT b)

Zastąpmy AND AND i NOT symbolami języka programowania, aby ułatwić czytanie:

sum = (!a & b) | (a & !b)

Zasadniczo przekonwertowaliśmy tabelę tak:

a b  |  sum  equation
-------------------
0 0  |   0   
0 1  |   1   (!a & b)
1 0  |   1   (a & !b)
1 1  |   0   

Można to bezpośrednio zaimplementować jako obwód:

                _____
 a ------------|     |
    \          | AND |-.     ____
     \  ,-NOT--|_____|  \   |    |
      \/                 `--| OR |----- sum
      /\        _____    ,--|____|
     /  `-NOT--|     |  /
    /          | AND |-`
 b ------------|_____|

Obserwatorzy czytający w tym miejscu zauważą, że powyższą logikę można faktycznie zaimplementować jako pojedynczą bramę - bramę XOR, która dogodnie ma zachowanie wymagane przez naszą tabelę prawdy:

                _____
 a ------------|     |
               | XOR |---- sum
 b ------------|_____|

Ale jeśli twój sprzęt nie zapewnia ci bramki XOR, powyższe kroki opisują, jak możesz ją zdefiniować i wdrożyć w zakresie bramek AND, OR i NOT.

Sposób przejścia na bramkę logiczną na rzeczywisty sprzęt zależy od posiadanego sprzętu. Można je zaimplementować przy użyciu różnych mechanizmów fizycznych, o ile mechanizm zapewnia pewien rodzaj przełączania. Wdrożono bramki logiczne ze wszystkim, od strumieni wody lub zaciągów powietrza (płynów), tranzystorów (elektronika) po spadające kulki. To duży temat sam w sobie, więc po prostu go pomaluję i powiem, że możliwe jest zaimplementowanie bramek logicznych jako urządzeń fizycznych.

Teraz robimy to samo dla sygnału przenoszenia. Ponieważ jest tylko jeden warunek, w którym sygnał przenoszenia jest prawdziwy, równanie jest po prostu:

carry = a & b

Noszenie jest proste:

                _____
 a ------------|     |
               | AND |---- carry
 b ------------|_____|

Łącząc je razem otrzymujemy tak zwany pół sumator:

                _____
 a ------;-----|     |
         |     | XOR |---- sum
 b --;---|-----|_____|
     |   |      _____
     |   '-----|     |
     |         | AND |---- carry
     '---------|_____|

Nawiasem mówiąc, równania dla powyższego obwodu wyglądają następująco:

sum = a ^ b
carry = a & b

W połowie sumatora czegoś brakuje. Wdrożyliśmy pierwszą zasadę - jeśli wynik jest więcej niż jedna cyfra niż przeniesienie, ale nie wdrożyliśmy drugiej reguły - jeśli istnieje przeniesienie, dodaj ją wraz z liczbami.

Aby więc wdrożyć pełny sumator, obwód sumowania, który może dodawać liczby, które są więcej niż jedną cyfrą, musimy zdefiniować tabelę prawdy:

a b c  |  sum  carry
---------------------
0 0 0  |   0     0
0 0 1  |   1     0
0 1 0  |   1     0
0 1 1  |   0     1
1 0 0  |   1     0
1 0 1  |   0     1
1 1 0  |   0     1
1 1 1  |   1     1

Równanie sumy jest teraz:

sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)

Możemy przejść przez ten sam proces, aby wyliczyć i uprościć równanie i zinterpretować je jako obwód itp., Jak to zrobiliśmy powyżej, ale myślę, że ta odpowiedź jest zbyt długa.

Do tej pory powinieneś dowiedzieć się, jak zaprojektowana jest logika cyfrowa. Są inne sztuczki, o których nie wspomniałem, takie jak mapy Karnaugh (używane w celu uproszczenia tabel prawdy) i kompilatory logiczne, takie jak espresso (abyś nie musiał ręcznie uwzględniać równań boolowskich), ale podstawową zasadą jest to, co mam przedstawione powyżej:

1. Rozłóż problem, aż będziesz mógł pracować na poziomie jednego bitu (cyfry).

2. Zdefiniuj pożądane wyniki za pomocą tabeli prawdy.

3. Przekształć tabelę w równanie boolowskie i uprość równanie.

4. Interpretuj równanie jako bramki logiczne.

5. Przekształć obwód logiczny w rzeczywiste obwody sprzętowe, wdrażając bramki logiczne.

W ten sposób naprawdę rozwiązuje się podstawowe (a raczej niskopoziomowe) problemy - mnóstwo tabel prawdy. Prawdziwa twórcza praca polega na rozkładaniu złożonego zadania, takiego jak dekodowanie MP3 do poziomu bitowego, aby można było pracować nad nim przy użyciu tabel prawdy.

Niestety nie mam czasu na wyjaśnienie, jak zaimplementować mnożenie. Możesz spróbować złamać go, ustalając zasady działania mnożenia, a następnie interpretując go w formacie binarnym, a następnie próbując rozbić go na tabele prawdy. Lub możesz przeczytać Wikipedię: http://en.wikipedia.org/wiki/Binary_multiplier

podstawowe instrukcje arytmetyczne są wykonywane z instrukcjami montażu, które są bardzo wydajne.

Bardziej złożone (lub abstrakcyjne) instrukcje są wykonywane w asemblerze za pomocą mechanizmów zapętlających lub obsługiwane w standardowej bibliotece.

Studiując matematykę na studiach, zaczniesz studiować takie rzeczy, jak rachunek Lambda i notacja Big-O. Wszystkie te i wiele innych są wykorzystywane przez programistów do oceny i tworzenia wydajnych algorytmów. W każdym razie, podstawowe rzeczy są zwykle osiągane na niskim poziomie, na przykład w asemblerze lub w c za pomocą wskaźników.

Świetnym wprowadzeniem do tego tematu jest „Kod” Charlesa Petzolda.

Zdobądź książkę podobną do Fundamentals of Digital Logic ... , która moim zdaniem jest wciąż dość standardowa dla studentów Freshman / Sophomore EE, i pracuj nad nią (wyd .: kosztuje niewielką fortunę, więc poszukaj używanej lub wcześniejszej wersji to). To poprowadzi cię przez sumatory i mnożniki i da ci wystarczająco dużo tła, aby zacząć rozumieć niektóre zasady stojące za tym, co robi sprzęt.

W krótkim czasie twoja odpowiedź brzmi: „ponieważ pasuje do siebie kilka kawałków prostszej logiki, aby wywołać to złożone zachowanie” zamiast „ponieważ tak jest”.

Jeśli chcesz spróbować zrozumieć wszystkie zasady kompilowania i uruchamiania programów, wybierz to w połączeniu, aby ostatecznie zobaczyć, jak wszystko spotyka się w środku.

Tutaj jest wiele dobrych odpowiedzi. Zacząłeś też od właściwego pomysłu: złożone operacje, takie jak mnożenie, są zbudowane z prostszych operacji. Jak się domyślacie, istnieją szybsze sposoby mnożenia bez instrukcji mnożenia niż przy użyciu szeregu dodatków. Każde zwielokrotnienie może być zaimplementowane jako suma pomnożonych zwielokrotnień lub jako kombinacja przesunięć i dodatków. Przykłady:

a = 5 + 5 + 5 + 5 + 5;           // 5*5, but takes 5 operations
b = (5 << 2) + 5;                // 5*5 in only 2 operations
c = (41 << 4) + (41 << 2) + 41   // 41*21 in 4 operations

Podział można również podzielić na mniejsze operacje. XOR (^) to wbudowana instrukcja na każdym procesorze, na który kiedykolwiek patrzyłem, ale mimo to może być zaimplementowana jako kombinacja AND, OR i NOT.

Mam jednak wrażenie, że konkretne odpowiedzi będą dla Ciebie mniej satysfakcjonujące niż ogólne wyobrażenie o rodzajach instrukcji dostarczanych przez procesor i sposobie łączenia tych instrukcji w bardziej złożone operacje. Dla tego rodzaju ciekawości nie ma nic lepszego niż zdrowa dawka języka asemblera. Oto bardzo przystępne wprowadzenie do języka asemblera MIPS.

Oto jak współczesny procesor może zaimplementować mnożenie dwóch 64-bitowych liczb całkowitych:

Wiesz, jak wykonać mnożenie długiej ręki. Aby pomnożyć dwie liczby 10-cyfrowe, należy pomnożyć jedną 10-cyfrową liczbę przez każdą z 10 cyfr drugiego numeru, zapisać wynik 11 cyfr jeden pod drugim i przesunąć, a następnie dodać całą liczbę.

Nowoczesny procesor robi to z wszystkimi bitami 64 na 64. Jednak mnożenie dwóch liczb pojedynczych bitów jest bardzo proste: 1 x 1 = 1, wszystkie inne produkty są zerowe. Jest to realizowane za pomocą logicznego i. I w przeciwieństwie do iloczynu dziesiętnego, w którym wynikiem mogą być dwie cyfry, iloczyn binarny liczb jednobitowych ma zawsze jeden bit.

Teraz masz 64 wiersze po 64 bity, które należy dodać. Ale 64 dodatki 64-bitowych liczb są zbyt wolne. Tak więc procesor używa sumatora 3/2 lub sumatora 7/3: Jeśli dodasz 3 liczby jednobitowe, wynikiem może być 0, 1, 2 lub 3, co pasuje do dwóch bitów. Jeśli dodasz 7 liczb jednobitowych, wynikiem będzie liczba od 0 do 7, którą można przedstawić za pomocą 3 bitów. IBM twierdzi, że może zrobić adder 7/3 za pomocą zaledwie 18 prymitywnych obwodów (dokumentacja PowerPC), założę się, że Intel i ARM mogą to zrobić.

Masz 4096 bitów, zgrupuj je w około 600 grup 7 bitów w tych samych pozycjach bitów i użyj około 600 7/3 sumatorów, aby zmniejszyć wynik z 4096 bitów do mniej niż 2000. Następnie robisz to samo raz za razem, dopóki nie skończysz z parami bitów, które można wprowadzić do zwykłego pełnego sumatora.