0
$\begingroup$

I need a reliable arbitrary-precision division of discrete real numbers (ℝ), using arbitrary-precision discrete integers (ℤ).

It is a classic problem, but it is not easy to verify the good solutions on the Web. I need a division algorithm to calculate $N/D$ with the following "real life" computational constraints:

  1. The result can represented as "integer part" and "fractional part", that is ordinate pair $r=(i,f)$, or by a integer and a standard divisor like $10^n$.

  2. The algorithm is a function $f(N,D)$ that use bitwise operations and/or basic arithmetic operations; and a fast function like $SRT(n_0,d_0)$, that returns the quotient $Q_0$ and the remainder $R_0$, so it returns the pair $(Q_0,R_0)$.

All values ($i,f,n_0,d_0,Q_0,R_0$) are arbitrary-precision discrete integers (example)... How to calculate? Are there optimized algorithms to do it?


COMMENTS

In nowadays is commom to use floating-point arithmetic with a reasonable number of bits (e.g. 32)... And to ignore the precision problems. In general programming languages offer simgle and double precision, but no Quadruple-precision floating-point data type.

When you can not ignore precision problems, the programming languages also offer some alternative, such as the arbitrary-precision discrete integers (e.g. Javascript offer BigInt), but it only offers integer division algorithm, with quotient Q and remainder R. No function to return "integer part" and "fractional part" (that's what I need).

Related question this one have good clues, but no objective answer about best algorithms (to obtain "integer part" and "fraction part" from integer division).

$\endgroup$
  • 1
    $\begingroup$ How do you intend to represent your "real numbers"? As a large integer times a power of ten (often a negative power)? Or do you want to work in powers of two? How many digits do you want to store for the result of $1/3$? $\endgroup$ – David K Apr 6 at 13:20
  • $\begingroup$ Hi @DavidK, I edited, please check if now better... Well, specifically, and imagining a to store in Javascript (BigInts), as the pair r=[0n,3333333333333333333333333n]... Or by a single integer (using a reference like $2^{512}$ to divide it). $\endgroup$ – Peter Krauss Apr 6 at 14:57
1
$\begingroup$

Given positive integers $\ N, D,\ $ and $\ P>0.\ $ Define $\ I := \lfloor N/D\rfloor\ $ while the remainder $\ R := \mod(N,D)\ $ or $\ R := N - I\cdot D.\ $ The fractional part $\ F := \lfloor (10^P \cdot R) / D\rfloor.\ $ The result returned is $\ (I, F)\ $ which represents $\ N/D \approx I + F/10^P.$

$\endgroup$
  • $\begingroup$ Yes ... For an obvious question, an obvious answer. It is perfect! Except by a small notational improvement, $\ F := \lfloor (10^P \cdot R) / D\rfloor.\ $ $\endgroup$ – Peter Krauss Apr 6 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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