[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gcl-devel] Re: [Maxima] faster factorial
From: |
Camm Maguire |
Subject: |
[Gcl-devel] Re: [Maxima] faster factorial |
Date: |
13 Apr 2006 10:39:29 -0400 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 |
Greetings!
Richard Fateman <address@hidden> writes:
> I have another program that is about twice as fast as k.
> The code is much longer, and also produces an array of bits
> with 1 at the position of prime numbers
> up to n/2, but it uses code from commercial Macsyma.
> The mpz_fac_ui code may be faster in GMP 4.2. I am guessing
> your test used GMP 4.1.14 or so.
Good guess -- 4.1.4. Do you have specific reason to suspect
improvements in 4.2?
> I'm using Allegro CL, and I've been using destructive operations
> to avoid making new bignum (GMP) boxes. It adds to the code size
> but reduces garbage collection (on the Lisp side, anyway) to zero.
Well, that at least is an advantage of a single gmp call, one bignum
creation.
At some point, I should make a gmp3 package in gcl and export the
functions directly in lisp.
Take care,
> RJF
> Camm Maguire wrote:
>
> Greetings!
>
> Well, I thought I could do better by bringing forward mpz_fac_ui, but:
>
> (time (progn (setq a (si::factorial 100000) c 2) (= a c))) ;just call
> ;to mpz_fac_ui in
> gmp
>
> real time : 0.560 secs
> run-gbc time : 0.570 secs
> child run time : 0.000 secs
> gbc time : 0.000 secs
> NIL
>
>
>
> (time (progn (setq a (k 100000 1) c 2) (= a c)))
>
>
>
> real time : 0.450 secs
> run-gbc time : 0.450 secs
> child run time : 0.000 secs
> gbc time : 0.000 secs
> NIL
>
>
>
> So I guess there is no interest in including such a factorial function
> in GCL.
>
> Take care,
>
>
> "Richard Fateman" <address@hidden> writes:
>
>
>
> For GCL, this program is faster than the much longer one
> used in Maxima
> (defined in ASUM.lisp.).
>
> Almost 3X faster computing 20000! .
>
>
> (defun k (n m) ;; (k n 1) is n!
> (declare (fixnum n m))
> (if (<= n m) n
> (* (k n (* 2 m))
> (k (- n m)(* 2 m)))))
>
> There are even faster ways, but I'm not sure how to actually use the
> GMP arithmetic to best advantage in GCL.
>
> see http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf
> for more thoughts.
>
> RJF
>
> _______________________________________________
> Maxima mailing list
> address@hidden
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
>
>
>
>
>
>
>
--
Camm Maguire address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah