Can any characterized property give a solid account of why multiplication is a harder computation operation than addition?

For humans, in general, it's far easier to do an addition than a multiplication. One might argue this is just an effect of the particular way brains are wired.

But from what I find, multiplication is also more expensive on computers, where one could certainly arrange chips in an arbitrary way, or at least without any pre-established biological constraint.

But from a group theory point of view, addition is not more fundamental than multiplication, is it?

Are there some characteristics, like associativity or commutativity that explain that difference in terms of computational complexity?

The answer might of course rely on other mathematical fields, like topology, or even be related to some physical constraints that hold for both brains and common CPUs but are not strictly constrainted by mathematical characteristics.

Related resources:

• Presburger arithmetic can be decided in doubly exponential time, while Skolem arithmetic is triply exponential in its decision problem. Commented Mar 6 at 22:30
• @BrevanEllefsen, Could you elaborate on that? This could be a useful complement to D.W.'s answer. Commented Mar 7 at 13:37
• As far as real numbers go, the multiplicative group $(\mathbb R^\times, \cdot)$ is isomorphic to $\{\pm 1\} \times (\mathbb R, +)$, which means that from an abstract viewpoint, multiplication is "harder" exactly by a factor of $\pm 1$. (That isomorphism, although not under this name, was exploited for centuries to facilitate computation, look up slide rules and logarithm tables.) As some answers state, the way we write numbers makes addition easier, so the conversion was mostly used to translate from multiplication to addition, then back. A different system might use it vice versa. Commented Mar 7 at 21:08
• @MikhailKatz Presburger arithmetic is the fragment of Peano arithmetic containing addition but not multiplication, while Skolem arithmetic is the fragment of Peano arithmetic containing multiplication but not addition. Both are decidable (which is curious since Peano arithmetic isn't... Apparently just induction+addition or induction+multiplication isn't enough), but the decision problems have different asymptotic complexity. Skolem arithmetic, i.e. "multiplication" (plus a bit more), has an exponentially harder decision problem than does Presburger arithmetic ("addition"). Commented Mar 8 at 0:06
• @BrevanEllefsen, do go ahead and post this as a separate answer. Commented Mar 10 at 10:50

It's not quite completely true that multiplication is harder than addition.

When we want to write numbers, we usually use a writing system that's based on addition: a notation like "$$125$$" means "$$100 + 20 + 5$$," and likewise, "$$81$$" means "$$80 + 1$$." If we want to add two numbers that are written using this system, then we're basically calculating a sum of two sums, which, thanks to associativity and commutativity, is pretty straightforward. Multiplication, on the other hand, means calculating a product of two sums, and that's more complex; it involves using the distributive property, which gets cumbersome for large numbers.

However, this writing system is not the only possible writing system! We could write our numbers as, for example, $$5 \cdot 5 \cdot 5$$ and $$3 \cdot 3 \cdot 3 \cdot 3$$. With this system, multiplication is very easy: you just combine the numbers, giving $$3 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 5$$. On the other hand, in this writing system, addition is extremely difficult.

So, in theory, whether addition or multiplication is harder depends on what number writing system you're using. In practice, the standard system is extremely overwhelmingly popular, so you'll usually find addition easier than multiplication.

• Your example is unfair in that the decomposition representation can't represent all integers so you're operating on a subset of numbers that happens to work nicely. There's probably deep insights from a information-theoretic perspective somewhere in here that I can't put my finer on. Commented Mar 6 at 19:18
• @PasserBy Well, every integer besides 0 can be written as a product of prime numbers and possibly -1, and then 0 can just be written as 0. That allows you to multiply any two integers easily. (Granted, you still need some way to assign a unique name to every prime number. I think that just using plain base 10 for that purpose will work just fine, and doesn't impair the point I'm making.) Commented Mar 6 at 20:00
• I thought you're restricting yourself to single digit factors. If you allow infinite "bases", it becomes even harder to say comparing the two systems is fair. Decimal requires you to compute operations until it's normalized to base 10. The decomposition system requires you to normalize to... factors? It's not clear why it should be prime factors, the notation works just as well with any factor. At that point, the simplicity of multiplication really is just delaying the computation by recording all operations in the string. Commented Mar 7 at 6:09
• @PasserBy You normalize to prime factors because there's a theorem stating that every integer has a unique prime factorization, just as there's a theorem stating every integer has a unique decimal representation. Both systems have a notion of "normalization". If using base-10 to represent the primes is a problem, use a finite sequence $(a_1,\ldots,a_n)$ of natural numbers to represent the number $p_1^{a_1}\ldots p_n^{a_n}$ and write this sequence as unary numerals separated by zeros: $5^3=00111_p,3^4=01111_p,3^4\cdot5^3=011110111_p.$ Multiplication is even easier and addition is still hard.
– HTNW
Commented Mar 7 at 16:07
• @Stef: Multiplication is as easy as adding lengths, as long as you express numbers multiplicatively, as described in this answer. I think of a multiplicative number as a row of stacks of blocks. Since I was raised with additive numbers, I might like to think of the stacks as representing the exponents in the decomposition $2^{n_1}\,3^{n_2}\,5^{n_3}\,7^{n_4}\,11^{n_5} \cdots$, but to someone who grew up with multiplicative numbers, the row of stacks is just what a number is. To multiply two numbers, you put one number's stacks on top of the other's. It's the same as adding lengths. Commented Mar 8 at 6:54

