<p>That looks correct to me (assuming you take advantage of the fact that you don't have to do a full multiplication from scratch each time, but keep track of the results of the last multiplication and adjust it appropriately).</p>
<p>Or, approximately equivalently, if you want to compute <span class="math-container">$x_1/y,\dots,x_N/y$</span> where <span class="math-container">$x_1,\dots,x_N$</span> are similar and (wlog) <span class="math-container">$x_1&lt;\cdots&lt;x_N$</span>, then one simple approach is to compute <span class="math-container">$q = \lceil x_1/y \rceil$</span>, then compute <span class="math-container">$(x_i-qy)/y$</span> for each <span class="math-container">$i=2,\dots,N$</span>.</p>

CC BY-SA 4.0
2022-09-14T07:59:14.233Z
Oh! This is an even simpler optimization that I had not thought about. Thanks!
J.y B.y
CC BY-SA 4.0
2022-09-13T05:42:52.240Z
2022-09-13T05:42:52.240Z
D.W.
<p>What is the complexity of performing  <span class="math-container">$N$</span> divisions with &quot;close&quot; results and does it have  applications in practice?</p>
<p>It seems that some algorithms to divide a number <span class="math-container">$x$</span> by a number <span class="math-container">$y$</span> boil down to a binary search performing a multiplication at each state:</p>
<ul>
<li><a href="https://twitter.com/BooleanAnalysis/status/1569285838868996097" rel="nofollow noreferrer">Ryen O'Donnel mentioned it in a tweet recently</a>,</li>
<li><a href="https://cs.stackexchange.com/questions/67827/complexity-of-integer-division">this CS-SE answer mentions it</a>, pointing to this</li>
<li><a href="https://en.wikipedia.org/wiki/Division_algorithm" rel="nofollow noreferrer">wikipedia page</a>, and</li>
<li>here is the <a href="https://www.techiedelight.com/division-two-numbers-using-binary-search-algorithm/" rel="nofollow noreferrer">code in C, Java and Python</a>.</li>
</ul>
<p>I guess it means that, given a sequence of <span class="math-container">$N$</span> divisions with &quot;similar&quot; results (e.g. dividing <span class="math-container">$N$</span> &quot;similar&quot; numbers <span class="math-container">$(x_1,\ldots,x_N)$</span> by the same number <span class="math-container">$y$</span>) could be computed much faster than <span class="math-container">$N$</span> times the time required for each division separately, using  an algorithm such as  <a href="https://en.wikipedia.org/wiki/Exponential_search" rel="nofollow noreferrer">Exponential Search</a> instead of binary search, taking as a starting point the result of the previous division? That would result in divisions which cost at most twice as much as classical divisions, and in the best case much less, depending on how close the results of consecutive divisions are.</p>
<ul>
<li>Is it a known result?</li>
<li>Are there practical applications where one has to divide many numbers in sequence, and the results of consecutive divisions are varying very little?</li>
</ul>
<p>Or did I miss something?</p>

<range-searching>
Complexity and Applications of performing $N$ divisions with "similar" results?
J.y B.y
# Complexity and Applications of performing $N$ divisions with "similar" results?

(Asked by: username_0 on 2022-09-12)

What is the complexity of performing $N$ divisions with "close" results and does it have applications in practice?

It seems that some algorithms to divide a number $x$ by a number $y$ boil down to a binary search performing a multiplication at each state:

* [Ryen O'Donnel mentioned it in a tweet recently](https://twitter.com/BooleanAnalysis/status/1569285838868996097),
* [this CS-SE answer mentions it](https://cs.stackexchange.com/questions/67827/complexity-of-integer-division), pointing to this
* [wikipedia page](https://en.wikipedia.org/wiki/Division_algorithm), and
* here is the [code in C, Java and Python](https://www.techiedelight.com/division-two-numbers-using-binary-search-algorithm/).

I guess it means that, given a sequence of $N$ divisions with "similar" results (e.g. dividing $N$ "similar" numbers $(x\_1,\ldots,x\_N)$ by the same number $y$) could be computed much faster than $N$ times the time required for each division separately, using an algorithm such as [Exponential Search](https://en.wikipedia.org/wiki/Exponential_search) instead of binary search, taking as a starting point the result of the previous division? That would result in divisions which cost at most twice as much as classical divisions, and in the best case much less, depending on how close the results of consecutive divisions are.

* Is it a known result?
* Are there practical applications where one has to divide many numbers in sequence, and the results of consecutive divisions are varying very little?

Or did I miss something?

**Tags:** range-searching

---

## 1 answers

### Answer by username_1 on 2022-09-13. Score: 2

That looks correct to me (assuming you take advantage of the fact that you don't have to do a full multiplication from scratch each time, but keep track of the results of the last multiplication and adjust it appropriately).

Or, approximately equivalently, if you want to compute $x\_1/y,\dots,x\_N/y$ where $x\_1,\dots,x\_N$ are similar and (wlog) $x\_1<\cdots, then one simple approach is to compute $q = \lceil x\_1/y \rceil$, then compute $(x\_i-qy)/y$ for each $i=2,\dots,N$.

> **Comments:**
> **username_0**: Oh! This is an even simpler optimization that I had not thought about. Thanks!  

---

