mul by const, fastest way possible

playground.py

from functools import cache
from math import *

def remove_chunk(x: int):
    return x & (x + 1)

def p_remove_chunk(x: int):
    print(bin(x))
    print(bin(remove_chunk(x)))

def lsb(x: int):
    # 0xf00 -> 0x100
    return (x & -x)

def count_chunks(x: int):
    counter = 0
    while x != 0:
        x //= lsb(x) # f00 -> f
        x = remove_chunk(x) # f -> 0
        counter += 1
    return counter

@cache
def linear_method(x: int, trace = False, cost_so_far = 0):
    # breakpoint()
    # if trace:
    # print(bin(x))
    if x == 1 or x == 0:
        return 0
    if x % 2 == 0:
        return linear_method(x // lsb(x)) + 1
    # we have an odd number. simplest case: 0b_xxxx01 - one add
    if x & 2 == 0:
        return linear_method(x - 1) + 1
    # lets do the transformation.
    # 0 1111 -> 1 000p where p = -1
    # we dont need to store that crap, since we only compute cost.
    # cost of removing that leading p is 1 (sub x)
    return linear_method(x+1) + 1

@cache
def bernstein_algo(x: int):
    counter = 0

    if x <= 1:
        return 0
    if x % 2 == 0:
        return bernstein_algo(x // lsb(x)) + 1

    best = x
    for c in range(2 * int(log2(x))):
        for try_divider in [lsb(x) + 1, lsb(x) - 1]:
            if try_divider == 0:
                continue
            if try_divider > x:
                continue
            best = min(best, bernstein_algo(x // try_divider) + 2)

    return min(
        bernstein_algo(x + 1) + 1,
        bernstein_algo(x - 1) + 1,
        best
    )

@cache
def bruteforce_method(x: int):
    # linear_method is an upper bound
    best = linear_method(x)

    def inner(x, fuel, computed_so_far = []):
        if fuel == 0:
            return best
        # what can we do with x?
        # we can do add(whatever)
        # we can do sub(whatever)
        # we can do shift(whatever)
        for i in range(2 * int(log2(x))):
            pass
        # best = min(best, )

    inner(x, best)
    return best

def partial_sums(l: list):
    return [sum(l[:i+1]) for i, _ in enumerate(l)]

def hist(l: list):
    d = dict()
    for e in l:
        d.setdefault(e, 0)
        d[e] += 1
    arr = [0] * (max(d.keys()) + 1)
    for k in d:
        arr[k] = d[k]
    return arr

def print_counters(l: list):
    counters = [0] * (max(l) + 1)
    for i in range(1<<16):
        counters[l[i]] += 1
    print(*map(lambda x: f"%05x"%x, partial_sums(counters)))


tree_exploration = list(map(linear_method, range(1<<16)))
original_tree_exploration = [a for a in tree_exploration]
print_counters(tree_exploration)

# optimize a * (i * j) -> (a * i) * j; cost -> e1 + e2
def factorization_opt(tree_exploration: list):
    optimizations_performed = 0
    for i, e1 in enumerate(tree_exploration):
        # a * (i * j) = (a * i) * j; cost = e1 + e2
        for j, e2 in enumerate(tree_exploration):
            # costs_checked.append(e1 + e2)
            if i * j >= len(tree_exploration):
                break
            if tree_exploration[i * j] > e1 + e2:
                tree_exploration[i * j] = e1 + e2
                optimizations_performed += 1
    return (optimizations_performed, tree_exploration)

# a * (i + j) = a * i + a * j; cost = e1 + e2 + 1
def add_opt(tree_exploration: list):
    tree_exploration = tree_exploration[:]
    optimizations_performed = 0
    global e1_vals
    e1_vals = []
    for i, e1 in enumerate(tree_exploration):
        # a * (i + j) = a * i + a * j; cost = e1 + e2 + 1
        # optimization: consider only e2 < 5
        if not e1 < 6:
            continue
        for j, e2 in enumerate(tree_exploration):
            # optimization: consider only e1 < e2 ; useless.
            if e1 >= e2:
                continue

            if i + j < len(tree_exploration):
                if tree_exploration[i + j] > e1 + e2 + 1:
                    tree_exploration[i + j] = e1 + e2 + 1
                    optimizations_performed += 1
                    e1_vals.append(e1)
                    # if optimizations_performed % 100 == 0:
                    #     print(f"{optimizations_performed}... ", end="")
            else:
                break
    return (optimizations_performed, tree_exploration)

# print("optimizations_performed:", optimizations_performed)
# print_counters(tree_exploration)

# more optimize...

# opt wrapper
def wrap_opt(opt: string, tree_exploration):
    fun = eval(f"{opt}_opt")
    print(f"starting {opt} optimization...")
    opts_performed, tree_exploration = fun(tree_exploration)
    print("optimizations_performed:", opts_performed)
    print_counters(tree_exploration)
    return tree_exploration

tree_exploration = wrap_opt("factorization", tree_exploration)
tree_exploration = wrap_opt("add", tree_exploration)