Эффективно возьмите N младших битов GMP mpz_t

#c #c #performance #bit-manipulation #gmp

Вопрос:

Существует mpz_class оболочка C типа GMP mpz_t . Имея mpz_class число, каков наиболее эффективный способ использовать его N младшие биты для создания другого mpz_class числа?

Конечно, я могу выполнить следующую операцию маскировки

 size_t N = 273; // how many lo bits to take
mpz_class x = ... ; // fill with something...
mpz_class mask = (mpz_class(1) << N) - 1; // mask having N 1-bits
mpz_class result = x amp; mask; // final result, N lowest bits taken

Но эта маскировка требует большого количества ненужных битовых операций и замедляет код. Может быть, для этого есть какой-нибудь короткий путь, например result = x.take_lo(N); ?

Также возможно, что mpz_class отсутствует такой ярлык, но, по крайней мере, может быть, C API имеет эту функцию? Потому что любой mpz_class из них может быть легко преобразован без дополнительных затрат в C-тип mpz_t mpz_t c_num = x.get_mpz_t(); . Так что для меня нормально иметь .take_lo(N) ярлык только в C API.

1. «и замедляет код» Было бы неплохо, если бы вы отредактировали свой ответ, чтобы показать нам профилировщик, показывающий, что он действительно работает и является узким местом в вашем коде.

2. API C имеет mpz_tdiv_r_2exp : разделите на степень 2 и возьмите остаток. Это то, что вы хотите, и в нем используется очевидная эффективная реализация . Кажется, стоит попробовать.

3. @Kaihaku Мой код интенсивно использует эти операции маскировки. Но в любом случае, когда вы занимаетесь кодированием, очень приятно знать все лучшие доступные функции/операции и использовать их. Здесь определенно делать И операции не нужно, вам просто нужно скопировать наименьшие N битов в новое число, и все, нет необходимости в И.

4. @NateEldridge Спасибо! Именно то, что нужно!

Ответ №1:

Хотя для оператора C нет перегрузки или функции mpz_class , вы действительно можете использовать: mpz_tdiv_r_2exp предоставлено C API. например,

 mpz_tdiv_r_2exp(result.get_mpz_t(), x.get_mpz_t(), N);

примечание: cdiv и fdiv варианты также доступны.

Использование mp_bitcnt_t в качестве типа для (N) или static_cast<mp_bitcnt_t>(N) в качестве аргумента было бы более надежным — как mp_bitcnt_t , по-видимому, безоговорочно определено как unsigned long , что может не совпадать size_t .

1. Вы уверены, что предложенная вами функция быстрее и оптимизирована, чем мое решение? Потому что я открыл вашу связанную документацию и в разделе функция увидел комментарий For the 2exp variants the divisor is 2^b. These functions are implemented as right shifts and bit masks. , так как я понимаю, что он выполняет маскировку битов, следовательно, делает то же самое, что и я, много ненужных И операций.

2. Хорошо, я написал код для измерения времени, и ваша функция появилась 2.1x в разы быстрее, чем мое решение для маскировки И маскировки. Так что, если ваша функция все еще работает И работает, то, по крайней мере, она делает это в два раза быстрее. Так что принимаю и одобряю ваш ответ. Спасибо!

3. Как @NateEldredge опубликовал ссылку на код в комментарии, по этой ссылке можно увидеть, что mpz_tdiv_r_2exp на самом деле это не так, и просто копирует более низкие данные числа. Так что это вполне оптимально.