One way to view your question is through the lens of computational complexity: why does the computational complexity of addition appear to be less than the computational complexity of multiplication? In particular, why can two $$n$$-bit integers be added with $$\Theta(n)$$ time complexity, but multiplication appears to require more than $$\Theta(n)$$ time complexity, as far as we can currently tell?

As it turns out, we don't know whether multiplication is actually significantly harder, at least by this metric. We do not have any proof that multiplication cannot be done with $$\Theta(n)$$ time complexity. It is known that multiplication can be done in $$O(n \log n)$$ time complexity -- which is asymptotically not that much slower than addition. Moreover, there is no known proof that multiplication requires $$\Omega(n \log n)$$ time, or even a proof that it requires $$\omega(n)$$ time.

Where you can read more: https://cs.stackexchange.com/q/77703/755, https://cs.stackexchange.com/q/126725/755.

• One, perhaps overly simplistic, measure is that adding two numbers with $n$ bits can result in a number of at most $n+1$ bits. But multiplying can lead to numbers with $2n$ bits. That is more complex. Commented Mar 6 at 21:43

A Finite State Machine can compute addition, but it cannot compute multiplication. See Computation: Finite and Infinite Machines, by Marvin Minsky. (Section 2.3 example 4 for addition, and Theorem 2.6 for multiplication.)

– Community Bot
Commented Mar 8 at 21:10

Since you mentioned computers, computers work "natively" with integers as $$n$$-bit binary words, such as a 64-bit value for a 64-bit processor. While for an addition the result fits in $$n+1$$ bits (one word and one carry bit like a carry flag), multiplication results require $$2n$$ bits, or 2 words to store. Binary digit arithmetic is just what is easiest to implement in silicon, after engineers experimented with decimal-based digits (what we normally use), binary-coded decimal, even ternary. Old processors didn't have the transistors for a hardware multiplication, but nowadays we dedicate a large area of silicon to fast multiplication because it's so important.

If you work with factoring large numbers, such as in the quadratic sieve, it is worth storing a number $$x$$ as a vector $$[e_1, e_2, \cdots]$$ where $$x = 2^{e_1} 3^{e_2} \cdots p_k ^{e_k}$$ is the prime factorization handling primes up to $$p_k$$. The vector can be arbitrarily long for arbitrarily large $$x$$. Then multiplication of two numbers is simply elementwise addition of the lists, and in fact you can check if a number is square-free just by seeing if all the exponents are less than 2.

Another interesting representation is factorial base, where each digit starting from least significant has base $$0!, 1!, 2!, \dots$$ If you extend the system to use fractional bases like $$1/0!, 1/1!, 1/2!, \dots$$ you can represent certain constants that have nice Taylor series in a nice way, for example $$e = 0.0 1 1 1 \dots$$

Each digit (to whatever base is used) of one term interacts (i.e., multiplies) with all the digits of the other term. Therefore if there are $$m$$ digits in each, this requires $$m^2$$ interactions.

In addition, each digit only interacts with one digit of the other term.

• Actually, one can do much better than $m^2$, see Karazuba's algorithm and it's improvements. Commented Mar 6 at 5:19
• How about Harvey et van der Hoeven? O(n log n) Commented Mar 6 at 6:44
• Its not quite clear what you mean by "each digit interacts with only one digit". What about 7777773 and 222227?
– Mike
Commented Mar 8 at 21:44