1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ By grade school algorithm I mean divide the an n bit number into n/logn words of size logn since word size is at least log of input size using the "grade school" algorithm where each word multiplies with each word of the other bit. This algorithm takes (n/logn)^2 time. Likewise for Karatsuba Multiplication you don't need O( n^(log_2(3)) ) you can get away with O( (n/logn)^(log_2(3)) ) idk how the more complicated stuff works but does this get used? $\endgroup$
    – Hao S
    Commented Jan 23, 2022 at 3:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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