How is fundamental mathematics efficiently evaluated by programming languages?

Question

As I get more and more involved with the theory behind programming, I find myself fascinated and dumbfounded by seemingly simple things.. I realize that my understanding of the majority of fundamental processes is justified through circular logic

Q: How does this work?

A: Because it does!

I hate this realization! I love knowledge, and on top of that I love learning, which leads me to my question (albeit it's a broad one).

Question:

How are fundamental mathematical operators assessed with programming languages?

How have current methods been improved?

Example

var = 5 * 5; 

My interpretation:

$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
    $num3 = $num3 + $num1;
    $num2 = $num2 - 1;
}
echo $num3;

This seems to be highly inefficient. With Higher factors, this method is very slow while the standard built in method is instantanious. How would you simulate multiplication without iterating addition?

var = 5 / 5;

How is this even done? I can't think of a way to literally split it 5 into 5 equal parts.

var = 5 ^ 5; 

Iterations of iterations of addition? My interpretation:

$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {

    $num2 = 5; $num3 = 0;
    while ($num2 > 0) {
        $num3 = $num3 + $num1;
        $num2 = $num2 - 1;
    }
    $num1 = $num3;
    $mod -=1;
}
echo $num3;

Again, this is EXTREMELY inefficient, yet I can't think of another way to do this. This same question extends to all mathematical related functions that are handled automagically.

Answer 1

To really understand how arithmetic works inside a computer you need to have programmed in assembly language. Preferably one with a small word size and without multiplication and division instructions. Something like the 6502.

On the 6502, virtually all arithmetic is done in a register called the Accumulator. (A register is a special memory location inside the processor that can be accessed quickly.) So to add two numbers, you load the first number into the Accumulator, then add the second number to it.

But that's oversimplifying. Because the 6502 is an 8-bit processor, it can handle numbers only from 0 to 255. Most of the time you will want to be able to work with larger numbers. You have to add these in chunks, 8 bits at a time. The processor has a Carry flag that is set when the result of adding two numbers overflows the Accumulator. The processor adds that in when doing an addition, so it can be used to "carry the 1" assuming you start with the lowest-order byte of a number. A multi-byte add on the 6502 looks like this:

1. Clear carry flag (CLC)
2. Load lowest-order-byte of first number (LDA, load accumulator)
3. Add lowest-order-byte of second number (ADC, add with carry)
4. Store lowest-order byte of result (STA, store accumulator)
5. Repeat steps 2-4 with successively higher-order bytes
6. If at the end, the carry is set, you have overflowed; take appropriate action, such as generating an error message (BCS/BCC, branch if carry set/clear)

Subtraction is similar except you set the carry first, use the SBC instruction instead of ADC, and at the end the carry is clear if there was underflow.

But wait! What about negative numbers? Well, with the 6502 these are stored in a format called two's complement. Assuming an 8-bit number, -1 is stored as 255, because when you add 255 to something, you get one less in the Accumulator (plus a carry). -2 is stored as 254 and so on, all the way down to -128, which is stored as 128. So for signed integers, half the 0-255 range of a byte is used for positive numbers and half for negative numbers. (This convention lets you just check the high bit of a number to see if it's negative.)

Think of it like a 24-hour clock: adding 23 to the time will result in a time one hour earlier (on the next day). So 23 is the clock's modular equivalent to -1.

When you are using more than 1 byte you have to use larger numbers for negatives. For example, 16-bit integers have a range of 0-65536. So 65535 is used to represent -1, and so on, because adding 65535 to any number results in one less (plus a carry).

On the 6502 there are only four arithmetic operations: add, subtract, multiply by two (shift left), and divide by two (shift right). Multiplication and division can be done using only these operations when dealing in binary. For example, consider multiplying 5 (binary 101) and 3 (binary 11). As with decimal long multiplication, we start with the right digit of the multiplier and multiply 101 by 1, giving 101. Then we shift the multiplicand left and multiply 1010 by 1, giving 1010. Then we add these results together, giving 1111, or 15. Since we are ever only multiplying by 1 or 0, we don't really multiply; each bit of the multiplier simply serves as a flag which tells us whether to add the (shifted) multiplicand or not.

