Division euclidienne

• Initialisation $q=0$, $r=a$. Progression : $a=qb+r\wedge r\ge b\Rightarrow a=(q+1)b+(r-b)\wedge r-b\ge 0$. Arrêt : $r<b$, donc $0\le r<b$.

static int[] divisionSoustraction(int a, int b) {  // a ≥ 0, b > 0
    int q = 0, r = a;                 // a = q×b + r et r ≥ 0
    while (r >= b) {                  // a = q×b + r et r ≥ b
        q = q + 1; r = r - b;         // a = q×b + r et r ≥ 0
    }                                 // a = q×b + r et 0 ≤ r < b
    return new int[] {q, r};
}

La boucle fait $q=\lfloor a/b\rfloor$ tours : $\Theta (a/b)$, exponentiel en le nombre de chiffres de $a$.

• Une première boucle double $c=p\times b$ jusqu'à $c>a$ ; alors $J(0,a,c,p)$ est vrai. Progression : si $p\ne 1$, on divise $c$ et $p$ par $2$ ; on a alors $0\le r<2c$, et $J\wedge r\ge c\Rightarrow J(q+p,r-c,c,p)$, $J\wedge r<c\Rightarrow J(q,r,c,p)$. Arrêt : $p=1$, donc $c=b$ et $0\le r<b$.

static long[] divisionRapide(long a, long b) {     // a ≥ 0, b > 0
    long c = b, p = 1;                // c = p × b
    while (c <= a) { c = 2 * c; p = 2 * p; }       // c = p × b > a
    long q = 0, r = a;                // J : a = q×b + r, 0 ≤ r < c, c = p×b
    while (p != 1) {                  // J et p ≠ 1
        c = c / 2; p = p / 2;         // a = q×b + r et 0 ≤ r < 2c
        if (r >= c) { r = r - c; q = q + p; }      // J
    }                                 // a = q×b + r et 0 ≤ r < b
    return new long[] {q, r};
}

Chaque boucle fait $\lceil {\log }_2(a/b)\rceil$ tours environ : $\Theta (\log (a/b))$. C'est l'algorithme de la division posée, en base $2$.

• Pour $a=10^9$ et $b=7$, le quotient est $142857142$ et le reste $6$. La première fonction fait $142857142$ tours, la seconde $56$ ($28$ doublements puis $28$ divisions par $2$).