Konwersja równań na operacje zmiany bitów

Question

Czy istnieje jakiś standardowy sposób przekształcania (dowolnego) równania w operacje zmiany bitów?

Przez to mam na myśli przekształcania niczego, co nie jest + lub - do przesunięć bitowych, więc równanie końcowy zawiera jedynie operandy < <, >>, + i -. Jest to w interesie tworzenia formuł mniej wymagających procesora.

Oczywiście te równania wypadkowe będą jedynie przybliżeniami, dając lepszą dokładność przy większej liczbie rozpatrywanych zamówień (pierwszego rzędu, drugiego rzędu e.t.c).

Przeszukałem internet w poszukiwaniu jakichkolwiek informacji na ten temat, ale nie mogę znaleźć żadnych, z wyjątkiem rzeczy o określonych formułach (sin, cos, inv e.t.c).

Wyobrażałem sobie coś w rodzaju procedury wielomianowej lub Taylora, a następnie przekształcania jej w operacje zmiany bitów.

Answer 1

Tylko dlatego, że redukujesz coś do prostszych instrukcji, nie oznacza to, że będą one wykonywane szybciej lub w jakiś sposób będą mniej intensywne. Chociaż możesz zredukować wiele rzeczy do zredukowanego podzbioru operacji, prawdopodobnie będziesz potrzebować wielu znacznie więcej operacji, aby wykonać to samo zadanie. Procesor może wykonywać tylko tyle operacji na sekundę, a ty masz zamiar to zrobić jako pierwszy.

Ogólnie rzecz biorąc, próbując zoptymalizować coś na niskim poziomie, próbujesz skorzystać z dużo bardziej złożonych kodów opcodes, tak, że potrzebujesz ich mniej. Jako przykład możesz wykonać mnożenie, wykonując wiele instrukcji ADD. Jednak w przypadku innych niż banalne przykładów, będzie to wymagało znacznie więcej ADD niż pojedynczego kodu MUL, a jego wykonanie zajmie znacznie więcej czasu.

Wracając do faktycznego pytania ... Całkowicie ignorując efektywność, można obliczyć wszystko, o ile posiadany zestaw instrukcji jest Turing Complete. Rzeczywiście możesz obliczyć wszystko przy użyciu a single instruction, jeśli uważnie wybierzesz tę instrukcję. Nie sądzę, żeby istniał jakikolwiek ogólny sposób mówienia "Konwertuj dowolny algorytm na używanie tylko tych instrukcji", to na ogół praca pisarza kompilatora.

Answer 2

Nie na ogól.

W przypadku większości procesorów mnożenie nie jest znacznie wolniejsze niż w przypadku innych operacji arytmetycznych, więc nie ma sensu próba konwersji mnożenia na operacje zmiany bitów, z wyjątkiem mnożenia przez stałe moce dwóch.

Jeśli chodzi o podział, istnieją pewne dobrze znane metody przekształcania podziału przez stałą na mnożenie przez odwrotność, a metody te są dość produktywne. Zobacz http://www.flounder.com/multiplicative_inverse.htm, aby uzyskać wyjaśnienie, w jaki sposób. Podział według wartości niestałych nie może być jednak zoptymalizowany.

Podnoszenie 2 do potęgi (lub dzielenie liczby przez potęgę 2) jest oczywiście łatwo konwertowane na przesunięcie bitowe. Inne potęgowania nie są jednak łatwo konwertowane.

Większość funkcji transcendentalnych nie może być sensownie reprezentowana na poziomie bitowym. To nie pomaga, że ​​większość nie jest zdefiniowana na liczbach całkowitych.

Answer 3

Mnożenie oprogramowania za pomocą operacji bitowych prawdopodobnie nie pokona multiplikacji sprzętowej na nowoczesnych procesorach.

Zwykle przejście na manipulację bitową może przynieść lepsze wyniki, jeśli pozwala uniknąć 1) pętli; i 2) rozgałęzienia.

A good online cookbook dla hakowania bitów. W przeciwnym razie istnieje A Hacker's delight.