IntXLib4Pascal

Tintx

TIntX - это порт Pascal в целочисленной целочисленной библиотеке Intx с быстрым, примерно O(N * log N) реализация алгоритмов умножения/деления. Он обеспечивает все основные арифметические операции на целых числах, сравнение, побитовое смещение и т. Д. Также позволяет анализировать числа в разных основаниях и преобразовать их в струну, а также в любой базе. Преимущество этой библиотеки - его быстрое умножение, деление и алгоритмы преобразования базы/до базы. Все быстрые версии алгоритмов основаны на быстрое умножение больших целых чисел с использованием Fast Hartley Transform, которое работает для O(N * log N * log log N) вместо классического O(N^2) .

Статус сборки

Пример кода

Вот образец кода, который использует TIntX для расчета 42 в Power 1048576 (который составляет 2^20 (1 Shl 20)):

 uses // including only the non-obvious
SysUtils, uIntX, uEnums;

procedure Calc ();
var
  valA, valB: UInt32;
  Delta: Double;

begin
  valA := GetTickCount;
  TIntX. Pow ( 42 , 1048576 );
  valB := GetTickCount;
  Delta := (valB - valA) / 1000 ;
  ShowMessage(Format( ' time elapsed is %f seconds ' , [Delta]));
end ;

procedure TForm1.Button1Click (Sender: TObject);

begin
  Calc();
  TIntX.GlobalSettings.MultiplyMode := TMultiplyMode.mmClassic;
  Calc();
end ;

  First 'Calc()' call uses fast multiplication implementation (which is default), 
second, classic one. On my machine (Windows 10 Update 2, Intel Core i3 2.53 GHz, 
6 GB RAM), Compiled with 64 bits, first call took 0.30 seconds while the second one 
took 17.91 seconds.Resulting number has 1,702,101 digits.

Некоторые другие функции, реализованные мне, являются

  IntegerSquareRoot (Integer SquareRoot) 
  Square 
  GCD (Greatest Common Divisor (HCF)) 
  LCM (Least Common Multiple)
  AbsoluteValue (Get Absolute Value of a Negative TIntX)
  Bézouts Identity
  InvMod (Modular Inverse)
  Factorial
  IntegerLogN (base, number) (Gets IntegerLog of a number using a specified base)
  Ln (The natural logarithm)
  Log10 (The base-10 logarithm)
  LogN (Logarithm of a number for a specified base)
  Random (Now Uses PcgRandom Instead of Mersemme Twister)
  Modular Exponentiation (ModPow)
  IsProbablyPrime (based on Miller Rabin Primality Test)

Как видите, TIntX реализует всех стандартных арифметических операторов, использующих operator overloading , поэтому его использование является прозрачным для разработчиков, например, если вы работаете с обычными целыми числами.

FHT и расчеты точности

Внутренняя библиотека TIntX работает с числами с плавающей точкой при умножении с использованием FHT (Fast Hartley Transform), поэтому в какой-то момент она перестает работать правильно и теряет точность. К счастью, эти неприятные эффекты побочных эффектов начинают появляться, когда размер целого числа составляет около 2^28 байтов, т.е. для действительно огромных целых чисел. В любом случае, для того, чтобы поймать такие ошибки, была добавлена некоторый код, проверка достоверности результатов умножения FHT - он занимает n последних цифр каждого большого целого числа, умножает их, используя классический подход, а затем сравнивает последние n цифры классического результата с последними n цифрами результата FHT (так что это своего рода упрощенная проверка CRC). Если обнаружено какое -либо несоответствие, то EFhtMultiplicationException выброшено; Эта проверка может быть отключена с помощью глобальных настроек.

Внутреннее представление и производительность toString ()

Для действительно огромных целочисленных чисел (например, 42 в Power 1048576 выше) вызов ToString() может занять довольно много времени для выполнения. Это связано с тем, что внутренние большие целые числа TIntX хранятся как 2^32 2^32 -базовый номер в массиве UInt32 и для создания десятичной строки Такой подход к хранению цифр был выбран намеренно-он делает ToString() медленнее, но использует память эффективно и делает примитивные операции на цифрах быстрее, чем мощность хранилища с 10 базой (что делает ToString() работать быстрее), и обычно вычисления используются чаще, чем ToString() .

Поддерживаемые компиляторы

 FreePascal 3.0.0 and Above.

Delphi 2010 and Above.

Установка библиотеки.

Метод первый:

Используйте предоставленные пакеты в папке "Пакеты".

Метод второй:

Добавьте путь библиотеки и погрузку на путь поиска проекта.

Модульные тесты.

Чтобы запустить модульные тесты,

Для FPC 3.0.0 и выше

 Simply compile and run "IntXLib.Tests" project in "FreePascal.Tests" Folder.

Метод первый (с использованием TestInSight и Dunitx) (предпочтительный).

 1). Download and Install TestInsight (and DunitX if not available).

2). Open Project Options of Unit Test (IntXLib.Tests.TestInsight) in "Delphi.Tests" 
    Folder.

3). To Use TestInsight, right-click on the project, then select 
	"Enable for TestInsight" or "TestInsight Project".
    Save Project then Build and Run Test Project through TestInsight. 

Метод второй (с помощью бегуна Dunitx Console).

 1). Download and Install DunitX (if not available).

2). Open Project Options of Unit Test (IntXLib.Tests.TestInsight) in "Delphi.Tests" 
    Folder.

3). Save Project then Build and Run Test Project.. 

###Лицензия

Это «программное обеспечение» лицензировано в соответствии с MIT License (MIT) .

Наконечник банки

• ? Биткойн : 1MhFfW7tDuEHQSgie65uJcAfJgCNchGeKf
• ? Ethereum : 0x6c1DC21aeC49A822A4f1E3bf07c623C2C1978a98
• ? Pascalcoin : 345367-40

Заключение

  Special Thanks to first of all, (Andriy Kozachuk) for creating the 
Original CSharp version, members of Delphi Developers Community on Google Plus,
Uncle Midnight,Ron4Fun for various support offered.