how would one multiplies two big integers in LISP

Question

Given an n-place integer and an m-place integer. How can I multiply them in LISP using lists, arrays or any other lisp specific data types?

for instance;

a(1)a(2)...a(n)

b(1)b(2)...b(m)

with result of;

r(1)r(2)...r(m+n)

Answer 1

Common Lisp has already bignums natively. Why don't you use them?

You basically don't have to declare anything specially, they "magically" happen:

 % sbcl
 This is SBCL 1.0.56.0.debian, an implementation of ANSI Common Lisp.

 * (defun fact (n) (if (< n 1) 1 (* n (fact (- n 1)))))
 FACT

 * (fact 50)
 30414093201713378043612608166064768844377641568960512000000000000

So with a Common Lisp, you basically don't have to bother...

addenda

And efficient bignum algorithms are a very difficult problem; Efficient algorithms have better complexity than naive ones; you can find difficult books explaining them (the underlying math is pretty hard). See also this answer.

If you want to make a competitive bignum implementation, be prepared to work hard several years, and make it a PhD thesis.

Answer 2

A simple algorithm to use is just mimicking what you do when computing mutiplications by hand:

  123 x
  456 =
  ---
  738
 615
492
-----
56088

The first step is implementing multiplication by a single "digit" (e.g. 123 x 6 = 738).

After you have that shifting is of course trivial (just slide elements in your list) and therefore multiplication can then be completed using your addition function.

Note that this is not the fastest way to compute the product of two big numbers (see Karatsuba algorithm for example).

PS: thinking to how you can compute the product of two large numbers by hand also explains some "amazing" result like 111111111*111111111 = 12345678987654321

         111111111 x
         111111111 =
         ---------
         111111111
        111111111
       111111111
      111111111
     111111111
    111111111
   111111111
  111111111
 111111111
 -----------------
 12345678987654321

Answer 3

(* 1234567890123456789123456789 1234567890123456789123456789)

Big ints are native to Common Lisp.