Pounds, Shillings, Pence
April 7, 2015
Mixed-radix number systems have a base, or radix, that varies at each position. For instance, the old-style British pounds, shillings and pence form a mixed-radix system where there are twelve pence in a shilling and twenty shillings in a pound, and calendars form a mixed-radix system where there are sixty seconds in a minute, sixty minutes in an hour, twenty-four hours in a day, and seven days in a week.
Your task is to write a program that accepts a definition of a mixed-radix system — for instance, (7 24 60 60) for the calendar mentioned above — and performs addition and subtraction of numbers written in that system. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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).