Division is analogous to manual long division using trial divisors, except in binary. If you are dividing by a constant, it is possible to do this in a way analogous to subtraction: rather than dividing by X, you multiply by a precalculated rendition of 1/X that produces the desired result plus an overflow. Even today, this is faster than division.

Here's a page showing some actual 6502 code for multiplication and division, including a nicely optimized multiplication routine that uses a 2 kilobyte lookup table. http://nparker.llx.com/a2/mult.html

Now try doing floating-point math in assembly, or converting floating-point numbers to nice output formats in assembly. And do remember, it's 1979 and the clock speed is 1 MHz, so you must do it as efficiently as possible.

Things still work pretty much like this today, except with bigger word sizes and more registers, and of course most of the math is done by hardware now. But it's still done in the same fundamental way. If you add up the number of shifts and adds required for a multiply, for example, it correlates rather well to the number of cycles required for a hardware multiply instruction on early processors having such an instruction, such as the 6809, where it was performed in microcode in much the same way you would do it manually. (If you have a larger transistor budget, there are faster ways to do the shifts and adds, so modern processors do not perform these operations sequentially and can perform multiplications in as little as a single cycle.)

Answer 2

In the end, basic arithmetic operations are done in hardware. More specifically, in the CPU (or actually, a subpart thereof)

In other words, it's electronic circuits. Set the appropriate bits as input and you will get the appropriate bits as output. It is a combination of basic logic gates.

http://en.wikipedia.org/wiki/Adder_%28electronics%29

http://en.wikipedia.org/wiki/Binary_multiplier

Answer 3

This is all covered with thorough patience in Don Knuth's The Art of Computer Programming.

Efficient algorithms for add, subtract, multiply and divide are all described in complete detail.

You can read things like this that cover division nicely.

http://research.microsoft.com/pubs/151917/divmodnote.pdf

Answer 4

It's done in picoseconds by electronic circuits. Google 'hardware multiplier' etc. for details. Modern CPUs are the extremely complex result of decades of continuous improvement.

BTW, Since you don't multiply by repeated addition, why would you imagine a computer would?

Answer 5

This isn't meant to be a thorough answer by any means but it should give you some idea how things are implemented. As you probably know numbers are represented in binary. For instance a computer could represent the number 5 as 00000101. A very basic operation a computer can do is shift left, which would give 00001010 which is decimal 10. If it were shifter right twice it would be 00010100 (decimal 20). Every time we shift the digits left 1 time we double the number. Say I had a number x and i wanted to multiply it by 17. I could shift x to the left 4 times and then add x to the result (16x + x = 17x). This would be an efficient way to multiply a number by 17. This should give you some insight into how a computer can multiply large numbers without just using repeated addition.

Division can use combinations of addition, subtraction, shift right, shift left, etc. There are also numerous tricks for raising numbers to exponents.

Answer 6

When I was a kid, I learned how to multiply and divide with a pen and a paper, without wasting time with too many additions. Later I learned that square roots are computable that way as well.

At university I learned how to compute trigonometric and logarithmic operations with a dozen of multiplications, divisions and additions. They called it Taylor series.

Before that, my father gave me a book where those complex operations were already computed for hundreds of values and presented in tables. There was also some explanations for estimating the error when you wanted the sine of a value between two computed values.

Integer units, floating point units, GPU and DSP just implement all those old techniques on silicon.

Answer 7

I'll try to give you an idea of how digital circuits are designed to solve digital processing problems by using the problems you pose: how do CPUs implement additions and multiplications.

Firstly, lets get the direct question out of the way: how does a programming language efficiently evaluate multiplications and additions. The answer is simple, they compile them into multiply and add instructions. For example, the following code:

a = 1 + 1;
b = a * 20;

is simply compiled to something like:

ADD 1 1  a
MUL a 20 b

(note, that the above assembly is for an imaginary CPU that doesn't exist, for simplicity's sake).

At this point you realize that the above answer simply shifts the problem and solve it by hardware magic. The follow-up question is obviously how does that hardware magic work?

Lets look at the simpler problem first: addition.

