Добрый день. Может кто знает, есть ли для Си (желательно, но можно и для C++) библиотека для работы с длинными двоичными числами, где поддерживаются стандартный операции сложения, деления, деления по модулю, умножения, сравнения?

gmp.

Нет, сам не пробовал.

Но вполне работает, многие пользуются.

tzirechnoy, ты вопрос внимательно прочитал? Ему с двоичными числами надо работать, а не с десятичными.

kemiisto, а какая разница? ;-) gmp, к слову, к системе счисления не привязан

Я не смог найти функций, отвечающих за какую-то определенную CC.
Нашеол только функции конвертации числа в другую систему. Она записывает результат в строку.
Смотрел для Си.

Конечно, можно было бы каждое двоичное число вручную переводить в десятичную СС, получить нужный результат, а потом перевести обратно.
Но это кастыль кастылем, и время работы увеличивается очень сильно, т.к. числа порядка 2^4000-5000.

Хотел сначала сам написать двоичную арифметику, но подумал, что есть готовая библиотека, где реализовано качественное продакш решение.

https://gmplib.org/manual/Converting-Integers.html
https://gmplib.org/manual/Assigning-Integers.html

Вопрос стоит в том, как умножить/разделить два числа, хранящихся в строке с помощью API библиотеки?

Ну так и сделать, перегнать их в gmp структура, перемножить gmp функциями, сделать обратно строки... А что вас смещает в таком подходе? Я не думаю что это на много медленнее чем перемножение строк вручную. А деление довольно сложно сделать в любом случае.

меня смущает конвертация чисел туда-сюда порядка 2^4000-2^5000 в количестве 1млн штук.

Хотя, если подумать, то наверное это не так много времени займет, как думается.
Попробую, потом вернусь к теме, если не устроит:)

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

Давайте подумаем, если взять умножение, то не переводить в бинарный вид, и числа, скажем по 4000 символов (0,1), то нужно посчитать в среднем 2000 4000-символьных строк сдвинуть и сложить. можно оптимизировать, но сразу заметно как это бьет по произовдительности. Поэтому правильное решение все же перевести в бинарную форму и скормить такому зверю как gmp.


Нужно бы бенчмарк сделать. быстрое умножение строки на строку в интернете легко найти



Это сообщение отредактировал(а) sQu1rr - 12.5.2015, 16:56

Это если хранить 1 бит в одном байте.
А если хранить биты в битах? Например, в типе __int64?
Производительность резко возрастает, если смотреть в конкретном случае, а не в термине "О большое".



Умножение столбиком и без интернета пишется ~5 минут.


Просто сравнивать самописное умножение столбиком двух строк, даже с оптимизацией хранения бит в бите (а не байте) немного глупо, так как умножение в gmp реализовано посредством метода Карацубы.

Я надеялся найти библиотеку наподобии gmp, но только для бинарных чисел.

P.S. Написав последнее предложение я понял, что всего лишь ищу gmp с оберткой для двух функций - конвертации и занесения результата в структуру:). Так как оптимизация по памяти - это то же n-разрядное число в машине, которые мы видим в десятичной СС, ну а оптимизация по времени - тут gmp монстр монстров.

sQu1rr, спасибо, Вы оказались правы.

Это сообщение отредактировал(а) konshyn - 12.5.2015, 17:13

  

наконец-то