GHC.Целое.GMP.Внутреннее представление

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

Тип Integer

data Integer Source

Инвариант: Jn# и Jp# используются, если значение не помещается в S#

Полезные свойства, вытекающие из инвариантов:

• abs (S# _) <= abs (Jp# _)

• abs (S# _) <  abs (Jn# _)

isValidInteger# :: Integer -> Int# Source

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

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

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

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

module GHC.Integer

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

bitInteger :: Int# -> Integer Source

Integer для которого установлен только n-й бит. Неопределенное поведение для отрицательных значений n.

popCountInteger :: Integer -> Int# Source

Подсчет количества установленных битов. Для отрицательных аргументов возвращает отрицательный счет установленных битов для отрицаемого аргумента.

gcdInteger :: Integer -> Integer -> Integer Source

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

gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#) Source

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

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

С: 0.5.1.0

lcmInteger :: Integer -> Integer -> Integer Source

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

sqrInteger :: Integer -> Integer Source

Квадрат Integer

powModInteger :: Integer -> Integer -> Integer -> Integer Source

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

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

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

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

С: 0.5.1.0

recipModInteger :: Integer -> Integer -> Integer Source

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

С: 0.5.1.0

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

wordToNegInteger :: Word# -> Integer Source

bigNatToInteger :: BigNat -> Integer Source

bigNatToNegInteger :: BigNat -> Integer Source

Тип BigNat

data BigNat Source

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

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

Необходимые инварианты:

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

type GmpLimb = Word Источник

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

type GmpLimb# = Word# Источник

type GmpSize = Int Источник

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

type GmpSize# = Int# Источник

isValidBigNat# :: BigNat -> Int# Источник

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

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

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

sizeofBigNat# :: BigNat -> GmpSize# Источник

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

zeroBigNat :: BigNat Источник

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

oneBigNat :: BigNat Источник

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

nullBigNat :: BigNat Источник

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

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

• minusBigNat
• minusBigNatWord

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

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

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

byteArrayToBigNat# :: ByteArray# -> GmpSize# -> BigNat Источник

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

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

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

wordToBigNat :: Word# -> BigNat Источник

Построение 1-членного BigNat из Word#

wordToBigNat2 :: Word# -> Word# -> BigNat Источник

Построение BigNat из 2 членов. Первый аргумент — старший член.

bigNatToInt :: BigNat -> Int# Источник

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

bigNatToWord :: BigNat -> Word# Источник

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

indexBigNat# :: BigNat -> GmpSize# -> GmpLimb# Источник

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

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

plusBigNat :: BigNat -> BigNat -> BigNat Источник

plusBigNatWord :: BigNat -> GmpLimb# -> BigNat Источник

minusBigNat :: BigNat -> BigNat -> BigNat Источник

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

minusBigNatWord :: BigNat -> GmpLimb# -> BigNat Источник

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

timesBigNat :: BigNat -> BigNat -> BigNat Источник

timesBigNatWord :: BigNat -> GmpLimb# -> BigNat Источник

sqrBigNat :: BigNat -> BigNat Источник

Квадрат BigNat

quotRemBigNat :: BigNat -> BigNat -> (#BigNat, BigNat#) Источник

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

quotRemBigNatWord :: BigNat -> GmpLimb# -> (#BigNat, GmpLimb##) Источник

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

quotBigNatWord :: BigNat -> GmpLimb# -> BigNat Источник

quotBigNat :: BigNat -> BigNat -> BigNat Источник

remBigNat :: BigNat -> BigNat -> BigNat Источник

remBigNatWord :: BigNat -> GmpLimb# -> Word# Источник

div/0 не проверяется

gcdBigNat :: BigNat -> BigNat -> BigNat Источник

gcdBigNatWord :: BigNat -> Word# -> Word# Источник

powModBigNat :: BigNat -> BigNat -> BigNat -> BigNat Источник

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

С момента: 1.0.0.0

powModBigNatWord :: BigNat -> BigNat -> GmpLimb# -> GmpLimb# Источник

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

С момента: 1.0.0.0

recipModBigNat :: BigNat -> BigNat -> BigNat Источник

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

С момента: 1.0.0.0

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

shiftRBigNat :: BigNat -> Int# -> BigNat Источник

shiftLBigNat :: BigNat -> Int# -> BigNat Источник

testBitBigNat :: BigNat -> Int# -> Bool Источник

andBigNat :: BigNat -> BigNat -> BigNat Источник

xorBigNat :: BigNat -> BigNat -> BigNat Источник

popCountBigNat :: BigNat -> Int# Источник

orBigNat :: BigNat -> BigNat -> BigNat Источник

bitBigNat :: Int# -> BigNat Источник

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

isZeroBigNat :: BigNat -> Bool Источник

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

isNullBigNat# :: BigNat -> Int# Источник

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

compareBigNatWord :: BigNat -> GmpLimb# -> Ordering Источник

compareBigNat :: BigNat -> BigNat -> Ordering Источник

eqBigNatWord :: BigNat -> GmpLimb# -> Bool Источник

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

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

С версии: 1.0.0.0

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

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

С версии: 1.0.0.0

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

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

С версии: 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()`.

С версии: 0.5.1.0

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

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

С версии: 1.0.0.0

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

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

С версии: 1.0.0.0

nextPrimeInteger :: Integer -> Integer Source

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

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

С версии: 0.5.1.0

nextPrimeBigNat :: BigNat -> BigNat Source

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

С версии: 1.0.0.0

nextPrimeWord# :: GmpLimb# -> GmpLimb# Source

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

С версии: 1.0.0.0

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

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

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

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

С версии: 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 является степенью 2, результат будет точным. В других случаях (например, для base = 10#) результат может иногда быть на 1 цифру больше.
• "sizeInBaseInteger i 2#" может быть использован для определения старшего бита i.

С версии: 0.5.1.0

sizeInBaseWord# :: Word# -> Int# -> Word# Source

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

С момента: 1.0.0.0

Экспорт

exportBigNatToAddr :: BigNat -> Addr# -> Int# -> IO Word Source

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

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

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

exportIntegerToAddr i addr e

См. описание exportIntegerToMutableByteArray для получения дополнительной информации.

С момента: 1.0.0.0

exportWordToAddr :: Word -> Addr# -> Int# -> IO Word Source

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

exportBigNatToMutableByteArray :: BigNat -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

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

С момента: 1.0.0.0

exportIntegerToMutableByteArray :: Integer -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

Вывести 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 для небольших целых чисел, так как эта функция в настоящее время преобразует их в большие целые числа в формате MSBF для вызова mpz_export().

С момента: 1.0.0.0

exportWordToMutableByteArray :: Word -> MutableByteArray# RealWorld -> Word# -> Int# -> IO Word Source

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

С момента: 1.0.0.0

Импорт

importBigNatFromAddr :: Addr# -> Word# -> Int# -> IO BigNat Source

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

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

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

importIntegerFromAddr addr size msbf

См. описание importIntegerFromByteArray для получения дополнительной информации.

С момента: 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

С момента: 1.0.0.0