Если вы когда-либо пробовали работать с большими числами в дельфи, то наверняка рано или поздно сталкивались с размерами чисел, которые явно превосходят допустимые пределы integer, и более того int64: Min значение integer = -2147483648 Max значение integer = 2147483647 Min значение int64 = -9223372036854775808 Max значение int64 = 9223372036854775807
Можно было бы изобрести велосипед и написать свой алгоритм для произведения операций с такими числами, записывая их в строки, или же создать свой тип данных, но проще использовать готовые библиотеки для работы с такими числами. Существует десятки разнообразных компонентов, библиотек и модулей для работы с большими числами, я остановил свой выбор на BigInt.
Установка простая: Добавляем папку с библиотекой в Enviroment Options - Librart Path. Для использования библиотеке в Вашем проекте в Uses дописываем sdpBigint и sdpConvert. Рассмотрим основные операции с нашими новыми типами:
Процедуры инициализации
Выделяет под число память размером StartSize блоков и присваивает числу значение 0. При этом обнуляется только младший блок числа. Если StartSize отсутствует или оно меньше, чем MinSizeBigint, то выделяется MinSizeBigint блоков. procedure CreateBigint(var A: TBigint; StartSize: Byte = 0);
Устанавливает размер числа равным NewSize блоков. Если старый размер числа был больше чем NewSize, то все старшие блоки отбрасываются. Если NewSize < MinSizeBigint, то устанавливается размер, равный MinSizeBigint. procedure SetSizeBigint(var A: TBigint; NewSize: Byte);
Удаляет лидирующие неиспользуемые блоки, но размер числа не может быть меньше, чем MinSizeBigint блоков. procedure PackBigint(var A: TBigint);
Выполняет A := 0 и обнуляет всю память, отведенную под число. Если необходимо выполнить только присваивание A := 0, то рекомендуется воспользоваться процедурой конвертации IntToBigint из модуля sdpConvert. procedure SetZeroBigint(var A: TBigint);
Копирует A в B, то есть выполняет B := A. procedure CopyBigint(const A: TBigint; var B: TBigint);
Перемещает A в B, то есть выполняет B := A и A := 0. Эффективнее, чем CopyBigint, особенно для очень больших чисел. procedure MoveBigint(var A, B: TBigint);
Основные арифметические операции
Вычисляет C := A + B procedure AddBigint(const A, B: TBigint; var C: TBigint); overload; procedure AddBigint(const A: TBigint; B: Cardinal; var C: TBigint); overload;
Вычисляет A := A + Delta, эквивалентно AddBigint(A, Delta, A). procedure IncBigint(var A: TBigint; Delta: Cardinal);
Вычисляет C := A - B procedure SubBigint(const A, B: TBigint; var C: TBigint); overload; procedure SubBigint(const A: TBigint; B: Cardinal; var C: TBigint); overload;
Вычисляет A := A - Delta, эквивалентно SubBigint(A, Delta, A). procedure DecBigint(var A: TBigint; Delta: Cardinal);
Вычисляет C := A * B procedure MulBigint(const A, B: TBigint; var C: TBigint); overload; procedure MulBigint(const A: TBigint; B: Cardinal; var C: TBigint); overload;
Вычисляет C := A div B, D := A mod B. procedure DivBigint(const A, B: TBigint; var C, D: TBigint); overload; function DivBigint(const A: TBigint; B: Cardinal; var C: TBigint): Cardinal; overload;
Дополнительные арифметические операции
Вычисляет B := A*(Base^N), где Base - основание системы счисления, и в данном случае равно 2^32. Фактически, означает сдвиг влево на N блоков. procedure MulByPowerBase(A: TBigint; N: Byte; var B: TBigint);
Вычисляет Y := X^N mod M. Используется бинарный метод "S и X". procedure PowerMod(const X, N, M: TBigint; var Y: TBigint);
Обобщенный алгоритм Евклида A*B + C*D = G = GCD(A,B) procedure ExtEuclidGCD(const A, B: TBigint; var G, C, D: TBigint); procedure EuclidGCD(const A, B: TBigint; var C: TBigint);
procedure SqrBigint(const A: TBigint; var B: TBigint);
Низкоуровневые арифметические операции
Выполняет C := |A|+|B|. Беззнаковое низкоуровневое сложение. Поле C.MSB устанавливается соответствующим образом. Все остальные поля аргументов остаются неизменными. Аргументы должны удовлетворять следующим условиям (проверок на корректность аргументов не производится): 1) A.MSB >= B.MSB. 2) результат операции должен помещаться в C. procedure LowLevelAdd(const A, B: TBigint; var C: TBigint);
Выполняет C := |A|-|B|. Беззнаковое низкоуровневое вычитание. Поле C.MSB устанавливается соответствующим образом. Все остальные поля аргументов остаются неизменными. Аргументы должны удовлетворять следующим условиям (проверок на корректность аргументов не производится): 1) |A| > |B|, т. е. результат операции должен быть положительным. В случае, если |A| = |B|, процедура установит C.MSB = 0. 2) результат операции должен помещаться в C. procedure LowLevelSub(const A, B: TBigint; var C: TBigint);
Выполняет C := |A|*|B|. Беззнаковое низкоуровневое умножение "столбиком". Поле C.MSB устанавливается соответствующим образом. Все остальные поля аргументов остаются неизменными. Аргументы должны удовлетворять следующим условиям (проверок на корректность аргументов не производится): 1) C.Digits должен содержать нули во всех байтах. 2) входные и выходные аргументы совпадать не могут. 3) результат операции должен помещаться в C. procedure LowLevelMul(const A, B: TBigint; var C: TBigint);
Вот и все. Библиотека легка в использовании, довольно быстра и удобна.
hanik, в общем баловался я с этой библиотекой, когда программу для вычисления огромных факториалов писал, гиблое дело, выходит, совсем не порадовало. И перепробовал ряд других библиотек - тоже самое. Пришлось писать самому алгоритм умножения в столбик, а уже ним - получиться и факториалы рассчитывать, и в степень возводить. Тоже самое с добавлением/вычитанием. Так что выход тут - либо найти что-то понятное, простое и стабильное, либо написать свое.
MAcK, да, но если речь идет, например, о вычислении факториалов, хотя бы, больше, чем 20! (20!=2432902008176640000), то тут int64 уже поможет в роли уж очень большого контейнера для промежуточной записи значений во время использования алгоритма умножения, например, в столбик (ну, к примеру, для записи результатов сложения столбиков цифр). Или я что-то упускаю?
