lisp - LISP で 2 つの大きな整数を乗算する方法

Question

n 桁の整数と m 桁の整数が与えられます。リスト、配列、またはその他の Lisp 固有のデータ型を使用して、LISP でそれらを乗算するにはどうすればよいですか?

例えば;

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

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

の結果で;

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

Answer 1

Common Lisp はすでにbignumをネイティブに持っています。なぜ使わないのですか？

基本的に、特別に宣言する必要はありません。それらは「魔法のように」発生します。

 % 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

したがって、Common Lisp を使用すると、基本的に気にする必要はありません...

補遺

また、効率的な bignum アルゴリズムは非常に難しい問題です。効率的なアルゴリズムは単純なアルゴリズムよりも複雑です。それらを説明する難しい本を見つけることができます (基礎となる数学はかなり難しいです)。この回答も参照してください。

競争力のある bignum の実装を作成したい場合は、数年間懸命に取り組み、博士論文にする準備をしてください。

Answer 2

使用する単純なアルゴリズムは、乗算を手で計算するときに行うことを模倣するだけです。

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

最初のステップは、単一の「数字」による乗算を実装することです (例: 123 x 6 = 738)。

もちろん、シフトは簡単です（リスト内の要素をスライドさせるだけです）。したがって、加算関数を使用して乗算を完了することができます。

これは、2 つの大きな数の積を計算する最速の方法ではないことに注意してください (たとえば、からつばアルゴリズムを参照してください)。

PS: 2 つの大きな数の積を手で計算する方法を考えると、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.