Tuesday, January 22, 2008

Making Arithmetic function from Logical function ( Pascal, C )

When I was in 12th Grade High School, I asked myself how a computer can do arithmetic. I had already programming Pascal since I was in Grade 7th, and I don’t know much about logic gates, yet at that time. But I know that in its very basic form, computer can only do logical operation such as AND, OR, NOT, XOR, SHL and SHR, so I asked myself, how can I make a function in capable to do addition without the use of the sign “+” in the program. These are the steps I take :

First, I make a truth table for basic binary addition in order to know what is needed in the function :
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

Then I realize that the right hand side of the addition process above must be two bits long instead of only one bit, so I rewrite them in the form below
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

Later, I compare the truth table for several logic gates with the result I got above, it turn out that :
- the least significant bit, which I called R, show XOR logical relationship with the input.
R = A xor B .…(E1)

- the most significant bit, which I called C, show AND logical relationship with the input.
C = A and B ….(E2)

Since in its basic form the equation must be in the form of :
A + B = C shl 1 + R ….(E3)

By substituting E1 and E2 to equation E3 we got equation E4, below :
A + B = (A and B) shl 1 + (A xor B) ….(E4)

Then I write a Pascal recursive function capable of doing addition without using the sign “+”.

function AddLogic(const A : integer, B : integer) : integer;
var R,C : integer;
R:=A xor B;
C:=(A and B) shl 1;

if (R=0) then R:=C;
else R:=AddLogic(R,C);


I realize later that I can do away with the recursive bit, by using repetition.

function AddLogic(const A : integer, B : integer) : integer;
var A1,B1,R,C : integer;
R:=A1 xor B1;
C:=(A1 and B1) shl 1;
until (C=0) or (R=0);
if (R=0) then R:=C;

Which later I translate to C.

int AddLogic( int A, int B)
{ int A1,B1,R,C;
{ R=A1^B1;
} while (C&R);
if C R=C;
return R;

These programs didn't run as fast as if I just use the sign "+", which is a proof that something is still missing from my understanding. Later I realize that this level of detail is done in hardware layer instead of software layer. I will tell you what is missing in later posting.

No comments: