Arithmetics with strings

Richard Suchenwirth 2003-06-10 - To teach programming to children, we need simple examples (simple both in contents and code) which are easily understood, and yet convey some of the fascination we old guys find in Tcl. Here's what I came up with, after a few evenings of |_Ps (drinks):

Imagine the computer couldn't compute, i.e. do arithmetics with numbers, but could only do string operations (everything is a string). Now we want to teach it arithmetics on natural numbers (0 included) by expressing them as strings in a simple way:

 1 <-> x
 5 <-> xxxxx

and so forth: a natural number is expressed by so many x's. (Introduce "" as notation for the empty string, length 0, here.) At least we can type in decimal numbers on the keyboard, so the first step is to write converters between natural numbers and x-strings:

 proc s<-num {n} {string repeat x $n}
 proc s->num {s} {string length $s}

Obviously, addition of such "string-numbers" is easily achieved by just concatenation:

 xx + xxx = xxxxx

which can be had without any function calls:

 set a xx
 set b xxx
 puts $a$b

but we want to preserve this first solution in a proc, so:

 proc s+ {a b} {return $a$b}

Multiplication is also easy, we just have to repeat the string repeat of s<-num, but this time with one argument which might be longer (or shorter) than an "x":

 proc s* {a b} {string repeat $a [s->num $b]}

Heavy testing should of course happen after each of these steps - I'll save them for the end of this page. For subtraction we introduce regsub which does the job very simply, but leaves the minuend unchanged if the subtrahend exceeds it in length (which case is undefined for natural numbers):

 proc s- {a b} {regsub $b $a ""}

As this doesn't work in 8.4a2 on PocketPC, I had to rewrite it slightly wordier:

 proc s- {a b} {regsub $b $a "" a; return $a}

Division is again done with regsub, but this time using the -all switch to subtract b as often as possible, and give a target variable; so regsub returns the number of substitutions, which we have to convert into a "string-number" again:

 proc s/ {a b} {s<-num [regsub -all $b $a "" a]}

Now, with only the string and regsub commands (plus a little help from proc and return), we have recreated four-species math on natural numbers (as long as virtual memory suffices to store possibly very long "string-numbers" - at least 32 bits is not the limit). I wonder how kids react... I at least am again amazed by the simplicity and power of Tcl.

Though we at first should not expect that extending these games to reals, rationals, or even integers, is another child's play, we can of course think of more uses. For example, modulo is even simpler than division:

 proc s% {a b} {regsub -all $b $a ""}

But again, I had to work around 8.4a2, so make that:

 proc s% {a b} {
    regsub -all $b $a "" a
    return $a
 }

...and squaring is just a special case of multiplication:

 proc s2 {a} {string repeat $a [s->num $a]}

Taking a to the b-th power introduces the concept of looping, which can go over the x's of the counter:

 proc s^ {a b} {
    set res x ;# neutral element
    foreach i [split $b ""] {
       set res [s* $res $a]
    }
    set res
 }

...but let's go testing, which is long overdue. Here's a simple but strict "test harness", which only succeeds if no test fails:

 proc test cases {
    foreach {cmd expected} $cases {
       catch $cmd res
       if {$res != $expected} {
          error "$cmd=$res, expected $expected"
       }
    }
    puts "Passed all tests."
 }
 test {
    {set x [s<-num 7]} xxxxxxx
    {set y [s<-num 4]} xxxx
    {s<-num 0} ""
    {s->num xxxxx} 5
    {s->num ""} 0
    {s->num [s+ $x $y]} 11
    {s->num [s+ $x ""]} 7
    {s->num [s- $x $y]} 3
    {s->num [s- $x ""]} 7
    {s->num [s- "" ""]} 0
    {s->num [s* $x $y]} 28
    {s->num [s* $x ""]} 0
    {s->num [s/ $x $y]} 1
    {s->num [s/ "" $y]} 0
    {s->num [s% $x $y]} 3
    {s->num [s2  $y]} 16
    {s->num [s2 ""]} 0
    {s->num [s^ xx xxx]} 8
    {s->num [s^ xxx ""]} 1
    {s->num [s^ "" ""]} 1
 }

This test suite passes on my little box - note that it's longer than the few lines of source code that are tested, but that's normal and even good (but might bore kids). The earlier a bug is found, the better, so best spend at least as much time on test design as on coding :-

Just remembering the old computer folk joke, "back then, all we had was 0 and 1, and at some times we even didn't have 1": replace "x" with "0" in the above examples, and you get five(6?)-species math with 0 only :)

 s+ 00 000 -> 00000

FW: Or, replace x with 1 to make it correct base 1 notation, which is what it really is.

Another application: determining whether a number is a prime, with regexp:

 proc isprime x {
   expr {$x>1 && ![regexp {^(xx+?)\1+$} [string repeat x $x]]}
 }