3 ms·

Well, I will take your word for it - the wiki article is only talking about additions and multiplications and only counting them, even though it mentions that i

Well, I will take your word for it - the wiki article is only talking about additions and multiplications and only counting them, even though it mentions that it uses up to four times more memory I don't see where it's been accounted for. >Only for small problem sizes. As the problem size increases This is the difference between software engineering and computer science. The real problems do not grow in size quite often. If I am writing a 3D engine I do not expect my matrices suddenly grow. Ditto if I am solving some linear system derived from a real model - it's unlikely that the model properties are going to change any time soon.

betterunix 13y ago
The memory access cost is part of the cost of arithmetic -- the operands and results need to be read from and written to memory. It is not explicitly counted because the precise sequence of events is very architecture-specific (in a register machine, there will be load/store operations; in a three-address architecture, memory is explicitly accessed by each opcode; in a stack machine, operands need to be pushed onto the stack; etc.), but in any RAM machine the cost of memory access is constant (i.e., it is upper bounded by a constant -- it may be faster if you already have the data in a register or a cache, but the worst case does not depend on the input size or algorithm being run). As for problem sizes not growing, I think your view is a bit limited. For example, matrices in a financial model might become larger if any number of parameters change -- the time period, the number of instruments, etc. Sure, there are cases where you can guarantee that the problem size will not change -- but one of the big advantages of software is that it can scale arbitrarily (unlike a matrix multiplier circuit).
- pandaman 13y ago
  Some problem sizes grow, some don't. Sorry, if you think that asserting that both exist somehow limited my view.

betterunix 13y ago

The memory access cost is part of the cost of arithmetic -- the operands and results need to be read from and written to memory. It is not explicitly counted because the precise sequence of events is very architecture-specific (in a register machine, there will be load/store operations; in a three-address architecture, memory is explicitly accessed by each opcode; in a stack machine, operands need to be pushed onto the stack; etc.), but in any RAM machine the cost of memory access is constant (i.e., it is upper bounded by a constant -- it may be faster if you already have the data in a register or a cache, but the worst case does not depend on the input size or algorithm being run). As for problem sizes not growing, I think your view is a bit limited. For example, matrices in a financial model might become larger if any number of parameters change -- the time period, the number of instruments, etc. Sure, there are cases where you can guarantee that the problem size will not change -- but one of the big advantages of software is that it can scale arbitrarily (unlike a matrix multiplier circuit).

pandaman 13y ago
Some problem sizes grow, some don't. Sorry, if you think that asserting that both exist somehow limited my view.