Natural number arithmetic via unary representationIn unary representation of natural number, one simply writes as many digits as the number one wants to represent. string length sort of converts unary to decimal, and string repeat can be used to convert decimal to unary. That way, one can do things such as the following.
proc plus {a b} {
string length "[string repeat 1 $a][string repeat 1 $b]"
}As expected, we get% plus 2 2 4 % plus 2 3 5Negative input seems to be accepted, but is then treated as zero.
% plus -2 2 2In a similar vein, one can define
proc minus {a b} {
string length [string range [string repeat 1 $a] $b end]
}
proc times {a b} {
string length [string repeat [string repeat 1 $a] $b]
}
proc div {a b} {
string length [string map [
list [string repeat 1 $b] N 1 {}
] [string repeat 1 $a]]
}
proc mod {a b} {
string length [string map [
list [string repeat 1 $b] {}
] [string repeat 1 $a]]
}From these one gets for example% minus 10 4 6 % minus 4 10 0 % times 6 7 42 % div 10 4 2 % mod 7 2 1 % mod 7 0 7 % div 7 0 0some of which are unusual, still (kind of) make sense.
DKF: An alternative strategy is to break things up into digits, use a lookup table for the combining of digits and then apply primary school long-arithmetic rules for combining these manipulations.Once you can handle cardinal numbers, you just extend it to signed numbers (it's just a matter of swapping the operation or flipping the result sign). Then decimals.This sort of thing is actually the basis of some arbitrary-precision arithmetic packages, except they tend to use real math ops instead of LUTs (and hence work on larger numbers of digits at once.)
set plusLUT(result) {
{0 1 2 3 4 5 6 7 8 9}
{1 2 3 4 5 6 7 8 9 0}
{2 3 4 5 6 7 8 9 0 1}
{3 4 5 6 7 8 9 0 1 2}
{4 5 6 7 8 9 0 1 2 3}
{5 6 7 8 9 0 1 2 3 4}
{6 7 8 9 0 1 2 3 4 5}
{7 8 9 0 1 2 3 4 5 6}
{8 9 0 1 2 3 4 5 6 7}
{9 0 1 2 3 4 5 6 7 8}
}
set plusLUT(carry) {
{0 0 0 0 0 0 0 0 0 0}
{0 0 0 0 0 0 0 0 0 1}
{0 0 0 0 0 0 0 0 1 1}
{0 0 0 0 0 0 0 1 1 1}
{0 0 0 0 0 0 1 1 1 1}
{0 0 0 0 0 1 1 1 1 1}
{0 0 0 0 1 1 1 1 1 1}
{0 0 0 1 1 1 1 1 1 1}
{0 0 1 1 1 1 1 1 1 1}
{0 1 1 1 1 1 1 1 1 1}
}
proc rev list {
set result {}
foreach item $list {
set result [linsert $result 0 $item]
}
return $result
}
proc plus {x y} {
global plusLUT
set xDigits [rev [split $x ""]]
set yDigits [rev [split $y ""]]
set carry 0
set result {}
foreach xd $xDigits yd $yDigits {
if {$xd eq ""} {set xd 0}
if {$yd eq ""} {set yd 0}
set r0 [lindex $plusLUT(result) $xd $yd]
set c0 [lindex $plusLUT(carry) $xd $yd]
lappend result [lindex $plusLUT(result) $r0 $carry]
set c1 [lindex $plusLUT(carry) $r0 $carry]
set carry [lindex $plusLUT(result) $c0 $c1] ;# This never carries!
set xd 0; set yd 0
}
if {$carry ne "0"} {lappend result $carry}
return [join [rev $result] ""]
}Now, all it requires is subtraction, multiplication and a div-mod function (IIRC life is easier if you implement div-mod and derive both division and modulo functions from it.)(Arguably, the above code uses numbers in indices, but you could replace them with Tcl arrays.)Zarutian 30.mars 2005: Here is a näive implemention of minus:
proc minus {a b} {
set t1 $b
set t2 0
while {"$a" != "$t1"} {
set t1 [plus $t1 1]
set t2 [plus $t2 1]
}
return $t2
}BH: While it does seem rather like cheating...
$ tclsh8.0
% proc plus { x y } { incr x $y }
% proc minus { x y } { incr x -$y }
% plus 2 2
4
% minus 10 4
6Surprisingly, incr in 8.0 is quite happy with a double-negative increment:% minus 5 -2 7 % set x 5 5 % incr x --3 8Unfortunately, this doesn't seem to hold true in the general case:
% incr x ---3
expected integer but got "---3"
% set y --1
--1
% expr {$y + 1}
can't use non-numeric string as operand of "+"
% if { $y < 0 } { puts Neg } else { puts Pos }
NegOr in newer versions:$ tclsh8.4 % set x 5 5 % incr x --1 expected integer but got "--1"
Other approaches ... Arithmetics with strings Church numerals[ Arts and crafts of Tcl-Tk programming - ] Category Concept
