Multiplication is an elementary binary operation, written \(ab\), \(a \times b\), \(a(b)\) or \(a \cdot b\) (pronounced "\(a\) times \(b\)"). For natural numbers, it is defined as repeated addition:
\[a \times b = \underbrace{a + a + \cdots + a + a}_b.\]
For example, \(3 \times 4 = 3 + 3 + 3 + 3 = 12\). The result of a multiplication problem is called the product.
For real numbers, the product \(x \times y\) is defined as the product of the equivalence classes of Cauchy sequences of rational numbers. For positive reals \(x\) and \(y\), it can be thought as a product of width and height of a rectangle.
Like addition, multiplication is commutative and associative on \(\mathbb{N}\) and \(\mathbb{R}\): \(a \times b = b \times a\) and \((a \times b) \times c = a \times (b \times c)\) for all natural and real values of \(a,b\) and \(c\). Repeated multiplication is called exponentiation.
However, multiplication is not commutative on ordinals. For any limit ordinal \(\alpha\), \(2 \times \alpha = \alpha \neq \alpha \times 2\).
It is possible to define multiplication for natural numbers in the recursive way:
\begin{eqnarray*} a \times 0 & = & 0 \\ a \times (b+1) & = & (a \times b) + a \end{eqnarray*}
In googology, it is the second hyper operator.
Other properties[]
- \(0 \times n = 0\)
- \(1 \times n = n\)
- \((-a) \times (-b) = a \times b\)
- \((-a) \times b = a \times (-b) = -(a \times b)\)
Turing machine code[]
Given input of form (string of a 1's) (string of b 1's) it outputs string of a*b 1's.
0 1 _ r 1 0 _ _ r 9 1 1 1 r 1 1 _ _ r 2 2 1 _ r 3 2 _ _ l 7 3 1 1 r 3 3 _ _ r 4 4 1 1 r 4 4 _ 1 l 5 5 1 1 l 5 5 _ _ l 6 6 1 1 l 6 6 _ 1 r 2 7 1 1 l 7 7 _ _ l 8 8 1 1 l 8 8 _ _ r 0 9 1 _ r 9 9 _ _ r halt
Time Complexity[]
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | 2 | 7 | 14 | 23 | 34 |
1 | 3 | 14 | 29 | 48 | 71 |
2 | 4 | 25 | 56 | 97 | 148 |
3 | 5 | 40 | 95 | 170 | 265 |
4 | 6 | 59 | 146 | 267 | 422 |
Using the table above, we can deduce the time complexity for this program is
\(T(a,b)=(b^{2}+1)a^{2} + (b+2)^{2}a + b + 2\)
or if we expand out, we will have \(T(a,b)=a^{2}b^{2} + a^{2} + ab^2 + 4ab + 4a + b + 2\)
For more general way of deduce the time complexity of a program written in Turing Machine, go to Turing Machine Online Simulator (Morphett version) and Lagrange Online Calculator
Space Complexity[]
Space Complexity for this program is unknown yet
Dependency of properties on arithmetics[]
When we work in ZFC set theory, properties of multiplication such as commutativity and associativity hold. However, in Robinson arithmetic, the commutativity does not necessarily hold. That is, the statement \(\forall a,b \in \mathbb{N} : a \times b = b \times a\) is independent of Robinson arithmetic.
See also[]
Bowers' extensions: expansion · multiexpansion · powerexpansion · expandotetration · explosion (multi/power/tetra) · detonation · pentonation
Saibian's extensions: hexonation · heptonation · octonation · ennonation · deconation
Tiaokhiao's extensions: megotion (multi/power/tetra) · megoexpansion (multi/power/tetra) · megoexplosion · megodetonation · gigotion (expand/explod/deto) · terotion · more...