13,352,879 members (81,185 online)
alternative version

Stats

13.4K views
20 bookmarked
Posted 2 Jan 2011

vALU: Virtual Arithmetic Logic Unit

, 2 Jan 2011
 Rate this:
Algorithms of Hardware Mathematics

Background

A few days ago, I was reading an article on Instructables.com, where a guy had made a 4-Bit adder circuit using logic gates, similar to how an early computer would work. This gave me the idea to implement this in code.

What Exactly...

A computer performs mathematical functions through series of logic gates and bit shifts. This is done within the Arithmetic Logic Unit (ALU), which is either a separate processor, or a part of the main CPU that is specifically designed to perform these functions. This code allows us to take an integer, and perform the same operations the ALU would in order to Add, Subtract, Multiply, Divide, as well as find the Square Root and Logarithm of Integers.

Let's Get Started

{
uint Carry;
{
}
}

Addition is the simplest of the mathematical functions and is the basis for most of the other functions. Let's say we're adding two bits, in order to add them together, we XOR them.

0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

This will give you the current bit that should be in that position. However as you can see in the case of 1 ^ 1, there will be a carry bit. In order to find out what bit this should be, we need to AND them.

0 & 0 = 0;
0 & 1 = 0;
1 & 0 = 0;
1 & 1 = 1;

As you can see, it is only in the least case that will give us the carry bit;

Subtraction

static uint Subtractor(uint Subtrahend, uint Minuend)
{
}

Subtraction is merely an extension of addition. We do it by adding the Subtrahend to the Negative value of the Minuend, which is found by NOTting it, and adding 1 to it.

Multiplication

static uint Multiplier(uint Factor_One, uint Factor_Two)
{
uint Ans;
Ans = 0;
while(Factor_Two ! = 0)
{
if((Factor_Two & 1) == 1)
{
}
Factor_Two >>= 1;
Factor_One <<= 1;
}
return Ans;
}

Now we get into the really fun stuff. There are various Multiplication algorithms to be used. In this case, I've used what is called Peasant Multiplication, so called because it is simple enough to be used by peasants, and apparently computers.

Let's say we have our two factors, A & B. Division is done through a series of doubling one variable, and halving another. So we'll double A and halve B. First, we check to see if B is even or odd, if it's odd, then we'll add A to the Answer; if it's even, we do nothing. Shift A once to the left to double it, and shift B once to the right to halve it. We do the same thing again; if B is odd, we add A to the Answer, if even, we do nothing. Continue to do this until B is equal to 0.

Division

static uint Divider (uint Dividend, uint Divisor)
{
uint  Quotient, Hold;

Hold = Divisor;
Quotient = 0;
while(Hold < (1 << 30) && Hold < Dividend) // Should be 1 << (Bitsize - 2)
{
Hold <<= 1;
}
while(Hold >= Divisor)
{
Quotient <<= 1;
if(Dividend >= Hold)
{
Dividend = Subtractor(Dividend, Hold);
Quotient |= 1;
}
Hold >>= 1;
}
return Quotient;
}

Those of you who have studied ways to optimized code will likely have heard what a pain division is. Compared to the other math functions, division is quite complicated, and takes the most time. Check this out to see this algorithm in action.

Modulus

static uint Modulus(uint Dividend, uint Divisor)
{
uint Hold;

Hold = Divisor;
while(Hold < (1 << 30) && Hold < Dividend) // Same as division; 1 << (Bitsize - 2)
{
Hold <<= 1;
}
while(Hole >= Divisor)
{
if(Dividend >= Hold)
{
Dividend = Subtractor(Dividend, Hold);
}
Hold >>= 1;
}
return Dividend;
}

Modulus is essentially the same as division, minus having to keep track of a quotient.

Square Root

static uint SquareRoot(uint Square)
{
uint Root, Temp, One;
Root = 0;
One = 1 << 30;  // Like division & modulus; 1 << (Bitsize - 2)
while(One > Square)
{
One >>= 2;
}
while(One != 0)
{
Root >>= 1;
if(Square >= Temp)
{
Square = Subtractor(Square, Temp);
}
One >>= 2;
}
return Root;
}

Unfortunately, there isn't much I can say about this algorithm, as I'm still trying to wrap my head around it as well. More information on Square Roots can be found on Wikipedia, and the original site of this algorithm is here.

Logarithms

Binary Logarithm

static uint BinaryLogarithm(uint Num)
{
uint Exp;

Exp = 0;
while(Num >= 2)
{
Num >>= 1;
}
return Exp;
}

A couple of weeks ago, I was working on a Logarithm function, so I took it and adapted it to this. It's quite simple; all it does is find out how many times 2 must be multiplied to get to this number (or the closest to it). This is done by shifting the Number to the right, which is the same as halving it, which is the same as dividing it by two, until it is less than 2.

Logarithm

static uint Logarithm(uint Num, uint Base)
{
uint Exp;

Exp = 0;
while(Num >= Base)
{
Num = Divider(Num, Base);
}
return Exp;
}

As you can see, this works similar to the Binary Logarithm, but now you find the Logarithm of any Base you want.

Conclusion

I've always felt that algorithms like these were important to know; they provide the foundation for all computing platforms, and without them none of us here at CodeProject would have anything to do.

Well, I hope these algorithms have piqued your interest, and that you take something away from learning about them as I did.

Enjoy!

History

• 2nd January, 2011: Initial post

Share

 United States
No Biography provided

You may also be interested in...

 Pro

 First Prev Next
 My vote of 4 Yasser Azeem9-Jan-11 19:17 Yasser Azeem 9-Jan-11 19:17
 good for students Yasser Azeem9-Jan-11 19:16 Yasser Azeem 9-Jan-11 19:16
 My vote of 5 ShilpaKumari6-Jan-11 23:59 ShilpaKumari 6-Jan-11 23:59