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. 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
    
  3. 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[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:

    $ ./a.out 357 64
    357 + 64 = 367
    357 * 64 = 3564
    
  4. 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,[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))
    
  5. 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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: