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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.