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.

Posted by programmingpraxis

Filed in Exercises

16 Comments »

16 Responses to “Base-26 Arithmetic”

Manoj Senguttuvan said

March 23, 2012 at 9:29 AM

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));?>

Graham said

March 23, 2012 at 10:40 AM

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)) == s as far as I can tell.

Graham said
March 23, 2012 at 10:42 AM
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.
Graham said
March 23, 2012 at 10:43 AM
Yup. Changing all 25s to 26s does the trick. I won’t repost, since I’ve already filled this page with my comments.

Paul G. said

March 23, 2012 at 2:01 PM

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";

Johann Hibschman said
March 23, 2012 at 2:49 PM
Ok, I should stop, but this is good J practice for me.
```
toDigits=: 65 -~ a. i. ]
toNumber=: 26 #. toDigits
```
Typically, I wouldn’t then bother with defining the multiply function and instead just use:
```
'CSGHJ' *&.toNumber 'CBA'
```
Of course, I could always define it if I wanted to:
```
b26mul=: *&.toNumber
'CSGHJ' b26mul 'CBA'
```
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.

Manoj Senguttuvan said

March 23, 2012 at 5:31 PM

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]);
}

Manoj Senguttuvan said
March 23, 2012 at 5:35 PM
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]);
}
```
boc said
March 24, 2012 at 7:13 PM
an erlang example.

“FNEUZJA” = base26:mult(“CSGHJ”, “CBA”).

Globules said

March 24, 2012 at 10:02 PM

In Haskell, but written for conciseness at the expense of speed and safety. :-)

import Data.Char
import Numeric

digits = ['A'..'Z']
from = fst . head . readInt 26 (`elem` digits) (\c -> ord c - ord 'A')
to n = showIntAtBase 26 (digits !!) n ""

x `mul` y = to $ from x * from y

main = putStrLn $ "CSGHJ" `mul` "CBA"

jonathanjohansen said

March 26, 2012 at 3:05 AM

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"

Axio said

March 26, 2012 at 7:15 AM

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))))

MVUTMJAWRZ said

March 26, 2012 at 5:42 PM

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’)

Siyuan said

April 5, 2012 at 7:06 AM

Also python version

def b26_to_int(a):
	if len(a) == 0:
		return 0
	return ord(a[-1]) - 97 + 26 * b26_to_int(a[0: -1])

def int_to_b26(a):
	return ''.join(chr(i+97) for i in dec_to_26(a))

def dec_to_26(a):
	if a == 0:
		return []
	b = dec_to_26(a//26)
	b.insert(len(b), a%26)
	return b

def b26_mul(a, b):
	answer = int_to_b26(b26_to_int(a.lower()) * b26_to_int(b.lower())).upper()
	if answer == '':
		return 'A'
	else:
		return answer

Christian Siegert said
June 17, 2012 at 11:26 AM
My solution written in Go lang: https://gist.github.com/2944246
Stuart Axon said
October 17, 2013 at 11:35 AM
@Siyuan The python one is a bit weird … int_to_b26(25) == ‘z’ int_to_b26(26) == ‘ba’ < should be 'aa'

Programming Praxis