GHC.Integer.GMP.Internals

Авторские права	(c) Herbert Valerio Riedel 2014
Лицензия	BSD3
Поддерживающий	ghc-devs@haskell.org
Стабильность	временная
Переносимость	непереносимая (расширения GHC)
Безопасный Haskell	Нет
Язык	Haskell2010

Тип Integer

data Integer Источник

Целые числа произвольной точности. В отличие от целочисленных типов фиксированной длины, таких как Int, тип Integer представляет весь бесконечный диапазон целых чисел.

Дополнительную информацию о представлении этого типа можно найти в комментариях к его реализации.

isValidInteger# :: Integer -> Int# Источник

Проверка, выполняются ли все внутренние инварианты для значения Integer

Возвращает 1#, если значение допустимо, 0#, в противном случае.

Эта операция в основном полезна для наборов тестов и/или кода, который напрямую создает значения Integer.

Основные операции Integer

module GHC.Integer

Дополнительные операции Integer

gcdInteger :: Integer -> Integer -> Integer Источник

Вычисление наибольшего общего делителя.

gcdExtInteger :: Integer -> Integer -> (# Integer, Integer #) Источник

Расширенный алгоритм Евклида.

Для a и b, вычислить их наибольший общий делитель g и коэффициент s удовлетворяющий as + bt = g.

С момента: integer-gmp-0.5.1.0

lcmInteger :: Целое число -> Целое число -> Целое число Исходный код

Вычислить наименьшее общее кратное.

sqrInteger :: Целое число -> Целое число Исходный код

Возвести Integer в квадрат

powModInteger :: Целое число -> Целое число -> Целое число -> Целое число Исходный код

"powModInteger b e m" вычисляет основание b в степени e по модулю abs(m).

Поддерживаются отрицательные показатели, если существует обратный элемент по модулю m.

Предупреждение: Рекомендуется избегать вызова этой функции с отрицательными показателями, если не гарантировано существование обратного элемента, так как это может привести к прерыванию программы из-за ошибки деления на ноль. См. также recipModInteger.

В будущих версиях integer_gmp могут быть больше не поддерживаться отрицательные e значения.

С момента: integer-gmp-0.5.1.0

powModSecInteger :: Целое число -> Целое число -> Целое число -> Целое число Исходный код

"powModSecInteger b e m" вычисляет основание b в степени e по модулю m. Требуется, чтобы e >= 0 и m были нечётными.

Это "безопасная" версия powModInteger, использующая функцию mpz_powm_sec(), разработанную для устойчивости к атакам по каналам утечки информации и предназначенную для криптографических применений.

Этот примитив доступен только при условии поддержки им underlying GMP библиотекой (GMP >= 5). В противном случае он внутри переключается на powModInteger, и при использовании будет выведено предупреждение.

С момента: integer-gmp-1.0.2.0

recipModInteger :: Целое число -> Целое число -> Целое число Исходный код

"recipModInteger x m" вычисляет обратный элемент x по модулю m. Если обратный элемент существует, возвращаемое значение y будет удовлетворять 0 < y < abs(m), в противном случае результат будет 0.

С момента: integer-gmp-0.5.1.0

Дополнительные операции преобразования в Integer

wordToNegInteger :: Слово# -> Целое число Исходный код

bigNatToInteger :: BigNat -> Целое число Исходный код

bigNatToNegInteger :: BigNat -> Целое число Исходный код

Тип BigNat

data BigNat Исходный код

Тип, представляющий сырые натуральные числа произвольной точности

Этот тип часто используется в Natural и Integer. Поскольку этот тип состоит из одного конструктора, обернутого вокруг ByteArray#, его можно распаковать.

Основные инварианты:

• Размер ByteArray# является точным кратным размеру Word#
• Значения разрядов хранятся в порядке от младшего к старшему разряду,
• старший разряд должен быть ненулевым, за исключением
• 0, который представлен одним разрядом.

type GmpLimb = Word Исходный код

Тип, представляющий GMP Limb

type GmpLimb# = Word# Исходный код

type GmpSize = Int Исходный код

Количество GmpLimbs, должно быть положительным (если не указано иное).

type GmpSize# = Int# Исходный код

isValidBigNat# :: BigNat -> Int# Исходный код

Проверка, удовлетворяются ли все внутренние инварианты значением BigNat

Возвращает 1#, если значение валидно, 0# в противном случае.

Эта операция в основном полезна для наборов тестов и/или кода, который напрямую создаёт значения Integer

sizeofBigNat# :: BigNat -> GmpSize# Исходный код

Возвращает количество разрядов, содержащихся в BigNat.

Результат всегда >= 1 , так как даже ноль кодируется одним разрядом.

zeroBigNat :: BigNat Исходный код

CAF, представляющий значение 0 :: BigNat

oneBigNat :: BigNat Исходный код

CAF, представляющий значение 1 :: BigNat

nullBigNat :: BigNat Исходный код

Специальный bigNat размером 0, возвращаемый в случае арифметического переполнения.

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

• minusBigNat
• minusBigNatWord

Другие операции, такие как quotBigNat , могут возвращать nullBigNat, а также фиктивное/заполнительное значение вместо undefined, так как мы не можем выбросить исключения. Но на этом поведении полагаться не стоит.

Примечание: isValidBigNat# nullBigNat ложно

Преобразования в/из BigNat

byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat Исходный код

Создаёт BigNat из существующего ByteArray# , содержащего n GmpLimb в порядке от наименее значимого к наиболее значимому.

Если возможно ByteArray#, будет использоваться напрямую (т.е. общий, без клонирования ByteArray# в вновь выделенный).

Примечание: параметр размера (умноженный на sizeof(GmpLimb)) должен быть меньше или равен его sizeofByteArray#.

wordToBigNat :: Word# -> BigNat Source

Создать 1-разрядное BigNat из Word#

wordToBigNat2 :: Word# -> Word# -> BigNat Source

Создать BigNat из 2 разрядов. Первый аргумент - старший разряд.

bigNatToInt :: BigNat -> Int# Source

Эквивалентно word2Int# . bigNatToWord

bigNatToWord :: BigNat -> Word# Source

То же, что и indexBigNat# bn 0#

indexBigNat# :: BigNat -> GmpSize# -> GmpLimb# Source

Извлечь n-ый (с нулевой базой) разряд в BigNat. n должно быть меньше размера, как сообщается sizeofBigNat#.

BigNat арифметические операции

plusBigNat :: BigNat -> BigNat -> BigNat Source

plusBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

minusBigNat :: BigNat -> BigNat -> BigNat Source

Возвращает nullBigNat (см. isNullBigNat#) в случае underflow

minusBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

Возвращает nullBigNat (см. isNullBigNat#) в случае underflow

timesBigNat :: BigNat -> BigNat -> BigNat Source

timesBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

sqrBigNat :: BigNat -> BigNat Source

Квадрат BigNat

quotRemBigNat :: BigNat -> BigNat -> (# BigNat, BigNat #) Source

Если делитель равен нулю, возвращается (# nullBigNat, nullBigNat #)

quotRemBigNatWord :: BigNat -> GmpLimb# -> (# BigNat, GmpLimb# #) Source

Примечание: Результат деления на 0 не определен

quotBigNatWord :: BigNat -> GmpLimb# -> BigNat Source

quotBigNat :: BigNat -> BigNat -> BigNat Source

remBigNat :: BigNat -> BigNat -> BigNat Source

remBigNatWord :: BigNat -> GmpLimb# -> Word# Source

Деление на 0 не проверяется

gcdBigNat :: BigNat -> BigNat -> BigNat Source

gcdBigNatWord :: BigNat -> Word# -> Word# Source

powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat Source

Версия powModInteger для работы с BigNat.

С: integer-gmp-1.0.0.0

powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb# Source

Версия powModInteger для модулей размера Word#.

С: integer-gmp-1.0.0.0

recipModBigNat :: BigNat -> BigNat -> BigNat Source

Версия recipModInteger для работы с BigNat.

С: integer-gmp-1.0.0.0

BigNat логические операции

shiftRBigNat :: BigNat -> Int# -> BigNat Source

shiftLBigNat :: BigNat -> Int# -> BigNat Source

testBitBigNat :: BigNat -> Int# -> Bool Source

andBigNat :: BigNat -> BigNat -> BigNat Source

xorBigNat :: BigNat -> BigNat -> BigNat Source

popCountBigNat :: BigNat -> Int# Source

orBigNat :: BigNat -> BigNat -> BigNat Source

bitBigNat :: Int# -> BigNat Source

Специализированная версия

bitBigNat = shiftLBigNat (wordToBigNat 1##)

избегающая нескольких избыточных выделений.

BigNat предикаты сравнения

isZeroBigNat :: BigNat -> Bool Source

Проверка, является ли значение BigNat равным нулю.

isNullBigNat# :: BigNat -> Int# Source

Проверка на специальное значение BigNat размером 0, представляющее переполнение.

compareBigNatWord :: BigNat -> GmpLimb# -> Ordering Source

compareBigNat :: BigNat -> BigNat -> Ordering Source

eqBigNatWord :: BigNat -> GmpLimb# -> Bool Source

eqBigNatWord# :: BigNat -> GmpLimb# -> Int# Source

eqBigNat :: BigNat -> BigNat -> Bool Source

eqBigNat# :: BigNat -> BigNat -> Int# Source

gtBigNatWord# :: BigNat -> GmpLimb# -> Int# Source

Разные операции, предоставляемые GMP

gcdInt :: Int# -> Int# -> Int# Source

Вычислить наибольший общий делитель.

Предупреждение: результат может стать отрицательным, если (по крайней мере) один аргумент minBound

gcdWord :: Word# -> Word# -> Word# Source

Вычислить наибольший общий делитель.

С момента: integer-gmp-1.0.0.0

powModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# -> GmpLimb# Source

Версия powModInteger, работающая с Word#

С момента: integer-gmp-1.0.0.0

recipModWord :: GmpLimb# -> GmpLimb# -> GmpLimb# Source

Версия recipModInteger, работающая с Word#

С момента: integer-gmp-1.0.0.0

Проверка простоты

testPrimeInteger :: Integer -> Int# -> Int# Source

Вероятностный тест простоты Миллера-Рабина.

«testPrimeInteger n k» определяет, является ли n простым числом, и возвращает один из следующих результатов:

• 2# возвращается, если n определённо простое,
• 1# если n — вероятное простое число, или
• 0# если n определённо не является простым.

Аргумент k управляет тем, сколько раундов теста выполняется для определения вероятного простого числа. Подробности см. в документации GMP для `mpz_probab_prime_p()`.

С момента: integer-gmp-0.5.1.0

testPrimeBigNat :: BigNat -> Int# -> Int# Source

Версия testPrimeInteger, работающая с BigNat

С момента: integer-gmp-1.0.0.0

testPrimeWord# :: GmpLimb# -> Int# -> Int# Source

Версия testPrimeInteger, работающая с Word#

С момента: integer-gmp-1.0.0.0

nextPrimeInteger :: Integer -> Integer Source

Вероятностно вычислить следующее простое число, большее n.

Согласно документации GMP, подлежащая функция mpz_nextprime() «использует вероятностный алгоритм для определения простых чисел. Для практических целей это достаточно, вероятность того, что составное число пройдёт, будет чрезвычайно мала».

С момента: integer-gmp-0.5.1.0

nextPrimeBigNat :: BigNat -> BigNat Source

Версия nextPrimeInteger, работающая с BigNat

С момента: integer-gmp-1.0.0.0

nextPrimeWord# :: GmpLimb# -> GmpLimb# Source

Версия nextPrimeInteger, работающая с Word#

С момента: integer-gmp-1.0.0.0

Функции импорта/экспорта

Вычисление размера сериализации

sizeInBaseBigNat :: BigNat -> Int# -> Word# Source

Версия sizeInBaseInteger, работающая с BigNat

С момента: integer-gmp-1.0.0.0

sizeInBaseInteger :: Integer -> Int# -> Word# Source

Вычислить количество цифр (без знака) в заданном base.

Эта функция оборачивает mpz_sizeinbase(), которая имеет некоторые особенности реализации, которые необходимо учитывать:

• "sizeInBaseInteger 0 base = 1" (см. также комментарий в exportIntegerToMutableByteArray).
• Эта функция определена только если base >= 2# и base <= 256# (Примечание: документация утверждает, что поддерживается только base <= 62#, однако фактическая реализация поддерживает базы до 256).
• Если base является степенью двойки, результат будет точным. В других случаях (например, для base = 10#), результат может быть иногда на 1 разряд больше.
• "sizeInBaseInteger i 2#" может использоваться для определения старшего бита i.

С момента: integer-gmp-0.5.1.0

sizeInBaseWord# :: Word# -> Int# -> Word# Источник

Версия sizeInBaseInteger, работающая с Word#

С момента: integer-gmp-1.0.0.0

Экспорт

exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word Источник

Версия exportIntegerToAddr, работающая с BigNat.

exportIntegerToAddr :: Integer -> Addr# -> Int# -> IO Word Источник

Выгрузка Integer (без знака) в addr в представлении в базе-256.

exportIntegerToAddr i addr e

См. описание exportIntegerToMutableByteArray для более подробной информации.

С момента: integer-gmp-1.0.0.0

exportWordToAddr :: Word -> Addr# -> Int# -> IO Word Источник

Версия exportIntegerToAddr, работающая с Word.

exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Источник

Версия exportIntegerToMutableByteArray, работающая с BigNat.

С момента: integer-gmp-1.0.0.0

exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Источник

Выгрузка Integer (без знака) в изменяемый массив байтов в представлении в базе-256.

Вызов

exportIntegerToMutableByteArray i mba offset msbf

записывает

• значение Integer i
• в изменяемый массив байтов MutableByteArray# mba начиная с позиции offset
• с старшим байтом впереди, если msbf равно 1#, или с младшим байтом впереди, если msbf равно 0#, и
• возвращает количество записанных байтов.

Используйте "sizeInBaseInteger i 256#", чтобы предварительно вычислить точное количество записываемых байтов для i /= 0. В случае i == 0, exportIntegerToMutableByteArray запишет и сообщит о нулевых записанных байтах, тогда как sizeInBaseInteger сообщит об одном байте.

Рекомендуется избегать вызова exportIntegerToMutableByteArray для небольших целых чисел, так как эта функция в настоящее время преобразует их в большие целые числа в порядке от старшего к младшему биту, чтобы вызвать mpz_export().

С момента: integer-gmp-1.0.0.0

exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Источник

Версия exportIntegerToMutableByteArray, работающая с Word.

С момента: integer-gmp-1.0.0.0

Импорт

importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat Источник

Версия importIntegerFromAddr, создающая BigNat

importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer Source

Прочитать Integer (без знака) из местоположения памяти по адресу addr в представлении по основанию 256.

importIntegerFromAddr addr size msbf

См. описание importIntegerFromByteArray для получения дополнительных сведений.

С момента: integer-gmp-1.0.0.0

importBigNatFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> BigNat Source

Версия importIntegerFromByteArray для построения BigNat.

importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer Source

Прочитать Integer (без знака) из массива байтов в представлении по основанию 256.

Вызов

importIntegerFromByteArray ba offset size msbf

читает

• size байт из ByteArray# ba, начиная с offset
• с старшим байтом впереди, если msbf является 1#, или с младшим байтом впереди, если msbf является 0#, и
• возвращает новый Integer

С момента: integer-gmp-1.0.0.0