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)
> (prashant->number "CSGHJ")

Then the multiplication function is simple:

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

And here’s another example:

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

You can run the program at

About these ads

Pages: 1 2

16 Responses to “Base-26 Arithmetic”

  1. PHP CLI:

    <? $a=str_split(strtoupper($argv[1]));
    foreach($a as $val)
    foreach ($b as $val)
    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]
            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[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";
  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 :

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

       for(i=strlen(ans)-1;i>=0;i--) printf("%c",ans[i]);
  9. boc said

    an erlang example.

    “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))
        (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))
                raise ValueError("invalid literal for WholeSym()")
        def __repr__(self):
            if self == 0:
                digits = [self.SYM[0]]
                digits = []
                N = self
                while N != 0:
                    N,d = divmod(N, len(self.SYM))
            return "%s(%r)" % (self.__class__.__name__, ''.join(digits))
        __str__ = __repr__

    >>> WholeSym(WholeSym(‘CSGHJ’) * WholeSym(‘CBA’))
    >>> W = WholeSym
    >>> W( W(‘C’) * W(‘BL’) * W(‘CJ’) * W(‘FV’) * W(‘VHJ’) * W(‘MVUTMJAWRZ’) )

  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'
    		return answer
  15. Christian Siegert said

    My solution written in Go lang:

  16. @Siyuan The python one is a bit weird … int_to_b26(25) == ‘z’ int_to_b26(26) == ‘ba’ < should be 'aa'

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: