## Base-26 Arithmetic

### March 23, 2012

We write functions to convert between Prashant strings and Scheme numbers, then use normal Scheme multiplication; the digits and undigits functions of the Standard Prelude make the conversions easy:

```(define (number->prashant n)   (define (d->c d) (integer->char (+ d 65)))   (list->string (map d->c (digits n 26))))```

```(define (prashant->number p)   (define (c->d c) (- (char->integer c) 65))   (undigits (map c->d (string->list p)) 26))```

Here are two examples:

```> (number->prashant 1234567) "CSGHJ" > (prashant->number "CSGHJ") 1234567```

Then the multiplication function is simple:

```(define (prashant-times x y)   (number->prashant     (* (prashant->number x)        (prashant->number y))))```

And here’s another example:

> (prashant-times "CSGHJ" "CBA")
"FNEUZJA"

You can run the program at http://programmingpraxis.codepad.org/ZXOpICfm.

Pages: 1 2

### 16 Responses to “Base-26 Arithmetic”

1. PHP CLI:

```<? \$a=str_split(strtoupper(\$argv));
\$b=str_split(strtoupper(\$argv));
\$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));?>
```
2. Graham said

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.

3. Graham said

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.

4. Graham said

Yup. Changing all 25s to 26s does the trick. I won’t repost, since I’ve already filled this page with my comments.

5. Paul G. said

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 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 * \$ARGV = " . FromBaseTen(ToBaseTen(\$ARGV, \$base) * ToBaseTen(\$ARGV, \$base), \$base) . "\n";
```
6. Johann Hibschman said

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.

7. 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;
for(i=0;i<strlen(argv);i++)	a=a*26+(toupper(argv[i])-65);
for(i=0;i<strlen(argv);i++)	b=b*26+(toupper(argv[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]);
}
```
8. 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]);
}
```
9. boc said

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

10. Globules said

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"
```
11. jonathanjohansen said

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"
```
12. Axio said

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))))
```
13. MVUTMJAWRZ said
```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]
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’)

14. Siyuan said

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: