Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?

Question

I'm not nearly at the experience level in computer science to be able to properly determine the number of instructions involved in basic ALU calculations, and I'm interested in a certain software concept where the difference is important.

Multiplication

---

       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

I've been studying the binary multiplier, which seems to calculate partial products with binary, and then shifts them to the left, the very same way that we do with base-10 multiplication in grade school. It would seem to me that this would require 2 instructions per digit, but that's merely a barely-educated guess.

Addition

I've found Wiki's explanation of an adder-subtractor to be far more advanced, (in description, not operation, surely), and I've had less luck interpreting it thus far.

Purpose

My goal is to determine the number of instructions required to compute the addition / multiplication (respectively) of number sets. Basically, I want to figure:

5 x 5 = 10 --> 5 instructions //example
5,000,000,001 x 456892 --> 50 instructions //example

1 + 1 = 2 --> 4 instructions //example
1,000,042,569 + 1,491 = 1,000,044,060 --> 45 instructions //example

---

Tl;dr - My Question:

• Is it possible to accurately determine the number of instructions required to multiply or add two (whole number) integers in a modern processor?

• If so, how is this figured (in both addition and multiplication, based on the size of the number)?

Answer 1

Yes and no.

“Instructions” isn't the right unit of measure: most processors include an ALU and require a single instruction to perform addition or multiplication on a number of a certain size (usually 8, 16, 32 or 64 bits, often with several possible sizes). A more relevant measure is the number of clock cycles required by this instruction. Counting instructions only comes into play when talking about bignums.

The number of clock cycles is determined by the depth of the circuit. A signal can traverse many gates in the same clock cycle, but more gates means a longer path which can be a limiting factor when trying to increase the clock frequency. It doesn't depend on the input values, only on the circuit that is being used (of course the values have to fit within the width of the circuit). For example a 32-bit adder will take the same number of cycles to calculate 1 + 1 and 1,000,042,569 + 1,491.

There are many possible designs for an adder or multiplier circuit. One of the design parameters is using more transistors or more complex connections to achieve faster operations. For example, addition the way we usually perform it requires adding the lowest-order bits, then adding their carry to the bits of order 1, and so on: the carry is propagated linearly, which means that the depth of the circuit is proportional to the word size. There are more sophisticated adders which parallelize the additions to reduce the depth.

The depth of the circuit tells you how many clock cycles the arithmetic operation requires inside the ALU. On a typical complex processor, going from there to the time it takes to perform instructions can be very complex, because you need to consider how the ALU fits in the processor. In order to actually add two values, the CPU must do many things:

• Fetch the addition instruction from memory.
• Decode the instruction to find that it is an addition, where its inputs are and where its output is.
• Fetch the inputs — this can take different number of cycles depending on the width of the operation and whether the inputs are immediates, in registers, in memory, etc.
• Make the arithmetic calculation.
• Write the result into the output register or memory.

Most processors are very heavily pipelined: all of these steps are performed in parallel for different instructions. For example, at any given clock cycle, there are typically instructions in various stages of being fetched and decoded, different arithmetic operations in various stages of being carried out, etc. Advanced processors often have multiple ALUs so as to be able to make computations in parallel. For these reasons, the time it takes to perform $N$ successive additions is often not $N$ times the time it takes to perform one addition. Though in practice, the biggest variability comes from memory access — accessing an inner cache is dramatically faster than accessing RAM.

Answer 2

Yes, one (most of the time).

But that is useless, depending on the instructions before/after this one, the sequence of instructions will take wildly varying times on modern CPUs that execute instructions in paralell, execute them out of order, and do other funky rearrangements. Add to that that on modern CPUs an access to RAM can cost the same as hundreds of instructions, so previous memory accesses will be crucial (cache effects).

Answer 3

Multiplication is one instruction, in most instruction sets, for 64 or 32 bit integers. You can find reference manuals for various instruction sets by Googling -- look for "MIPS" for a relatively easy-to-understand version.

If you want to multiply integers of arbitrary size (>64 bits), it gets more complicated. Good algorithms exist.