Dear Haskell implementors,
In what way the Haskell implementations may use the GMP library?
(GNU Multi-Precision integers ?)
I had some dim idea of that the implementations rely on gmp for the
arithmetic of integers of arbitrary size.
This letter encloses the reproduction of some part of the new GMP
announcement.
And there also exist other powerful libraries for Integer and for the
number theory. Probably, some of them written in C. One could consider
exploiting them in the Haskell implementation.
Now, if we rely, say, on GMP, then why not enrich the standard Haskell
algebraic library?
Inspecting the names of the library functions below, we see the names
like
..gcdext, ..nextprime, ..root, ..perfectpower
Maybe, gcdext gives the extended gcd ?
You see, it is very natural to include into the class Integral
gcdExt :: a -> a -> (a,a,a) -- x -> y -> (g, u, v),
-- u*x+v*y = g = gcd x y
root :: Integer -> a -> Maybe a -- root of degree n
nextPrime :: ...
factor :: a -> [(a,Integer)] -- example: 12 -> [(2,2),(3,1)]
-- though, I do not see `factor'
-- in GMP
- they are extremely useful for applications.
There may occur other goodies in GMP.
Notice aside:
I have an impression that Haskell-98 calls `Integral' various models
for the domain of integer numbers. And this is for Haskell-98'.
While the good standard of future (I hope for Haskell-2) has, to my
mind, to remove Integral and introduce GCDRing, FactorizationRing,
EuclideanRing, Field - see
http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/
Another question.
Discussing the library standard may take many years.
Meanwhile, can the implementation provide some non-standard library
functions (like in `data' of GHC) for Integer relying, say, on GMP ?
For example, my program defines the classes with the above
gcdExt, root, factor, nextPrime, isPrime,
squareFree, isSquareFree.
And their instances for Integer could apply this library in hope to
obtain faster implementation.
In particular, I do not know of any reasonably cheap method to factor
integers greater than 10^11. Just a gap in education. And as I do not
want to immediately study this piece of theory, it would be good to
fill the gap in the application program with the knowledge of the
library developers ...
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
---------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Zimmermann)
To: [EMAIL PROTECTED]
Subject: [[EMAIL PROTECTED]: GMP 3 released]
> C,a y est, GMP 3 est (enfin) sorti !
> C'est dans [..]
> ftp.gnu.org:pub/gnu/gmp/gmp-3.0.tar.gz
> [..]
------- Start of forwarded message -------
Sender: [EMAIL PROTECTED]
Subject: GMP 3 released
From: Torbjorn Granlund <[EMAIL PROTECTED]>
Date: 17 Apr 2000 17:34:40 +0200
After years of development and some very intensive weeks, GNU MP 3 is
finally ready for release. It should be available from all the GNU
ftp sites shortly. [...]
GMP 3 was finished and released by Torbjörn Granlund, Linus Nordberg,
and Kevin Ryde. Important code contributions were made by Robert
Harley and Paul Zimmermann. A complete list of contributors can be
found in the gmp.texi manual in the distribution.
CHANGES BETWEEN GMP VERSION 2 AND 3
* Source level compatibility with past releases (except mpn_gcd).
* Bug fixes.
* Much improved speed thanks to both host independent and host dependent
optimizations.
* Switch to autoconf/automake/libtool.
* Multiplication and squaring using 3-way Toom-Cook.
* Division using the Burnikel-Ziegler method.
* New functions computing binomial coefficients: mpz_bin_ui, mpz_bin_uiui.
* New function computing Fibonacci numbers: mpz_fib_ui.
* New random number generators: mpf_urandomb, mpz_rrandomb, mpz_urandomb,
mpz_urandomm, gmp_randclear, gmp_randinit, gmp_randinit_lc,
gmp_randinit_lc_2exp, gmp_randseed, gmp_randseed_ui.
* New function for quickly extracting limbs: mpz_getlimbn.
* New functions performing integer size tests: mpz_fits_sint_p,
mpz_fits_slong_p, mpz_fits_sshort_p, mpz_fits_uint_p, mpz_fits_ulong_p,
mpz_fits_ushort_p.
* New mpf functions: mpf_ceil, mpf_floor, mpf_pow_ui, mpf_trunc.
* New mpq function: mpq_set_d.
* New mpz functions: mpz_addmul_ui, mpz_cmpabs, mpz_cmpabs_ui, mpz_lcm,
mpz_nextprime, mpz_perfect_power_p, mpz_remove, mpz_root, mpz_swap,
mpz_tdiv_ui, mpz_tstbit, mpz_xor.
* New mpn function: mpn_divexact_by3.
* New CPU support: DEC Alpha 21264, AMD K6 and Athlon, HPPA 2.0 and 64,
Intel Pentium Pro and Pentium-II/III, Sparc 64, PowerPC 64.
* Almost 10 times faster mpz_invert and mpn_gcdext.
* The interface of mpn_gcd has changed.
* Better support for MIPS R4x000 and R5000 under Irix 6.
* Improved support for SPARCv8 and SPARCv9 processors.
- --
Torbjörn
------- End of forwarded message -------
