Остатък модул 2s-1

При програмиране в по-старите процесори, където умножение и деление номера са извършени бавно, програмисти са се обърнали към този трик, за да се ускори изчисления. Така че, малко трик, за да получи остатъка от делението на броя равен на точната степен на две, остава в сила и днес. тип операция # 038 ((1<

Нека да се съгласите, че е> 1 и е цяло число. Необходимо е да се изчисли и мод (2 S-1).

Всяко неотрицателно цяло число може да бъде разложен на сума

Следователно, МО (2 S-1), могат да бъдат представени като

Последният равенство е възможно благодарение на факта, че 2 и ≡ 1 мод (2S -1). Получената формула се получава рекурсивно изчисляване алгоритъм остатък: изчисляване на мод (2S -1). Ние трябва да се изчисли на остатъка от. измества надясно от У бита, и след това се добавя долната битът е в резултат на сумата и след това отново да вземе остатъка от деление от 2 и -1. Тази операция трябва да се направи, докато получената стойност е по-малко от или равно на 2 и -1.

Алгоритъм може да бъде представена по различен начин: разделят битово представяне на номерата на частите на S бита и ги обобщи като номера, и след това към получения размер на прилагане на същата операция като дълго, тъй като това количество е по-голямо от делителя.

Например нека = 3. Изчислява остатъка от разделяне на броя на 100 (10) от 7. За тази цел, 100 описват броя в двоичен код, битът се раздели на три части:

Изчислява: 100 мод 7 = ((7 мод 12) + 4) мод 7 = (1 + 4 + 4) мод 7 = 9 мод 7 = [като 9 = 1 | 001 (2)] = 1 + 1 = 2.

Има малък проблем, когато първоначалния брой е равен на 2 S-1. алгоритъмът не работи, както и необходимостта да разглобите случай поотделно. Това означава, че ако искаме да брои 7 мод 7, че ще има 7 така че тези резултати трябва да се нулират ръчно.

Горната теория дава възможност да се приготвят един прост пример програма:
P = (1 Р х = Z)
за (Z = 0; х; х >> = S)
Z + = х P;
ако (X == P)
х = 0;

Броят на х - е оригиналният номер, той ще бъде един и същ резултат. Броят Z - го подкрепят след не се изисква броенето.

Когато се вгледате в този код, е веднага ясно, че на практика е безполезно. На съвременните процесори операция разделение не е толкова бавно, за да играе като вложено цикъл. Най-малко в тези проблеми, които имах, за да реши дали процедурата е загубено нормална работа дивизия. И ако вземем предвид, че съвременните компилатори са в състояние да замени разделението от 2 сек -1 при операции на битови, въпреки че това не винаги е хубаво нещо, по-добре е да не ги устои. Можете да проверите за себе си, с този код, ще загубите.

Друг разговор започва, когато му номер е известен предварително (и обикновено е). Дори по-добре, когато е на власт от две. В този случай, вътрешният цикъл на нашата процедура може да бъде заменен с поредица от битове смени и допълнения и операции. Налице е известен трик за цел да се преброят на бита данни в двоично число. Предполагам, че този метод на вас преброяване са добре известни. Така че, една малка промяна ще му позволи да се вземе предвид не бита, както и количеството на а-битови числа извън оригиналния номер. Например, ако У = 8. вътрешният цикъл отива, има само на външния вид:
за (Z = х; х> P х = Z) Z = (Z # 038; 0x00FF00FFu) + ((Z >> 8) # 038; 0x00FF00FFu);
Z = (Z # 038; 0x0000FFFFu) + (Z >> 16);
>
ако (X == P)
х = 0;

Можете да отидете напред и че броят на повторения на този цикъл ще бъде със сигурност по-малко от някаква граница (в зависимост от проблема е решен) на Великобритания. Това ще даде възможност за разполагане на цикъл многократно.

Конкуренцията за изчисляване модул броя на обратен матрица S = 31. Въпреки че е известно, че първоначалния брой не надвишава 62. 2 прави възможно също така да се отстрани вътрешния контур, заменяйки я с незначителни дейности тридесет и един малко по един бит от тридесет. Така външният контур на не повече от две повторения, втората от които функционира вече 32-битови числа, но не и 64-битова прави.

Може би някой ще се съберат, за да направи мащабни експерименти, за да се тества ефективността на метода в практиката? После, след съставянето на програма, уверете се, че компилаторът напусна Разделение инструкция на мястото, където тя е трябвало да бъде, и не се прилагат към кода си SSE инструкции, в противен случай сравнението не е съвсем вярна. Както казах по-горе, съвременни компилатори са вмъкнати като малко трик за да се разделят с мощност от две минус едно, ако знаят предварително, че разделителят е от този тип и "решиха", че в този случай ще бъде по-бързо от всички други методи баланс изчисляване (например, чрез разделяне на броя на тип поплавък). Това е, когато се изпитват, се уверете, че тестът е това, което искате.

Аз не се извършват такива експерименти, но мога да кажа, че този трик е полезна, тъй като наистина ускорява програмата. Така например, в посочения по-горе конкурса "с главата напред" версия на Гаус е работил около 2400, и ако ние замени работата на вземане на функцията за баланс
Int Mod (int64 х) int32u Z;
Z = int32u (х # 038; P) + int32u (х >> 31);
Z = (Z # 038; P) + (Z >> 31);
ако (Z == P)
връщане 0;
връщане междинно съединение (Z);
>
Докато работа веднага намали до 1200 секунди.

Разбира се, като максималният ефект се постига чрез пренаписване на асемблер, но това е друга история. Тази статия се предполага, че не разполагат с достъп до програмирането на ниско ниво.

Дискусия статии на форума в тази тема.