Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
A little bit of backstory on me, I'm heading to college for computer science, and later in life mathematical theory as well as possibly philosophy and theoretical physics. Many aspirations, little time. –  Korvin Szanto Sep 26 '11 at 22:37
7  
Is it safe to presume you've looked at all the links from en.wikipedia.org/wiki/Category:Computer_arithmetic ? –  JB King Sep 26 '11 at 22:50
add comment

9 Answers

up vote 14 down vote accepted

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 up 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 two 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; the 1 or 0 simply serves as a flag which tells us whether to add the (shifted) multiplicand or not.

Division is somewhat hairier and I can't remember all the details but it is analogous to manual long division using trial divisors, except in binary.

You think that's complicated, try doing floating-point math in assembly, or converting floating-point numbers to nice output formats in assembly. And do remember, 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, where it was performed in microcode in much the same way as 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 as single cycle.)

share|improve this answer
1  
Hey, thank you for your very detailed explanation! It's exactly what I wanted! Being at my level, you often forget that what is supporting you is generally more complex than anything you're doing. That is the exact reason why I want to study computer science. I hate the fact that if I were to go back in time, I'd know nothing world changing, just how to formulate a proper SQL statement ;) At any rate, thank you very much for spending the time to write out this answer, you've given me a taste tester into what I'm about to delve into. –  Korvin Szanto Sep 27 '11 at 5:00
3  
disagree, assembly is still too high, if you want to know how computers do arithmetic you have to look at hardware, or at least hardware algorithms –  jk. Sep 27 '11 at 9:09
    
Eh. Once you know there are adders and shifters, it's as easy to imagine them controlled by hardware as by software, and it's easier to play with software. –  kindall Sep 30 '11 at 5:22
1  
-1. Hardware multiply has not been done with shifts and adds for close to 3 decades now, and many CPUs can do a multiply in one cycle. Check the Wikipedia article on Binary Multiplier for the details. –  Mason Wheeler Nov 24 '11 at 0:59
1  
Addressed this. Thanks! –  kindall Nov 27 '11 at 18:25
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Just to be clear, you can generally shift by more than one bit at a time. So those 4 shift operations are actually just one operation, like: shl r0, 4. –  Caleb Sep 27 '11 at 1:05
add comment

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

share|improve this answer
3  
The algorithms for the hardware are carefully specified and can be studied separate from the hardware. –  S.Lott Sep 27 '11 at 1:12
    
@S.Lott: I find your comment confusing. To me, algorithms involve a series of steps you follow, a procedure, something you can program. Here, we are talking about electronic circuits performing the basic arithmetic operations. In other words, just a sequence of gates where the current flows. So it's more "logical" than "algorithmic" at best. ...my 2 cents. –  arnaud Sep 27 '11 at 19:50
2  
An algorithm is "finite, definite and effective" It can be in circuits, or done with paper and pencil, or done with Tinkertoys or molecules in a dish or DNA. Algorithm can be anything. An electronic circuit must follow a defined algorithm. It doesn't magically get past the need for algorithms. –  S.Lott Sep 27 '11 at 21:00
add comment

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.

share|improve this answer
    
Or lookup tables. Much quicker to precompute values and look them up. Examples Sin/Cos/Tan (integer division though this is pre-computed and stored in the hardware). –  Loki Astari Sep 26 '11 at 22:53
add comment

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?

share|improve this answer
    
My question is regarding the reasoning behind the functions rather than the functions themselves, I understand that it's interpreted by the processor, I'm curious how. Specifically the theory behind it and how it could be replicated in pseudo-code. –  Korvin Szanto Sep 26 '11 at 22:43
1  
The multiplication I do in my head is memory. Also long multiplication requires iteration in the way that I did it. I'll go ahead and throw together a function for long multiplication –  Korvin Szanto Sep 26 '11 at 22:45
1  
@Korvin, the book I recommended will serve you well if this is your interest. I also recommend "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman. It deals with these questions in depth. –  Jonathan Henson Sep 26 '11 at 23:14
    
Several early computers supported only addition and subtraction. Some only supported subtraction! So the operation x = y * z was implemented as do( z times) {x + y} similarly division x = y / z was implemented as while (y > z) {x + 1; y = y - z} –  James Anderson Sep 27 '11 at 6:17
    
@James: did they support shift? I would expect multiplication was done via shift and add, while division was shift, compare, subtract. –  kevin cline Nov 28 '11 at 4:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.