Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is $x$ necessarily an integer, or could it be fractional? –  MJD Jun 20 '12 at 16:29
    
$x$ is an integer and $x<(2p+1)^2$. –  asmith Jun 20 '12 at 16:34
add comment

3 Answers

up vote 2 down vote accepted

$$ \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$.

share|improve this answer
    
This is just the old trick of reducing division by $11$ to division by $10$ - see my answer. –  Bill Dubuque Jun 20 '12 at 19:28
add comment

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$.

share|improve this answer
    
+1 I guess the natural question would be "does it work for odd primes?" but the reasoning seems to work fine anyway. –  Simon Markett Jun 20 '12 at 16:57
    
I was imprecise. I didn't mean a function of $floor(x/p)$, but a function that doesn't explicitly use division by $2p+1$. –  asmith Jun 20 '12 at 17:00
    
@simon It's easy to find examples for any prime $p$. We want $x_1$ and $x_2$ such that $\lfloor x_1/p \rfloor = \lfloor x_2/p \rfloor$ but $\lfloor x_1/(2p+1) \rfloor \ne \lfloor x_2/(2p+1) \rfloor$. So take $x_1=2p$ and $x_2=2p+1$. –  MJD Jun 20 '12 at 17:06
    
See my edit.... –  asmith Jun 20 '12 at 17:07
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: hackersdelight.org/divcMore.pdf –  Erick Wong Jun 20 '12 at 17:38
show 1 more comment

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}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.