Чрезвычайно большое целочисленное умножение и сложение - PullRequest
Новая
       33

Чрезвычайно большое целочисленное умножение и сложение

4 голосов
/ 06 июня 2010

Привет,

Мне нужно умножить два чрезвычайно длинных целочисленных значения, хранящихся в текстовом файле (экспортированном через GMP (точнее, MPIR), чтобы они могли быть любыми в любой базе).Теперь я обычно импортирую эти целые числа через функцию mpz_inp_str () и выполняю умножение в ОЗУ, однако эти значения настолько длинные, что я не могу их реально загрузить (около 1 ГБ данных каждый).Какой самый быстрый способ сделать это?Возможно, есть какие-то внешние библиотеки, которые уже делают подобные вещи?Существуют ли какие-либо легко реализуемые методы для этого (производительность не является невероятно важной, поскольку эта операция будет выполняться только один или два раза)?

tl; dr: мне нужно умножить значения настолько большими, чтобы они не вписывались в процессограничения памяти (Windows).

Спасибо за потраченное время.

1 Ответ

4 голосов
/ 06 июня 2010

Я не знаю, есть ли библиотека, которая поддерживает это, но вы могли бы использовать GMP / MPIR для частей каждого действительно большого числа (RBN). То есть начните с разбивки каждого RBN на управляемые куски одинакового размера (например, 10-значные куски, ожидайте меньший по размеру кусочек для наиболее значимых цифр, также см. Ниже). 

    RBN1 --> A B C D E
    RBN2 --> F G H I J

Чанкинг можно выполнить в базе 10, поэтому просто прочитайте символы из файла для каждого фрагмента. Затем умножьте куски от каждого номера по одному. 

     AxF BxF CxF DxF ExF
    +    AxG BxG CxG DxG ExG
    +        AxH BxH CxH DxH ExH
    +            AxI BxI CxI DxI ExI
    +                AxJ BxJ CxJ DxJ ExJ

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

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

Как для чтения, так и для записи, я бы предложил использовать файлы с отображением в памяти, у boost есть приятный интерфейс для this (обратите внимание, что при этом не загружается весь файл, он просто в основном буферизирует IO на виртуальном объем памяти). Откройте один сопоставленный файл для каждого входного номера RBN и один выход с размером = размер (RBN1) + размер (RBN2) + 1; Для файлов, отображаемых в память, доступ к файлам обрабатывается как raw char *, поэтому вы можете читать / записывать куски напрямую, используя gmp c-string io методы. Вам, вероятно, потребуется прочитать в промежуточный буфер, чтобы NULL завершал строки для GMP (если только вы не хотите временно изменить файл отображения памяти).

Это не очень легко реализовать правильно, но опять же, это не особенно простая проблема (может быть, просто утомительная). Преимущество этого подхода состоит в том, что он точно отражает то, что GMP выполняет в памяти, поэтому алгоритмы хорошо известны.

...