0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ As a rule, the product of many integers can not fit in a register, $O(1)$ products are out of question. $\endgroup$
    – user16034
    Nov 15, 2022 at 12:55
  • $\begingroup$ Okay. I am right on the term $m \cdot M( m \cdot \max(\log n_i))$ though ? I have seen other posts where the complexity would be $m\cdot M(\max(\log n_i))$ instead; and it changes a lot of things. $\endgroup$ Nov 15, 2022 at 13:04
  • $\begingroup$ Are the products performed sequentially or in pairs ? $\endgroup$
    – user16034
    Nov 15, 2022 at 13:09
  • $\begingroup$ In my implementation, I use a foor loop, so I would guess sequentially. But I'm open to any suggestion that might speed up / achieve better complexity. I added the pseudocode in the body of the question, just in case. $\endgroup$ Nov 15, 2022 at 13:13
  • $\begingroup$ I guess that in pairs is more efficient. $\endgroup$
    – user16034
    Nov 15, 2022 at 13:16

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for the very clear perspective on this question. Actually, le me detail a little bit so that you can hopefully tell me if the RAM model might apply. I am actually multiplying prime numbers; the largest prime number I have is $< k (\log k + \log\log k)$, so it have $\log [ k (\log k +\log\log k)]$ bits at most. $k$ is related to the size $n$ of my input in $k=O(\sqrt{n})$. So I believe that for the size of primes to be tremendous, it implies that $n$ itself is unrealistically big. My problem is that the number $m$ of primes I multiply can be, this time, in order of $n$. $\endgroup$ Nov 18, 2022 at 9:23
  • $\begingroup$ So, if the complexity for computing the product of $m$ primes with at most $s$ bits is $O(m \cdot M(ms))$ as I computed in my question, then I cannot expect that $ms$ is small enough for me to use the RAM model. In the other case, if multiplying two $s$ bits numbers can be assumed $O(1)$ -- by virtue of $s$ being comparatively small to the size of my input $n$ (I checked, for $s>64$ I need $n>10^{51}$) -- then my loop would be $O(m)$. I must precise that experimentally, the size of the primes does not seem to have any impact whatsoever on the overall complexity (which seems linear in $n$). $\endgroup$ Nov 18, 2022 at 9:27
  • $\begingroup$ @FlorianIngels, Models are intended as a tool to let you predict the behavior of real computers, or to prove theorems in some rigorous setting. For the former goal, all models are wrong; some are useful. I remain skeptical that the RAM model is the appropriate model to use for your situation, because the essence of your problem involves working with integers that are too large to fit in one machine word, but you can be the ultimate arbiter of that. I hope I have given you enough information to make an informed decision and choose what you find useful. $\endgroup$
    – D.W.
    Nov 18, 2022 at 9:53
  • $\begingroup$ Thank you for your time, I will accept your answer ! $\endgroup$ Nov 18, 2022 at 11:00

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.