Introducing NUMS -- an Arbitrary Precision Math Library

[REDEBOLT]

Hello, Everyone,

I am happy to announce the NUMS Arbitrary Precision Math Library by Eddy Van Esch, the author of H.I.M.E., the Huge Integer Math and Encryption library. (http://www.thinbasic.com/community/showthread.php?11156-H.i.m.e.) It is free for non-commercial use and can be downloaded from Devotechs.com (http://www.devotechs.com/FreeDownloads.html).

I will be offering some Thinbasic scripts based upon math problems here on these fora.

Download and enjoy.

Regards,
Bob

[REDEBOLT]

On the topic "n! - very slowly (http://www.thinbasic.com/community/showthread.php?11331-n!-very-slowly.)," I submit a TB script that calculates n! to 100,000 digits in 61 seconds.


===========================================================
================ N U M S ===================
===========================================================
Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_Info.txt'
(c) 2011 DevOTechS
===========================================================
Last Modified = 09-01-2011 at 00:28:05
Program = Factorial.tbasic
Factorial (n)
100000! = 456575 digits
61,086.917 msecs.
Done...
Press any key to end program.



Regards,
Bob

[Petr Schreiber]

Hi Bob,

thanks for letting us know. I downloaded the package from website, run the example, but ThinBASIC seemed to have problem with line:


DECLARE FUNCTION nu_PutString_AZ LIB "NUMS.dll" (BYVAL azStr AS ASCIIZ * 100, BYVAL lVar AS LONG) AS LONG


I modified it to:


DECLARE FUNCTION nu_PutString_AZ LIB "NUMS.dll" (BYVAL azStr AS ASCIIZ, BYVAL lVar AS LONG) AS LONG


And then the example ran OK. I will talk to Eros why this is happening.


Thanks,
Petr

[danbaron]

I get an error when I try to run it.

Main script name: C:\Users\root\Desktop\NUMS\Factorial.tbasic

Included script: C:\Users\root\Desktop\NUMS\NUMS.inc

Error code: 20

Error Description: Missing Close Parens ')'. Expected a ')' but found something else.

Line number: 102

Line code: DECLARE FUNCTION NU_PUTSTRING_AZ LIB "NUMS.dll"(BYVAL AZSTR AS ASCIIZ * 100, BYVAL LVAR AS LONG) AS LONG

Token found: AZSTR

My guess is that thinBasic does not like the, "* 100".

That is the only difference I can detect in line 102.

-----------------------------------------------------------------------------------------------------------------------------

On my computer, and using Racket, it takes 130 seconds.

But, I get 456574 digits.

And, Mathematica agrees (next two lines).

2.8242294079603478742934215780245355184774949260912... × 10^456573

http://www.wolframalpha.com/input/?i=100000! (http://www.wolframalpha.com/input/?i=100000%21)

Dan


' code ----------------------------------------------------------------------------------------------------------------------

#lang racket

(define fact-value 0)

(define (num-digits n)
(add1 (order-of-magnitude n)))

(define (time-function f n)
(let ((t1 (current-milliseconds)))
(set! fact-value (f n))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
tt))))

(define (fact n)
(define prod 1)
(define (loop m)
(cond
((> m n) prod)
(else
(set! prod (* prod m))
(loop (+ m 1)))))
(loop 1))

' REPL interactions ---------------------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (time-function fact 100000)
130.026
> (num-digits fact-value)
456574
>

[danbaron]

Like Petr said, I took out the, "* 100", and it runs OK.

On my computer, it took 103 seconds.

(I didn't know how to use a DLL with thinBasic, I have to admit, NUMS works nice.)

Dan


================ N U M S ===================
===========================================================

Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com

===========================================================
Last Modified = 09-01-2011 at 00:00:23

Program = Factorial.tbasic

Factorial (n)

100000! = 456575 digits

103,081.056 msecs.

Done...

Press any key to end program.

[danbaron]

I tried finding 100000! using Python.

On my machine it took 54 seconds.

Somehow, it seems that Python and Ruby are very hard to beat.

(But, unlike NUMS, I don't think they can be called from thinBasic.)

Dan


' code --------------------------------------------------------------------------------------

# fact.py

import time

def fact(n):
fact = 1
for i in range(1,n+1):
fact *= i
return fact

t1 = time.clock()
f = fact(100000)
t2 = time.clock()
print(t2-t1)

' output ------------------------------------------------------------------------------------

C:\Users\root\Desktop\py>python
Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.exit()

C:\Users\root\Desktop\py>python fact.py
54.26329864

C:\Users\root\Desktop\py>

[REDEBOLT]

Hi Bob,

thanks for letting us know. I downloaded the package from website, run the example, but ThinBASIC seemed to have problem with line:


DECLARE FUNCTION nu_PutString_AZ LIB "NUMS.dll" (BYVAL azStr AS ASCIIZ * 100, BYVAL lVar AS LONG) AS LONG


I modified it to:


DECLARE FUNCTION nu_PutString_AZ LIB "NUMS.dll" (BYVAL azStr AS ASCIIZ, BYVAL lVar AS LONG) AS LONG


And then the example ran OK. I will talk to Eros why this is happening.


Thanks,
Petr

I changed the declare to:

Declare Function nu_PutString_AZ Lib "NUMS.dll" Alias "nu_PutString_AZ" (ByVal azStr As Asciiz * 100, ByVal lVar As Long) As Long

[Eddy Van Esch]

But, I get 456574 digits.
And, Mathematica agrees

That's correct Dan. Bob used the NUMS function nu_ConvertDT (to convert from one datatype to another) to convert from floating point to ascii string.
nu_ConvertDT adds a leading space in case of a positive number or a minus sign in case of a negative number, as is custom in the various BASIC languages.
That explains the extra digit count.

Kind regards
Eddy

[danbaron]

I tried finding 100000! using Ruby.

On my machine it took 47 seconds.

(But, I don't think anyone will be calling Ruby from thinBasic.)

Dan


' code --------------------------------------------------------------------------------------

# fact.rb

def fact(n)
fact = 1
i=1
while i<=n
fact = fact*i
i = i+1
end
fact
end

t1 = Time.now.to_f
fact(100000)
t2 = Time.now.to_f
puts t2-t1

' output ------------------------------------------------------------------------------------

C:\Users\root\Desktop\Ruby\test>ruby -v
ruby 1.9.2p0 (2010-08-18) [i386-mingw32]

C:\Users\root\Desktop\Ruby\test>ruby fact.rb
47.15880012512207

C:\Users\root\Desktop\Ruby\test>

[zak]

this is a usefull thread as always with REDEBOLT and Dan posts.
using the example posted here (http://www.thinbasic.com/community/showthread.php?8577-GMP-library-free-library-for-arbitrary-precision-arithmetic/page2) about using GMP with Thinbasic it took 125871 microseconds for 100000! the example in that link needs a correction for the size of the output buffer :
'---Used as output buffer
Global outb As Asciiz * 500000


and instead of directing the factorial output to RichText box which needs more time to display, direct the output to text file "test.txt" .
attached the re edited calc_v0_4.tbasic‎ bundled with gmp dll
Jack have posted a more gmp declarations before the old example Calc_v0_3.tbasic‎ so we can add more functions in the future. the rarely used code are used through space and time this is why the calc... example downloaded 91 times from 2008, possibly by people who was searching google for gmp dlls. this is why we must not disappointed if a file have not downloaded and used immediately, the possible users are there standing over time line and will use your code someday.

[REDEBOLT]

Wow Zak!!

That is really fast.

I will have to study the GMP method to see how they do it.

Does GMP do trigonometric functions?

Regards,
Bob

[jack]

Does GMP do trigonometric functions?

no, for trig and other functions you need MPFR (http://www.mpfr.org/) which uses GMP, here's an example, scroll down to bottom.

[REDEBOLT]

Jack,

I was unable to download a working copy of "libmpfr-1.dll"

Bob

[jack]

I was unable to download a working copy of "libmpfr-1.dll"
OK, it's in the new attachement, plus updated example.

[REDEBOLT]

Thanks Jack,

I ran the program, but it crashed near line 630.
I commented the for loop and then it ran fine.

The code (to my simple mind) seems very complex.

I will further persue the docs to see what I can learn.

Regards,
Bob

[danbaron]

I think there is something wrong with the NUMs calculation of 100000!.

Notice the following lines in the thinBasic code.



'You can set the precision in digits:
nu_SetPrecision(%nu_SetPrec_Digits, 40000) 'NUMS math precision in digits


As we determined, 100000! has 456574 digits, but, the precision set in the code is 40000 digits.

So, I think the NUMs calculation is only an approximation to 100000!.

I think the only possible way it could be exact, is if 100000! has not more than 40000 significant digits.

A large factorial does have a long string of zeroes at the right end. I guess if for 100000!, that string was greater than or equal to 456574 - 40000 = 416574, then, the NUMs calculation could possibly be correct.

But, I did the calculation in Racket (below), and 100000! only has 24999 right end zeroes.

So, I think the NUMs calculation is missing 456574 - 24999 - 40000 = 391575 significant digits.

Worse, I think that once the factorial product reaches 40000 digits, roundoff error begins to accumulate, and propagates to the left.

Therefore, the right end of the 40000 significant digits that NUMs calculated for 100000!, may be wrong.



' code -----------------------------------------------------------------------------------------------------------

#lang racket

(define value 0)

(define (num-digits n)
(add1 (order-of-magnitude n)))

(define (time-function f n)
(let ((t1 (current-milliseconds)))
(set! value (f n))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
tt))))

(define (fact n)
(define prod 1)
(define (loop m)
(cond
((> m n) prod)
(else
(set! prod (* prod m))
(loop (+ m 1)))))
(loop 1))

(define (num-right-end-zeroes n)
(define sum 0)
(define (loop m)
(cond
((= (remainder m 10) 0) (set! sum (add1 sum))
(loop (/ m 10)))
(else
sum)))
(loop n))

' REPL interactions ----------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define n 100000)
> (time-function fact n)
131.009
> (num-digits value)
456574
> (num-right-end-zeroes value)
24999


On my computer, using 40000 digits precision, the thinBasic program took 103 seconds.


================ N U M S ===================
===========================================================

Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com

===========================================================
Last Modified = 09-01-2011 at 00:00:23

Program = Factorial.tbasic

Factorial (n)

100000! = 456575 digits

103,081.056 msecs.

Done...

Press any key to end program.

When I set the precision to 460000 digits (> 456574), which is what I think it should be to do the complete calculation for 100000!, on my computer it takes 842 seconds.


'You can set the precision in digits:
nu_SetPrecision(%nu_SetPrec_Digits, 460000) 'NUMS math precision in digits

================ N U M S ===================
===========================================================

Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com

===========================================================
Last Modified = 09-02-2011 at 11:15:08

Program = Factorial.tbasic

Factorial (n)

100000! = 456575 digits

842,025.731 msecs.

Done...

Press any key to end program.


I think, strangely, when I set the precision to 100 digits, on my computer it still takes 92 seconds.

Dan


'You can set the precision in digits:
nu_SetPrecision(%nu_SetPrec_Digits, 100) 'NUMS math precision in digits


================ N U M S ===================
===========================================================

Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com

===========================================================
Last Modified = 09-02-2011 at 22:44:28

Program = Factorial.tbasic

Factorial (n)

100000! = 456575 digits

92,144.476 msecs.

Done...

Press any key to end program.

[zak]

thanks Jack, it works for me without commenting the for loop in line 630.
Jack if you changed the name libgmp-3.dll inside the gmp.tbasic to libgmp-10.dll for the future possible users.
REDEBOLT yes it is a complex library , i think it is used by mathematica program, and it is here:C:\Program Files\Wolfram Research\Mathematica\8.0\SystemFiles\Kernel\Binaries\Windows
and here:
C:\Program Files\Wolfram Research\Mathematica\8.0\SystemFiles\Kernel\Binaries\Windows-x86-64
with the name GMP.dll

also compiling mpfr needs gmp so the name of xxxgmpxxx.dll and xxxmpfrxxx.dll must every dll know each other. preferably to use precompiled dlls such as posted by Jack, i never was able to compile gmp or mpfr.

[REDEBOLT]

Hi Dan,

Thanks for your analysis.

First, from the help file:


nu_SetPrecision

SYNTAX

nu_SetPrecision (BYVAL lUnit AS LONG, BYVAL lVal AS LONG) AS
LONG

lUnit
: unit in which the precision is specified: use %nu_SetPrec_Digits
for digits or %nu_SetPrec_Bits for bits.

lVal
: required precision, specified in digits or bits, depending on the value
of lUnit.

RETURN VALUE

The actual (internal) precision that is used. This will often be higher than the
specified precision because, internally, the precision is represented as a
multiple of 32 bits.

PURPOSE

To set the precision of the mantissa of BinFloat and DecFloat variables.

The precision can be specified in digits (lUnit = %nu_SetPrec_Digits) or
bits (lUnit = %nu_SetPrec_Bits).

Whether the precision unit is digits or bits, internally the precision is defined in
bits and rounded up to a multiple of 32 bits.

This means that NUMS' internal precision will be equal or higher to what you
specified.

The actually used internal precision is returned by nu_SetPrecision, in digits or
bits, depending on what you specified for lUnit.


As you see, precision applies only to float variables.
The variables I defined are BigInt.

I specified both 46000 and 0 for precision and got essentially the same run times. The attached zip file contains my TB script and both test files.

test.txt is the file output from the "script calc_v0_4.tbasic" by zak.
MyTest.txt is the file output from "Factorial.tbasic".
They are identical.


===========================================================
================ N U M S ===================
===========================================================
Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com (http://www.devotechs.com)
===========================================================
Last Modified = 09-03-2011 at 04:14:06
Program = Factorial.tbasic
Factorial (100000)
100000! = 456575 digits
nu_GetPrecision = 9
%nu_Opt_Kara_Thresh_mul = 324
Number of variables used = 2
40,981.260 msecs.
Done...
Press any key to end program.




===========================================================
================ N U M S ===================
===========================================================
Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com (http://www.devotechs.com)
===========================================================
Last Modified = 09-03-2011 at 04:12:09
Program = Factorial.tbasic
Factorial (100000)
100000! = 456575 digits
nu_GetPrecision = 460002
%nu_Opt_Kara_Thresh_mul = 324
Number of variables used = 2
39,992.561 msecs.
Done...
Press any key to end program.



Regards,
Bob

[jack]

i never was able to compile gmp or mpfr.
assuming you have MinGW installed, follow this steps

launch the msys shell and cd to the gmp directory, then do

./configure --disable-static --enable-shared
make
make check

if make check passed then do

make install
if all went well then cd to the mpfr directory, then do

./configure --disable-static --enable-shared --with-gmp=/usr/local
make
make check

again, if make check passed then do

make install
I usually copy the dll's to the Windows\system32 directory so it's visible to all applications.

[zak]

at last i have a gmp dll compiled in my system, thanks jack for the detailed instructions. my gmp can be downloaded from here.. (http://www.mediafire.com/?3ehy2dldm1kvbxc).
the dll size is 446 kb
i have used the latest gmp source from http://gmplib.org/
but it took too much time : about 5 hours & 30 minutes, the comfigure alone took 1h:30m , much time consumed by make check.
is this normal Jack or it is my system somehow was under a not normal situation ?, i have windows xp, cpu 3GHz dual core (old generation), 3GB memory.
due to this huge time i will try to compile mpfr in later time.
thanks Jack again.

[danbaron]

I think you are right, Bob.

In that case, I think it was not necessary to set the precision in the program.

I re-tested the program with large precisions, and now it doesn't seem to affect the elapsed time.

But, I don't understand why the first time I set the precision to 460000 and ran the program, it took 842 seconds.

Dan


'You can set the precision in digits:
nu_SetPrecision(%nu_SetPrec_Digits, 460000) 'NUMS math precision in digits

================ N U M S ===================
===========================================================

Arbitrary precision floating point and integer math library
Free for personal use.
Commercial use not allowed.
Please read 'NUMS_EULA.txt'
(C) 2011 DevOTechS
www.devotechs.com

===========================================================
Last Modified = 09-02-2011 at 11:15:08

Program = Factorial.tbasic

Factorial (n)

100000! = 456575 digits

842,025.731 msecs.

Done...

Press any key to end program.

[jack]

is this normal Jack or it is my system somehow was under a not normal situation ?, i have windows xp, cpu 3GHz dual core (old generation), 3GB memory.
hanks Jack again.
the compile time is high, but I noticed the compile time is almost instantanaous on the Mac compared to the time it takes on a PC with MinGW,
perhaps a newer version of MinGW is in order?

[REDEBOLT]

Dan,

Read the help topic "Disk caching."

With caching turned off, There is a noticable delay on program start-up.
Although I don't believe it would take fourteen minutes. Unless windows was running something in the background.

On my machine, it takes about 40 seconds to calculate 100000!

Bob

[danbaron]

I read it, it's good, Bob.

I think Eddy Van Esch made something good.

Concerning the code,


nu_SetOption(%nu_Opt_DiskCache, -2) 'Enable disk caching: use Windows temp directory

I think "-2" indicates the current directory.

Dan

[REDEBOLT]

I read it, it's good, Bob.

I think Eddy Van Esch made something good.

Concerning the code,


nu_SetOption(%nu_Opt_DiskCache, -2) 'Enable disk caching: use Windows temp directory

I think "-2" indicates the current directory.

Dan



Yes, Dan, you are correct. I changed the value but not the comment.

Bob

[danbaron]

My experience is that Perl is slow compared to Python and Ruby.

(But, to me, Perl is a lot of fun. It seems there is nothing that is theoretically impossible to do in it.)


' code ------------------------------------------------------------------------------------

# fact.pl

use bignum;

sub fact
{
my ($n) = @_;
my $fact = 1;
my $i;
for($i=2;$i<=$n;$i++) {$fact *= $i;}
return $fact;
}

my $n = 20000;
my ($user1, $system1) = times;
my $f = fact($n);
my ($user2, $system2) = times;
my $user = $user2 - $user1;
print $user;
print "\n";

'output -----------------------------------------------------------------------------------

C:\Users\root\Desktop\Perl>perl -v

This is perl, v5.10.1 (*) built for MSWin32-x86-multi-thread

Copyright 1987-2009, Larry Wall

Perl may be copied only under the terms of either the Artistic License or the
GNU General Public License, which may be found in the Perl 5 source kit.

Complete documentation for Perl, including FAQ lists, should be found on
this system using "man perl" or "perldoc perl". If you have access to the
Internet, point your browser at http://www.perl.org/, the Perl Home Page.


C:\Users\root\Desktop\Perl>perl fact.pl
138.373

C:\Users\root\Desktop\Perl>

[REDEBOLT]

Aaaah, come on Dan

Now I'll have to learn Perl!!!

:rolleyes::eek::D

Bob

[danbaron]

I think a person could spend a long time trying to master Perl.

I think a lot of ignorant people try to sell it way way short.

http://padre.perlide.org/

http://www.perl.org/books/library.html

[REDEBOLT]

Thanks, Dan, for the links.
The online books look intriguing.

Bob

[jack]

zak, I apologize for a totally inappropriate response, please forgive me.
regarding the long compile time, apparently it's due to the version of make,
go to http://sourceforge.net/projects/mingw/files/
click on: MSYS -> make -> make-3.81-3 and download make-3.81-3-msys-1.0.13-bin.tar.lzma and extract to msys\1.0\bin folder.
my compile time for gmp 5.0.2 after having run config was about 10 minutes, make check time was about 12 minutes :)

[zak]

thank you jack, i have downloaded make-3.81-3-msys-1.0.13-bin.tar.lzma, my old Msys make.exe have this property: Modified :July 11, 2009, 3:34:32 PM
while the new downloaded one: Modified :April 29, 2010, 8:18:54 PM
so may be this one reason; that i have used old Make.exe.
in my previous attempt the configure alone took 1h:30m.
also the total slowdown may be because my windows xp install are too old and have many programs floating in memory eating the cpu. it resembles an old man walking slowly.


so i prefer to install a fresh windows xp then MingW with the new make.exe and then to try again. i will report the results when i do that.
what sytem you have used for the 10 minutes run config and 12 minutes check time ; windows xp or windows 7 ??.

[jack]

zak
presently I run windows xp-32 in a virtual machine using vmware fusion on a mac pro, but am thinking it's time to upgrade to windows 7 x64.
the timing was done on a clean mingw install except I grabbed the latest make utility.

[zak]

Jack, the new make.exe are incredibly faster, i have installed MingW with the new make.exe on a slow old laptop but with a new windows xp/sp2 instalation, the hardware specifications:
cpu T2400 - 1.83 Ghz, 504 MB Ram
the time from /.configure ... to the end of make install is less than 20 minutes only, the details approximately like this:
./configure... 3 minutes
make 4
make check 11
make install 1
you can download the gmp dll from here. (http://www.mediafire.com/?46ghjc42pp7bvnq)..
i have checked it with the thinbasic example.
this is what should be , and thanks for refering to the new make.exe

[jack]

zak, the compile time is amazing compared to before. :)