Implementing Binary Arithmetic
Python, 429 chars - 10% bonus = 386.1
Numbers are kept in little endian order, which is stretching the rules a bit but makes for easier processing. Maximum number size is 32 bits. Addition is standard, subtraction is implemented by x-y = x+~y+1 (throwing away the carry out of the 32 bits), multiplication is done using the Russian Peasant algorithm, and division is done with repeated subtraction.
z,i='01'
P=z*32
def A(x,y):
r='';c=z
for a,b in zip(x+P,y+P):k=(a+b+c).count(i);r+='0101'[k];c='0011'[k]
return r[:32]
S=lambda x,y:A(A(x,''.join(chr(ord(c)^1)for c in y+P)),i)
def M(x,y):
r=''
while y:
if y[0]==i:r=A(r,x)
x=z+x;y=y[1:]
return r
def D(x,y):
x=(x+P)[:32];y=(y+P)[:32];r=''
while x[::-1]>=y[::-1]:r=A(r,i);x=S(x,y)
return r
def B(x,y,o):r=[A,S,M,D][o](x,y).rstrip(z)[:len(x)+len(y)];return[r,z][r=='']
B is the function of interest, here is its result on the test cases:
print B('01010','10101',0)
11111
print B('01111','01010',1)
00101
print B('0100','0001',2)
00001
print B('0101101','1000100',3)
101
Scala 785:
Let's start with a famous quote of Bjarne Stroustrup, the inventor of C++, which in his great wisdom told us:
Don't divide without necessity!
To make a submission to this fine question, we not only have to perform division - we have to implement it! Well - let's not talk about that.
object B{
val(l,o)=('1',"0")
type S=String
def n(v:S,c:S)=o*(c.size-v.size)+v
def g(n:S,m:S)=((n zip m)find(a=>a._1!=a._2)).getOrElse((l,'0'))._1==l
def a(x:S,y:S)=(((x zip y):\o)((n,m)=>{val s=Seq(m(0),n._1,n._2).filter(_==l).size
Seq("00","01","10","11")(s)}+m.tail))
def P(x:S,y:S)=t(a(n(x,y),n(y,x)))
def m(a:S,b:S)=(o/:a.zipWithIndex.filter(_._1==l).map(x=>b+o*(a.size-x._2-1)))(P)
def x(x:S,y:S)=t(s(x,y))
def s(x:S,y:S)=((x zip y):\o)((n,m)=>{val s=Seq(if(n._1==l)'0'else l,m(0),n._2).filter(_==l).size
Seq("01","00","11","10")(s)}+m.tail)
def M(a:S,b:S)=if(b==o)a else t(x(n(a,b),n(b,a)))
def d(n:S,m:S):S=if(g(n,m))P(D(M(n,m),m),"1")else o
def D(a:S,b:S)=t(d(n(a,b),n(b,a)))
def t(s:S)={val r=(s.substring(s.size-math.min(s.size,32))).replaceAll("^0*","")
if(r=="")o else r}
}
As usual, I have a less golfed version too, to explain 1 or 2 points (and this thread has much space left):
object BinArithmetic {
def normalize (v: String, cmp: String) = "0" * (cmp.size - v.size) + v
def ge(n:String, m:String)=((n zip m)find(a=>a._1!=a._2)).getOrElse(('1','0'))._1=='1'
def greaterEqual (a:String, b:String): Boolean = ge (normalize (a, b), normalize (b, a))
def i(s:String)=if(s=="0")"0"else trim32(j(s))
def j(s:String):String=if(s.size==0)""else{if(s(0)=='1')'0'else'1'}+j(s.tail)
def add (x:String, y: String): String =
(((x zip y) :\ "0")((b, a) => {
List (a(0), b._1, b._2).filter (_ == '1').size match {
case 0 => "00"
case 1 => "01"
case 2 => "10"
case 3 => "11"
}
}+a.tail))
def plus (a:String, b:String): String = {
trim32 (add (normalize (a, b), normalize (b, a)))
}
def mul (a:String, b: String): String =("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)
def sub(x:String, y: String): String = trim32(s(x,y))
def s(x:String, y: String): String =
((x zip y) :\ "0")((b, ü) => {
List (if(b._1=='1')'0' else '1', ü(0), b._2).filter (_ == '1').size match {
case 0 => "01"
case 1 => "00"
case 2 => "11"
case 3 => "10"
}
}+ü.tail)
def minus (a:String, b:String): String = if (b=="0") a else {
trim32 (sub (normalize (a, b), normalize (b, a)))
}
def d(n:String,m:String):String=if(ge(n,m))plus(div(minus(n,m),m),"1")else "0"
def div (a:String, b:String): String = {
trim32 (d (normalize (a, b), normalize (b, a)))
}
def trim32 (s: String): String = {
val res = (s.substring (s.length - math.min (s.length, 32))).replaceAll ("^0*", "")
if (res == "") "0" else res
}
}
Half way through golfing and obfuscating the code I changed the methods add and s(ub) a bit. Later I recognized that I didn't used the methods i(nv) and j which handled inversing numbers - my research showed that you can inverse a number as binary string, you can add "1" and so sub (a, b) should theoretically be the same as add (add (a, inv(b)), "1") but in practice, it isn't. :)
There are 4 sorts of Methods:
- preparation (normalize (a,b)) for example, which takes tow numbers, and makes them equal long
- core calculation methods (add, sub, mul, div)
- wrapping methods, which usually take (a,b) and normalize the call to the calculation methods with similar names (plus, minus)
- finishing methods, which post process the result (trim32)
The root is the add method.
def a(x:S, y: S) = (((x zip y) :\ "0")((n, m) => {
val s=List (m(0), n._1, n._2).filter (_ == '1').size
List ("00", "01", "10", "11") (s)
}+m.tail))
:\ is the right-fold operator. x zip y produces the list of pairs (10), (01), (11) from "101", "011", combines it with the overrun of the last operation, starting with no such overrun 0, counts the 1s in the result and produces a micro String like "10" from it. The 0 gets the growing part of the output, while 1 is the new overrun. You learned that at elementary school, didn't you? Now you remember!
The mul - method is interesting:
def mul (a:String, b: String): String =
("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)
From mul ("1010", "0110"), it takes a and zips with index ("1010"->0123 => 10, 01, 12, 03) filters those which are 1 in a: (10, 12) takes the b and adds (a.size=4 - (x._2=[0,2]) - 1) times a literal "0". 4-0-1 = 3, 4-2-1=1 => "0110"+"000", "0110"+"0". The result is put into the already defined plus operation, which is a normalized add.
div is just subtraction combined with addition:
def d (n:String, m:String):String=
if (greaterEqual (n,m)) plus (div (minus (n, m), m),"1") else "0"
if (n > m) then n/m = (n-m)/m + 1 else 0
if (8 > 3) 8/3 = (8-3)/3 + 1
if (5 > 3) 8/3 = (5-3)/3 + 1 + 1
since ! (2 > 3) 8/3 = 0 + 1 + 1
Sub is just similar implemented like add. Thanks to cyclic nature of ints, it doesn't really matter if the result is positive or negative.
Maybe I try the 2s-complement part later again.
Invocation
val ba = B
ba.plus ( "01010", "10101") // 11111
res412: String = 11111
ba.minus ( "11110", "01010") // 10100
res413: String = 10100
ba.mul ( "0010", "1000") // 10000
res414: String = 10000
ba.div ("1011010", "0010001") // 101
res415: String = 101
Smalltalk Squeak 4.x flavour, 570 bytes
First Try: define an operator in Object to evaluate any Object:
`x^self cull:x
We refine the eval message in Character to get the value:
`x^value
Then define bit ops with binary messages in Character:
&x^self class value:(x`1bitAnd:value)
|x^self class value:(x`1bitOr:value)
/x^self class value:((x`1bitXor:value)bitXor:$0`1)
/ is xor operator, because it looks like the truth table
01
10
Then add two more messages in Character for repeating in a String and concatanating
*n^String new:n withAll:self
,s^(String with:self),s
Or my favourite hack to gain 2 chars:
,s^'',(self`1+#[0]),s
Now create a new notation for accessing Array elements because (x at:i) costs two much. The operator @ could be used for at: and <@ would then means that it starts from the right (0-based) because our bit-Strings are big-endian.
That would be
Object subclass:#At instanceVariableNames:'a i'classVariableNames:''poolDictionaries:''category:''
In At, we would define two methods for initializing and accessing:
a:b i:j a:=b.i:=j
`x^(a atWrap:0-i)`x
Since this costs to much, we will replace this nice thing by using Association. So we define the accessor message in String (or in SequenceableCollection)
<@i^self->i
And just define ` to retrieve the At value in Association:
`x^(key atWrap:0-value)`x
Now we are ready to implement the operations in String first, strip the $0 left:
\~c |x|(x:=self)size>1or:[^x].c=(x at:1)or:[^x].^x allButFirst\~c
Then the awfull bit sum +| (just a naive xor with carry)
+|y|x z c m n|(m:=(x:=self)size)<=(n:=y size)or:[^y+|x].c:=$0.z:=''.0to:m-1do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m to:n-1do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z
Then the bit multiply *| :
*|y|x z|x:=self.z:='0'.0to:y size-1do:[:i|$0/(y<@i)=$0or:[z:=z+|x].x:=x,$0].^z
Then the bit subtraction -| is using two complement. Result is truncated to receiver length, so it must not be negative:
-|y|n x|n:=(x:=self\~$0)size.^(x+|'1'+|($1*n,(y collect:[:c|c/$1])))last:n
Then a test <| for bit less than:
<|y|m n|m:=self size.n:=y size.^m<n or:[m=n and:[self<y]]
Then the bit division /| (by subtraction) - this will also raise a zero divide exception when appropriate:
/|z| x y q t n|y:=z\~$0.x:=self\~$0.y='0'and:[1/0].n:=0max:x size-y size.q:=''.[n>=0]whileTrue:[t:=y,($0*n).n:=n-1.q:=q,(x<|t ifTrue:[$0]ifFalse:[x:=x-|t\~$0.$1])].^q
And finally the operation encoding - we reuse <@ to access right to left 0-based:
y:y o:o|x|x:=self.^({[x/|y].[x*|y].[x-|y].[x+|y]}<@o)`1\~$0
The small test suite:
self assert: ('01010' y:'10101' o:0) = '11111'.
self assert:('11110' y:'01010' o:1) = '10100'.
self assert:('0010' y:'1000' o:2) = '10000'.
self assert:('1011010' y:'0010001' o:3) = '101'.
The longer test suite:
| n |
n := 100.
0 to: n do: [:i|0 to:n do:[:j |
self assert: (i printStringBase:2)+|(j printStringBase:2)\~$0=(i+j printStringBase:2)]].
0 to: n do: [:i|0 to:n do:[:j |
self assert: (i printStringBase:2)*|(j printStringBase:2)\~$0=(i*j printStringBase:2)]].
0 to: n do: [:i|0 to:i do:[:j |
self assert: (i printStringBase:2)-|(j printStringBase:2)\~$0=(i-j printStringBase:2)]].
0 to: n do: [:i|1 to:n do:[:j |
self assert: (i printStringBase:2)/|(j printStringBase:2)\~$0=(i//j printStringBase:2)]].
And the score is given by:
{Object>>#`. SequenceableCollection>>#<@. Association>>#`}
, ({#`. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
, ({#\~. #+|. #-|. #*|. #/|. #<|. #y:o:} collect:[:selector | String>>selector])
detectSum: [:method | method getSource size].
Which is 921 chars...
We can do much better if we use Boolean instead of Integer. They can be easily transformed in character:
Implement in True:
c^$1
And in False:
c^$0
Now transform a binary Character in Boolean, implement in Character:
b^self=$1
Now logical operations are expressed much simply in Character:
&x^(x b&self b)c
|x^(x b|self b)c
/x^(x b xor:self b)c
Plus the two operations to repeat and concatenate:
*n^String new:n withAll:self
,s^self*1,s
Now, the message size is long, let's create a shorter binary message in String:
\n^self size-n
We shorten the message for stripping leading chars in String:
~c|x|(x:=self)\1<1or:[c~=(x at:1)or:[^(x last:x\1)~c]]
Now we'd better implement binary >= rather than < for division, let's call it >~ in String:
>~y^self\0>(y\0)or:[self\0=(y\0)and:[self>=y]]
Now back to the operations, we will call them + - * / even if we have to override existing methods in String (they are presumably not used):
y:y o:o|x|x:=self.^({[x/y].[x*y].[x-y].[x+y]}<@o)value~$0
+y|x z c m n|(m:=(x:=self)\1)<=(n:=y\1)or:[^y+x].c:=$0.z:=''.0to:m do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m+1to:n do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z
-y|n x|n:=(x:=self~$0)\0.^(x+'1'+($1*n,(y collect:[:c|c/$1])))last:n
*y|z|z:='0'.0to:y\1do:[:i|(y<@i)b and:[z:=self,($0*i)+z]].^z
/z| x y q t|y:=z~$0.x:=self~$0.y='0'and:[1/0].q:=''.(0max:x\0-(y\0))to:0by:-1do:[:n|t:=y,($0*n).q:=q,(x>~t and:[x:=x-t~$0.$1b])c].^q
The score is now
methods := {SequenceableCollection>>#<@. True>>#c. False>>#c}
, ({#b. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
, ({#\. #~. #+. #-. #*. #/. #>~. #y:o:} collect:[:selector | String>>selector]).
methods detectSum: [:method | method getSource size].
That is 742 chars
Another snippet to browse our code alltogether:
methods do: [:e | e methodClass organization classify: e selector under: '*CodeGolfBinaryArithmetic'].
SystemNavigation default
browseMessageList:
(methods collect: [:e | MethodReference class: e methodClass selector: e selector])
name: 'CodeGolfBinaryArithmetic'
We can further reduce the division to repeated subtraction (slower):
/z|x y|y:=z~$0.x:=self~$0.y='0'and:[1/0].x>~y or:[^'0'].^x-y/y+'1'
We can also omit 1/0 for ZeroDivide exception, anyway the result will be infinite on a computer with infinite memory after an infinite time:
/z|x y|y:=z~$0.x:=self~$0.x>~y or:[^'0'].^x-y/y+'1'
We can also reduce addition to a recursive form:
+y|x|(x:=self)\0>0or:[^y].y\0>0or:[^x].^x<@0&(y<@0)*1+(x first:x\1)+(y first:y\1),(x<@0/(y<@0))
And we now are at 570 chars... Not bad for Smalltalk.