Does multiplying word size numbers take constant time?

Question

Does multiplying word size numbers (using standard grade school algorithm) take constant time? Can you use this to speed up computation and do the fast multiplication algorithms use this?

By constant time I mean under the word ram model or whatever model of computation is standard.

I mean in the purely theoretical model how is run-time defined In the word ram model if you fix word size then everything is constant so I'm assuming that you're always given a computer whose bit/word size is logarithmic in your input size please tell me if thats reasonable and if not what should be assumed instead.

Answer 1

For a fixed word size, multiplying word sized numbers takes a fixed maximum time.

If you were to compare implementations with n bit words for n = 8, 16, 32, 64, 128, 256 etc., the amount of time with a fast hardware implementation takes time proportional to log n, with hardware cost proportional to n^2 (that's using n^2 3/2 adders or 7/3 adders which may be just slightly faster). With current technology, having a chip with dozens of 64 bit multipliers is quite affordable.

Using the methods that you learnt at high school, the time for multiplying two n bit numbers is proportional to n^2, with hardware cost proportional to n.

Answer 2

In the word RAM model, data is stored in machine words, whose length is $\log n$; here $n$ is the length of the input, in bits. In this model, arithmetic operations on machine words have unit cost. These usually include addition, subtraction, multiplication, and division. Sometimes logical operations are also included: bitwise AND, OR, XOR.

In his paper How Fast Can We Multiply Large Integers on an Actual Computer, Fürer argues that the word RAM model (which he calls log-RAM) best reflects the performance of fast integer multiplication algorithms in practice. Indeed, for modern CPUs, arithmetic on machine words are atomic operations.