Lunar Arithmetic
January 22, 2019
We represent lunar number as lists of digits, least significant digit first. Here are conversions to and from lunar representation:
(define (terran->lunar n) (reverse (digits n))) (define (lunar->terran xs) (undigits (reverse xs)))
Addition is easy enough; it’s just map max over the two lists. We need a specialized version of map to substitute leading zeroes where one number is shorter than the other:
(define (plus xs ys)
(define (map0 f xs ys)
(let loop ((xs xs) (ys ys) (zs (list)))
(cond ((and (null? xs) (null? ys)) (reverse zs))
((null? xs) (loop xs (cdr ys)
(cons (f 0 (car ys)) zs)))
((null? ys) (loop (cdr xs) ys
(cons (f (car xs) 0) zs)))
(else (loop (cdr xs) (cdr ys)
(cons (f (car xs) (car ys)) zs))))))
(map0 max xs ys))
Multiplication is a little bit harder. It’s essentially map min, but we have to then add the partial results, remembering to shift the implied zeroes:
(define (times xs ys)
(define (times-one m xs)
(map (lambda (x) (min m x)) xs))
(let loop ((ys ys) (0s (list)) (zs (list)))
(if (null? ys) zs
(loop (cdr ys) (cons 0 0s)
(plus (times-one (car ys) (append 0s xs)) zs)))))
Note that 0s (that’s zero ess) is a valid symbol in Scheme; you may need to spell it zeroes in other languages. Here are our sample problems:
> (lunar->terran (plus (terran->lunar 357) (terran->lunar 64))) 367 > (lunar->terran (times (terran->lunar 357) (terran->lunar 64))) 3564
You can run the program at https://ideone.com/ExyYk0. Be sure to watch the video.
Programming Praxis 
(defpackage "LUNAR" (:use) (:export "+" "*")) (defpackage "LUNAR-ARITHMETIC" (:use "COMMON-LISP")) (in-package "LUNAR-ARITHMETIC") (deftype natural () `(integer 0)) (deftype digit () `(integer 0 9)) (defun make-decimal (length &optional (default-digit 0)) (make-array length :element-type 'digti :initial-element default-digit)) (defun decimal-from-integer (n) (check-type n natural) (loop :with result := (make-decimal (if (< n 2) 1 (ceiling (log n 10)))) :while (plusp n) :for i :from 0 :for (q d) := (multiple-value-list (truncate n 10)) :do (setf (aref result i) d n q) :finally (return result))) (defun decimal-to-integer (digits) (reduce (lambda (d n) (+ (* n 10) d)) digits :initial-value 0 :from-end t)) (defun lunar:+ (&rest arguments) (cond ((null arguments) 0) ((null (rest arguments)) (first arguments)) (t (let* ((arguments (mapcar (function decimal-from-integer) arguments)) (result (make-decimal (reduce (function max) arguments :key (function length))))) (replace result (pop arguments)) (dolist (argument arguments) (map-into result (function max) result argument)) (decimal-to-integer result))))) (defun binary* (a b) (let ((result (make-decimal (1- (+ (length a) (length b)))))) (loop :for bd :across b :for start :from 0 :do (loop :for ad :across a :for i :from start :do (setf (aref result i) (max (aref result i) (min ad bd))))) result)) (defun lunar:* (&rest arguments) (if (null arguments) 0 (loop :with arguments := (mapcar (function decimal-from-integer) arguments) :while (rest arguments) :do (setf arguments (loop :for (a b) :on arguments :by (function cddr) :if b :collect (binary* a b) :else :collect a)) :finally (return (decimal-to-integer (first arguments)))))) (assert (equal (list (lunar:+ 357 64) (lunar:* 357 64) (lunar:+ 123 65400) (lunar:+ 54321 9876004 4) (lunar:* 54321 9000004 4) (lunar:* 22 54321) (lunar:* 54321 9 8 7 6 5 4) (lunar:* 54321 44) (lunar:+ 54321 9000004)) '(367 3564 65423 9876324 44321044321 222221 44321 444321 9054324)))57s/0/1/ ; sorry.
In Python.
from itertools import zip_longest class lunar(object): def __init__(self, n): self.n = n assert isinstance(n, int) def __add__(self, other): n = self.n res = [] for ni, mi in zip_longest(reversed(str(n)), reversed(str(other)), fillvalue="0"): res.append(max(ni, mi)) return lunar(int("".join(reversed(res)))) def __mul__(self, other): n = self.n res = lunar(0) for shift, mi in enumerate(reversed(str(other))): L = ["0"] * shift + [min(mi, ni) for ni in reversed(str(n))] res = res + lunar(int("".join(reversed(L)))) return res def __pow__(self, p): if p == 0: return lunar(1) if p == 1: return lunar(self.n) if p == 2: return self * self if p % 2 == 0: return self.__pow__(p // 2) ** 2 else: return self.__pow__(p // 2) ** 2 * self def __str__(self): return str(self.n) n = lunar(357) m = lunar(64) print("n * m =", n * m) # 3564 print("n + m =", n + m) # 367 print("n ** 10 =", n ** 10) # 333333333355555555557 print("12321**5 =", lunar(12321) ** 5) # 111112222232222211111Here’s a solution in C.
#include <stdlib.h> #include <stdio.h> int lunar_add(int x, int y) { int result = 0; int multiplier = 1; while (x || y) { int x0 = x % 10; x /= 10; int y0 = y % 10; y /= 10; int max = x0 > y0 ? x0 : y0; result += max * multiplier; multiplier *= 10; } return result; } int lunar_multiply(int x, int y) { int x_copy = x; int result = 0; int multiplier = 1; while (y) { int y0 = y % 10; int product = 0; int inner_multiplier = 1; while (x) { int x0 = x % 10; x /= 10; int min = x0 < y0 ? x0 : y0; product += min * inner_multiplier; inner_multiplier *= 10; } result = lunar_add(result, product * multiplier); y /= 10; multiplier *= 10; x = x_copy; } return result; } int main(int argc, char* argv[]) { if (argc != 3) { fprintf(stderr, "Usage: %s INT INT\n", argv[0]); return EXIT_FAILURE; } int x = atoi(argv[1]); int y = atoi(argv[2]); int sum = lunar_add(x, y); int product = lunar_multiply(x, y); printf("%d + %d = %d\n", x, y, sum); printf("%d * %d = %d\n", x, y, product); return EXIT_SUCCESS; }Example Usage:
Here’s another Python solution, I nicked a few bits of Paul’s solution, including use of zip_longest, which I didn’t know about. The Lunar class internally uses the list of digits representation. It’s fun to implement the Sieve of Eratosthenes too:
from itertools import zip_longest # Basic operations on lunar numbers (digit sequences, # least significant first). def int2lunar(n): return [int(c) for c in str(n)][::-1] def lunar2int(n): return int("".join([str(d) for d in n][::-1])) def lunaradd(n,m): # Thanks to Paul for zip_longest return [max(*a) for a in zip_longest(n,m,fillvalue=0)] def lunarmul(n,m): result = [] for i,d in enumerate(n): u = [min(d,e) for e in m] result = lunaradd(result,[0]*i+u) return result # Wrap it up in a nice class class lunar(object): def __init__(self, n): if isinstance(n, int): self.n = int2lunar(n) else: self.n = n def __add__(self, other): return lunar(lunaradd(self.n,other.n)) def __mul__(self, other): return lunar(lunarmul(self.n,other.n)) def __int__(self): return lunar2int(self.n) def __str__(self): return str(int(self)) n = lunar(64) m = lunar(357) print(n+m) print(n*m) # Find the lunar primes with the lunar sieve of Eratosthenes # Note that multiplication is not monotonic, but we can # use the fact that len(n*m) = len(n)+len(m)-1 (where len(n) # is the number of digits) to terminate scan. def lunarprimes(K): N = 10**K primes = [True]*N primes[9] = False for i in range(1,N): if not primes[i]: continue for j in range(2,N): if j == 9: continue if len(lunar(i).n)+len(lunar(j).n)-1 > K: break primes[int(lunar(i)*lunar(j))] = False; return [i for i in range(1,N) if primes[i]] # [19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] print(lunarprimes(2))A Haskell version.
{-# OPTIONS_GHC -fno-warn-type-defaults #-} -- Add two numbers. add :: Integral a => a -> a -> a add 0 0 = 0 add x y = let (xq, xr) = x `quotRem` 10 (yq, yr) = y `quotRem` 10 in max xr yr + 10 * add xq yq -- Multiply a digit and a number. muld :: Integral a => a -> a -> a muld _ 0 = 0 muld d x = let (xq, xr) = x `quotRem` 10 in min d xr + 10 * muld d xq -- Multiply two numbers. mul :: Integral a => a -> a -> a mul 0 _ = 0 mul x y = let (xq, xr) = x `quotRem` 10 in muld xr y `add` (10 * mul xq y) main :: IO () main = do -- Some examples from the Numberphile video. print $ 58 `add` 19 -- 59 print $ 17 `mul` 24 -- 124 print $ 7 `mul` 7 -- 7 print $ 10 `mul` 10 -- 100 print $ 11 `mul` 11 -- 111 print $ 19 `mul` 19 -- 119 -- Variations on the Programming Praxis example. print $ 357 `add` 0 print $ 0 `add` 357 print $ 357 `mul` 64 print $ 64 `mul` 357 print $ 1 `mul` 357 print $ 357 `mul` 0 -- A couple of larger numbers. print $ 12345678901112131415 `mul` 9876543210And apparently, there are applications: https://twitter.com/numberphile/status/1348613413619040256