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 both Free Pascal (2.0.4, 2.0.5 or 2.2.0, i386 32-bit processors) and Turbo Delphi. 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

Turbo Delphi Explorer (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.27.5 -> v0.27.6

Improved the nx_rcfs.QConvergent procedure.

v0.27.4 -> v0.27.5

Fixed a bug in the nx_rcfs.QConvergent procedure.

v0.27.3 -> v0.27.4

Added the nx_strs.RawToBase4Str function.
Added base-4 conversion code to the nx_zstrs unit.
Added base-4 conversion code to the nx_rstrs unit.
Added the TStrBaseDelimiters type to the nx_strs unit.
Added the BaseDelimiters parameter to the nx_zstrs.IStr function.
Added the BaseDelimiters parameter to the nx_rstrs.XStr function.
Added the BaseDelimiters parameter to the nx_gf2strs.GF2Str function.
Fixed a bug in nx_q.QFree and nx_q.QFreeMany (the rationals were not correctly freed).
Added the nx_rfcs unit (Regular Continued Fractions).
Added 2 demos to nx_demo_floats: Regular continued fraction expansion of Sqrt(U) and Approximations of e using continued fractions.

Download

Pascal source: nx.zip (v0.27.6 alpha, 518 KB)