How quickly can we find an arbitrary digit in multiplication?

Question

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?

Related: Most significant bit of integer multiplication and binary decision diagrams, Complexity of exponential function. — Tsuyoshi Ito, Sep 25 '12 at 00: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
Also, the most significant bit is probably as hard as multiplication because of carrying. However you can approximate its position as $n+m$. However, if you define a "digit" as multiple bits, you can get a good idea of what the digit is. For example, A B * C D, you can multiply AC, and that should be the most significant digit, plus a carry. Which means that it can be AC + {0|1}, depending on the carry. — Realz Slaw, Nov 13 '12 at 22:31

How quickly can we find an arbitrary digit in multiplication?

0 Answers0