Как найти остаток без деления или оператора по модулю в сборке MIPS

Я хочу найти способ узнать, делится ли целое число на 3 или 7 без использования деления, потому что это очень медленно в сборке MIPS.

Я провел много исследований, но ничего не нашел.


assembly mips modulo modulus
person user3380858    schedule 05.03.2014    source источник
comment
stackoverflow .com/questions/6896533/   -  person phuclv    schedule 05.03.2014

Ответы (2)


arrow_upward
3
arrow_downward

Существует метод, описанный Granlund & Montgomery, который требует модульной/мультипликативной инверсии ( нечетный) делитель по модулю 2**b. (Некоторые части этого документа были улучшены недавно)

Делители: (d) = 3, 7 (нечетные числа) — это простой случай. Предполагая 32-битную (беззнаковую) арифметику, инверсии по модулю 2**32 дают 2863311531 (0xAAAAAAAB) и 3067833783 (0xB6DB6DB7) соответственно. здесь есть онлайн-калькулятор.

Нам также нужны значения qmax = (2**32 - 1) / d: 0x55555555 и 0x24924924 соответственно.

Чтобы проверить 32-битное (беззнаковое) число (n), выполните умножение одного слова, то есть отбросьте старшее слово полного 64-битного результата: q = dinv * n

Если (n) делится на (d), то (q) должно удовлетворять: q * d == n и q <= qmax. например.,

int is_divisible_by_3 (uint32_t n)
{
    uint32_t q = n * 0xAAAAAAAB;
    return (q <= 0x55555555 && (q * 3 == n))    
}

Который заменяет деление/остаток парой умножений отдельных слов.

И аналогично для d = 7. В качестве альтернативы современный компилятор, такой как gcc, будет выполнять аналогичную оптимизацию для постоянного делителя/модуля, например, if (n % 3 == 0) ... - в сборке, сгенерированной для MIPS и т. д.

person Brett Hale    schedule 05.03.2014

arrow_upward
0
arrow_downward

Вы можете суммировать остатки для отдельных битов. 2^n mod 3 идет как 1,2,1,2,..., а 2^n mod 7 идет как 1,2,4,1,2,4,....

Используйте таблицу поиска, чтобы сделать это еще быстрее.

person Jester    schedule 05.03.2014