Skim to the conclusion is fine.
Let us not assume the schoolbook multiplication's time complexity is O(1), but O(ab). Where a is the first number's binary digit count and b is the second number's binary digit count. Put another way, the complexity of multiplication is the product of the binary digit count of each multiple. of course this could be faster than O(ab), it would accord to how many zeros in the binary format of the number.
for example. 2×1024(10×10000000000), some optimized CPU only did one bit multiplication and one addition. But we can forget that kind of special case since it depend on CPU architecture most of the time.
If one of the multiple is 0, the product is always 0. Every equation after this point is assuming there is only positive integers.
Many people does not know. that chain multiplication's time complexity have something to do with the order of the multiplication. For example.
5×7×3 is in theory, slower than 3×5×7
3×5 = 15, complexity= 2×3 = 6
15×7 = 105, complexity= 4×3 = 12
Total complexity = 6+12 = 18
For 5×7×3
5×7 = 35, complexity= 3×3 = 9
35×3 = 105, complexity= 6×2 = 12
Total complexity = 9+12 = 21
Now, it's easy to formulate some mathematical model.
Before that, we have to define a function that count the binary digit of a number.D(x)

We know that ab and ba have the same time complexity.(O(ab) = O(ba)), so there are only 3 orders to calculate abc:
(ab)c
(ac)b
(bc)a
The complexity formula for each one of them



Expand the formula by replace all D(x) with equals? No, let's try expand D(ab) in the form of D(a) + D(b) + c first.
Look this though and carefully.


ahh, so D(ab) can be either D(a)+D(b)-1 or D(a)+D(b). Assume that D(ab), D(ac) and D(bc) all follow the later equation.
D(a)×D(b)+(D(a)+D(b))×D(c)=D(a)×D(b)+D(a)×D(c)+D(b)×D(c)
D(a)×D(c)+(D(a)+D(c))×D(b)=D(a)×D(b)+D(a)×D(c)+D(b)×D(c)
D(b)×D(c)+(D(b)+D(c))×D(a)=D(a)×D(b)+D(a)×D(c)+D(b)×D(c)
Wow, then all 3 equations is completely the same! Let's call this equation MAX.
To calculates most efficiently, we have to find one or more D(xy) = D(x)+D(y)-1
Suppose all 3 equations can have D(ab) = D(a)+D(b)-1
we will get these 3 results
D(a)×D(b)+D(a)×D(c)+D(b)×D(c)-D(c)=MAX-D(c)
D(a)×D(b)+D(a)×D(c)+D(b)×D(c)-D(b)=MAX-D(b)
D(a)×D(b)+D(a)×D(c)+D(b)×D(c)-D(a)=MAX-D(a)
Above equations states it's better to have the largest number multiply in the end.
Conclusion:
3 numbers, a,b and c.
x and y and z are 3 variables does not equal to each other(unless there is equality among a, b and c) and it's domain are {a, b, c}.
If it's not possible to find a D(xy) = D(x)+D(y)-1. then the order of the multiplication does not have effect on the time complexity.
If it's it is possible to find a D(xy) = D(x)+D(y)-1. then when z is the largest while the previous relation still holds, then it reduce the most on the time complexity.
After Note:
The chain multiplication introduced here is only for 3 numbers, but it can be applied to larger chains by calling this recursively.
I have googled around and I can't find any article about this subject, most likely it's because the time complexity it saves are extremely low(D(n) is approximately log(n)) and to find the perfect order for the chain multiplication would cost a lot more than the multiplication itself.
If I made any error(likely.) please leave a comment so I can admire your skill publicly.
Recent comments
1 day 3 hours ago
1 day 12 hours ago
1 day 13 hours ago
1 day 22 hours ago
2 days 4 hours ago
2 days 14 hours ago
4 days 22 hours ago
5 days 19 hours ago
5 days 21 hours ago
5 days 23 hours ago