NX - Numerics

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 and higher, i386 32-bit processors) and Delphi (Delphi 5 and higher, for Win32).

With NX, one can implement algorithms that require

  • big integers (pseudoprime creation, elliptic curves over GF(P), etc.);
  • big rationals;
  • big floats (reals and complexes);
  • big polynomials over GF(2), polynomials and elliptic curves over GF(2**N);
  • big polynomials over GF(3), polynomials and elliptic curves over GF(3**N).

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 33 units and 7 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.26 / FPC 2.2.2  (Win XP Pro SP2);
  • Lazarus 0.9.26 / FPC 2.2.2  (Linux - Ubuntu 9.04).

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 four examples of use (from the projects nx_demo_ints, nx_demo_floats, nx_demo_gf2 and nx_demo_gf3). For the four examples, the running times were obtained with an AMD Athlon 3200+ processor.

Example #1: 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

Example #2: 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

Example #3: computation of the two halves of an elliptic curve point over the field GF(2257).

Example #3
Curve coefficients and field polynomial --------------------------------------- A = 16#15FC704EB6DA1F0E29F4E51D070DDEDDD0C6C017A00DD6840BC1AB438FA762646# B = 16#12D06E870BA2D3C932912A8F7EED5F6797B8F5B0A59D8ECDD5456E4B16780FB52# P = [257,12,0] Basis Type = Polynomial 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

Example #4: change of basis over the field GF(387).

Example #4
GF(3**N,P) ---------- Field polynomial P = 3#1101121012010000221202221100120001200011121210212211201221 121200002221100202200110101012# Field degree = 87 Polynomial type = Ordinary Basis type = Normal Identity element = 3#2222222222222222222222222222222222222222222222222222222222 22222222222222222222222222222# GF(3**N,Q) ---------- Field polynomial Q = [1,87,2,86,2,28,2,0] Field degree = 87 Polynomial type = Tetranomial Basis type = Normal Identity element = 3#1111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111# Root of P mod Q --------------- R = 3#120002012200102001202001100112212111010000202010121212000110122000102020100 122020102010# R degree = 86 Check (P(R) = 0 mod Q) -> OK Random polynomial U ------------------- U over GF(3**N,P) = 3#20012111102002201210102221222110220021221112112220201112122 0001200221110100222200211212# Conversion of U from GF(3**N,P) to GF(3**N,Q) --------------------------------------------- U over GF(3**N,Q) = 3#02021102201012100121100120000020012211022200212122202222102 2110222020222112220111001200# Computation of V = (U**(1/3) + 1)/U**2 -------------------------------------- V over GF(3**N,P) = 3#20120210212100222201112010202112201122212222012010012210200 0111010012020100201221021100# V over GF(3**N,Q) = 3#11210211012210210020112010101021102121022011110211210021112 0120011021020122122100220211# Conversion of V from GF(3**N,Q) to GF(3**N,P) --------------------------------------------- V over GF(3**N,P) = 3#20120210212100222201112010202112201122212222012010012210200 0111010012020100201221021100# Check (Conversion) -> OK


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.32.2 -> v0.32.3
  • Fixed a bug in the nx_nt.UI32Divisors function.
  • Added the nx_nt.ICyclotomic procedure.
  • Added the nx_nt.SI32IsFundamentalDiscriminant function.
  • Added the nx_z.IRnd procedure (overload).
  • Improved (slightly) the nx_gf3.MulTo2x2 procedure.
v0.32.1 -> v0.32.2
  • Updated links.
v0.32.0 -> v0.32.1
  • Fixed a bug in the nx_z.BigIntToBase10Str function. Thanks to Jean Bayon who reported it.
v0.31.1 -> v0.32.0
  • The constant checking has been modified.
  • The nx_z.TBigInt type has been simplified (there is no more Negative field).
  • The nx_z.ISetSignFlag procedure is deprecated.
  • The nx_z.ISignFlag function is deprecated.
  • The nx_r.XSignFlag function is deprecated.
  • Compiling with Delphi 7 should no more raise Delphi internal errors.

Download

Pascal source:  nx.zip  (v0.32.3 alpha, 628 KB)


Stop Software Patents Petition

Valid XHTML 1.0 Strict
 URL: http://www.ellipsa.eu/public/nx/nx.html (hosted by Online)
Last update July 19, 2010
Copyright © 2010, Marcel Martin. All rights reserved.