Page 1 of 1

binomial coefficient, factorial lisp

PostPosted: Fri Jun 08, 2012 7:49 am
by inka

i´m a newbie in lisp, :roll:
(sorry, my english is not so good,
because i didn´t found a forum in my country, just for Python, C++, Java etc...)

so my problem is, i try to programm a programm in lisp, that calculate binomial coefficient with factorial function(iterative ) NOT recursive...
i´ve try everthing, but my programm doesn´t work...
(i tried with global function, local function (factorial)), but evertime got an error

Code: Select all
(defun binom-coef(a b)   
       (if (or (< a b) (< b 0))
       nil            )    ;
       (flet fakul(n)    ;factorial
               (cond ((= n 0) 1)
              (t (* n (fakul (- n 1))))))
   (/ (fakul a) (* (fakul b) (fakul(- a b)))))

and one more question:
how to compile in emacs???
(i tried in in *scatch* => (load "binom-coef.el")
but also an error message) :cry:

Many thanks,
inka :mrgreen:

Re: binomial coefficient, factorial lisp

PostPosted: Sat Jun 09, 2012 3:32 am
by edgar-rft
The "Emacs style" solution, using two functions, would look like this:

Code: Select all
(defun fakul (n)    ; factorial
  (if (= n 0)
      (* n (fakul (- n 1)))))

(defun binom-coef (a b)   
  (if (or (< a b) (< b 0))
      (/ (fakul a) (* (fakul b) (fakul (- a b))))))

Note that the "fakul" function will run into infinite recursion with floating-point numbers that have digits other than zero after the dot.

A "Common Lisp style" solution, using a local "labels" function, would look like this:

Code: Select all
(require 'cl)

(defun binom-coef (a b)   
  (if (or (< a b) (< b 0))
      (labels ((fakul (n)    ; factorial
                 (if (= n 0)
                     (* n (fakul (- n 1))))))
        (/ (fakul a) (* (fakul b) (fakul (- a b)))))))

First you need to (require 'cl), because the Emacs "labels" macro is defined in "cl-macs.el", that is no standard part of Emacs. The main difference between "flet" and "labels" is that "labels" can be called recursively from inside a local function.

The "flet" and "labels" special operators are borrowed from Common Lisp and are ducumented in the "Common Lisp Hyperspec" under:

What I do not really understand is that first you write that you want to compute the factorial iterativeley, not recursively, but then you show Lisp code that computes the factorial recursively, but not iterativeley.

Compiling the code:

If you save the code in a file, called e.g. "binom.el", then an "Emacs-Lisp" menu appears with an entry "Byte-compile this file". If you go with the mouse pointer to "Byte-compile this file" then a "binom.elc" file will be produced from the "binom.el" file. But note that the Emacs byte compiler does not make the Lisp code run faster, the only difference is that loading the "binom.elc" file is faster than loading the "binom.el" file.

If you're looking for a Lisp with a compiler that makes the code run faster (not only loading faster), then try Common Lisp or Scheme.

- edgar