Click here to Skip to main content
15,908,776 members
Articles / Programming Languages / C#

vALU: Virtual Arithmetic Logic Unit

Rate me:
Please Sign up or sign in to vote.
4.96/5 (12 votes)
2 Jan 2011CPOL3 min read 19.2K   2   20   5
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

Addition

C#
static uint Adder(uint Addend_One, uint Addend_Two)
{
    uint Carry;
    while(Addend_Two != 0)
    {
        Carry = Addend_One & Addend_Two;
        Addend_One ^= Addend_Two;
        Addend_Two = Carry << 1;
    }
    return Addend_One;
} 

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

C#
static uint Subtractor(uint Subtrahend, uint Minuend)
{
    Minuend = Adder(~Minuend, 1);
    return Adder(Subtrahend, 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.

For more information, read here.

Multiplication

C#
static uint Multiplier(uint Factor_One, uint Factor_Two)
{
    uint Ans;
    Ans = 0;
    while(Factor_Two ! = 0)
    {
        if((Factor_Two & 1) == 1)
        {
            Ans = Adder(Ans, Factor_One);
        }
        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

C#
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

C#
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

C#
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)
    {
        Temp = Adder(Root, One);
        Root >>= 1;
        if(Square >= Temp)
        {
            Square = Subtractor(Square, Temp);
            Root = Adder(Root, One);
        }
        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

C#
static uint BinaryLogarithm(uint Num)
{
    uint Exp;

    Exp = 0;
    while(Num >= 2)
    {
        Num >>= 1;
        Exp = Adder(Exp, 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

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

    Exp = 0;
    while(Num >= Base)
    {
        Num = Divider(Num, Base);
        Exp = Adder(Exp, 1);
    }
    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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 4 Pin
Yasser Azeem9-Jan-11 18:17
Yasser Azeem9-Jan-11 18:17 
Generalgood for students Pin
Yasser Azeem9-Jan-11 18:16
Yasser Azeem9-Jan-11 18:16 
nice article.
GeneralMy vote of 5 Pin
ShilpaKumari6-Jan-11 22:59
ShilpaKumari6-Jan-11 22:59 
GeneralMy vote of 5 Pin
prasad025-Jan-11 15:56
prasad025-Jan-11 15:56 
Generalinteresting Pin
Christ Kennedy5-Jan-11 5:36
Christ Kennedy5-Jan-11 5:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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