jest szybki algorytm podobny do potęgi 2, który może być użyty z 3, tj. N% 3. Być może coś, co wykorzystuje fakt, że jeśli suma cyfr jest podzielna przez trzy, to liczba jest również podzielna.Fast modulo 3 lub algorytm podziału?
To prowadzi do następnego pytania. Jaki jest szybki sposób dodawania cyfr w liczbie? To znaczy. 37 -> 3 +7 -> 10 szukam czegoś, co nie ma warunkowe jak te wydają się hamować wektoryzacja
dzięki
4 % 3 == 1, czyli (4^k * a + b) % 3 == (a + b) % 3. Można wykorzystać ten fakt, aby ocenić x% 3 dla 32-bit x:
x = (x >> 16) + (x & 0xffff);
x = (x >> 10) + (x & 0x3ff);
x = (x >> 6) + (x & 0x3f);
x = (x >> 4) + (x & 0xf);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
if (x == 3) x = 0;
(. Nietestowane - może trzeba jeszcze kilka redukcje) Czy to szybciej niż twój sprzęt może zrobić x% 3? Jeśli tak, to prawdopodobnie nie za dużo.
Czy to naprawdę jest szybsze niż 'x% 3'? Zobacz https://godbolt.org/g/aRbqrW – plasmacel
Nie jestem pewien na pierwsze pytanie, ale za sekundę, można wziąć zaletą podziału % operatora i liczby całkowitej:
int num = 12345;
int sum = 0;
while (num) {
sum += num % 10;
num /= 10;
}
To działa, ponieważ 12345 % 10 = 5, 12345/10 = 1234 i iść aż num == 0
+1 Ładne # 2. rozwiązanie. –
tak, to jest oczywiste rozwiązanie. Jednak podział i modulo to bardzo kosztowne operacje, rzędu setek cykli na mojej platformie. Jestem bardziej zainteresowany czymś, co ich nie dotyczy. Muszę powiedzieć, że jest to kwestia czysto ciekawości. – Anycorn
to comp.compilers item ma specjalne zalecenia do obliczeń modulo 3.
Alternatywnie, w szczególności, jeśli rozmiar dające maksimum dywidendy jest niewielki, to należy pomnożyć przez odwrotność 3 jako stałą wartość zadanej, z wystarczającą ilością bity precyzji, aby obsłużyć dywidendę o maksymalnej wielkości, aby obliczyć iloraz, a następnie odejmij 3 * iloraz od dywidendy, aby uzyskać pozostałą część. Wszystkie te mnożenia można realizować za pomocą ustalonej sekwencji zmian i uzupełnień. Liczba instrukcji będzie zależeć od wzoru bitowego odwrotności. Działa to całkiem dobrze, gdy maksymalna wartość dywidendy jest niewielka.
Jeśli chodzi o dodawanie cyfr w liczbie ... jeśli chcesz dodać cyfry dziesiętną, skończy się to robieniem tego, co równa się konwersji liczby na dziesiętne, co oznacza dzielenie przez 10 gdzieś . Jeśli chcesz wyrazić zgodę na dodanie cyfr w base2, możesz to zrobić za pomocą łatwej zmiany w prawo i dodania pętli. Do tego można użyć różnych sprytnych sztuczek w kawałkach N bitów, aby przyspieszyć to dalej.
Dodanie cyfr nie zadziała w tym przypadku, ponieważ musisz najpierw przekonwertować liczbę na liczbę dziesiętną, która zajmuje _ dużo więcej czasu niż tylko podział. –
Co właściwie chcesz osiągnąć? O ile nie jest to teoretyczna ciekawostka, wątpię, by ten konkretny problem mógł być wąskim gardłem aplikacji świata rzeczywistego ... –
jest zarówno praktyczny, jak i teoretyczny. powstaje pytanie, próbując rozprowadzić wiele zagnieżdżonych pętli przez centra kartezjańskie wśród wątków (Cuda, ale nie jest to ważne). Już rozwiązałem problem w inny sposób, ale nadal chciałbym wiedzieć, czy jest jakiś sposób. To jest prawdziwe wąskie gardło, ponieważ podział na liczby całkowite i modulo są znacznie droższe niż rzeczywiste operacje zmiennoprzecinkowe, które próbuję wykonać równolegle. – Anycorn