Click here to Skip to main content
Click here to Skip to main content

vALU: Virtual Arithmetic Logic Unit

, 2 Jan 2011
Rate this:
Please Sign up or sign in to vote.
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

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

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

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

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)
    {
        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

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

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)

About the Author

John Paul Walker

United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 4 PinmemberYasser Azeem9-Jan-11 18:17 
Generalgood for students PinmemberYasser Azeem9-Jan-11 18:16 
GeneralMy vote of 5 PinmemberShilpaKumari6-Jan-11 22:59 
GeneralMy vote of 5 Pinmemberprasad025-Jan-11 15:56 
Generalinteresting PinmvpChrist Kennedy5-Jan-11 5:36 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 2 Jan 2011
Article Copyright 2011 by John Paul Walker
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid