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?

  • 4
  • $\begingroup$ The most significant digit would be 1, wouldn't it? Or do you mean something like "the position of the most significant digit"? $\endgroup$
    – Cem Say
    Sep 25, 2012 at 15:22
  • $\begingroup$ @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. $\endgroup$
    – Matt Groff
    Sep 25, 2012 at 18:59
  • $\begingroup$ Computing the multiplication of two given numbers is easily reducible to the computation of a given digit of the product. $\endgroup$
    – Kaveh
    Sep 25, 2012 at 22:30
  • $\begingroup$ 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. $\endgroup$
    – Realz Slaw
    Nov 13, 2012 at 22:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.