Task

Explicitly implement   long multiplication.

This is one possible approach to arbitrary-precision integer algebra.



For output, display the result of    264 * 264.

Optionally, verify your result against builtin arbitrary precision support.

The decimal representation of    264    is:

18,446,744,073,709,551,616

The output of    264 * 264    is    2128,    and is:

340,282,366,920,938,463,463,374,607,431,768,211,456



 
#lang racket
 
(define (mult A B)
  (define nums
    (let loop ([B B] [zeros '()])
      (if (null? B)
        '()
        (cons (append zeros (let loop ([c 0] [A A])
                              (cond [(pair? A)
                                     (define-values [q r]
                                       (quotient/remainder
                                        (+ c (* (car A) (car B)))
                                        10))
                                     (cons r (loop q (cdr A)))]
                                    [(zero? c) '()]
                                    [else (list c)])))
              (loop (cdr B) (cons 0 zeros))))))
  (let loop ([c 0] [nums nums])
    (if (null? nums)
      '()
      (let-values ([(q r) (quotient/remainder (apply + c (map car nums)) 10)])
        (cons r (loop q (filter pair? (map cdr nums))))))))
 
(define (number->list n)
  (if (zero? n) '()
      (let-values ([(q r) (quotient/remainder n 10)])
        (cons r (number->list q)))))
 
(define 2^64 (number->list (expt 2 64)))
(for-each display (reverse (mult 2^64 2^64))) (newline)
;; for comparison
(* (expt 2 64) (expt 2 64))
 
;; Output:
;; 340282366920938463463374607431768211456
;; 340282366920938463463374607431768211456
 