def division_euclidienne_dichotomique(a, b):
    """Renvoie le quotient q et le reste r de la division euclidienne de a par b"""

    n = 0
    while 2 ** n * b <= a:
        n += 1
    inf = 2 ** (n - 1)
    sup = 2 ** n
    for i in range(1, n):
        mid = (inf + sup) / 2
        if mid * b <= a:
            inf = mid
        else:
            sup = mid
    return inf, a - b * inf