NX - Numerics

Overview
Examples of use
License
Changes
Download

Overview

There is no greater mistake than to call arithmetic an exact science. There are... hidden laws of number which it requires a mind like mine to perceive. For instance, if you add a sum from the bottom up, and then again from the top down, the result is always different.

M. P. La Touche (quoted in Knuth, TAOCP, volume 2, chapter 4)

NX - Numerics is a library of multiprecision numbers for Free Pascal (2.0.4, 2.0.5 or 2.2.0, i386 32-bit processors) and Delphi (Delphi 5 and Turbo Delphi for Win32).

With NX, one can implement algorithms that require big integers, rationals, floats (reals and complexes) and/or polynomials over GF(2). Though it is copyrighted, NX is freeware (see License below) and its Pascal source is available. In short, you may use it for free at your own risk in any program (commercial or not) assuming you checked that, by using NX, you are not infringing any software patent.

The current release contains 32 units and 6 demo programs. These programs were compiled with

Delphi 5 (Win XP Pro SP2);
Turbo Delphi Explorer for Win32 (Win XP Pro SP2);
Lazarus 0.9.24 / FPC 2.2.0 (Win XP Pro SP2);
Lazarus 0.9.22 / FPC 2.0.4 (Linux - Ubuntu 7.10 Gutsy Gibbon).

The current version is an alpha version. Many things can still be modified and there is no documentation yet (but the code is commented).

Examples of use

Here are three examples of use (from the projects nx_demo_ints, nx_demo_floats and nx_demo_gf2). For the three examples, the running times were obtained with an AMD Athlon 3200+ processor.

First example: computation of the GCD (Greatest Common Divisor) of two random integers with the standard Euclidean algorithm and with the function IGCD of NX.

Example #1

A=
1240547249271360694313489775940233480319195905258357618451445943012224
5705421962095622352938949559667102942811733395811075573370622879013510
3214432709543001904561892955472916755669008653253843291317705928886805
8228031808246355217438248339659026437425009783310839411120528872172951
9790242632031847719245171938483582958585872265975272766603003515942672
8263117628745880756006683014450464300437091350148696873471268879492156
9944396835456508815517229721817711616472916405835035677299228118016256
182576014

B=
1104929776196471686960034606366444954348437859404144640645582761164796
4339369483115272037525442690991669708319431688251434776103636789533213
6253549413085648609175779652651494927635848617100908345311915353266666
0431083970164177588429014454538497575028110008118142406467588294102647
6713030751738270987975344098740250598727651963731034650845486899525650
1230669772865150824987314375402696690849622185592567516407374392206323
9348004013898558032931815598428163021464686423645453300890062848124428
4752456912

Decimal size of A = 499
Decimal size of B = 500

GCD(A,B) = 6
Running time = 0.472 milliseconds

GCD(A,B) = 6
Running time = 0.083 milliseconds

Check (GCD #1 = GCD #2) -> OK

Second example: computation of the number Fibonacci[999] using big reals and with the procedure IFibonacci (using only big integers).

Example #2

Golden Ratio
------------
+1.618033988749894848204586834365638117720309179805762862135448622705260462818902
449707207204189391137484754088075386891752126633862223536931793180060766726354433
38908659593958290563832266131992829026788067520876689250171169620703222

X = (Golden Ratio)**999 / Sqrt(5)
--------------------------------
+2.686381002448535938614672720214292396761660931898695234012317599761798170024788
168933836965448335656419182785616144335631297667364221035032463485041037768036733
41511728991697231970827639856157644500784741746260000000000000000000058E+208

Round(X)
--------
+26863810024485359386146727202142923967616609318986952340123175997617981700247881
689338369654483356564191827856161443356312976673642210350324634850410377680367334
151172899169723197082763985615764450078474174626

Fibonacci[999]
--------------
+26863810024485359386146727202142923967616609318986952340123175997617981700247881
689338369654483356564191827856161443356312976673642210350324634850410377680367334
151172899169723197082763985615764450078474174626

Check (Round(X) = Fibonacci[999]) -> OK

Running times (microseconds)
----------------------------
Computing Golden Ratio .. 12
Computing X ............. 33
Rounding X .............. 2
Computing Fibonacci ..... 7

Third example: computation of the two halves of an elliptic curve point over the field GF(2²⁵⁷).

Example #3

Curve coefficients and field polynomial
---------------------------------------
A = 16#15FC704EB6DA1F0E29F4E51D070DDEDDD0C6C017A00DD6840BC1AB438FA762646#
B = 16#12D06E870BA2D3C932912A8F7EED5F6797B8F5B0A59D8ECDD5456E4B16780FB52#
P = [257,12,0]
Basis Type = Standard

Random point P
--------------
X = 16#3269B178D3C7077717B1735DE1BEF7825A846E59CD9EE1EF97F6E5629FF7783F#
Y = 16#1DCD30CAF17911150ACBEA6E3EAD04A1954FA3E7478DF23544C0830AA2FBA15D8#

Q = P + (0,Sqrt(B))
-------------------
X = 16#BF37D31BA236B32AEC9AE7D00229263A4BA0429EDC7FF3A928383D5301BDDEFF#
Y = 16#A80F6E236920004C8C24303E955D726B0FFDD3876C2061E259E5A652B9E8959F#

2P
--
X = 16#A9A32C1A2EF272BF8129F4A923069216C7D5F87E73CAAF89C15E1A46E6AEE3A1#
Y = 16#1DBA1D849150DA161BAF8FB45292EBE9B5DF63C68402133A5BA81D15B93F5CF7E#

2Q
--
X = 16#A9A32C1A2EF272BF8129F4A923069216C7D5F87E73CAAF89C15E1A46E6AEE3A1#
Y = 16#1DBA1D849150DA161BAF8FB45292EBE9B5DF63C68402133A5BA81D15B93F5CF7E#

Check (2P = 2Q) -> OK

H1
--
X = 16#BF37D31BA236B32AEC9AE7D00229263A4BA0429EDC7FF3A928383D5301BDDEFF#
Y = 16#A80F6E236920004C8C24303E955D726B0FFDD3876C2061E259E5A652B9E8959F#

H2
--
X = 16#3269B178D3C7077717B1735DE1BEF7825A846E59CD9EE1EF97F6E5629FF7783F#
Y = 16#1DCD30CAF17911150ACBEA6E3EAD04A1954FA3E7478DF23544C0830AA2FBA15D8#

Check halves -> OK

Running times (microseconds)
----------------------------
Random point ... 482
Order-2 point .. 4
Addition ....... 56
Double ......... 54
Double ......... 54
Halves ......... 431

Licence

The NX - Numerics library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3.0 of the License, or (at your option) any later version.

The NX - Numerics library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. If, for some reason, you cannot access their site, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Changes

v0.28.0 -> v0.28.1

The NX_USE_HEAPTRACE symbol (for Free Pascal) has been defined in order to make use of the heaptrc unit when the NX_DEBUG symbol is not defined.
The Free Pascal and Lazarus demos have been modified accordingly.

v0.27.6 -> v0.28.0

The directive NX_USE_ASM_CODE has been suppressed. There is no more "pure" Pascal code.
NX can be used with Delphi 5 (and presumably any higher version for Win32).
The nx_common and nx_stackbooks units have been merged (the nx_stackbooks unit has been suppressed).
The nx_nt.UI32Divisors function has been added.
The nx_nt.UI32PrimeFactors function has been added.
3 overloaded nx_nt.IKronecker functions have been added.
The nx_nt.SI32Kronecker function has been added.

Download

Pascal source: nx.zip (v0.28.1 alpha, 497 KB)