First we do a familiar problem, adding in regular base 10 numbers:

 17
+28

The first step would be to add 7 and 8. But this results in 15 which is more than a single digit. So we carry the 1:

(1)
 17
+28
= 5

Now we add 1, 1 and 2 together:

 17
+28
=45

So from this we get the following rules:

1. when the result of addition is more than one digit, we keep the least significant digit and carry the most significant digit forward

2. if we have a digit carried forward into our column we add it along with the numbers we're adding

Now it's time to interpret the rules above in base 2 - boolean algebra.

So in boolean algebra, adding 0 and 1 together = 1. Adding 0 and 0 = 0. And adding 1 and 1 = 10 which is more than one digit so we carry the 1 forward.

From this we can construct a truth table:

a b  |  sum  carry
-------------------
0 0  |   0     0
0 1  |   1     0
1 0  |   1     0
1 1  |   0     1

From this, we can construct two circuits/boolean equations - one for the output of sum and one for the output of carry. The most naive way is to simply list out all the inputs. Any truth table, no matter how big and complex can be restated in this form:

(AND inputs in first row) OR (AND of inputs in second row) OR ...

This is basically the sum of products form. We only look at outputs that result in a 1 and ignore the 0s:

sum = (NOT a AND b) OR (a AND NOT b)

Let's replace the AND OR and NOT with programming language symbols to make that easier to read:

sum = (!a & b) | (a & !b)

Basically, we've converted the table like so:

a b  |  sum  equation
-------------------
0 0  |   0   
0 1  |   1   (!a & b)
1 0  |   1   (a & !b)
1 1  |   0   

