Base-26 Arithmetic
March 23, 2012
A reader named Prashant recently wrote to suggest an exercise in base-26 arithmetic:
Write a function that takes two base-26 numbers in which digits are represented by letters with A=0, B=1, … Z=25 and returns their product using the same notation. As an example, CSGHJ × CBA = FNEUZJA.
Prashant was worried that the problem was specific to C/C++, but that’s not an issue.
Your task is to write the base-26 multiplication function. 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 
PHP CLI:
<? $a=str_split(strtoupper($argv[1])); $b=str_split(strtoupper($argv[2])); $no=array();$c=0;$d=0;$i=0; foreach($a as $val) $c=$c*26+(ord($val)-65); foreach ($b as $val) $d=$d*26+(ord($val)-65); $e=$c*$d; while($e) { $no[$i++]=chr(($e%26)+65); $e=(int)($e/26); } echo strrev(join($no));?>Maybe it’s too early for me and I made a mistake, but I think that “CSGHJ” x “CBA” = “FOFVAJA”; here’s my Python:
#!/usr/bin/env python from itertools import count, imap, izip, repeat, starmap from operator import mul from string import ascii_uppercase def powers(n): return imap(pow, repeat(n), count()) def digits(n): return imap(int, str(n)) def b26_to_int(s): return sum(starmap(mul, izip(powers(25), reversed([ascii_uppercase.index(k) for k in s])))) def int_to_b26(n): if n < 25: return ascii_uppercase[n] else: q, r = divmod(n, 25) return int_to_b26(q) + ascii_uppercase[r] def b26_mul(s, t): return int_to_b26(b26_to_int(s) * b26_to_int(t)) if __name__ == "__main__": print b26_mul("CSGHJ", "CBA")Changing bases seems to work fine, i.e.
int_to_b26(b26_to_int(s)) == sas far as I can tell.Woops, never mind. I tested against 25, instead of 26; let me work on this (make sure I don’t have any more embarassing mistakes) and get back to you later.
Yup. Changing all 25s to 26s does the trick. I won’t repost, since I’ve already filled this page with my comments.
Here is a Perl solution
use warnings; use strict; # declare the valid digits within the numbering system along with their values my @digits = ('A' .. 'Z'); my $base = scalar(@digits); my %values = map { $digits[$_] => $_ } 0 .. $#digits; sub ToBaseTen { my ($q, $base) = @_; my $n = 0; foreach (split(//, $q)) { my $digit = uc($_); # make sure the input string is valid return 0 unless exists $values{$digit}; # process the input number one digit at a time $n *= $base; $n += $values{$digit}; } return $n; } sub FromBaseTen { my ($q, $base) = @_; return $digits[0] unless $q; my $n = ''; while ($q > 0) { $n = $digits[$q % $base] . $n; $q = int($q / $base); } return $n; } die "Usage: $0 <base26num1> <base26num2>\n" unless scalar(@ARGV) == 2; print "$ARGV[0] * $ARGV[1] = " . FromBaseTen(ToBaseTen($ARGV[0], $base) * ToBaseTen($ARGV[1], $base), $base) . "\n";Ok, I should stop, but this is good J practice for me.
Typically, I wouldn’t then bother with defining the multiply function and instead just use:
Of course, I could always define it if I wanted to:
The trick here, besides having base-conversion built-in (“#.”), is the “under” adverb, “&.”. “f &. g” translates to
(define (under f g) (lambda (x y) ((inverse g) (f (g x) (g y)))))J is pretty clever about deducing the inverses of functions, and you can always explicitly set the inverse to a function, if it can’t figure it out.
Hey! Here’s the C code :
#include<stdio.h> #include<string.h> int main(int argc,char* argv[]) { unsigned long a=0,b=0;int i; char ans[20]; for(i=0;i<strlen(argv[1]);i++) a=a*26+(toupper(argv[1][i])-65); for(i=0;i<strlen(argv[2]);i++) b=b*26+(toupper(argv[2][i])-65); a=a*b,i=0; while(a) { ans[i++]=(a%26)+65; a/=26; } printf("%s",i==0?"A":""); for(i=strlen(ans)-1;i>=0;i--) printf("%c",ans[i]); }Hey! there’s a flaw :P replace the last 3 lines with:
if(i==0) printf("A"); else for(i=strlen(ans)-1;i>=0;i--) printf("%c",ans[i]); }an erlang example.
“FNEUZJA” = base26:mult(“CSGHJ”, “CBA”).
In Haskell, but written for conciseness at the expense of speed and safety. :-)
Looks long now that I’ve seen the other comments, but here’s one in Common Lisp:
;;;; Base-26 Multiplication (defun char-digit-value (c) (assert (alpha-char-p c)) (- (char-code (char-upcase c)) #.(char-code #\A))) ; (char-digit-value #\B) ; (char-digit-value #\b) ; (char-digit-value #\Y) (defun value-char-digit (n) (assert (<= 0 n 25)) (code-char (+ #.(char-code #\A) n))) ; (value-char-digit 0) ; (value-char-digit 1) ; (value-char-digit 25) ; (value-char-digit 26) (defun base-26-to-10 (string) (loop for c across (if (symbolp string) (symbol-name string) string) for value = (char-digit-value c) then (+ (* 26 value) (char-digit-value c)) finally (return value))) ; (base-26-to-10 'b) ; (base-26-to-10 'bc) (defun base-10-to-26 (integer) (when (zerop integer) (return-from base-10-to-26 "A")) (loop with n = integer and digits = () while (plusp n) do (multiple-value-bind (next dig) (floor n 26) (push (value-char-digit dig) digits) (setf n next)) finally (return (coerce digits 'string)))) ; (base-10-to-26 1) ; (base-10-to-26 0) ; (base-10-to-26 28) (defun base-26-mult (a b) (base-10-to-26 (* (base-26-to-10 a) (base-26-to-10 b)))) ; (base-26-mult 'b 'b) = "B" ; (base-26-mult 'bc 'ba) = "BCA" ; (base-26-mult 'loop 'do) = "BOXNPC" ; (base-26-mult 'abcdefghijklmnopqrstuvwxyz 'zyxwvutsrqponmlkjihgfedcba) = "BCBZUKWAYNTOYWGBGVSXHXROMMMNQXHXTXJEKBEWBXJNKALSWZA"Another CL version, in a slightly different style from that of Jonathan.
(defun f26->10 (str) (loop for i from 0 for j across (reverse (format nil "~:@(~a~)" str)) sum (* (expt 26 i) (- (char-code j) 65)))) (defun f10-26 (n &optional (r 0)) (reverse (concatenate 'string (loop while (> n 0) do (setf (values n r) (truncate n 26)) collect (code-char (+ 65 r)))))) (defun mul (a b) (f10-26 (* (f26->10 a) (f26->10 b))))from string import ascii_uppercase class WholeSym(long): SYM = ascii_uppercase def __new__(cls, value): if isinstance(value, (int,long)) and value>=0: return long.__new__(cls, value) elif isinstance(value, basestring) and all(ch in cls.SYM for ch in value): base = len(cls.SYM) digit = cls.SYM.index return long.__new__(cls, reduce(lambda x,y:base*x+digit(y), value, 0)) else: raise ValueError("invalid literal for WholeSym()") def __repr__(self): if self == 0: digits = [self.SYM[0]] else: digits = [] N = self while N != 0: N,d = divmod(N, len(self.SYM)) digits.append(self.SYM[d]) digits.reverse() return "%s(%r)" % (self.__class__.__name__, ''.join(digits)) __str__ = __repr__>>> WholeSym(WholeSym(‘CSGHJ’) * WholeSym(‘CBA’))
WholeSym(‘FNEUZJA’)
>>> W = WholeSym
>>> W( W(‘C’) * W(‘BL’) * W(‘CJ’) * W(‘FV’) * W(‘VHJ’) * W(‘MVUTMJAWRZ’) )
WholeSym(‘PROGRAMMINGPRAXIS’)
Also python version
My solution written in Go lang: https://gist.github.com/2944246
@Siyuan The python one is a bit weird … int_to_b26(25) == ‘z’ int_to_b26(26) == ‘ba’ < should be 'aa'