<p>In considering an answer to <a href="https://cstheory.stackexchange.com/questions/12671/is-there-a-proof-that-addition-is-faster-than-multiplication">this question</a>, I once again wondered how quickly we could find a digit in multiplication.</p>

<p>We may first consider previous results.  Finding the least significant digits is fairly obvious.  I was intrigued by <a href="https://math.stackexchange.com/q/59562/2626">this question</a>, 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.</p>

<hr>

<p>This brings up a few questions.</p>

<p>(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?</p>

<p>(2)  How quickly can we find an arbitrary digit in multiplication?</p>

<p>(3) Is finding an arbitrary digit in multiplication as hard as multiplication itself?</p>

CC BY-SA 3.0
2012-09-25T00:49:42.003Z
Related: [Most significant bit of integer multiplication and binary decision diagrams](http://cstheory.stackexchange.com/questions/3462), [Complexity of exponential function](http://cstheory.stackexchange.com/questions/1811).
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-25T15:22:47.757Z
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
CC BY-SA 3.0
2012-09-25T18:59:37.203Z
@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
CC BY-SA 3.0
2012-09-25T22:30:43.230Z
Computing the multiplication of two given numbers is easily reducible to the computation of a given digit of the product.
Kaveh
CC BY-SA 3.0
2012-11-13T22:30:20.790Z
See [New Results on the Complexity of the Middle
Bit of Multiplication](http://dl.acm.org/citation.cfm?id=1340407) ([view](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.124.2817%26rep%3Drep1%26type%3Dpdf&ei=_MiiUKu5LpS70AGuoYCgBg&usg=AFQjCNF6ch6XT4nRzfZu17hM_voW0vzsIA&sig2=xcw3qq3PNhaMhe81kD2neA)). The paper mentions that the middle bit is the hardest to extract.
Realz Slaw
CC BY-SA 3.0
2012-11-13T22:31:50.023Z
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 A*C, and that should be the most significant digit, plus a carry. Which means that it can be A*C + {0|1}, depending on the carry.
Realz Slaw
<ds.algorithms><time-complexity>
How quickly can we find an arbitrary digit in multiplication?
Matt Groff
# How quickly can we find an arbitrary digit in multiplication?

(Asked by: username_0 on 2012-09-25)

In considering an answer to [this question](https://cstheory.stackexchange.com/questions/12671/is-there-a-proof-that-addition-is-faster-than-multiplication), 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](https://math.stackexchange.com/q/59562/2626), 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?

**Tags:** ds.algorithms, time-complexity

> **Comments:**
> **username_1**: Related: [Most significant bit of integer multiplication and binary decision diagrams](http://cstheory.stackexchange.com/questions/3462), [Complexity of exponential function](http://cstheory.stackexchange.com/questions/1811).  
> **username_2**: The most significant digit would be 1, wouldn't it? Or do you mean something like "the position of the most significant digit"?  
> **username_0**: @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.  
> **username_3**: Computing the multiplication of two given numbers is easily reducible to the computation of a given digit of the product.  
> **username_4**: See [New Results on the Complexity of the Middle Bit of Multiplication](http://dl.acm.org/citation.cfm?id=1340407) ([view](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.124.2817%26rep%3Drep1%26type%3Dpdf&ei=_MiiUKu5LpS70AGuoYCgBg&usg=AFQjCNF6ch6XT4nRzfZu17hM_voW0vzsIA&sig2=xcw3qq3PNhaMhe81kD2neA)). The paper mentions that the middle bit is the hardest to extract.  
> **username_4**: 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 A*C, and that should be the most significant digit, plus a carry. Which means that it can be A*C + {0|1}, depending on the carry.  

---

## 0 answers

