# How quickly can we find an arbitrary digit in multiplication?

In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication.

We may first consider previous results. Finding the least significant digits is fairly obvious. I was intrigued by this question, on Math.SE, which has several answers that show a mathematical series solution to obtaining the most significant digit to a division, albeit one with little necessary information.

This brings up a few questions.

(1) How quickly can we find the most significant digit in a multiplication (between two $n$-bit integers)? (Just to clarify, I intended this to mean knowing the position of the digit itself.) Can we find other most significant digits in approximately the same time?

(2) How quickly can we find an arbitrary digit in multiplication?

(3) Is finding an arbitrary digit in multiplication as hard as multiplication itself?

• – Tsuyoshi Ito Sep 25 '12 at 0:49
• The most significant digit would be 1, wouldn't it? Or do you mean something like "the position of the most significant digit"? – Cem Say Sep 25 '12 at 15:22
• @CemSay: You're correct. I was really thinking in terms of most significant digits (plural). I also thought that we should be able to determine the position of this digit, or these digits. That's where the complication really seems to arrive. I'll edit the question accordingly. – Matt Groff Sep 25 '12 at 18:59
• Computing the multiplication of two given numbers is easily reducible to the computation of a given digit of the product. – Kaveh Sep 25 '12 at 22:30
• See New Results on the Complexity of the Middle Bit of Multiplication (view). The paper mentions that the middle bit is the hardest to extract. – Realz Slaw Nov 13 '12 at 22:30