How to calculate only the n-th digit of a given multiplication?

Question

In a regular binary multiplication between two numbers, lets say 452*945 which equals to 427,140, Is there a way to get the 4th digit(which is 7) without calculating the whole thing? would it be faster then solving it in the traditional way to get the n-th digit?

(Just in case: Binary as of binary-operator, not the base...)

Answer 1

Assuming the numbers are given in decimal representation, you actually got sequences $a_i,b_i\in\{0,1,2,3,4,5,6,7,8,9\}\;$ of digites, interpreted as the numbers

$$a=\sum_{i=0}^n a_i10^i, \qquad b=\sum_{j=0}^m b_i10^i$$

respectively. When multiplying you will have to pair up all those terms in the following way:

$$ab=\sum_{i=0}^n\sum_{j=0}^m a_ib_j10^{i+j}.$$

When you are looking for the $4$-th digit of $ab$, you just have to include those pairs that have a chance to eventually influence the coefficient $10^3$ of the result. These are the pairs $a_ib_j$ with $i+j\leq 3$. Independent of the length of the input numbers, these are at most $10$ pairs. The reason why you can drop all pairs with $i+j\geq 4$ is because they all are multiples of $10^4$, hence have four trailing zeros and do not influence the $4$-th digit of the result.

Side note: This will be of no big use when dealing with the usual computer integers as used in programming. Extracting the digits from the numbers might be more expensive than the full but hardware supported multiplication.

---

Example

Applying this to your example above, we have

\begin{align} 452 &= 4\cdot 10^2+ 5\cdot 10^1+ 2\cdot 10^0,\\ 945 &= 9\cdot 10^2+ 4\cdot 10^1+ 5\cdot 10^0. \end{align}

We compute the relevant fragment

\begin{align} 10^0\cdot 2\cdot 5 &+ 10^1\cdot(2\cdot4+5\cdot5) \\ &+ 10^2\cdot(2\cdot 9+ 5\cdot4 + 4\cdot 5) \\ &+ 10^3\cdot(5\cdot 9+4\cdot4) \\ &=67140 \end{align}

whichs fourth digit is indeed $7$ and it only performed seven of all eight possible multiplications. Of course the gain is small in this case, but significant in the case of two at least four digit factors.

Answer 2

Kinda. If you want to find the first digit, you just multiply the two first digits together -> 2 * 5 = 10 -> 0. If you want the second digit, you multiply the first two digits together. 52*45 = 2340 -> 40. This also gives the first digit. Unfortunately this does not simplify the problem you have given, but if you were asked for 2345987*1932587 you could find the fourth digit of 5987*2587 to be 8.

Answer 3

There is, but it's not pretty. You have to realize that you are working mod 10. The last digit of a product is, as said above the last digit of their product mod 10. The second last digit, will be the sum of the products of the last digits with the second last of the other number plus the carry ( if it exists, it will be the product of the last digits divided by 10 ( plus any carry in the addition) mod 10). So you can it's just cumbersome. This if basically what we do when we do long multiplication, we find the products of the individual digits with the other number, and add them together.