Pounds, Shillings, Pence
April 7, 2015
Let’s take as an example the pounds-shillings-pence system (20 12). We express a number as (7 12 3) meaning 7 poungs, 12 shillings, and 3 pence. The sum of (7 12 3) and (8 14 10) is then (16 7 1), since 3 pence and 10 pence form 1 shilling and 1 penny, 12 shillings and 14 shillings, plus the 1 shilling carried over from the pence calculation, for 1 pound and 7 shillings, and 7 pounds and 8 pounds, plus the 1 pound carried over from the shilling calculation, form 16 pounds. We never write (15 26 13), even though that is the position-by-position sum, because that is considered incorrect form, so our first function normalizes a number:
(define (normalize schema number)
(let loop ((ss (reverse schema))
(ns (reverse number))
(result (list)) (carry 0))
(drop-while zero?
(cond ((null? ns)
(if (zero? carry) result
(cons carry result)))
((null? ss)
(cons (+ carry (car ns)) result))
(else (loop (cdr ss) (cdr ns)
(cons (modulo (+ (car ns) carry) (car ss)) result)
(let* ((x (+ (car ns) carry))
(q (quotient x (car ss)))
(r (remainder x (car ss))))
(if (negative? r) (- q 1) q))))))))
This is tricky, for a couple of reasons. First, Scheme rounds the quotient toward zero, which does the wrong thing when one of the elements of the number is negative. Second, we want to suppress leading zeros. For instance:
> (normalize '(20 12) '(15 26 13))
(16 7 1)
> (normalize '(20 12) '(1 -2 7))
(18 7)
Then addition or subtraction just proceeds element-wise through the number-lists and normalizes at the end; we can’t say (normalize schema (map op x y))
because the numbers might have varying length:
(define (plus/minus schema op x y)
(let loop ((xs (reverse x))
(ys (reverse y))
(result (list)))
(cond ((and (null? xs) (null? ys))
(normalize schema result))
((null? xs)
(loop xs (cdr ys) (cons (car ys) result)))
((null? ys)
(loop (cdr xs) ys (cons (car xs) result)))
(else (loop (cdr xs) (cdr ys)
(cons (op (car xs) (car ys)) result))))))
Here are some examples:
> (plus/minus '(20 12) + '(8 12 10) '(7 14 3))
(16 7 1)
> (plus/minus '(20 12) - '(8 12 10) '(7 14 3))
(18 7)
> (plus/minus '(20 12) - '(7 14 3) '(8 12 10))
(-1 1 5)
We used drop-while
from the Standard Prelude. You can run the program at http://ideone.com/yojsBB.
In Python.
fix markup?
really
Nice little problem. Here’s a solution using C arrays, handling carries and borrows as in normal decimal addition. Input can be non-normalized, but the output is always normalized (so adding or subtracting zero normalizes a number). Least significant digit first (though I’ve printed the digits in the opposite order):
radixadd and radixsub should return void there (I missed -Wall off the compilation line).
Solution in Java. However, leading zero’s are not removed..
An example in ISO Prolog (gprolog):
:- initialization(main).
main :-
% Weeks, days, hours, minutes, seconds
Number is 7*24*60*60-1, % 1 second less than 1 week
mixed_radix_number([52,7,24,60,60], Ns, Number),
format(‘~d weeks, ~d days, ~d hours, ~d minutes, and ~d seconds~n’, Ns),
Hourm1sec = [0,0,1,0,-1], % 1 second less than 1 hour
mixed_radix_number([52,7,24,60,60], Hourm1sec, Secs),
mixed_radix_number([52,7,24,60,60], Nd, Secs),
format(‘1 second less than 1 hour ~w = ~w = ~d seconds~n’,
[Hourm1sec,Nd,Secs]),
Ym1sec = [364,0,0,-1], % 1 year – 1 second, but 7*52 = 364
mixed_radix_number([365,24,60,60],Ym1sec,S),
mixed_radix_number([365,24,60,60],Ym1sec,S),
mixed_radix_number([52,7,24,60,60],Yw,S),
format(‘1 second less than 1 year in days and time: ~w~n’,[Ym1sec]),
format(‘1 second less than 1 year in weeks, days and time: ~w~n’,
[Yw]),
format(‘ 7 weekdays * 52 weeks in days: 364~n’,[]),
format(‘1 second less than 1 year in seconds: ~d~n’,[S]),
% Pounds, shillings, pence
mixed_radix_number([999999,20,12],[8,12,10],Pence),
format(‘~d £, ~d shillings, and ~d pence are ~d pence total~n’,
[8,12,10,Pence]),
mixed_radix_number([1000,20,12],Ps,Pence),
format(‘~d pence are ~d £, ~d shillings, and ~d pence~n’,[Pence|Ps]),
mixed_radix_number([1000,20,12],[8,12,10],Pence),
% Degrees, minutes, seconds
mixed_radix_number([360,60,60],[53,45,20],Seconds),
format(’53 degrees 45”20”” W is ~d seconds west~n’,[Seconds]),
% Binary numbers
mixed_radix_number([2,2,2,2,2,2,2,2],B,67),
format(’67 in a binary (octet) is ~w~n’,[B]),
% Hexadecimal numbers
mixed_radix_number([16,16],[7,15],Hx),
format(‘7F hexadecimal is ~d decimal~n’, [Hx]),
mixed_radix_number([16,16],Hx1,254),
format(‘254 decimal is ~w hexadecimal~n’, [Hx1]),
halt.
% mixed_radix_number(+Radices, +Mixed, ?Number)
% mixed_radix_number(+Radices, -Mixed, +Number)
mixed_radix_number(Rs, Ns, S) :- nonvar(Ns), !,
decoded_mixed_radix_number(Rs, Ns, 0, S).
mixed_radix_number(Rs, Ns, S) :- var(Ns),
reverse(Rs, Rs1),
encoded_mixed_radix_number(Rs1, [], Ns, S).
decoded_mixed_radix_number([], [], S, S).
decoded_mixed_radix_number([R|Rs], [N|Ns], S0, S) :-
S1 is R * S0 + N,
decoded_mixed_radix_number(Rs, Ns, S1, S).
encoded_mixed_radix_number([], Ns, Ns, _S).
encoded_mixed_radix_number([R|Rs], Ns0, Ns, S) :-
Rem is S mod R,
S1 is floor(S / R),
encoded_mixed_radix_number(Rs, [Rem|Ns0], Ns, S1).
[/source/
Alas, try again to get formatting right:
Have mercy, this does not bode well, 3rd time: