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

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

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

Сила 2.

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

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

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

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

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

ab+cd...;

Либо выберите 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-кратным лежачим полицейским, на который вы могли бы надеяться.

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

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

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