January 2013 - alexandria-devel - mailman3.common-lisp.net

[alexandria-devel] minor spelling patch
by Michael Stevens 26 Jan '13

26 Jan '13

Minor spelling improvements in README.

2 1

[alexandria-devel] Question about FORMAT-SYMBOL
by Luís Oliveira 26 Jan '13

26 Jan '13

Hello, I often try to support Allegro's modern mode by doing things like (format-symbol t "~A-~A" :foo :bar). We just came across an issue on #quicklisp where a user had set his *PRINT-CASE* to :DOWNCASE and that caused FORMAT-SYMBOL to intern lower-case symbols, thus breaking the idiom I described. Should fix my code to use SYMBOLICATE instead or should FORMAT-SYMBOL use WITH-STANDARD-IO-SYNTAX? Any opinions? -- Luís Oliveira http://r42.eu/~luis

5 8

[alexandria-devel] Documentation fix and feature suggestion
by Jan Moringen 26 Jan '13

26 Jan '13

Dear alexandria developers, please the documentation fix and new functions in the two most recent commits in git://github.com/scymtym/alexandria.git for inclusion. Many thanks in advance. Kind regards, Jan

2 1

[alexandria-devel] Regarding %MULTIPLY-RANGE, BINOMIAL-COEFFICIENT
by Robert Smith 26 Jan '13

26 Jan '13

Hello all. I've been trying to speed up BINOMIAL-COEFFICIENT for combinatorial calculations and ended up writing my own functions which were originally based off of Alexandria's design. For computing the binomial coefficient of (10^11, 10^5), Alexandria's takes about 9.990 seconds on my 64-bit Windows machine with a relatively recent SBCL with (optimize speed (safety 0) (debug 0)). I've ended up writing my own version of %MULTIPLY-RANGE, which I ended up calling RANGE-PRODUCT, and it's definition is: (declaim (ftype (function (integer integer) integer) range-product)) (defun range-product (lower upper) "Compute LOWER * (LOWER+1) * ... * (UPPER-1) * UPPER." (assert (<= lower upper)) (case (- upper lower) ((0) lower) ((1) (* lower upper)) (otherwise (let ((mid (floor (+ lower upper) 2))) (* (range-product lower mid) (range-product (1+ mid) upper)))))) [ from QTILITY: https://bitbucket.org/tarballs_are_good/qtility/src/65eff10fdece/arithmetic… ] >From that, the definition of FACTORIAL follows: (declaim (ftype (function ((integer 0)) (integer 1)) factorial)) (defun factorial (n) "Compute the factorial of N, N! = 1 * 2 * ... * N." (if (zerop n) 1 (range-product 1 n))) [ from QTILITY: https://bitbucket.org/tarballs_are_good/qtility/src/65eff10fdece/arithmetic… ] Then, I wrote BINOMIAL-COEFFICIENT that uses a closure to direct the swapping of the K and N-K, instead of mutating them. This seemed to at least help with SBCL's flow analysis. I also chose not to use CHECK-TYPE in favor of declarations (which I understand are not the same, but I think they should attempt to act the same given a sufficient compiler policy). (declaim (ftype (function ((integer 0) (integer 0)) (integer 0)) binomial-coefficient)) (defun binomial-coefficient (n k) "Binomial coefficient of N and K." (assert (>= n k)) (labels ((core (k n-k) (if (= 1 n-k) n (nth-value 0 (floor (range-product (+ k 1) n) (factorial n-k)))))) (declare (inline core) (ftype (function ((integer 0) (integer 0)) (integer 0)) core)) (if (or (zerop k) (= n k)) 1 (let ((n-k (- n k))) (declare (type (integer 0) n-k)) (if (< k n-k) (core n-k k) (core k n-k)))))) [ from QTILITY: https://bitbucket.org/tarballs_are_good/qtility/src/65eff10fdece/arithmetic… ] With the code above, I can compute the same binomial coefficient in about 7.503 seconds, so about a 2.5 second speed up. I'd like to submit a patch using the code above, but I could see how these speed ups are both implementation-dependent and platform-dependent. A particular unfortunate consequence is that we don't have those tweakable limits which (in theory; as the comments say) could be computed at compile time. Any thoughts? -Robert

2 1