You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
139 lines
3.9 KiB
Racket
139 lines
3.9 KiB
Racket
;; Copyright 2019 Edward L. Platt <elplatt@alum.mit.edu>
|
|
|
|
#lang racket
|
|
|
|
;; This module implements a mixed radix number system using Sylvester's sequence.
|
|
;;
|
|
;; Examples:
|
|
;; 0 -> '()
|
|
;; 1 -> '(1)
|
|
;; 2 -> '(0 1)
|
|
;; 3 -> '(1 1)
|
|
;; 4 -> '(0 2)
|
|
;; 41 -> '(1 2 6)
|
|
;; 42 -> '(0 0 0 1)
|
|
;;
|
|
;; Numbers are represented as a list of digits. The place value for the ith digit is s_i - 1, where s_i is the ith element
|
|
;; of Sylvester's sequence. The first few place values are 1, 2, 6, 42.
|
|
;;
|
|
;; The ith digit is an integer in [0, s_i).
|
|
|
|
(provide
|
|
|
|
;; Find a given element in Sylvester's sequence
|
|
;;
|
|
;; Example:
|
|
;; > (sylvester 4)
|
|
;; 1807
|
|
sylvester
|
|
|
|
;; Represent an integer as a sylvester-radix number
|
|
;;
|
|
;; Example:
|
|
;; > (make-sylvester-radix 1337)
|
|
;; '(1 2 5 31)
|
|
make-sylvester-radix
|
|
|
|
;; Find the integer value of a sylvester-radix number
|
|
;;
|
|
;; Example:
|
|
;; > (sylvester-radix-value '(1 2 5 31))
|
|
;; 1337
|
|
sylvester-radix-value
|
|
|
|
;; Add two sylvester-radix numbers
|
|
;;
|
|
;; Example:
|
|
;; > (add-sylvester-radix '(1 0 1) '(1 0 2))
|
|
;; '(0 1 3)
|
|
add-sylvester-radix
|
|
|
|
;; Extend length of sylvester-radix number with zero elements.
|
|
;;
|
|
;; Example:
|
|
;; > ((extend-sylvester-radix 4) '(1 2))
|
|
;; '(1 2 0 0)
|
|
extend-sylvester-radix)
|
|
|
|
;; —————————————————————————————————
|
|
;; Implementation Section
|
|
|
|
;; Find the nth element of Sylvester's sequence
|
|
;; https://oeis.org/A000058
|
|
(define (sylvester n)
|
|
(if (= n 0)
|
|
2
|
|
(let ([last (sylvester (- n 1))])
|
|
(+ (* last last)
|
|
(* -1 last)
|
|
1))))
|
|
|
|
;; Find the sylvester-radix representation of an integer
|
|
(define (make-sylvester-radix n)
|
|
(normalize-sylvester-helper '() 0 n))
|
|
|
|
;; Find the integer representation of a sylvester-radix number
|
|
(define (sylvester-radix-value v)
|
|
(sylvester-radix-value-helper v 0 0))
|
|
|
|
;; Add two sylvester-radix numbers
|
|
(define (add-sylvester-radix v w)
|
|
(normalize-sylvester-radix (add-components v w)))
|
|
|
|
;; Create procedure to extend list to length n
|
|
(define (extend-sylvester-radix n)
|
|
(lambda (v)
|
|
(if (>= (length v) n)
|
|
v
|
|
(append v
|
|
(build-list
|
|
(- n (length v))
|
|
(lambda (x) 0))))))
|
|
|
|
;; Ensure digits are in the required range by carrying surplus value.
|
|
(define (normalize-sylvester-radix v)
|
|
(normalize-sylvester-helper v 0 0))
|
|
|
|
;; Recursively normalize a sylvester-radix number.
|
|
;;
|
|
;; remaining: Remaining digits. The first is removed on each recursion.
|
|
;; index: The index of the first remaining digit.
|
|
;; carry: The total integer value carried from lower places.
|
|
(define (normalize-sylvester-helper remaining index carry)
|
|
(let* ([digit (if (empty? remaining) 0 (car remaining))]
|
|
[place-value (- (sylvester index) 1)]
|
|
[value (+ (* place-value digit) carry)]
|
|
[next-place-value (- (sylvester (+ index 1)) 1)]
|
|
[remainder (modulo value next-place-value)])
|
|
(if (and (= carry 0) (empty? remaining))
|
|
null
|
|
(cons (/ remainder place-value)
|
|
(normalize-sylvester-helper
|
|
(if (empty? remaining) '() (cdr remaining))
|
|
(+ index 1)
|
|
(- value remainder))))))
|
|
|
|
;; Recursively find the value of a sylvester-radix number
|
|
;;
|
|
;; remaining: The remaining digits. The first is removed on each recursion.
|
|
;; index: The index of the first remaining digit.
|
|
;; total: The total integer value of non-remaining digits.
|
|
(define (sylvester-radix-value-helper remaining index total)
|
|
(if (empty? remaining)
|
|
total
|
|
(let ([digit (car remaining)]
|
|
[place-value (- (sylvester index) 1)])
|
|
(sylvester-radix-value-helper
|
|
(cdr remaining)
|
|
(+ index 1)
|
|
(+ total (* digit place-value))))))
|
|
|
|
;; Add two lists componentwise
|
|
(define (add-components a b)
|
|
(if (and (> (length a) 0) (> (length b) 0))
|
|
(cons (+ (car a) (car b))
|
|
(add-components (cdr a) (cdr b)))
|
|
(if (= 0 (length a))
|
|
b
|
|
a)))
|