## 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.

Advertisements

Pages: 1 2

### 6 Responses to “Lunar Arithmetic”

1. ```
(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)))

```
2. 57s/0/1/ ; sorry.

3. Paul said

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)  # 111112222232222211111
```
4. Daniel said

Here’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);
return EXIT_FAILURE;
}
int x = atoi(argv);
int y = atoi(argv);
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:

```\$ ./a.out 357 64
357 + 64 = 367
357 * 64 = 3564
```
5. matthew said

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,*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 = 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))
```
6. Globules said

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` 9876543210
```
```\$ ./lunar
59
124
7
100
111
119
357
357
3564
3564
111
0
12345678987654333445555543210
```