Подскажите пожалуйста оптимальный алгоритм

M mod N = F

M — большое целое число
N — значение от 4 до 26;

Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..

Здравствуйте, <Аноним>, Вы писали:

А>Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..
Деление легко реализуется через сдвиг, сравнение и вычитание

Здравствуйте, Аноним, Вы писали:

А>M mod N = F

А>M — большое целое число
А>N — значение от 4 до 26;

А>Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..

Умножение есть? Какова разрядность регистров?

Здравствуйте, <Аноним>, Вы писали:

А>M mod N = F
А>M — большое целое число
А>N — значение от 4 до 26;
А>Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..

Как-то так:

C = N << k; // k подобрать таким, чтобы С было больше, чем M
while (1) {
    if (M < N) return M;
    if (M >= C) M = M - C
    C = C >> 1;
}

Сложность — O(log M)

Здравствуйте, Буравчик, Вы писали:

А>>M mod N = F
А>>M — большое целое число
А>>N — значение от 4 до 26;
А>>Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..

Б>Как-то так:
Б>

Б>C = N << k; // k подобрать таким, чтобы С было больше, чем M
Б>while (1) {
Б>    if (M < N) return M;
Б>    if (M >= C) M = M - C
Б>    C = C >> 1;
Б>}    
Б>

Для неотрицательных чисел — идея неплохая, только надо ещё учесть ограничение на представление чисел.
Например, если речь идёт о беззнаковых 32-разрядных числах, то, к примеру, для N = 5 максимальное возможное значение для N<<k будет равно 0xA0000000, т.е. для чисел M из диапазона [0xA0000001..0xFFFFFFFF] алгоритм работать не будет.

Здравствуйте, andy1618, Вы писали:

A>Для неотрицательных чисел — идея неплохая, только надо ещё учесть ограничение на представление чисел.
A>Например, если речь идёт о беззнаковых 32-разрядных числах, то, к примеру, для N = 5 максимальное возможное значение для N<<k будет равно 0xA0000000, т.е. для чисел M из диапазона [0xA0000001..0xFFFFFFFF] алгоритм работать не будет.

Код с учетом замечаний

if (M < N) return M;

C = N << k; // k = "битов в M" - "битов в N"
do {
    if (M >= C) M = M - C
    C = C >> 1;
} while (M >= N)

return M

А Аноним пропал. Как всегда...

Здравствуйте, Буравчик, Вы писали:

Б>Код с учетом замечаний

Б>

Б>C = N << k; // k = "битов в M" - "битов в N"
..
Б>

Да, работать будет.
Осталось справиться с подбором k — можно это сделать, сдвигая N влево в цикле, причём с контролем выхода за разрядность используемого типа.
Например, так:

// Предполагается, что все числа 32-х разрядные беззнаковые.
if (N == 0) throw "Modulo is zero";

C = N;
while (C < Min(M, 0x80000000)) 
  C = C << 1;

while (M >= N)
{
  if (M >= C) 
    M = M - C;
  C = C >> 1;
}
return M;

Сложность та же, O(log(M)).

Здравствуйте, Аноним, Вы писали:

Надо исходить из того, что
остаток равен остатку от суммы
остатков от степеней двойки.
Без всяких предварительных оценок
для положительных цисел будет так:

(текст на C, но, надеюсь, понятный всем)

int big = ...
int small = ...

int rest2 = 1;
int rest = 0;

// В rest2 будет формироваться остаток от деления степени двойки на small

while(big)
{
if(big & 1) // Младший бит равен 1
{
rest = rest + rest2;
if(rest >= small)
rest = rest — small;
}
rest2 <<= 1; // Сдвигаем влево

if(rest2 >= small)
rest2 = rest2 — small;

big >>= 1; // Сдвигаем вправо
}

В rest — остаток.

big вообще может быть не числовым типом, а битовой последовательностью
фиксированного размера с первым нулевым битом.
Вместо >> надо сдвигать биты в сторону последнего,
и вместо big & 1 анализировать последний бит

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста оптимальный алгоритм

А>M mod N = F

А>M — большое целое число
А>N — значение от 4 до 26;

А>Необходимо взять по модулю, если нет операции деления, только сдвиги вправо и влево..
N -не такое уж и большое. Я б отдельно кля каждого N написал бы алгоритмы. Так при n=4 это последние два разряда.т=8, 16 3 и 4 разряда. Ну, и совместил там, где на множители можно разложить. И сдвигами, конечно, там где нельзя выкрутиться. Классика..