Complexity of multiplication when computing product of $m$ integers

Question

I designed an algorithm where, at some point, I need to compute the product of a list of integers $n_1,\dots,n_m$ (possibly, there are repetitions in the list). The integers themselves do not depend on $m$ but can be, somehow, arbitrarily large.

EDIT: right now, I'm using a naive for loop:

prod=1
for n_i in list:
    prod *= n_i

When analyzing this part of the algorithm, I wondered whether I should - or not - consider the multiplication $O(1)$ - i.e. computing the product would only be $O(m)$.

I still looked at what could happen if I considered non-constant multiplication, and noted $M(n)$ the complexity of multiplying two $n$ bit numbers, the complexity would be something like that:

$$\sum_{i=1}^m M\left(\sum_{j=1}^i \log_2 n_i\right)$$

Since multiplying two $n$-bits number leads to a $2n$-bits number. With roughs bounds, I can estimate the complexity as $m \cdot M\left( m\cdot \max_{i=1}^m(\log_2 n_i)\right)$ - as stated in the comment to this question. The bound is tight if I take $m$ copies of the same integer.

I understood that as soon as $n<k$, with a $k$-bit machine, one can consider $M(n)=O(1)$. Does this mean that as soon as $m\cdot \max_{i=1}^m(\log_2 n_i) < k$, I can consider the multiplication $O(1)$ ? I surely must have missed something, because it doesn't feel right: with $m=k$ (say, $32$ or $64$), even with $1$-bits integers, I would exceed $k$.

Any help to better understand this problem is welcome; and since this is for academic purpose, I would be happy to receive some literature recommandation.

Answer 1

There are two standard ways to compute running time. Both are valid. Each conveys slightly different information, and which one is more useful may depend on the circumstance.

One approach is to compute the running time in terms of the number of bit-operations. For instance, it takes $O(B^2)$ bit operations to multiply two $B$-bit numbers using the classical multiplication algorithm. This is most helpful when computing the size of circuits needed.

A slight variant of this is to compute the running time in terms of the number of word-operations. In other words, we assume that operation can operate on fixed-size (say, 32-bit) words. For instance, you can add or multiply two 32-bit words in a single step. In this model, it takes $O(B^2)$ word operations to multiply two $B$-bit numbers using the classical multiplication algorithm. The constant factor is about $32^2$ lower than if you count the number of bit operations, but this is a constant and hence does not affect the asymptotic analysis. Consequently, if you ignore constant factors, this will often give you the same asymptotic result as counting bit-operations. If you care about real machines and constant factors, this model is probably most appropriate. This model is also sometimes known as the word RAM model.

Closely related is the transdichotomous model, which basically counts the number of word operations, but additionally assumes that the word size is "large enough" to be able to store pointers and indices to the entire input. In particular, if the input length is $L$, then the transdichotomous model lets you assume that the word size is at least $\lg L$. For practical purposes, you can basically ignore this issue and just count the number of word operations. From a pedantic/nitpicky theoretical perspective, the transdichotomous model corrects a problem with the word RAM model, but you probably can safely ignore that.

Finally, there is the RAM model, which assumes that you can do any single operation on two values in a single step. For instance, you can add or multiply two arbitrarily-large integers in a single step. This model is not a good model of reality, because in reality if you have very large integers, there is no way to add or multiply them in a single step. But it has the advantage of being simple, and if all numbers that you operate with are small, then its issues probably don't matter. For your problem, you are dealing with large numbers, so the word RAM is not a good model of real computers.

I hope this answers your question about whether to consider the multiplication as taking $O(1)$ or $M(n)$ time.

TL;DR: no, you can't consider multiply to take $O(1)$ time, as that isn't how things will work in a real computer, if you have to deal with large numbers.