Каков максимальный предел для boost-multiprecision cpp_int?

Question

Я работаю над факторингом больших полупростых чисел. Я работаю над Java, но мне просто интересно изучить и другие варианты. Я знаю, что C ++ Boost multiprecision поддерживает большие числа.

На странице Boost я нашел следующую информацию:

typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> >   uint128_t;
typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> >   uint256_t;
typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> >   uint512_t;
typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;

Мой вопрос: каково ограничение наибольшего числа типов cpp_int? В Java BigInteger поддерживает до 2 ^ Integer.MAX_VALUE.

Спасибо.

Answer 1

cpp_int не имеет [теоретического] максимального значения

Важно иметь в виду, что в Java максимальный размер значения ограничен физическими ограничениями виртуальной машины Java для представления значения. В базовой реализации Java (возможно) реализует BigInteger примерно так:

public class BigInteger {
    private long[] bits;//limited by the maximum size of an array in Java
    /*...*/
}

^{Отказ от ответственности: я не знаю, используют ли они long[] или int[] для хранения битов.}

Аналогично, в C ++, cpp_int, когда вы стираете абстракции, реализован в довольно похожей конструкции:

class boost::multiprecision::cpp_int {
    uint64_t * bits;
    uint64_t * end; //Points to the element-after-the-last in bits
    /*...*/
};

^{Отказ от ответственности Еще раз: они, вероятно, делают что-то более умное, чем это.}

Теоретическим ограничением для Java является тот факт, что JVM устанавливает жесткие ограничения для размеров массивов на Integer.MAX_VALUE, поскольку массивы индексируются с int вместо long. C ++ может напрямую использовать указатели, поэтому максимальный размер cpp_int в C ++ пропорционален максимальному диапазону памяти, к которому может обращаться указатель - который в 64-битных архитектурах обычно, но не всегда ™ 2 ⁶⁴ -1; или, другими словами, максимальное значение cpp_int составляет 2 ^{2 64 -1} -1, с учетом или на порядок в зависимости от того, как они реализуют знак.

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

На практике самое большое значение для cpp_int (и, соответственно, для BigInteger в Java) - это практический предел того, сколько памяти может быть выделено вашей среде выполнения.