lisp - 在 LISP 中实现 64 位二进制数乘法的问题

Question

我正在尝试用 LISP 编写代码来将两个 64 位数字相乘。在ubuntu平台上使用SBCL编译程序。我的算法如下。

1) 将第一个数字转换为 64 位二进制表示。

2) 对第一个数和它自己进行第二次二进制加法。

我编写了以下函数将十进制数转换为二进制数(以十进制数和空列表作为参数)

(defun bin (N B) 
(cond
((= N 0) B)
((evenp N)(bin (round (/ N 2)) (cons 0 B)))
((oddp N) (bin (floor (/ N 2))  (cons 1 B)))    
))

以下函数执行二进制加法。(取位数，初始进位，第一个二进制数，第二个二进制数，空列表)

 (defun addbin (n carry L1 L2 L3)
 (cond
((< n 0) (cons carry L3))
((and (= (lastE L1 n) 0) (= (lastE L2 n) 0) (= carry 0)) (addbin (- n 1) 0  L1 L2 (cons 0 L3)))
((and (= (lastE L1 n) 0) (= (lastE L2 n) 0) (= carry 1)) (addbin (- n 1) 0  L1 L2 (cons 1 L3)))
((and (= (lastE L1 n) 0) (= (lastE L2 n) 1) (= carry 0)) (addbin (- n 1) 0 L1 L2 (cons 1 L3)))
((and (= (lastE L1 n) 0) (= (lastE L2 n) 1) (= carry 1)) (addbin (- n 1) 1 L1 L2 (cons 0 L3)))
((and (= (lastE L1 n) 1) (= (lastE L2 n) 0) (= carry 0)) (addbin (- n 1) 0 L1 L2 (cons 1 L3)))
((and (= (lastE L1 n) 1) (= (lastE L2 n) 0) (= carry 1)) (addbin (- n 1) 1 L1 L2 (cons 0 L3)))
((and (= (lastE L1 n) 1) (= (lastE L2 n) 1) (= carry 0)) (addbin (- n 1) 1 L1 L2 (cons 0 L3)))
((and (= (lastE L1 n) 1) (= (lastE L2 n) 1) (= carry 1)) (addbin (- n 1) 1 L1 L2 (cons 1 L3)))
))

返回二进制数第 n 位的补充函数是(获取列表和 n)

(defun lastE (L n)
(cond
((= n 0) (first L))
(t (lastE (rest L) (- n 1)))
))

乘法函数为

(defun bin_mult(nA A B)
(cond
    ((= B 1) A)
    (t (bin_mult  (addbin (- (length A) 1) 0 A nA ()) A (- B 1)))
 ))

我正在执行以下代码来执行乘法

(print "Enter two numbers to be multiplied")
(finish-output nil)
(defvar num1)
(defvar num2)
(defvar a)

(setq num1 (read))
(setq num2 (read))
(setq a (bin num1 ()))


(defvar cnt)
(setq cnt (integer-length num1))
(print cnt)
(dotimes (i (- 63 cnt))
(push 0 a)
)

(print "First number in binary format is" )
(print a)
(print "Multiplication two numbers with concurrency is")

(print (bin_mult a a num2))

我得到以下输出(10*4)

(1 0 1 0)

我尝试在命令提示符下跟踪 bin_mult 函数的执行。我得到以下 (trace bin_mult x x 4) 的输出，其中 x 是 (1 0 1 0)

(bin_mult x x 4)
  0: (BIN_MULT (1 0 1 0) (1 0 1 0) 4)
    1: (BIN_MULT (1 0 1 0 0) (1 0 1 0) 3)
      2: (BIN_MULT (1 0 1 0 0) (1 0 1 0) 2)
       3: (BIN_MULT (1 0 1 0 0) (1 0 1 0) 1)
       3: BIN_MULT returned (1 0 1 0)
     2: BIN_MULT returned (1 0 1 0)
   1: BIN_MULT returned (1 0 1 0)
  0: BIN_MULT returned (1 0 1 0)
 (1 0 1 0)

不知何故没有添加中间结果。请帮助解决这段代码中的错误..

谢谢你..

Answer 1

我不确定你想做什么，但你可以稍后做乘法和模拟溢出。

(defun multiply-overflow (bits &rest xs)
  (let ((result (reduce #'* xs :initial-value 1)))
    (multiple-value-bind (_ remainder) (floor result (1- (ash 1 bits)))
      remainder)))

(multiply-overflow 64 1000000000000 1000000000000)
; ==> 2003764205206950850