Какова удобная база для алгоритма тестирования bignum библиотеки и простоты?

Question

Я должен запрограммировать тест примитивности Соловая-Штрассена, представленный в оригинальной статье на RSA.

Кроме того, мне нужно написать небольшую библиотеку bignum, поэтому при поиске удобного представления для bignum я наткнулся на эту спецификацию :

struct {
  int sign;
  int size;
  int *tab;
} bignum;

Я также буду писать процедуру умножения с использованием метода Карацубы.

Итак, на мой вопрос:

На какой базе будет удобно хранить целочисленные данные в структуре bignum?

Примечание. Мне запрещено использовать сторонние или встроенные реализации для bignum, такие как GMP.

Спасибо.

Answer 1

мощность 2.

Для простой реализации, возможно, половина размера слова на вашем компьютере, чтобы вы могли умножить две цифры без переполнения. Так, 65536 или 4294967296. Или, возможно, вдвое меньше, чем самый большой целочисленный тип, по той же причине, но, возможно, лучшая производительность по сравнению со всеми.

Но я никогда не реализовывал такую ​​библиотеку: если вы используете самые известные алгоритмы, вы не будете делать длинное умножение в школьном стиле. Умножение Карацубы (и любые другие хитрые трюки, которые вы используете) может принести пользу от целого числа, которое более чем в два раза больше цифр, я действительно не знаю, как работает производительность. Если это так, то лучше всего использовать 256- и 32-разрядную арифметику или 65536 и 64-разрядную арифметику.

В любом случае, если ваше представление является двоичным, то вы можете выбирать более мощные базы двух степеней, удобные для каждой операции. Например, вы можете обработать данные как базу 2 ^ 16 для умножения, но базу 2 ^ 32 для сложения. Это все то же самое, если вы осторожны с порядком байтов. Я, вероятно, начну с базы 2 ^ 16 (поскольку это заставляет меня правильно начинать с порядком байтов, а 2 ^ 8 - нет), и посмотрим, как я добьюсь - поскольку каждая операция оптимизирована, часть Оптимизация заключается в том, чтобы определить лучшую базу.

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

Answer 2

В целом вы будете выполнять следующую операцию:

а B + C д ...;

Либо выберите 1/4 самого большого размера слова, либо 1/2 самого большого размера слова, не более одного-двух битов. Это будет 2 ^ 16 или 2 ^ 30 для 64-битных систем и 2 ^ 8 или 2 ^ 14 для 32-битных систем. Используйте самый большой размер, поддерживаемый компилятором, а не аппаратное обеспечение.

Если вы выберете 2 ^ 31 в 64-битной системе, это означает, что вы можете добавить 4 продукта без переполнения. Если вы выберете 2 ^ 30, вы можете добавить 16 продуктов без переполнения. Чем больше вы можете добавить без переполнения, тем больше промежуточных блоков вы можете использовать.

Если вы выберете 1/4 размера слова, у вас останется собственный тип, поэтому будет проще сохранять результаты обратно. Вы можете в значительной степени игнорировать переполнение тоже. Это в основном сделает написание кода быстрее и менее подвержено ошибкам, а также немного более эффективно использует память. Я бы порекомендовал это, если вы не любите много манипуляций с математикой.

Выбор большего основания сделает большие числа O лучше. На практике, хотя, вероятно, было бы быстрее иметь большую базу, это не будет 4-кратным ударом скорости, на который вы могли бы надеяться.

Answer 3

Целые числа в массиве табуляции должны быть без знака. Они должны иметь максимально возможный размер (основание), который вы можете умножить, и при этом представлять продукт. Если ваш компилятор / процессор поддерживает, например, 64-битный long без знака long, вы можете использовать uint32_t для массива «цифр». Если ваш компилятор / процессор может производить только 32-битные продукты, используйте uint16_t.

Когда вы суммируете два массива, вам придется иметь дело с переполнением; в сборке это легко. В C вы можете использовать один бит меньше (31 или 15), чтобы упростить обнаружение переполнения.

Также учтите порядок байтов и то, как он и алгоритм будут влиять на поведение кэша.

Answer 4

Используемое вами основание должно быть степенью 2. Поскольку похоже, что вы собираетесь отслеживать знак отдельно, вы можете использовать беззнаковые целые для хранения самих чисел. Вам понадобится умение умножать по 2 штуки / цифры / единицы этих чисел за раз, поэтому размер должен быть не больше, чем половина имеющегося у вас размера слова. то есть на x86 беззнаковое целое число составляет 32 бита, поэтому вы хотите, чтобы ваши цифры были не более 16 бит. Вы также можете использовать «long long» для промежуточных результатов продуктов беззнаковых целых. Тогда вы смотрите на 2 ^ 32 для вашей базы. И последнее, что нужно учитывать, - это то, что вы можете добавить суммы продуктов, которые будут переполнены, если вы не будете использовать меньше битов.

Если производительность не является серьезной проблемой, я бы просто использовал базу 256 и назвал бы ее день. Возможно, вы захотите использовать typedefs и определенные константы, чтобы впоследствии вы могли легко изменить эти параметры.