Disclaimer: This isn't a 100% complete answer, but for the case that I need it for, it works. Maybe someone with additional ideas can improve it...
One can make some progress by looking at different possible special cases:
If $P*r<2^{63}$, there is no problem with overflows to begin with, so we can just calculate the answer directly as $p=\lfloor P*r/R \rfloor$. The only thing we need to do is to perform the check as $P<\lfloor2^{63}/r \rfloor$ instead to allow for a false result without overflow.
To cover the other case, one can do the following transformation:
$$
p=\lfloor P*r/R \rfloor= \bigg\lfloor\frac{P}{R/r}\bigg\rfloor=\bigg\lfloor\frac{P}{\lfloor R/r \rfloor + (R\bmod{r})/r}\bigg\rfloor
$$
$$
=\bigg\lfloor\frac{P}{\lfloor R/r \rfloor}-\frac{P(R\bmod{r})/r}{\lfloor R/r \rfloor(R/r)}\bigg\rfloor=\Bigg\lfloor\bigg\lfloor\frac{P}{\lfloor R/r\rfloor}\bigg\rfloor + \frac{P\bmod{\lfloor R/r\rfloor}}{\lfloor R/r\rfloor}-\frac{P(R\bmod{r})}{R\lfloor R/r \rfloor}\Bigg\rfloor
$$
$$
=\bigg\lfloor\frac{P}{\lfloor R/r\rfloor}\bigg\rfloor + \Bigg\lfloor\frac{P\bmod{\lfloor R/r\rfloor}}{\lfloor R/r\rfloor}-\frac{P}{R}\frac{R\bmod{r}}{\lfloor R/r \rfloor}\Bigg\rfloor
$$
The first term in the sum can be calculated directly without overflow issues. The second half after the '$+$' - sign is a little more difficult. But, looking at it, one realizes the following: The fraction to the left of the '$-$' - sign is always between $\ge 0$ and $<1$. Also: $0 \le P/R < 1$. So, we can look at two different special cases here:
- If $R\ge r^2$, the entire part to the right of the '$+$' - sign can only be either $0$ or $-1$.
- Otherwise, things could get more complicated...
Luckily, in my application, I know for a fact, that $R\ge r^2$ is always true. Therefore, for me, the answer is:
$$
p = \left\{\begin{array}{1 1}\lfloor (P*r)/R \rfloor & \quad \text{if $P<\lfloor2^{63}/r \rfloor$} \\ \lfloor P/\lfloor R/r\rfloor \rfloor \;[-1] & \quad \text{if $P\ge \lfloor2^{63}/r \rfloor$ and $R\ge r^2$} \\ \text{here be dragons} & \quad \text{if $P\ge \lfloor2^{63}/r \rfloor$ and $R<r^2$} \end{array} \right.\
$$
Here, $[-1]$ indicates that I only subract -1 in some cases, which I check by first leaving it out, testing the value of $p$ I get and then putting it in if I need it.
In the third case, one could use an arbitrary precision approach (c.f. GMP) and calculate the answer by doing long division as suggested by MvG. But maybe someone can find a more elegant way to slay the dragons for completeness... ;) Otherwise, if I have time a little later, I (or someone else) might add the formula for implementing the long division.
Best Answer
Doerfler's book Dead Reckoning: Calculating Without Instruments contains algorithms specifically designed for computing nontrivial things mentally. But it's still not easy and requires quite a lot of practice, I guess. To begin with, one must be really good at multiplying two-digit numbers (so I'm lost there already...).