0

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

Peter Krauss
  • 163
  • 8
  • 1
    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$? – David K Apr 06 '19 at 13:20
  • 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). – Peter Krauss Apr 06 '19 at 14:57

1 Answers1

2

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

Somos
  • 35,251
  • 3
  • 30
  • 76
  • 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.\ $ – Peter Krauss Apr 06 '19 at 15:32