5 ms·

The part I don't follow is that I thought multiplication used the same number of CPU cycles as addition, so I didn't get the the part where one multiplication r

The part I don't follow is that I thought multiplication used the same number of CPU cycles as addition, so I didn't get the the part where one multiplication replaced with many additions was obviously better. Could someone explain that part? I feel I must be fundamentally misunderstanding something.

saeta 5y ago
While that's true for fixed-precision integer arithmetic, this doesn't hold true for floating point multiplication.
Ductapemaster 5y ago
The multipliers in CPUs are a mass of logic gates and are challenging to make work in a single cycle. While I believe it is possible with integer multiplication to do so, doing so with other larger data types might take multiple cycles. Division is even more complex, although not part of the question here. Additions really can be done in 1 cycle, so it's possible to optimize by using them instead of multiplications in operations like this. Here's a Berkeley EECS lecture on multiplier circuits if you want more info: https://inst.eecs.berkeley.edu/~eecs151/sp18/files/Lecture21.pdf https://inst.eecs.berkeley.edu/~eecs151/sp18/files/Lecture21...
matbatt38 5y ago
> multiplication used the same number of CPU cycles as addition Only thanks to lookup table and parallelism. And that's not even true for old computers, where multiplications can take multiple cycles. Also I think complexity is calculated with a pen and paper approach in mind. Number of CPU cycles might vary a from actual complexity when the chips are optimised for certain tasks
reportingsjr 5y ago
If you look at operations per cycle, in this example for Intel Haswell processors, you'll find that an equivalent add and multiple are quite a bit different. An add/subtract from a 32 bit register to register is 0.25 cycles per operation. A multiply from 32 bit register to register is 2 cycles per operation. So a 8x speed difference, not counting for latency, etc. See page 230 and 231 of this paper: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
- gnufx 5y ago
  For what it's worth, what counts for normal implementations is the number of multiply-add operations per cycle, typically two on current hardware with FMA.
teawrecks 5y ago
It has nothing to do with clock cycles, it's about how the number of additions and multiplications scale for large matrices.
gameswithgo 5y ago
This isn’t about running stuff on hardware. The point is that for a large matrix the number of additions grows much more slowly, such that the represent an increasingly small percentage of operations. So they don’t matter much no matter the hardware at some sufficiently large matrix
Ar-Curunir 5y ago
From a complexity perspective, addition is linear time, whereas multiplication is superlinear (nlogn at best)
davidgrenier 5y ago
I feel the other answers you got do not directly answer your question for the following reason. In practice, I believe it is Strassen's algorithm that is used for very large matrix multiplication. Strassen's algorithm improves on both the number of multiplications of scalars as well as addition of scalars which both ends up bound by O(n^(lg 7)). This is because Strassen's algorithm replaces a single large conventional matrix multiplication consisting of n^3 multiplications and n^3-n^2 additions with 7 recursive application of Strassen's multiplication on matrices of size n/2 along with 15 addition of matrices of size n/2. The number of additions in a matrix addition is n^2 for a matrix of size n. Thus Strassen's requires 7 recursive calls as well as 15(n/2)^2 additions of scalars. You win on both fronts if the matrices are sufficiently large and you default to conventional matrix multiplication on a recursive call below a certain threshold.

saeta 5y ago

While that's true for fixed-precision integer arithmetic, this doesn't hold true for floating point multiplication.

Ductapemaster 5y ago

The multipliers in CPUs are a mass of logic gates and are challenging to make work in a single cycle. While I believe it is possible with integer multiplication to do so, doing so with other larger data types might take multiple cycles. Division is even more complex, although not part of the question here. Additions really can be done in 1 cycle, so it's possible to optimize by using them instead of multiplications in operations like this. Here's a Berkeley EECS lecture on multiplier circuits if you want more info: https://inst.eecs.berkeley.edu/~eecs151/sp18/files/Lecture21.pdf https://inst.eecs.berkeley.edu/~eecs151/sp18/files/Lecture21...

matbatt38 5y ago

> multiplication used the same number of CPU cycles as addition Only thanks to lookup table and parallelism. And that's not even true for old computers, where multiplications can take multiple cycles. Also I think complexity is calculated with a pen and paper approach in mind. Number of CPU cycles might vary a from actual complexity when the chips are optimised for certain tasks

reportingsjr 5y ago

If you look at operations per cycle, in this example for Intel Haswell processors, you'll find that an equivalent add and multiple are quite a bit different. An add/subtract from a 32 bit register to register is 0.25 cycles per operation. A multiply from 32 bit register to register is 2 cycles per operation. So a 8x speed difference, not counting for latency, etc. See page 230 and 231 of this paper: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf

gnufx 5y ago
For what it's worth, what counts for normal implementations is the number of multiply-add operations per cycle, typically two on current hardware with FMA.

teawrecks 5y ago

It has nothing to do with clock cycles, it's about how the number of additions and multiplications scale for large matrices.

gameswithgo 5y ago

This isn’t about running stuff on hardware. The point is that for a large matrix the number of additions grows much more slowly, such that the represent an increasingly small percentage of operations. So they don’t matter much no matter the hardware at some sufficiently large matrix

Ar-Curunir 5y ago

From a complexity perspective, addition is linear time, whereas multiplication is superlinear (nlogn at best)

davidgrenier 5y ago

I feel the other answers you got do not directly answer your question for the following reason. In practice, I believe it is Strassen's algorithm that is used for very large matrix multiplication. Strassen's algorithm improves on both the number of multiplications of scalars as well as addition of scalars which both ends up bound by O(n^(lg 7)). This is because Strassen's algorithm replaces a single large conventional matrix multiplication consisting of n^3 multiplications and n^3-n^2 additions with 7 recursive application of Strassen's multiplication on matrices of size n/2 along with 15 addition of matrices of size n/2. The number of additions in a matrix addition is n^2 for a matrix of size n. Thus Strassen's requires 7 recursive calls as well as 15(n/2)^2 additions of scalars. You win on both fronts if the matrices are sufficiently large and you default to conventional matrix multiplication on a recursive call below a certain threshold.