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



 
(lib 'math) ;; for poly multiplication
 
;; convert string of decimal digits to polynomial
;; "1234" → x^3 +2x^2 +3x +4 
;; least-significant digit first
(define (string->long N)
	(reverse (map string->number (string->list N))))
 
;; convert polynomial to string
(define (long->string N)
(if (pair? N)
   (string-append (number->string (first N)) (long->string (rest N)))  ""))
 
;; convert poly coefficients to base 10
(define (poly->10 P (carry 0))
(append
	(for/list ((coeff P)) 
		(set! coeff (+ carry coeff )) 
		(set! carry (quotient coeff 10)) ;; new carry
		(modulo coeff 10)) 
	(if(zero? carry) null (list carry)))) ;; remove leading 0 if any
 
;; long multiplication
;; convert input - strings of decimal digits - to polynomials
;; perform poly multiplication in base 10
;; convert result to string of decimal digits
 
(define (long-mul A B )
 (long->string (reverse  (poly->10 (poly-mul (string->long A) (string->long B))))))
 
(define two-64 "18446744073709551616")
(long-mul two-64 two-64)
    → "340282366920938463463374607431768211456"
 
;; check it
(lib 'bigint)
Lib: bigint.lib loaded.
(expt 2 128)
   → 340282366920938463463374607431768211456
 
 
 