elisp factorial calculation gives incorrect result

Question

If I write this function in emacs-lisp:

(defun factorial (n)
  (if (<= n 1)
      1
      (* n (factorial (- n 1)))))
      => factorial

It works well for small numbers like 5 or 10, but if I try and calculate (factorial 33) the answer is -1211487723752259584 which is obviously wrong, all large numbers break the function. In python this doesn't happen. What is causing this problem?

Nalley

Answer 1

Integers have a specific range. Values outside this range can't be represented. This is pretty standard across most -- but not all -- programming languages. You can find the largest number Emacs Lisp's integer datatype can handle on your computer by checking the value of most-positive-fixnum.

Go to your *scratch* buffer -- or any Lisp buffer -- and type in most-positive-fixnum. Put the cursor at the end, then press C-x C-e. On my computer, I get 2305843009213693951 as the value. Yours might differ: I'm on a 64 bit machine, and this number is about 2^61. The solution to the factorial of 33 is 8683317618811886495518194401280000000. That's about 2^86, which is also more than my Emacs can handle. (I used Arc to calculate it exactly, because Arc can represent any size integer, subject to boring things like the amount of memory you have installed).

Tardif

The answers below show, on the contrary, that Emacs is perfectly able to handle a calculation like factorial 33. Just do (calc-eval "33!") and check for yourself. – Polyadelphous

kotchwane: calc was only able to do that because it wasn't relying on Emacs' native integer implementation. However in much more recent times (starting from 27.1) Emacs has acquired native support for bignums (via the GNU Multiple Precision (GMP) library), meaning that integers actually can be of arbitrary size. I do not know whether calc continues to use its own implementation, or if it has been modified to use the new native bignums. – Maiocco

Answer 2

You can always invoke Emacs' calc library when dealing with large numbers.

(defun factorial (n)
  (string-to-number (factorial--1 n)))

(defun factorial--1 (n)
  (if (<= n 1)
      "1"
    (calc-eval (format "%s * %s"
                       (number-to-string n)
                       (factorial--1 (- n 1))))))


ELISP> (factorial 33)  
8.683317618811886e+036

Further reading:

• http://www.masteringemacs.org/articles/2012/04/25/fun-emacs-calc/
• C-hig (calc) RET
• C-hig (calc) Calling Calc from Your Programs RET

Maiocco

I have no idea why you'd reimplement factorial if you're passing off the evaluation to calc, (defun factorial (n) (calc-eval (format "%s!" n))) – Shorthorn

Answer 3

The most simple solution seems to be Paul's one:

(defun factorial (n) (calc-eval (format "%s!" n)))

ELISP> (factorial 33)
8683317618811886495518194401280000000

However, I tried for fun, by another Calc way, without using calc-eval and string. Because much more complex Emacs Lisp programs with Calc can be done in this way.

Calc's defmath and calcFunc- functions are so powerful within Emacs Lisp.

(defmath myFact (n) (string-to-number (format-number (calcFunc-fact n))))

ELISP> (calcFunc-myFact 33)
8.683317618811886e+36

Streetwalker

Answer 4

I landed on this question searching for a quick and easy way to compute a factorial in Elisp, preferrably without implementing it.

From the other answers, I gather that it is:

(calc-eval "10!")

which is equivalent to

(calc-eval "fact(10)")

and which is as concise as, and more powerful than, redefining a factorial function. For instance, you can have a binomial coefficient this way:

(calc-eval "7!/3!(7-3)!")

or even that way:

(calc-eval "choose(7,3)")

Calc is really worth exploring. I suggest doing the interactive tutorial inside Emacs. You can launch it with C-x * t. As for calc, you can use it with C-x * c, or with M-x calc.

Polyadelphous