То, как делает GMP, хранит его целые числа на произвольном числе байтов?
2^64 все еще далеко от "бесконечности", которую может обработать мой поршень/жесткий диск...
Сначала интересно, как GMP работает с памятью/процессором, так как это делает некоторые теневые оптимизации...
Я также задавался вопросом, существует ли способ сохранить целое число (неподписанный, это легче) на произвольном числе байтов. Например, на 50 байтах, у меня было бы ограничение 2^400 - 1. Нужно должен работать хорошо с переносами для хранения числа последовательным от одного байта до другого, у меня есть некоторая идея об этом, но я действительно не уверен, что это был бы самый быстрый способ сделать это. Я даже не уверен, прав ли я.
Я предполагаю, что GMP использует этот способ, чтобы хранить его данные, но я просто хочу некоторых (даже мало) объяснение или некоторая передача некоторой теории (у меня нет докторской степени, не будьте жестки).
1 ответ
GMP динамически выделяет пространство для представления чисел (и перераспределяет, когда нужно увеличить).
Это описано в легких деталях в Integer Internals, в руководстве GMP, там описывается, как он разбивает представление на "конечности" и хранит конечности в массиве.
Описание термина "конечности" взято из GMP Basics: Номенклатура и типы:
Лимб означает часть многопрецизионного числа, которая помещается в одно слово. (Мы выбрали это слово, потому что конечность человеческого тела аналогична цифре, только больше и содержит несколько цифр). Обычно лимб содержит 32 или 64 бита. Тип данных языка Си для конечности - mp_limb_t.
Таким образом, представление числа в GMP работает путем группировки количества конечностей вместе для представления величины целого числа, хранящегося со знаковым битом (знаковый бит имеет двойное назначение для хранения количества конечностей).
Что это значит для вас? Ну, обычно int64 представляется в 64 битах. Готово. Если вы соберете их вместе, то сможете значительно увеличить это число. Сложите два вместе, 2^64*2^64, или 2^128. Добавьте еще две конечности и получите 2^256. Это очень много чисел, хранящихся в 4 словах (плюс накладные расходы на представление).
Конечно, представление плавающих чисел сложнее (см. здесь), хранение представления с использованием мантиссы (состоящей из знака и величины) и экспоненты.