QUESTION
I've been wondering if it's possible to solve two multiplication equations at the same time by only being able to multiply once? It's a very odd question but it's for an algorithm that I'm working on to improve it's time complexity.
THE PROBLEM
2 * 4 = 8
3 * 5 = 15
For example I am multiplying two times to get two separate answers 8 and 15 but what I'm trying to do is multiply ONCE and get the answer for both 2 * 4 and 3 * 5. Though I want the method to work with any number that I'm trying to solve. So long as the solution doesn't require Σ (no extra looping on the equation). What I ideally want is that you can only multiply ONCE and you can add/subtract/divide/mod/etc… beforehand or afterwards.
WHAT I'VE TRIED
I've tried many things that haven't worked. One was reliable method I did was getting the median by manipulating the 4 numbers that I'm going to multiply. Though the median value has the be in between the two solution so I can subtract and add from the median so I can the the answer to both equations. Besides that I've tried other small things that didn't go anywhere because it gave me mixed results with other values.
Hopefully this gives enough context. I'd appreciate the help very much! Thank You!
Best Answer
Expanding on Hagen von Eitzen's hint: $(ax+c)(bx+d)=abx^2+(ad+bc)x+cd$, so if you take $x$ larger than $ad+bc$ (e.g. by ensuring that $x$ has more than twice as many digits as any of the inputs), then $ab$ and $cd$ are the first and last digits of the base-$x$ representation of $(ax+c)(bx+d)$. You could implement this with bit shifting, taking $x$ to be a sufficiently large power of $2$.
This approach won't improve the asymptotic time complexity of a conventional algorithm, though, because multiplying arbitrarily large integers takes $\Omega(n)$ time in the output length and we're throwing away the inner digits of the result. It's also unlikely to be a worthwhile optimization in practice. If all you want is two multiplications, just do them separately.