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):
#include <stdio.h> int radixadd(int *a, const int *b, const int *r, int n) { for (int c = 0, i = 0; ; i++) { int k = a[i]+b[i]+c; if (i < n) { c = k/r[i]; a[i] = k%r[i]; } else { a[n] = k; break; } } } int radixsub(int *a, const int *b, const int *r, int n) { for (int c = 0, i = 0; ; i++) { int k = a[i]-b[i]+c; if (i < n) { c = k/r[i]; a[i] = k%r[i]; if (a[i] < 0) { a[i] += r[i]; c--; // modulus should be positive } } else { a[n] = k; break; } } } int total(int *a, const int *r, int n) { int c = a[n]; for (int i = n; i > 0; i--) { c = r[i-1]*c + a[i-1]; } return c; } int main() { int r[] = { 12, 20 }; int zero[] = { 0, 0, 0 }; int a[] = { 1729, 0, 0 }; int b[] = { 250, 0, 0 }; radixadd(a,zero,r,2); // Normalize printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2)); radixadd(b,zero,r,2); // Normalize printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2)); radixadd(a,b,r,2); // Add b to a radixadd(a,b,r,2); // Add b to a printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2)); radixsub(a,b,r,2); // Sub b from a radixsub(a,b,r,2); // Sub b from a printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2)); radixsub(b,a,r,2); // Sub a from b printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2)); radixadd(b,a,r,2); // Sub a from b printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2)); }radixadd and radixsub should return void there (I missed -Wall off the compilation line).
Solution in Java. However, leading zero’s are not removed..
package com.experiment; public class PoundsShillingsPence { private static int[] result; public static void main(String[] args) { operate('+', new int[] {20, 12}, new int[] {8, 12, 10}, new int[] {7, 14, 3}); operate('-', new int[] {20, 12}, new int[] {8, 12, 10}, new int[] {7, 14, 3}); operate('-', new int[] {20, 12}, new int[] {7, 14, 3}, new int[] {8, 12, 10}); } private static void normalize(int[] scheme, int[] input) { int mod, s, i, carry=0; result = new int[input.length]; for(s = scheme.length-1, i = input.length-1;i>=0;i--,s--) { if(s>=0) { mod = (input[i]+carry)%scheme[s]; carry = (input[i]+carry)/scheme[s]; if(mod<0) { mod = mod+scheme[s]; carry = carry-1; } result[i] = mod; } else { result[i] = (input[i]+carry); } } System.out.print("{"); for(int l=0;l<result.length;l++) { System.out.print(result[l]); if(l!=result.length-1) System.out.print(","); } System.out.print("}\n"); } private static void operate(char operator, int[] schema, int[] input1, int[] input2) { int i1 = input1.length; int i2 = input2.length; int r = i1<i2?i2:i1; int result[] = new int[r]; for(i1=i1-1,i2=i2-1,r=r-1;;i1--,i2--,r--) { if(i1<0 && i2<0) { break; } if(i1<0) { result[i2] = input2[i2]; continue; } if(i2<0) { result[i1] = input1[i1]; continue; } if(operator=='+') { result[r] = input1[i1]+input2[i2]; } else if(operator=='-') result[r] = input1[i1]-input2[i2]; else { System.out.println("Invalid operator. Only + and - are supported"); return; } } normalize(schema, result); } }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:
:- 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).Have mercy, this does not bode well, 3rd time:
:- 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).