# vALU: Virtual Arithmetic Logic Unit

, 2 Jan 2011 CPOL
 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

```static uint Adder(uint Addend_One, uint Addend_Two)
{
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

 First Prev Next
 My vote of 4 Yasser Azeem 9-Jan-11 19:17
 good for students Yasser Azeem 9-Jan-11 19:16
 My vote of 5 ShilpaKumari 6-Jan-11 23:59
 Nice article.
 My vote of 5 prasad02 5-Jan-11 16:56
 interesting Christ Kennedy 5-Jan-11 6:36
 Last Visit: 31-Dec-99 19:00     Last Update: 30-Mar-15 14:24 Refresh 1

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Web02 | 2.8.150327.1 | Last Updated 2 Jan 2011
Article Copyright 2011 by John Paul Walker