Base Conversion
May 2, 2017
We begin with the original task. Since this is homework for a beginning programming course, the intent is almost certainly to perform the conversion by converting the number to a string, segmenting the binary number into pairs of digits, from right to left, converting each pair from binary to quadary (is that the word? quartary? quatenary?), and converting back to a string:
(define (2to4 str)
(let loop ((bits (reverse (string->list str))) (quads (list)))
(cond ((null? bits)
(list->string quads))
((null? (cdr bits))
(loop (cdr bits) (cons (car bits) quads)))
((and (char=? (car bits) #\0) (char=? (cadr bits) #\0))
(loop (cddr bits) (cons #\0 quads)))
((and (char=? (car bits) #\1) (char=? (cadr bits) #\0))
(loop (cddr bits) (cons #\1 quads)))
((and (char=? (car bits) #\0) (char=? (cadr bits) #\1))
(loop (cddr bits) (cons #\2 quads)))
((and (char=? (car bits) #\1) (char=? (cadr bits) #\1))
(loop (cddr bits) (cons #\3 quads)))
(else (error '2to4 "can't happen")))))
> (2to4 "11011000") "3120"
Pattern matching looks a little bit better:
(define (2to4 str)
(let loop ((bits (reverse (string->list str))) (quads (list)))
(list-match bits
(() (list->string quads))
((b) (loop '() (cons b quads)))
((#\0 #\0 . bs) (loop bs (cons #\0 quads)))
((#\1 #\0 . bs) (loop bs (cons #\1 quads)))
((#\0 #\1 . bs) (loop bs (cons #\2 quads)))
((#\1 #\1 . bs) (loop bs (cons #\3 quads)))
(else (error '2to4 "can't happen")))))
> (2to4 "11011000") "3120"
Of course, Scheme can convert between bases natively:
(define (2to4 str) (number->string (string->number str 2) 4))
> (2to4 "11011000") "3120"
And that gives us a way to answer the extra credit task:
(define (convert in out str) (number->string (string->number str in) out))
>"3120" "3120"
You can run the program at http://ideone.com/qtTD4h.
Programming Praxis 
%X=qw(00 0 01 2 10 1 11 3); sub base2to4 { return join q(), reverse map { $X{$_}//$_ } ( (reverse $_[0]) =~ m{(..?)}g ); } print base2to4('11011000'),"\n";'In Python.
def base10toBase(num, base): result = '' current = num while current != 0: remainder = current%base result = str(remainder)+result current = current//base return result def baseBaseto10(num, base): result = 0 exp = 1 for d in reversed(num): result += int(d) * exp exp *= base return result for i in [1, 11, 101, 1101, 1111, 1000]: print(i, 'base2 = \n', base10toBase(baseBaseto10(str(i), 2),4), 'base4\n', baseBaseto10(str(i), 2), 'base10\n',) #outputs: # 1 base2 = # 1 base4 # 1 base10 # # 11 base2 = # 3 base4 # 3 base10 # # 101 base2 = # 11 base4 # 5 base10 # #1101 base2 = # 31 base4 # 13 base10 # #1111 base2 = # 33 base4 # 15 base10 # #1000 base2 = # 20 base4 # 8 base10Up to base 64, so we cover also the Babylonians.
import string from functools import reduce # up to base 62 (10 + 26 + 26) digits = string.digits + string.ascii_lowercase + string.ascii_uppercase N = len(digits) D = dict(enumerate(digits)) I = {v:k for k, v in D.items()} def check_base(base): if not 2 <= base <= N: raise ValueError("base must be in between {} and {}".format(2, N)) def tobase10(astring, base=2): check_base(base) return reduce(lambda acc, i: acc*base + I[i], astring, 0) def frombase10(anumber, base=2): check_base(base) x, result = anumber, [] while x: x, m = divmod(x, base) result.append(D[m]) return "".join(reversed(result)) def convert_base(s, base_from, base_to): return frombase10(tobase10(s, base_from), base_to) print(int("11011000", 2)) # 216 print(convert_base("11011000", 2, 60)) # 3A print(convert_base("3A", 60, 2)) # 11011000 print(convert_base("3A", 60, 10)) # 216A web search indicates to me that the English word for base 4 is “quaternary”.
;; cannot bother with strings - put the digits as numbers in a vector ;; in their usual order, the most significant digit first - assume ;; base greater than one, and no empty vectors so that zero is a bit ;; special - also, error checking is inadequate, as usual (define (vector->natural vec base) (do ((nat 0 (+ (* base nat) (vector-ref vec pos))) (pos 0 (+ pos 1))) ((= pos (vector-length vec)) nat))) ;; first I had remainder and quotient the wrong way around (define (natural->vector nat base) (do ((lis '() (cons (remainder nat base) lis)) (nat nat (quotient nat base))) ((zero? nat) (if (null? lis) (vector 0) (list->vector lis))))) (write (natural->vector (vector->natural (vector 1 1 0 1 1 0 0 0) 2) 4)) (newline) (write (natural->vector (vector->natural (vector 3 1 2 0) 4) 2)) (newline) (write (natural->vector (vector->natural (vector 0) 10) 10)) (newline) (write (vector->natural (natural->vector 31415926 3) 3)) (newline)C11:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int ch;
initial: ch = getchar();
if (ch == '0') goto i0;
if (ch == '1') goto i1;
else goto end;
i0: ch = getchar();
if (ch == '0') goto i00;
if (ch == '1') goto i01;
else goto end;
i1: ch = getchar();
if (ch == '0') goto i10;
if (ch == '1') goto i11;
else goto end;
i00: putchar('0');
goto initial;
i01: putchar('1');
goto initial;
i10: putchar('2');
goto initial;
i11: putchar('3');
goto initial;
end: puts("");
exit(0);
}
MUMPS solution:
BASECHG (STR,BASE1,BASE2) ; Convert number to different base
N ACC,I,LEN,REM,REMS,STR2
S LEN=$L(STR),ACC=0
F I=1:1:LEN-1 S ACC=ACC+$E(STR,I),ACC=ACC*BASE1
S ACC=ACC+$E(STR,LEN)
I ACC<BASE2 S STR2=ACC
E D
. S I=0 F Q:ACC<BASE2 S REM=ACC#BASE2,ACC=ACC\BASE2,I=I+1,REMS(I)=REM
. S STR2=ACC,I="" F S I=$O(REMS(I),-1) Q:I="" S STR2=STR2_REMS(I)
W !,STR," (",BASE1,") = ",STR2," (",BASE2,")"
Q
—
D ^BASECHG("11011000",2,4)
11011000 (2) = 3120 (4)