Compiler Explorer

Source code

import math

def iter_div_2(x, xi):
    xi = (x >> 1) - xi
    xi = x >> 1
    return xi

def iter_div_3(x, xi):
    xi = ((x + 1*xi) >> 1) - xi
    xi = (x + 1*xi) >> 2
    return xi

def iter_div_4(x, xi):
    xi = (x >> 2) - xi
    xi = x >> 2
    return xi

def iter_div_5(x, xi):
    xi = ((x + 3*xi) >> 2) - xi
    xi = (x + 3*xi) >> 3
    return xi

def iter_div_6(x, xi):
    xi = ((x + 2*xi) >> 2) - xi
    xi = (x + 2*xi) >> 3
    return xi

def iter_div_7(x, xi):    
    xi = ((x + xi) >> 2) - xi
    xi = (x + xi) >> 3  
    return xi

def iter_div_8(x, xi):
    xi = (x >> 3) - xi
    xi = x >> 3
    return xi

def iter_div_9(x, xi):
    xi = ((x + 7*xi) >> 3) - xi
    xi = ((x + 7*xi) >> 4)    
    return xi

def iter_div_10(x, xi):
    xi = ((x + 6*xi) >> 3) - xi
    xi = ((x + 6*xi) >> 4)    
    return xi

def iter_div_11(x, xi):
    xi = ((x + 5*xi) >> 3) - xi
    xi = ((x + 5*xi) >> 4)    
    return xi

def iter_div_12(x, xi):
    xi = ((x + 4*xi) >> 3) - xi
    xi = ((x + 4*xi) >> 4)    
    return xi

def iter_div_13(x, xi):
    xi = ((x + 3*xi) >> 3) - xi
    xi = ((x + 3*xi) >> 4)    
    return xi

def iter_div_14(x, xi):
    xi = ((x + 2*xi) >> 3) - xi
    xi = ((x + 2*xi) >> 4)    
    return xi

def iter_div_15(x, xi):
    xi = ((x + 1*xi) >> 3) - xi
    xi = ((x + 1*xi) >> 4)    
    return xi

def iter_div_16(x, xi):
    xi = (x >> 4) - xi
    xi = x >> 4
    return xi

def test_div(x, p):    
    global iterations_pool;
    xi = 0
    count = 0
    while True:
        prev_x = xi                               
        xi = iterations_pool[p](x, xi)        
        count += 1                
        if xi == prev_x:                    
            break
    error = abs(x//p - xi)
    return (xi, error, count)

def test_range(n, p):
    if p not in iterations_pool:
        return
    ave_c = 0.
    for x in range(n):
        q, e, c = test_div(x, p)        
        ave_c += c
        assert(e < 1)
    ave_c /= (2*N*math.log2(N*math.log2(N)))
    print(f'div by {p}: {ave_c = :.3f} iterations')

if __name__ == "__main__":
    N = 8192*8

iterations_pool = dict()    
    iterations_pool[2] = iter_div_2
    iterations_pool[3] = iter_div_3
    iterations_pool[4] = iter_div_4
    iterations_pool[5] = iter_div_5
    iterations_pool[6] = iter_div_6
    iterations_pool[7] = iter_div_7
    iterations_pool[8] = iter_div_8
    iterations_pool[9] = iter_div_9
    iterations_pool[10] = iter_div_10
    iterations_pool[11] = iter_div_11
    iterations_pool[12] = iter_div_12
    iterations_pool[13] = iter_div_13
    iterations_pool[14] = iter_div_14
    iterations_pool[15] = iter_div_15
    iterations_pool[16] = iter_div_16

for i in range(1, 17):
        test_range(N, i)