This can be directly implemented as a circuit:

                _____
 a ------------|     |
    \          | AND |-.     ____
     \  ,-NOT--|_____|  \   |    |
      \/                 `--| OR |----- sum
      /\        _____    ,--|____|
     /  `-NOT--|     |  /
    /          | AND |-`
 b ------------|_____|

Observant readers would at this point notice that the above logic can actually be implemented as a single gate - an XOR gate which conveniently has the behavior required by our truth table:

                _____
 a ------------|     |
               | XOR |---- sum
 b ------------|_____|

But if your hardware doesn't provide you with an XOR gate, the steps above is how you'd go about defining and implementing it in terms of AND, OR and NOT gates.

How you'd go about converting logic gates to actual hardware depends on the hardware you have. They can be implemented using various physical mechanisms as long as the mechanism provides some sort of switching behavior. Logic gates have been implemented with everything from jets of water or puffs of air (fluidics) to transisitors (electronics) to falling marbles. It's a big topic in its own right so I'm going to just gloss it over and say that it's possible to implement logic gates as physical devices.

Now we do the same for the carry signal. Since there is only one condition where the carry signal is true, the equation is simply:

carry = a & b

So carry is simple:

                _____
 a ------------|     |
               | AND |---- carry
 b ------------|_____|

Combining them together we get what's known as the half adder:

                _____
 a ------;-----|     |
         |     | XOR |---- sum
 b --;---|-----|_____|
     |   |      _____
     |   '-----|     |
     |         | AND |---- carry
     '---------|_____|

The equations for the above circuit by the way looks like this:

sum = a ^ b
carry = a & b

The half adder is missing something. We've implemented the first rule - if the result is more than one digit than carry forward, but we haven't implemented the second rule - if there is a carry add it together with the numbers.

So to implement a full adder, an adding circuit that can add numbers that are more than one digit, we need to define a truth table:

a b c  |  sum  carry
---------------------
0 0 0  |   0     0
0 0 1  |   1     0
0 1 0  |   1     0
0 1 1  |   0     1
1 0 0  |   1     0
1 0 1  |   0     1
1 1 0  |   0     1
1 1 1  |   1     1

The equation for sum is now:

sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)

We can go through the same process to factor out and simplify the equation and interpret it as a circuit etc. as we've done above but I think this answer is getting overly long.

By now you should get an idea of how digital logic is designed. There are other tricks I've not mentioned such as Karnaugh maps (used to simplify truth tables) and logic compilers such as espresso (so that you don't have to factor boolean equations by hand) but the basic is basically what I've outlined above:

1. Decompose the problem until you can work at single bit (digit) level.

2. Define the outputs you want using a truth table.

3. Convert the table to a boolean equation and simplify the equation.

4. Interpret the equation as logic gates.

5. Convert your logic circuit to real hardware circuits by implementing logic gates.

That's how fundamental (or rather, low-level) problems are really solved - lots and lots of truth tables. The real creative work is in the breaking down of a complex task such as MP3 decoding to bit level so that you can work on it with truth tables.

Sorry I don't have the time to explain how to implement multiplication. You can try taking a crack at it by figuring out rules of how long multiplication works then interpreting it in binary then try to break it down to truth tables. Or you can read Wikipedia: http://en.wikipedia.org/wiki/Binary_multiplier

Answer 8

basic arithmetic instructions are performed with assembly instructions which are highly efficient.

More complex (or abstract) instructions are either done in assembly with looping mechanisms or are handled in std libs.

As you study mathematics in college you will start studying things like Lambda Calculus and Big-O notation. All of these, and many more, are used by programmers to evaluate and to create efficient algorithms. Anyways, the basic stuff is usually accomplished at the low-level such as in assembly or in c with pointers.

A great introduction to this topic is "Code" by Charles Petzold.

Answer 9

Get a book like Fundamentals of Digital Logic..., which I think is still pretty standard for Freshman/Sophomore EE students, and work your way through it (ed: it costs a small fortune, so look for a used or prior edition of it). That will take you up through the adders and multipliers, and give you enough of a background to start understanding some of the principles behind what the hardware is doing.

Your answer will, in the short term, become "because it fits together umpteen pieces of simpler logic to evoke this complex behavior" instead of "because it does."

If you want to try to understand all of the principles of how programs are compiled and run, go for that in conjunction, so you can ultimately see how everything meets in the middle.

Answer 10

There are a lot of good answers here. You started with the right idea, too: complex operations like multiplication are built from simpler operations. As you guessed, there are faster ways of multiplying without a multiplication instruction than using a series of additions. Any multiplication can be implemented as the sum of smaller multiplications, or as a combination of shifts and additions. Examples:

a = 5 + 5 + 5 + 5 + 5;           // 5*5, but takes 5 operations
b = (5 << 2) + 5;                // 5*5 in only 2 operations
c = (41 << 4) + (41 << 2) + 41   // 41*21 in 4 operations

Division can likewise be broken down into smaller operations. XOR (^) is a built-in instruction on every processor I've ever looked at, but even so it can be implemented as a combination of AND, OR, and NOT.

I have a feeling, though, that specific answers will be less satisfying to you than a general idea of the kinds of instructions a processor provides and how those instructions can be combined into more complex operations. There's nothing better for that kind of curiosity than a healthy dose of assembly language. Here's a very approachable introduction to MIPS assembly language.

Answer 11

Here's how a modern processor might implement multiplication of two 64 bit integers:

You know how to do a long hand multiplication. To multiply two 10 digit numbers, you would multiply one 10 digit number by each of the 10 digits of the other number, write the 11 digits result one below the other and shifted, then add all the number.

A modern processor does this with all the 64 by 64 bits. However, a multiplication of two single bit numbers is very simple: 1 x 1 = 1, all other products are zero. This is implemented with a logical and. And unlike the decimal product, where the result can be two digits, a binary product of single bit numbers is always one bit.

So now you have 64 rows of 64 bits that need to be added. But 64 additions of 64 bit numbers are slooooooow. So the processor uses either a 3/2 adder or a 7/3 adder: If you add 3 single bit numbers, the result can be 0, 1, 2 or 3, which fits into two bits. If you add 7 single bit numbers, the result is a number from 0 to 7, which can be represented by 3 bits. IBM claims they can make a 7/3 adder with just 18 primitive circuits (PowerPC documentation), I bet Intel and ARM can do this as well.

You have 4096 bits, group them into about 600 groups of 7 bits in the same bit positions, and use about 600 7/3 adders to reduce the result from 4096 bits to less than 2,000. Then you do the same again, and again, until you end up with pairs of bits that can be fed into an ordinary full adder.