2
$\begingroup$

Can $\left\lfloor{\dfrac{x}{2p+1}} \right\rfloor$ be expressed in terms of $\left\lfloor{\dfrac{x}{p}} \right\rfloor$ for prime $p$?

How to divide by $2p+1$ by only using division by $p$?

EDIT: The above formulation is wrong. I meant "expressed in terms" in a sense broader that "a function that takes $\left\lfloor{\dfrac{x}{p}} \right\rfloor$ as an argument.

Different version: let $0\leq a,b < 2p+1$ ($a,b$ known integers) and $x=ab$. How to divide $x$ by $2p+1$ in a way cheaper than just dividing by $2p+1$? Dividing by $p$ is cheaper than dividing by $2p+1$. It doesn't have to be a formula, algorithm is also ok.

  • 0
    $x$ is an integer and x<(2p+1)^2.2012-06-20

3 Answers 3

2

$ \frac{x}{2p+1} = \frac{x}{2p} \frac{1}{1+1/(2p)} = \sum_{j=0}^\infty (-1)^j \frac{x}{(2p)^{j+1}}$ For $\left\lfloor \dfrac{x}{2p+1} \right\rfloor$, you can stop the series if you come to a point where further terms can't make a difference (which should happen unless $x$ is an integer multiple of $2p+1$). Thus if $S_N = \sum_{j=0}^N (-1)^j \dfrac{x}{(2p)^{j+1}}$ $\left\lfloor \dfrac{x}{2p+1} \right\rfloor = \left\lfloor S_N \right\rfloor$ if $N$ is even and $x/(2p)^{N+2} < S_N - \lfloor S_N \rfloor$ or $N$ is odd and $x/(2p)^{N+2} < \lceil S_N \rceil - S_N$.

  • 0
    This is just the old trick of reducing division by $11$ to division by $10$ - see my answer.2012-06-20
1

I don't think it can, in general. By the time you get $\lfloor{x\over p}\rfloor$, information has already been lost that was required in order to know $\left\lfloor{x\over 2p+1}\right\rfloor$.

Say for example that you had $p=2$. You need an expression for $\left\lfloor{x\over 2p+1}\right\rfloor = \left\lfloor{x\over 5}\right\rfloor$ that yields 0 when $x=4$ and 1 when $x=5$. But no function of $\left\lfloor{x\over 2}\right\rfloor$ can do this, because $\left\lfloor{x\over 2}\right\rfloor = 2$ for both $x=4$ and $x=5$.

  • 1
    @MarkDominus I think asmith is looking for something along the lines of the well-known division by 3 algorithm using bitshifting. Here's a reference that goes into some detail into the $p=2$ case: http://www.hackersdelight.org/divcMore.pdf2012-06-20
0

Hint $\ $ Reverse engineer this old trick that reduces dividing by $11$ to dividing by $10$.

$\ \ \begin{eqnarray}13717.4\, -\, 1371.74\, &=&\, 12345.66_{\phantom{M^{M^M}}} \\ \Rightarrow\quad \dfrac{137174}{11}\, &=&\, 12345.66 + 123.4566 + 1.234566 + 0.01234566+\,\cdots \\ &=&\, 12470.36... \end{eqnarray}$