Is the bignum implementation in CLISP indeed better, or is there any
incantation to persuade CMUCL to work harder?
(defun harmonic (n)
(declare (optimize (speed 3) (safety 0)))
(loop :for i :from 1 :to n :summing (/ i)))
(time (harmonic 3000))
CMU Common Lisp release x86-linux 2.5.2 18c+ 2 May 2001 build 2174 gives:
Evaluation took:
26.2 seconds of real time
25.47 seconds of user run time
0.02 seconds of system run time
[Run times include 0.16 seconds GC run time]
149 page faults and
8372368 bytes consed.
CLISP gives:
Real time: 0.14185 sec.
Run time: 0.14 sec.
Space: 4201196 Bytes
GC: 8, GC time: 0.02 sec.
Thanks,
- huaiyuan
hey,
huaiyuan> Is the bignum implementation in CLISP indeed better, or is
huaiyuan> there any incantation to persuade CMUCL to work harder?
I've heard the same, and noticed the same. CLISP, while definitely
slower in general than the other Lisp implementations, does very well
with bignums. I tried this test with LispWorks vs. CLISP, and the
times were and 0.23s and 43.2s respectively.
I always wanted to know if it was possible for other implementations
to borrow CLISP's integer code, but I doubt it would be that easy.
Plus, there's difficulty because of the GPL.
I was recently talking to a Java guy who wrote some code for me on a
contract. He uses a bignum implementation for Java, and based on how
he described that library as working, it's probably slower than all of
these Lisp packages. We should just be happy that we have built-in
first class rational numbers. This effectively means that we have
(close to) infinite precision on rational numbers. In SQL, for
example, there is the type NUMERIC. In Common Lisp there's no problem
accomodating this in a very natural way.
dave
David Bakhash <·····@alum.mit.edu> wrote:
>
> I always wanted to know if it was possible for other implementations
> to borrow CLISP's integer code, but I doubt it would be that easy.
To make that easier, I have extracted the CLISP integer, floating-point
and complex number code and turned it into a C++ library called CLN
(= Common Lisp Numbers). See http://clisp.cons.org/~haible/packages-cln.html.
> Plus, there's difficulty because of the GPL.
CLISP and CLN are both under GPL, yes.
You could also use GNU GMP, which is under LGPL, but then you get only
the integers and the long-float numbers, and have to implement the
complex numbers and other CL specific primitives yourself.
Bruno
>>>>> "Huaiyuan" == Huaiyuan <········@rac1.wam.umd.edu> writes:
Huaiyuan> Is the bignum implementation in CLISP indeed better, or is there any
Huaiyuan> incantation to persuade CMUCL to work harder?
Huaiyuan> (defun harmonic (n)
Huaiyuan> (declare (optimize (speed 3) (safety 0)))
Huaiyuan> (loop :for i :from 1 :to n :summing (/ i)))
Huaiyuan> (time (harmonic 3000))
I think the main difference is that Clisp has a very fast bignum
multiplier, and perhaps a very fast GCD. CMUCL uses a simple
pencil-and-paper style multiplier that is fast for small bignums but
quite slow for large bignums. Some attempt have been made for a
faster multiplier for CMUCL, but that doesn't help here since we are
multiplying a bignum by a fixnum. I do not know how CMUCL's GCD
compares to Clisp.
Ray
Huaiyuan wrote:
>
> Is the bignum implementation in CLISP indeed better, or is there any
> incantation to persuade CMUCL to work harder?
It would be nice - but what I missed in _all_ Common Lisps is fast modular
exponentation. If you use the Montgomery representation you can do
modular exponentiations rather fast, but only if you code it rather
low-level.
ciao,
Jochen
Jochen Schmidt <···@dataheaven.de> wrote:
>
> It would be nice - but what I missed in _all_ Common Lisps is fast modular
> exponentation. If you use the Montgomery representation you can do
> modular exponentiations rather fast, but only if you code it rather
> low-level.
The reason you don't have Montgomery representation in Common Lisp itself
is that Montgomery representation is really an alternative representation
for a modular integer, i.e. an element of Z / N Z. The trivial representation
being #S(MODINT :MODULUS N :RESIDUE x), you want a
#S(MONTGOMERY-MODINT :MODULUS N :RESIDUE y).
You could do it all in Lisp with DEFSTRUCT and DEFMETHOD, if Common Lisp
had the necessary primitive for computing inverses modulo N. This primitive,
the computation of gcd of integers with Euclidean representation, is
missing. It could be specified as follows:
(XGCD x1 ... xn) returns n+1 values:
g = (gcd x1 ... xn), an integer >= 0,
and n integers u1,...,un with g = u1*x1+...+un*xn.
You can program this yourself using Euclid's algorithm, of course,
but it will be slow because it won't exploit the optimized algorithm
(Lehmer etc.) in the underlying bignum implementation.
Bruno