Problem 792

S(n) = sum_{k=1..n} (-2)^k * C(2k,k) u(n) = v2(3*S(n) + 4) (2-adic valuation) U(N) = sum_{n=1..N} u(n^3), N = 10000. In the 2-adics 3*sum_{k>=1} (-2)^k*C(2k,k) + 4 = 0, so 3*S(n) + 4 = -3 * sum_{k>n} R(k), R(k) = (-2)^k * C(2k,k). -3 is odd, so u(n) = v2( sum_{k>n} R(k) ). R(k+1)/R(k) = -4 * (2k+1)/(k+1), v2(R(k)) = k + popcount(k). We sum the tail k = n+1 .. n+m (m up to 220) keeping only odd parts modulo 2^P (powers of two tracked separately). The remainder for k >= n+m+1 is divisible by 2^(n+m+1), so once the partial sum's valuation drops below n+m+1 it equals u(n). Precision P starts at 256 bits and is doubled when the reduced sum vanishes mod 2^P.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 792: Too Many Twos
# S(n) = sum_{k=1..n} (-2)^k * C(2k,k)
# u(n) = v2(3*S(n) + 4)  (2-adic valuation)
# U(N) = sum_{n=1..N} u(n^3), N = 10000.
#
# In the 2-adics 3*sum_{k>=1} (-2)^k*C(2k,k) + 4 = 0, so
#   3*S(n) + 4 = -3 * sum_{k>n} R(k),  R(k) = (-2)^k * C(2k,k).
# -3 is odd, so u(n) = v2( sum_{k>n} R(k) ).
#
# R(k+1)/R(k) = -4 * (2k+1)/(k+1),  v2(R(k)) = k + popcount(k).
#
# We sum the tail k = n+1 .. n+m (m up to 220) keeping only odd parts
# modulo 2^P (powers of two tracked separately).  The remainder for
# k >= n+m+1 is divisible by 2^(n+m+1), so once the partial sum's
# valuation drops below n+m+1 it equals u(n).  Precision P starts at
# 256 bits and is doubled when the reduced sum vanishes mod 2^P.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function malloc(n: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

const MAXLIMBS: i32 = 32

# ---- helpers: popcount and ctz for u64 ----

function popcount64(x0: u64) -> i64 {
    let mut x: u64 = x0
    let mut c: i64 = 0
    while x != 0 {
        c = c + 1
        x = x & (x - 1)
    }
    return c
}

function ctz64(x: u64) -> i32 {
    if x == 0 { return 64 }
    let mut n: i32 = 0
    let mut v: u64 = x
    while (v & 1) == 0 {
        n = n + 1
        v = v >> 1
    }
    return n
}

# ---- bignum mod 2^(64*nl), little-endian u64 limbs ----

function bn_is_zero(a: ptr<u64>, nl: i32) -> bool {
    let mut i: i32 = 0
    while i < nl {
        if a[i] != 0 { return false }
        i = i + 1
    }
    return true
}

function bn_v2(a: ptr<u64>, nl: i32) -> i32 {
    let mut i: i32 = 0
    while i < nl {
        if a[i] != 0 { return i * 64 + ctz64(a[i]) }
        i = i + 1
    }
    return nl * 64
}

function bn_zero(a: ptr<u64>, nl: i32) -> void {
    let mut i: i32 = 0
    while i < nl {
        a[i] = 0
        i = i + 1
    }
}

function bn_copy(dst: ptr<u64>, src: ptr<u64>, nl: i32) -> void {
    let mut i: i32 = 0
    while i < nl {
        dst[i] = src[i]
        i = i + 1
    }
}

function bn_from_u64(a: ptr<u64>, v: u64, nl: i32) -> void {
    bn_zero(a, nl)
    a[0] = v
}

function bn_from_i64(a: ptr<u64>, v: i64, nl: i32) -> void {
    let all_ones: u64 = 0
    let fill: u64 = if v < 0 { all_ones - 1 } else { 0 }
    let mut i: i32 = 1
    while i < nl {
        a[i] = fill
        i = i + 1
    }
    a[0] = v as u64
}

function bn_add(dst: ptr<u64>, a: ptr<u64>, b: ptr<u64>, nl: i32) -> void {
    let mut carry: u64 = 0
    let mut i: i32 = 0
    while i < nl {
        let s: i128 = (a[i] as i128) + (b[i] as i128) + (carry as i128)
        dst[i] = s as u64
        carry = (s >> 64) as u64
        i = i + 1
    }
}

function bn_shl(dst: ptr<u64>, a: ptr<u64>, shift: i32, nl: i32) -> void {
    if shift <= 0 { bn_copy(dst, a, nl); return }
    if shift >= nl * 64 { bn_zero(dst, nl); return }
    let ws: i32 = shift / 64
    let bs: i32 = shift % 64
    bn_zero(dst, nl)
    if bs == 0 {
        let mut i: i32 = nl - 1
        while i >= ws {
            dst[i] = a[i - ws]
            i = i - 1
        }
    } else {
        let mut i: i32 = nl - 1
        while i >= ws {
            let lo: u64 = a[i - ws] << bs
            let hi: u64 = if i - ws - 1 >= 0 { a[i - ws - 1] >> (64 - bs) } else { 0 }
            dst[i] = lo | hi
            i = i - 1
        }
    }
}

function bn_mul(dst: ptr<u64>, a: ptr<u64>, b: ptr<u64>, nl: i32) -> void {
    let tmp: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let mut i: i32 = 0
    while i < nl {
        let mut carry: u64 = 0
        let mut j: i32 = 0
        while j < nl - i {
            let p: i128 = (a[i] as i128) * (b[j] as i128) + (tmp[i + j] as i128) + (carry as i128)
            tmp[i + j] = p as u64
            carry = (p >> 64) as u64
            j = j + 1
        }
        i = i + 1
    }
    bn_copy(dst, tmp, nl)
    free(tmp as ptr<void>)
}

function bn_inv_odd(dst: ptr<u64>, a: ptr<u64>, nl: i32) -> void {
    let x: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let t: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let two: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let ax: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let s: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let neg: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let all_ones: u64 = 0
    all_ones = all_ones - 1

    bn_from_u64(x, 1, nl)
    bn_from_u64(two, 2, nl)
    let bits: i32 = nl * 64
    let mut it: i32 = 0
    while (1 << it) < bits {
        bn_mul(ax, a, x, nl)
        let mut i: i32 = 0
        while i < nl {
            neg[i] = all_ones ^ ax[i]
            i = i + 1
        }
        let mut c: u64 = 1
        i = 0
        while i < nl && c != 0 {
            let s2: i128 = (neg[i] as i128) + (c as i128)
            neg[i] = s2 as u64
            c = (s2 >> 64) as u64
            i = i + 1
        }
        bn_add(s, neg, two, nl)
        bn_mul(t, x, s, nl)
        bn_copy(x, t, nl)
        it = it + 1
    }
    bn_copy(dst, x, nl)
    free(x as ptr<void>)
    free(t as ptr<void>)
    free(two as ptr<void>)
    free(ax as ptr<void>)
    free(s as ptr<void>)
    free(neg as ptr<void>)
}

# ---- inverse cache (parallel arrays) ----

let mut inv_key: ptr<u64> = null
let mut inv_val: ptr<u64> = null
let mut inv_cache_n: i32 = 0

function inv_odd(denom_odd: u64, nl: i32) -> i32 {
    let mut i: i32 = 0
    while i < inv_cache_n {
        if inv_key[i] == denom_odd { return i }
        i = i + 1
    }
    let a: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    bn_from_u64(a, denom_odd, nl)
    let idx: i32 = inv_cache_n
    bn_inv_odd(inv_val + (idx as i64 * MAXLIMBS as i64), a, nl)
    inv_key[idx] = denom_odd
    inv_cache_n = inv_cache_n + 1
    free(a as ptr<void>)
    return idx
}

# ---- core: u(n) ----

function u_of(n: i64) -> i64 {
    let P_list: ptr<i32> = calloc(4, 4) as ptr<i32>
    P_list[0] = 256; P_list[1] = 512; P_list[2] = 1024; P_list[3] = 2048

    let odd: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let scaled_sum: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let tmp: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let tmp2: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let odd_new: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>
    let factor: ptr<u64> = calloc(MAXLIMBS as i64, 8) as ptr<u64>

    let mut pi: i32 = 0
    while pi < 4 {
        let P: i32 = P_list[pi]
        let nl: i32 = P / 64
        inv_cache_n = 0

        let mut k: i64 = n + 1
        let mut exp: i64 = k + popcount64(k as u64)

        bn_from_u64(odd, 1, nl)

        let mut have_min: bool = false
        let mut min_exp: i64 = 0
        bn_zero(scaled_sum, nl)

        let mut m: i32 = 1
        while m <= 220 {
            if !have_min {
                min_exp = exp
                bn_copy(scaled_sum, odd, nl)
                have_min = true
            } else {
                if exp < min_exp {
                    let shift: i64 = min_exp - exp
                    if shift < (P as i64) { bn_shl(scaled_sum, scaled_sum, shift as i32, nl) }
                    else { bn_zero(scaled_sum, nl) }
                    min_exp = exp
                    bn_add(scaled_sum, scaled_sum, odd, nl)
                } else {
                    let shift: i64 = exp - min_exp
                    if shift < (P as i64) {
                        bn_shl(tmp, odd, shift as i32, nl)
                        bn_add(scaled_sum, scaled_sum, tmp, nl)
                    }
                }
            }

            if bn_is_zero(scaled_sum, nl) { break }

            let v_partial: i64 = min_exp + (bn_v2(scaled_sum, nl) as i64)
            if v_partial < n + (m as i64) + 1 {
                free(P_list as ptr<void>)
                free(odd as ptr<void>)
                free(scaled_sum as ptr<void>)
                free(tmp as ptr<void>)
                free(tmp2 as ptr<void>)
                free(odd_new as ptr<void>)
                free(factor as ptr<void>)
                return v_partial
            }

            # advance R(k) -> R(k+1): ratio = -4*(2k+1)/(k+1)
            let denom: i64 = k + 1
            let t: i32 = ctz64(denom as u64)
            let denom_odd: u64 = (denom as u64) >> t

            let inv_idx: i32 = inv_odd(denom_odd, nl)
            let inv_ptr: ptr<u64> = inv_val + (inv_idx as i64 * MAXLIMBS as i64)

            bn_from_i64(factor, -(2 * k + 1), nl)
            bn_mul(tmp2, factor, inv_ptr, nl)
            bn_mul(odd_new, odd, tmp2, nl)
            bn_copy(odd, odd_new, nl)

            exp = exp + 2 - (t as i64)
            k = denom

            if exp != k + popcount64(k as u64) {
                free(P_list as ptr<void>)
                free(odd as ptr<void>)
                free(scaled_sum as ptr<void>)
                free(tmp as ptr<void>)
                free(tmp2 as ptr<void>)
                free(odd_new as ptr<void>)
                free(factor as ptr<void>)
                return -1
            }
            m = m + 1
        }
        pi = pi + 1
    }
    free(P_list as ptr<void>)
    free(odd as ptr<void>)
    free(scaled_sum as ptr<void>)
    free(tmp as ptr<void>)
    free(tmp2 as ptr<void>)
    free(odd_new as ptr<void>)
    free(factor as ptr<void>)
    return -1
}

function main() -> i32 {
    inv_key = calloc(256, 8) as ptr<u64>
    inv_val = calloc(256 * MAXLIMBS as i64, 8) as ptr<u64>

    let mut total: i64 = 0
    let mut n: i64 = 1
    while n <= 10000 {
        let nc: i64 = n * n * n
        total = total + u_of(nc)
        n = n + 1
    }

    printf("%lld\n", total)
    free(inv_key as ptr<void>)
    free(inv_val as ptr<void>)
    return 0
}

Generated C

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
    while (flow_temp_head) {
        flow_temp_node* n = flow_temp_head;
        flow_temp_head = n->next;
        free(n);
    }
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
    flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
    if (!node) return NULL;
    node->next = flow_temp_head;
    flow_temp_head = node;
    if (!flow_temp_atexit_set) {
        flow_temp_atexit_set = 1;
        atexit(flow_temp_free_all);
    }
    return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
    size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
    char* r = (char*)flow_temp_alloc(la + lb + 1);
    if (!r) return NULL;
    if (la) memcpy(r, a, la);
    if (lb) memcpy(r + la, b, lb);
    r[la + lb] = '\0';
    return r;
}

#define __flow_in_arr(arr, val) __extension__ ({ \
    int _found = 0; \
    size_t _n = sizeof(arr)/sizeof((arr)[0]); \
    for (size_t _i = 0; _i < _n; _i++) { \
        if ((arr)[_i] == (val)) { _found = 1; break; } \
    } _found; })

/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
    fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
    abort();
#if defined(__GNUC__) || defined(__clang__)
    __builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")

#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif

#include <math.h>

void* _ui_state = NULL;

static inline float i32_to_f32(int32_t v) { return (float)v; }

/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }

int64_t popcount64_u64(uint64_t x0);
int32_t ctz64_u64(uint64_t x);
bool bn_is_zero_ptr_u64_i32(uint64_t* a, int32_t nl);
int32_t bn_v2_ptr_u64_i32(uint64_t* a, int32_t nl);
void bn_zero_ptr_u64_i32(uint64_t* a, int32_t nl);
void bn_copy_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* src, int32_t nl);
void bn_from_u64_ptr_u64_u64_i32(uint64_t* a, uint64_t v, int32_t nl);
void bn_from_i64_ptr_u64_i64_i32(uint64_t* a, int64_t v, int32_t nl);
void bn_add_ptr_u64_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, uint64_t* b, int32_t nl);
void bn_shl_ptr_u64_ptr_u64_i32_i32(uint64_t* dst, uint64_t* a, int32_t shift, int32_t nl);
void bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, uint64_t* b, int32_t nl);
void bn_inv_odd_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, int32_t nl);
int32_t inv_odd_u64_i32(uint64_t denom_odd, int32_t nl);
int64_t u_of_i64(int64_t n);
int32_t main(void);

static const int32_t MAXLIMBS = 32;

/* Module statics */
static uint64_t* inv_key = NULL;
static uint64_t* inv_val = NULL;
static int32_t inv_cache_n = 0;




int64_t popcount64_u64(uint64_t x0) {
    uint64_t x = x0;
    int64_t c = 0;
    while (x != 0) {
        c = (c + 1);
        x = (x & (x - 1));
    }
    return c;
}

int32_t ctz64_u64(uint64_t x) {
    if (x == 0) {
        return 64;
    }
    int32_t n = 0;
    uint64_t v = x;
    while ((v & 1) == 0) {
        n = (n + 1);
        v = FLOW_CHECKED_SHR((v), (1));
    }
    return n;
}

bool bn_is_zero_ptr_u64_i32(uint64_t* a, int32_t nl) {
    int32_t i = 0;
    while (i < nl) {
        if (a[i] != 0) {
            return 0;
        }
        i = (i + 1);
    }
    return 1;
}

int32_t bn_v2_ptr_u64_i32(uint64_t* a, int32_t nl) {
    int32_t i = 0;
    while (i < nl) {
        if (a[i] != 0) {
            return ((i * 64) + ctz64_u64(a[i]));
        }
        i = (i + 1);
    }
    return (nl * 64);
}

void bn_zero_ptr_u64_i32(uint64_t* a, int32_t nl) {
    int32_t i = 0;
    while (i < nl) {
        a[i] = 0;
        i = (i + 1);
    }
}

void bn_copy_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* src, int32_t nl) {
    int32_t i = 0;
    while (i < nl) {
        dst[i] = src[i];
        i = (i + 1);
    }
}

void bn_from_u64_ptr_u64_u64_i32(uint64_t* a, uint64_t v, int32_t nl) {
    bn_zero_ptr_u64_i32(a, nl);
    a[0] = v;
}

void bn_from_i64_ptr_u64_i64_i32(uint64_t* a, int64_t v, int32_t nl) {
    uint64_t all_ones = 0;
    uint64_t fill = ((v < 0) ? ((all_ones - 1)) : (0));
    int32_t i = 1;
    while (i < nl) {
        a[i] = fill;
        i = (i + 1);
    }
    a[0] = ((uint64_t)(v));
}

void bn_add_ptr_u64_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, uint64_t* b, int32_t nl) {
    uint64_t carry = 0;
    int32_t i = 0;
    while (i < nl) {
        __int128 s = ((((__int128)(a[i])) + ((__int128)(b[i]))) + ((__int128)(carry)));
        dst[i] = ((uint64_t)(s));
        carry = ((uint64_t)(FLOW_CHECKED_SHR((s), (64))));
        i = (i + 1);
    }
}

void bn_shl_ptr_u64_ptr_u64_i32_i32(uint64_t* dst, uint64_t* a, int32_t shift, int32_t nl) {
    if (shift <= 0) {
        bn_copy_ptr_u64_ptr_u64_i32(dst, a, nl);
        return;
    }
    if (shift >= (nl * 64)) {
        bn_zero_ptr_u64_i32(dst, nl);
        return;
    }
    int32_t ws = FLOW_CHECKED_DIV((shift), (64));
    int32_t bs = FLOW_CHECKED_MOD((shift), (64));
    bn_zero_ptr_u64_i32(dst, nl);
    if (bs == 0) {
        int32_t i = (nl - 1);
        while (i >= ws) {
            dst[i] = a[(i - ws)];
            i = (i - 1);
        }
    } else {
        int32_t i = (nl - 1);
        while (i >= ws) {
            uint64_t lo = FLOW_CHECKED_SHL((a[(i - ws)]), (bs));
            uint64_t hi = ((((i - ws) - 1) >= 0) ? (FLOW_CHECKED_SHR((a[((i - ws) - 1)]), ((64 - bs)))) : (0));
            dst[i] = (lo | hi);
            i = (i - 1);
        }
    }
}

void bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, uint64_t* b, int32_t nl) {
    uint64_t* tmp = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    int32_t i = 0;
    while (i < nl) {
        uint64_t carry = 0;
        int32_t j = 0;
        while (j < (nl - i)) {
            __int128 p = (((((__int128)(a[i])) * ((__int128)(b[j]))) + ((__int128)(tmp[(i + j)]))) + ((__int128)(carry)));
            tmp[(i + j)] = ((uint64_t)(p));
            carry = ((uint64_t)(FLOW_CHECKED_SHR((p), (64))));
            j = (j + 1);
        }
        i = (i + 1);
    }
    bn_copy_ptr_u64_ptr_u64_i32(dst, tmp, nl);
    free(((void*)(tmp)));
}

void bn_inv_odd_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* a, int32_t nl) {
    uint64_t* x = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* t = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* two = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* ax = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* s = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* neg = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t all_ones = 0;
    all_ones = (all_ones - 1);
    bn_from_u64_ptr_u64_u64_i32(x, 1, nl);
    bn_from_u64_ptr_u64_u64_i32(two, 2, nl);
    int32_t bits = (nl * 64);
    int32_t it = 0;
    while (FLOW_CHECKED_SHL((1), (it)) < bits) {
        bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(ax, a, x, nl);
        int32_t i = 0;
        while (i < nl) {
            neg[i] = (all_ones ^ ax[i]);
            i = (i + 1);
        }
        uint64_t c = 1;
        i = 0;
        while ((i < nl && c != 0)) {
            __int128 s2 = (((__int128)(neg[i])) + ((__int128)(c)));
            neg[i] = ((uint64_t)(s2));
            c = ((uint64_t)(FLOW_CHECKED_SHR((s2), (64))));
            i = (i + 1);
        }
        bn_add_ptr_u64_ptr_u64_ptr_u64_i32(s, neg, two, nl);
        bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(t, x, s, nl);
        bn_copy_ptr_u64_ptr_u64_i32(x, t, nl);
        it = (it + 1);
    }
    bn_copy_ptr_u64_ptr_u64_i32(dst, x, nl);
    free(((void*)(x)));
    free(((void*)(t)));
    free(((void*)(two)));
    free(((void*)(ax)));
    free(((void*)(s)));
    free(((void*)(neg)));
}

int32_t inv_odd_u64_i32(uint64_t denom_odd, int32_t nl) {
    int32_t i = 0;
    while (i < inv_cache_n) {
        if (inv_key[i] == denom_odd) {
            return i;
        }
        i = (i + 1);
    }
    uint64_t* a = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    bn_from_u64_ptr_u64_u64_i32(a, denom_odd, nl);
    int32_t idx = inv_cache_n;
    bn_inv_odd_ptr_u64_ptr_u64_i32((inv_val + (((int64_t)(idx)) * ((int64_t)(MAXLIMBS)))), a, nl);
    inv_key[idx] = denom_odd;
    inv_cache_n = (inv_cache_n + 1);
    free(((void*)(a)));
    return idx;
}

int64_t u_of_i64(int64_t n) {
    int32_t* P_list = (int32_t*)(((int32_t*)(calloc(4, 4))));
    P_list[0] = 256;
    P_list[1] = 512;
    P_list[2] = 1024;
    P_list[3] = 2048;
    uint64_t* odd = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* scaled_sum = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* tmp = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* tmp2 = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* odd_new = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    uint64_t* factor = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(MAXLIMBS)), 8))));
    int32_t pi = 0;
    while (pi < 4) {
        int32_t P = P_list[pi];
        int32_t nl = FLOW_CHECKED_DIV((P), (64));
        inv_cache_n = 0;
        int64_t k = (n + 1);
        int64_t exp = (k + popcount64_u64(((uint64_t)(k))));
        bn_from_u64_ptr_u64_u64_i32(odd, 1, nl);
        bool have_min = 0;
        int64_t min_exp = 0;
        bn_zero_ptr_u64_i32(scaled_sum, nl);
        int32_t m = 1;
        while (m <= 220) {
            if ((!(have_min))) {
                min_exp = exp;
                bn_copy_ptr_u64_ptr_u64_i32(scaled_sum, odd, nl);
                have_min = 1;
            } else {
                if (exp < min_exp) {
                    int64_t shift = (min_exp - exp);
                    if (shift < ((int64_t)(P))) {
                        bn_shl_ptr_u64_ptr_u64_i32_i32(scaled_sum, scaled_sum, ((int32_t)(shift)), nl);
                    } else {
                        bn_zero_ptr_u64_i32(scaled_sum, nl);
                    }
                    min_exp = exp;
                    bn_add_ptr_u64_ptr_u64_ptr_u64_i32(scaled_sum, scaled_sum, odd, nl);
                } else {
                    int64_t shift = (exp - min_exp);
                    if (shift < ((int64_t)(P))) {
                        bn_shl_ptr_u64_ptr_u64_i32_i32(tmp, odd, ((int32_t)(shift)), nl);
                        bn_add_ptr_u64_ptr_u64_ptr_u64_i32(scaled_sum, scaled_sum, tmp, nl);
                    }
                }
            }
            if (bn_is_zero_ptr_u64_i32(scaled_sum, nl)) {
                break;
            }
            int64_t v_partial = (min_exp + ((int64_t)(bn_v2_ptr_u64_i32(scaled_sum, nl))));
            if (v_partial < ((n + ((int64_t)(m))) + 1)) {
                free(((void*)(P_list)));
                free(((void*)(odd)));
                free(((void*)(scaled_sum)));
                free(((void*)(tmp)));
                free(((void*)(tmp2)));
                free(((void*)(odd_new)));
                free(((void*)(factor)));
                return v_partial;
            }
            int64_t denom = (k + 1);
            int32_t t = ctz64_u64(((uint64_t)(denom)));
            uint64_t denom_odd = FLOW_CHECKED_SHR((((uint64_t)(denom))), (t));
            int32_t inv_idx = inv_odd_u64_i32(denom_odd, nl);
            uint64_t* inv_ptr = (uint64_t*)((inv_val + (((int64_t)(inv_idx)) * ((int64_t)(MAXLIMBS)))));
            bn_from_i64_ptr_u64_i64_i32(factor, (-((2 * k) + 1)), nl);
            bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(tmp2, factor, inv_ptr, nl);
            bn_mul_ptr_u64_ptr_u64_ptr_u64_i32(odd_new, odd, tmp2, nl);
            bn_copy_ptr_u64_ptr_u64_i32(odd, odd_new, nl);
            exp = ((exp + 2) - ((int64_t)(t)));
            k = denom;
            if (exp != (k + popcount64_u64(((uint64_t)(k))))) {
                free(((void*)(P_list)));
                free(((void*)(odd)));
                free(((void*)(scaled_sum)));
                free(((void*)(tmp)));
                free(((void*)(tmp2)));
                free(((void*)(odd_new)));
                free(((void*)(factor)));
                return (-1);
            }
            m = (m + 1);
        }
        pi = (pi + 1);
    }
    free(((void*)(P_list)));
    free(((void*)(odd)));
    free(((void*)(scaled_sum)));
    free(((void*)(tmp)));
    free(((void*)(tmp2)));
    free(((void*)(odd_new)));
    free(((void*)(factor)));
    return (-1);
}

int32_t main(void) {
    inv_key = ((uint64_t*)(calloc(256, 8)));
    inv_val = ((uint64_t*)(calloc((256 * ((int64_t)(MAXLIMBS))), 8)));
    int64_t total = 0;
    int64_t n = 1;
    while (n <= 10000) {
        int64_t nc = ((n * n) * n);
        total = (total + u_of_i64(nc));
        n = (n + 1);
    }
    printf("%lld\n", total);
    free(((void*)(inv_key)));
    free(((void*)(inv_val)));
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func private @calloc(i64, i64) -> !llvm.ptr
  func.func private @malloc(i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  // Constant: MAXLIMBS
  llvm.mlir.global internal constant @MAXLIMBS(32 : i32) : i32
  func.func @popcount64(%arg0: i64) -> i64 {
    %0 = llvm.mlir.constant(1 : i64) : i64
    %1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %1 : i64, !llvm.ptr
    %2 = arith.constant 0 : i32
    %3 = arith.extsi %2 : i32 to i64
    %4 = llvm.mlir.constant(1 : i64) : i64
    %5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
    llvm.store %3, %5 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %6 = llvm.load %1 : !llvm.ptr -> i64
    %7 = arith.constant 0 : i32
    %9 = arith.extsi %7 : i32 to i64
    %8 = arith.cmpi ne, %6, %9 : i64
    cf.cond_br %8, ^bb1, ^bb2
    ^bb1:
      %10 = llvm.load %5 : !llvm.ptr -> i64
      %11 = arith.constant 1 : i32
      %13 = arith.extsi %11 : i32 to i64
      %12 = arith.addi %10, %13 : i64
      llvm.store %12, %5 : i64, !llvm.ptr
      %14 = llvm.load %1 : !llvm.ptr -> i64
      %15 = llvm.load %1 : !llvm.ptr -> i64
      %16 = arith.constant 1 : i32
      %18 = arith.extsi %16 : i32 to i64
      %17 = arith.subi %15, %18 : i64
      %19 = arith.andi %14, %17 : i64
      llvm.store %19, %1 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %20 = llvm.load %5 : !llvm.ptr -> i64
    func.return %20 : i64
  }
  func.func @ctz64(%arg0: i64) -> i32 {
    %21 = arith.constant 0 : i32
    %23 = arith.extsi %21 : i32 to i64
    %22 = arith.cmpi eq, %arg0, %23 : i64
    cf.cond_br %22, ^bb3, ^bb4
    ^bb3:
      %24 = arith.constant 64 : i32
      func.return %24 : i32
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %25 = arith.constant 0 : i32
    %26 = llvm.mlir.constant(1 : i64) : i64
    %27 = llvm.alloca %26 x i32 : (i64) -> !llvm.ptr
    llvm.store %25, %27 : i32, !llvm.ptr
    %28 = llvm.mlir.constant(1 : i64) : i64
    %29 = llvm.alloca %28 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %29 : i64, !llvm.ptr
    cf.br ^bb6
    ^bb6:
    %30 = llvm.load %29 : !llvm.ptr -> i64
    %31 = arith.constant 1 : i32
    %33 = arith.extsi %31 : i32 to i64
    %32 = arith.andi %30, %33 : i64
    %34 = arith.constant 0 : i32
    %36 = arith.extsi %34 : i32 to i64
    %35 = arith.cmpi eq, %32, %36 : i64
    cf.cond_br %35, ^bb7, ^bb8
    ^bb7:
      %37 = llvm.load %27 : !llvm.ptr -> i32
      %38 = arith.constant 1 : i32
      %39 = arith.addi %37, %38 : i32
      llvm.store %39, %27 : i32, !llvm.ptr
      %40 = llvm.load %29 : !llvm.ptr -> i64
      %41 = arith.constant 1 : i32
      %43 = arith.extsi %41 : i32 to i64
      %42 = arith.shrui %40, %43 : i64
      llvm.store %42, %29 : i64, !llvm.ptr
      cf.br ^bb6
    ^bb8:
    %44 = llvm.load %27 : !llvm.ptr -> i32
    func.return %44 : i32
  }
  func.func @bn_is_zero(%arg0: !llvm.ptr, %arg1: i32) -> i1 {
    %45 = arith.constant 0 : i32
    %46 = llvm.mlir.constant(1 : i64) : i64
    %47 = llvm.alloca %46 x i32 : (i64) -> !llvm.ptr
    llvm.store %45, %47 : i32, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %48 = llvm.load %47 : !llvm.ptr -> i32
    %49 = arith.cmpi slt, %48, %arg1 : i32
    cf.cond_br %49, ^bb10, ^bb11
    ^bb10:
      %51 = llvm.load %47 : !llvm.ptr -> i32
      %52 = arith.extsi %51 : i32 to i64
      %53 = llvm.getelementptr %arg0[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %50 = llvm.load %53 : !llvm.ptr -> i64
      %54 = arith.constant 0 : i32
      %56 = arith.extsi %54 : i32 to i64
      %55 = arith.cmpi ne, %50, %56 : i64
      cf.cond_br %55, ^bb12, ^bb13
      ^bb12:
        %57 = arith.constant 0 : i1
        func.return %57 : i1
      ^bb13:
        cf.br ^bb14
      ^bb14:
      %58 = llvm.load %47 : !llvm.ptr -> i32
      %59 = arith.constant 1 : i32
      %60 = arith.addi %58, %59 : i32
      llvm.store %60, %47 : i32, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %61 = arith.constant 1 : i1
    func.return %61 : i1
  }
  func.func @bn_v2(%arg0: !llvm.ptr, %arg1: i32) -> i32 {
    %62 = arith.constant 0 : i32
    %63 = llvm.mlir.constant(1 : i64) : i64
    %64 = llvm.alloca %63 x i32 : (i64) -> !llvm.ptr
    llvm.store %62, %64 : i32, !llvm.ptr
    cf.br ^bb15
    ^bb15:
    %65 = llvm.load %64 : !llvm.ptr -> i32
    %66 = arith.cmpi slt, %65, %arg1 : i32
    cf.cond_br %66, ^bb16, ^bb17
    ^bb16:
      %68 = llvm.load %64 : !llvm.ptr -> i32
      %69 = arith.extsi %68 : i32 to i64
      %70 = llvm.getelementptr %arg0[%69] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %67 = llvm.load %70 : !llvm.ptr -> i64
      %71 = arith.constant 0 : i32
      %73 = arith.extsi %71 : i32 to i64
      %72 = arith.cmpi ne, %67, %73 : i64
      cf.cond_br %72, ^bb18, ^bb19
      ^bb18:
        %74 = llvm.load %64 : !llvm.ptr -> i32
        %75 = arith.constant 64 : i32
        %76 = arith.muli %74, %75 : i32
        %79 = llvm.load %64 : !llvm.ptr -> i32
        %80 = arith.extsi %79 : i32 to i64
        %81 = llvm.getelementptr %arg0[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %78 = llvm.load %81 : !llvm.ptr -> i64
        %77 = func.call @ctz64(%78) : (i64) -> i32
        %82 = arith.addi %76, %77 : i32
        func.return %82 : i32
      ^bb19:
        cf.br ^bb20
      ^bb20:
      %83 = llvm.load %64 : !llvm.ptr -> i32
      %84 = arith.constant 1 : i32
      %85 = arith.addi %83, %84 : i32
      llvm.store %85, %64 : i32, !llvm.ptr
      cf.br ^bb15
    ^bb17:
    %86 = arith.constant 64 : i32
    %87 = arith.muli %arg1, %86 : i32
    func.return %87 : i32
  }
  func.func @bn_zero(%arg0: !llvm.ptr, %arg1: i32) -> () {
    %88 = arith.constant 0 : i32
    %89 = llvm.mlir.constant(1 : i64) : i64
    %90 = llvm.alloca %89 x i32 : (i64) -> !llvm.ptr
    llvm.store %88, %90 : i32, !llvm.ptr
    cf.br ^bb21
    ^bb21:
    %91 = llvm.load %90 : !llvm.ptr -> i32
    %92 = arith.cmpi slt, %91, %arg1 : i32
    cf.cond_br %92, ^bb22, ^bb23
    ^bb22:
      %93 = arith.constant 0 : i32
      %94 = llvm.load %90 : !llvm.ptr -> i32
      %95 = arith.extsi %93 : i32 to i64
      %96 = arith.extsi %94 : i32 to i64
      %97 = llvm.getelementptr %arg0[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %95, %97 : i64, !llvm.ptr
      %98 = llvm.load %90 : !llvm.ptr -> i32
      %99 = arith.constant 1 : i32
      %100 = arith.addi %98, %99 : i32
      llvm.store %100, %90 : i32, !llvm.ptr
      cf.br ^bb21
    ^bb23:
    func.return
  }
  func.func @bn_copy(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32) -> () {
    %101 = arith.constant 0 : i32
    %102 = llvm.mlir.constant(1 : i64) : i64
    %103 = llvm.alloca %102 x i32 : (i64) -> !llvm.ptr
    llvm.store %101, %103 : i32, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %104 = llvm.load %103 : !llvm.ptr -> i32
    %105 = arith.cmpi slt, %104, %arg2 : i32
    cf.cond_br %105, ^bb25, ^bb26
    ^bb25:
      %107 = llvm.load %103 : !llvm.ptr -> i32
      %108 = arith.extsi %107 : i32 to i64
      %109 = llvm.getelementptr %arg1[%108] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %106 = llvm.load %109 : !llvm.ptr -> i64
      %110 = llvm.load %103 : !llvm.ptr -> i32
      %111 = arith.extsi %110 : i32 to i64
      %112 = llvm.getelementptr %arg0[%111] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %106, %112 : i64, !llvm.ptr
      %113 = llvm.load %103 : !llvm.ptr -> i32
      %114 = arith.constant 1 : i32
      %115 = arith.addi %113, %114 : i32
      llvm.store %115, %103 : i32, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    func.return
  }
  func.func @bn_from_u64(%arg0: !llvm.ptr, %arg1: i64, %arg2: i32) -> () {
    func.call @bn_zero(%arg0, %arg2) : (!llvm.ptr, i32) -> ()
    %117 = arith.constant 0 : i32
    %118 = arith.extsi %117 : i32 to i64
    %119 = llvm.getelementptr %arg0[%118] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %arg1, %119 : i64, !llvm.ptr
    func.return
  }
  func.func @bn_from_i64(%arg0: !llvm.ptr, %arg1: i64, %arg2: i32) -> () {
    %120 = arith.constant 0 : i32
    %121 = arith.extsi %120 : i32 to i64
    %122 = arith.constant 0 : i32
    %124 = arith.extsi %122 : i32 to i64
    %123 = arith.cmpi slt, %arg1, %124 : i64
    %125 = scf.if %123 -> (i64) {
      %126 = arith.constant 1 : i32
      %128 = arith.extsi %126 : i32 to i64
      %127 = arith.subi %121, %128 : i64
      scf.yield %127 : i64
    } else {
      %129 = arith.constant 0 : i32
      scf.yield %129 : i32
    }
    %130 = arith.constant 1 : i32
    %131 = llvm.mlir.constant(1 : i64) : i64
    %132 = llvm.alloca %131 x i32 : (i64) -> !llvm.ptr
    llvm.store %130, %132 : i32, !llvm.ptr
    cf.br ^bb27
    ^bb27:
    %133 = llvm.load %132 : !llvm.ptr -> i32
    %134 = arith.cmpi slt, %133, %arg2 : i32
    cf.cond_br %134, ^bb28, ^bb29
    ^bb28:
      %135 = llvm.load %132 : !llvm.ptr -> i32
      %136 = arith.extsi %135 : i32 to i64
      %137 = llvm.getelementptr %arg0[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %125, %137 : i64, !llvm.ptr
      %138 = llvm.load %132 : !llvm.ptr -> i32
      %139 = arith.constant 1 : i32
      %140 = arith.addi %138, %139 : i32
      llvm.store %140, %132 : i32, !llvm.ptr
      cf.br ^bb27
    ^bb29:
    %141 = arith.constant 0 : i32
    %142 = arith.extsi %141 : i32 to i64
    %143 = llvm.getelementptr %arg0[%142] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %arg1, %143 : i64, !llvm.ptr
    func.return
  }
  func.func @bn_add(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i32) -> () {
    %144 = arith.constant 0 : i32
    %145 = arith.extsi %144 : i32 to i64
    %146 = llvm.mlir.constant(1 : i64) : i64
    %147 = llvm.alloca %146 x i64 : (i64) -> !llvm.ptr
    llvm.store %145, %147 : i64, !llvm.ptr
    %148 = arith.constant 0 : i32
    %149 = llvm.mlir.constant(1 : i64) : i64
    %150 = llvm.alloca %149 x i32 : (i64) -> !llvm.ptr
    llvm.store %148, %150 : i32, !llvm.ptr
    cf.br ^bb30
    ^bb30:
    %151 = llvm.load %150 : !llvm.ptr -> i32
    %152 = arith.cmpi slt, %151, %arg3 : i32
    cf.cond_br %152, ^bb31, ^bb32
    ^bb31:
      %154 = llvm.load %150 : !llvm.ptr -> i32
      %155 = arith.extsi %154 : i32 to i64
      %156 = llvm.getelementptr %arg1[%155] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %153 = llvm.load %156 : !llvm.ptr -> i64
      %157 = arith.extui %153 : i64 to i128
      %159 = llvm.load %150 : !llvm.ptr -> i32
      %160 = arith.extsi %159 : i32 to i64
      %161 = llvm.getelementptr %arg2[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %158 = llvm.load %161 : !llvm.ptr -> i64
      %162 = arith.extui %158 : i64 to i128
      %164 = arith.trunci %157 : i128 to i64
      %165 = arith.trunci %162 : i128 to i64
      %163 = arith.addi %164, %165 : i64
      %166 = llvm.load %147 : !llvm.ptr -> i64
      %167 = arith.extui %166 : i64 to i128
      %169 = arith.trunci %167 : i128 to i64
      %168 = arith.addi %163, %169 : i64
      %170 = arith.extsi %168 : i64 to i128
      %171 = arith.trunci %170 : i128 to i64
      %172 = llvm.load %150 : !llvm.ptr -> i32
      %173 = arith.extsi %172 : i32 to i64
      %174 = llvm.getelementptr %arg0[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %171, %174 : i64, !llvm.ptr
      %175 = arith.constant 64 : i32
      %177 = arith.trunci %170 : i128 to i64
      %178 = arith.extsi %175 : i32 to i64
      %176 = arith.shrsi %177, %178 : i64
      llvm.store %176, %147 : i64, !llvm.ptr
      %179 = llvm.load %150 : !llvm.ptr -> i32
      %180 = arith.constant 1 : i32
      %181 = arith.addi %179, %180 : i32
      llvm.store %181, %150 : i32, !llvm.ptr
      cf.br ^bb30
    ^bb32:
    func.return
  }
  func.func @bn_shl(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: i32) -> () {
    %182 = arith.constant 0 : i32
    %183 = arith.cmpi sle, %arg2, %182 : i32
    cf.cond_br %183, ^bb33, ^bb34
    ^bb33:
      func.call @bn_copy(%arg0, %arg1, %arg3) : (!llvm.ptr, !llvm.ptr, i32) -> ()
      func.return
    ^bb34:
      cf.br ^bb35
    ^bb35:
    %185 = arith.constant 64 : i32
    %186 = arith.muli %arg3, %185 : i32
    %187 = arith.cmpi sge, %arg2, %186 : i32
    cf.cond_br %187, ^bb36, ^bb37
    ^bb36:
      func.call @bn_zero(%arg0, %arg3) : (!llvm.ptr, i32) -> ()
      func.return
    ^bb37:
      cf.br ^bb38
    ^bb38:
    %189 = arith.constant 64 : i32
    %190 = arith.divsi %arg2, %189 : i32
    %191 = arith.constant 64 : i32
    %192 = arith.remsi %arg2, %191 : i32
    func.call @bn_zero(%arg0, %arg3) : (!llvm.ptr, i32) -> ()
    %194 = arith.constant 0 : i32
    %195 = arith.cmpi eq, %192, %194 : i32
    cf.cond_br %195, ^bb39, ^bb40
    ^bb39:
      %196 = arith.constant 1 : i32
      %197 = arith.subi %arg3, %196 : i32
      %198 = llvm.mlir.constant(1 : i64) : i64
      %199 = llvm.alloca %198 x i32 : (i64) -> !llvm.ptr
      llvm.store %197, %199 : i32, !llvm.ptr
      cf.br ^bb42
      ^bb42:
      %200 = llvm.load %199 : !llvm.ptr -> i32
      %201 = arith.cmpi sge, %200, %190 : i32
      cf.cond_br %201, ^bb43, ^bb44
      ^bb43:
        %203 = llvm.load %199 : !llvm.ptr -> i32
        %204 = arith.subi %203, %190 : i32
        %205 = arith.extsi %204 : i32 to i64
        %206 = llvm.getelementptr %arg1[%205] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %202 = llvm.load %206 : !llvm.ptr -> i64
        %207 = llvm.load %199 : !llvm.ptr -> i32
        %208 = arith.extsi %207 : i32 to i64
        %209 = llvm.getelementptr %arg0[%208] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %202, %209 : i64, !llvm.ptr
        %210 = llvm.load %199 : !llvm.ptr -> i32
        %211 = arith.constant 1 : i32
        %212 = arith.subi %210, %211 : i32
        llvm.store %212, %199 : i32, !llvm.ptr
        cf.br ^bb42
      ^bb44:
      cf.br ^bb41
    ^bb40:
      %213 = arith.constant 1 : i32
      %214 = arith.subi %arg3, %213 : i32
      %215 = llvm.mlir.constant(1 : i64) : i64
      %216 = llvm.alloca %215 x i32 : (i64) -> !llvm.ptr
      llvm.store %214, %216 : i32, !llvm.ptr
      cf.br ^bb45
      ^bb45:
      %217 = llvm.load %216 : !llvm.ptr -> i32
      %218 = arith.cmpi sge, %217, %190 : i32
      cf.cond_br %218, ^bb46, ^bb47
      ^bb46:
        %220 = llvm.load %216 : !llvm.ptr -> i32
        %221 = arith.subi %220, %190 : i32
        %222 = arith.extsi %221 : i32 to i64
        %223 = llvm.getelementptr %arg1[%222] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %219 = llvm.load %223 : !llvm.ptr -> i64
        %225 = arith.extsi %192 : i32 to i64
        %224 = arith.shli %219, %225 : i64
        %226 = llvm.load %216 : !llvm.ptr -> i32
        %227 = arith.subi %226, %190 : i32
        %228 = arith.constant 1 : i32
        %229 = arith.subi %227, %228 : i32
        %230 = arith.constant 0 : i32
        %231 = arith.cmpi sge, %229, %230 : i32
        %232 = scf.if %231 -> (i64) {
          %234 = llvm.load %216 : !llvm.ptr -> i32
          %235 = arith.subi %234, %190 : i32
          %236 = arith.constant 1 : i32
          %237 = arith.subi %235, %236 : i32
          %238 = arith.extsi %237 : i32 to i64
          %239 = llvm.getelementptr %arg1[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %233 = llvm.load %239 : !llvm.ptr -> i64
          %240 = arith.constant 64 : i32
          %241 = arith.subi %240, %192 : i32
          %243 = arith.extsi %241 : i32 to i64
          %242 = arith.shrui %233, %243 : i64
          scf.yield %242 : i64
        } else {
          %244 = arith.constant 0 : i32
          scf.yield %244 : i32
        }
        %245 = arith.ori %224, %232 : i64
        %246 = llvm.load %216 : !llvm.ptr -> i32
        %247 = arith.extsi %246 : i32 to i64
        %248 = llvm.getelementptr %arg0[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %245, %248 : i64, !llvm.ptr
        %249 = llvm.load %216 : !llvm.ptr -> i32
        %250 = arith.constant 1 : i32
        %251 = arith.subi %249, %250 : i32
        llvm.store %251, %216 : i32, !llvm.ptr
        cf.br ^bb45
      ^bb47:
      cf.br ^bb41
    ^bb41:
    func.return
  }
  func.func @bn_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i32) -> () {
    %253 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %254 = llvm.load %253 : !llvm.ptr -> i32
    %255 = arith.extsi %254 : i32 to i64
    %256 = arith.constant 8 : i32
    %257 = arith.extsi %256 : i32 to i64
    %252 = func.call @calloc(%255, %257) : (i64, i64) -> !llvm.ptr
    %258 = arith.constant 0 : i32
    %259 = llvm.mlir.constant(1 : i64) : i64
    %260 = llvm.alloca %259 x i32 : (i64) -> !llvm.ptr
    llvm.store %258, %260 : i32, !llvm.ptr
    cf.br ^bb48
    ^bb48:
    %261 = llvm.load %260 : !llvm.ptr -> i32
    %262 = arith.cmpi slt, %261, %arg3 : i32
    cf.cond_br %262, ^bb49, ^bb50
    ^bb49:
      %263 = arith.constant 0 : i32
      %264 = arith.extsi %263 : i32 to i64
      %265 = llvm.mlir.constant(1 : i64) : i64
      %266 = llvm.alloca %265 x i64 : (i64) -> !llvm.ptr
      llvm.store %264, %266 : i64, !llvm.ptr
      %267 = arith.constant 0 : i32
      %268 = llvm.mlir.constant(1 : i64) : i64
      %269 = llvm.alloca %268 x i32 : (i64) -> !llvm.ptr
      llvm.store %267, %269 : i32, !llvm.ptr
      cf.br ^bb51
      ^bb51:
      %270 = llvm.load %269 : !llvm.ptr -> i32
      %271 = llvm.load %260 : !llvm.ptr -> i32
      %272 = arith.subi %arg3, %271 : i32
      %273 = arith.cmpi slt, %270, %272 : i32
      cf.cond_br %273, ^bb52, ^bb53
      ^bb52:
        %275 = llvm.load %260 : !llvm.ptr -> i32
        %276 = arith.extsi %275 : i32 to i64
        %277 = llvm.getelementptr %arg1[%276] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %274 = llvm.load %277 : !llvm.ptr -> i64
        %278 = arith.extui %274 : i64 to i128
        %280 = llvm.load %269 : !llvm.ptr -> i32
        %281 = arith.extsi %280 : i32 to i64
        %282 = llvm.getelementptr %arg2[%281] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %279 = llvm.load %282 : !llvm.ptr -> i64
        %283 = arith.extui %279 : i64 to i128
        %285 = arith.trunci %278 : i128 to i64
        %286 = arith.trunci %283 : i128 to i64
        %284 = arith.muli %285, %286 : i64
        %288 = llvm.load %260 : !llvm.ptr -> i32
        %289 = llvm.load %269 : !llvm.ptr -> i32
        %290 = arith.addi %288, %289 : i32
        %291 = arith.extsi %290 : i32 to i64
        %292 = llvm.getelementptr %252[%291] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %287 = llvm.load %292 : !llvm.ptr -> i64
        %293 = arith.extui %287 : i64 to i128
        %295 = arith.trunci %293 : i128 to i64
        %294 = arith.addi %284, %295 : i64
        %296 = llvm.load %266 : !llvm.ptr -> i64
        %297 = arith.extui %296 : i64 to i128
        %299 = arith.trunci %297 : i128 to i64
        %298 = arith.addi %294, %299 : i64
        %300 = arith.extsi %298 : i64 to i128
        %301 = arith.trunci %300 : i128 to i64
        %302 = llvm.load %260 : !llvm.ptr -> i32
        %303 = llvm.load %269 : !llvm.ptr -> i32
        %304 = arith.addi %302, %303 : i32
        %305 = arith.extsi %304 : i32 to i64
        %306 = llvm.getelementptr %252[%305] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %301, %306 : i64, !llvm.ptr
        %307 = arith.constant 64 : i32
        %309 = arith.trunci %300 : i128 to i64
        %310 = arith.extsi %307 : i32 to i64
        %308 = arith.shrsi %309, %310 : i64
        llvm.store %308, %266 : i64, !llvm.ptr
        %311 = llvm.load %269 : !llvm.ptr -> i32
        %312 = arith.constant 1 : i32
        %313 = arith.addi %311, %312 : i32
        llvm.store %313, %269 : i32, !llvm.ptr
        cf.br ^bb51
      ^bb53:
      %314 = llvm.load %260 : !llvm.ptr -> i32
      %315 = arith.constant 1 : i32
      %316 = arith.addi %314, %315 : i32
      llvm.store %316, %260 : i32, !llvm.ptr
      cf.br ^bb48
    ^bb50:
    func.call @bn_copy(%arg0, %252, %arg3) : (!llvm.ptr, !llvm.ptr, i32) -> ()
    func.call @free(%252) : (!llvm.ptr) -> ()
    func.return
  }
  func.func @bn_inv_odd(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32) -> () {
    %320 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %321 = llvm.load %320 : !llvm.ptr -> i32
    %322 = arith.extsi %321 : i32 to i64
    %323 = arith.constant 8 : i32
    %324 = arith.extsi %323 : i32 to i64
    %319 = func.call @calloc(%322, %324) : (i64, i64) -> !llvm.ptr
    %326 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %327 = llvm.load %326 : !llvm.ptr -> i32
    %328 = arith.extsi %327 : i32 to i64
    %329 = arith.constant 8 : i32
    %330 = arith.extsi %329 : i32 to i64
    %325 = func.call @calloc(%328, %330) : (i64, i64) -> !llvm.ptr
    %332 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %333 = llvm.load %332 : !llvm.ptr -> i32
    %334 = arith.extsi %333 : i32 to i64
    %335 = arith.constant 8 : i32
    %336 = arith.extsi %335 : i32 to i64
    %331 = func.call @calloc(%334, %336) : (i64, i64) -> !llvm.ptr
    %338 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %339 = llvm.load %338 : !llvm.ptr -> i32
    %340 = arith.extsi %339 : i32 to i64
    %341 = arith.constant 8 : i32
    %342 = arith.extsi %341 : i32 to i64
    %337 = func.call @calloc(%340, %342) : (i64, i64) -> !llvm.ptr
    %344 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %345 = llvm.load %344 : !llvm.ptr -> i32
    %346 = arith.extsi %345 : i32 to i64
    %347 = arith.constant 8 : i32
    %348 = arith.extsi %347 : i32 to i64
    %343 = func.call @calloc(%346, %348) : (i64, i64) -> !llvm.ptr
    %350 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %351 = llvm.load %350 : !llvm.ptr -> i32
    %352 = arith.extsi %351 : i32 to i64
    %353 = arith.constant 8 : i32
    %354 = arith.extsi %353 : i32 to i64
    %349 = func.call @calloc(%352, %354) : (i64, i64) -> !llvm.ptr
    %355 = arith.constant 0 : i32
    %356 = arith.extsi %355 : i32 to i64
    %357 = arith.constant 1 : i32
    %359 = arith.extsi %357 : i32 to i64
    %358 = arith.subi %356, %359 : i64
    %361 = arith.constant 1 : i32
    %362 = arith.extsi %361 : i32 to i64
    func.call @bn_from_u64(%319, %362, %arg2) : (!llvm.ptr, i64, i32) -> ()
    %364 = arith.constant 2 : i32
    %365 = arith.extsi %364 : i32 to i64
    func.call @bn_from_u64(%331, %365, %arg2) : (!llvm.ptr, i64, i32) -> ()
    %366 = arith.constant 64 : i32
    %367 = arith.muli %arg2, %366 : i32
    %368 = arith.constant 0 : i32
    %369 = llvm.mlir.constant(1 : i64) : i64
    %370 = llvm.alloca %369 x i32 : (i64) -> !llvm.ptr
    llvm.store %368, %370 : i32, !llvm.ptr
    cf.br ^bb54
    ^bb54:
    %371 = arith.constant 1 : i32
    %372 = llvm.load %370 : !llvm.ptr -> i32
    %373 = arith.shli %371, %372 : i32
    %374 = arith.cmpi slt, %373, %367 : i32
    cf.cond_br %374, ^bb55, ^bb56
    ^bb55:
      func.call @bn_mul(%337, %arg1, %319, %arg2) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      %376 = arith.constant 0 : i32
      %377 = llvm.mlir.constant(1 : i64) : i64
      %378 = llvm.alloca %377 x i32 : (i64) -> !llvm.ptr
      llvm.store %376, %378 : i32, !llvm.ptr
      cf.br ^bb57
      ^bb57:
      %379 = llvm.load %378 : !llvm.ptr -> i32
      %380 = arith.cmpi slt, %379, %arg2 : i32
      cf.cond_br %380, ^bb58, ^bb59
      ^bb58:
        %382 = llvm.load %378 : !llvm.ptr -> i32
        %383 = arith.extsi %382 : i32 to i64
        %384 = llvm.getelementptr %337[%383] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %381 = llvm.load %384 : !llvm.ptr -> i64
        %385 = arith.xori %358, %381 : i64
        %386 = llvm.load %378 : !llvm.ptr -> i32
        %387 = arith.extsi %386 : i32 to i64
        %388 = llvm.getelementptr %349[%387] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %385, %388 : i64, !llvm.ptr
        %389 = llvm.load %378 : !llvm.ptr -> i32
        %390 = arith.constant 1 : i32
        %391 = arith.addi %389, %390 : i32
        llvm.store %391, %378 : i32, !llvm.ptr
        cf.br ^bb57
      ^bb59:
      %392 = arith.constant 1 : i32
      %393 = arith.extsi %392 : i32 to i64
      %394 = llvm.mlir.constant(1 : i64) : i64
      %395 = llvm.alloca %394 x i64 : (i64) -> !llvm.ptr
      llvm.store %393, %395 : i64, !llvm.ptr
      %396 = arith.constant 0 : i32
      llvm.store %396, %378 : i32, !llvm.ptr
      cf.br ^bb60
      ^bb60:
      %397 = llvm.load %378 : !llvm.ptr -> i32
      %398 = arith.cmpi slt, %397, %arg2 : i32
      %399 = scf.if %398 -> (i1) {
        %400 = llvm.load %395 : !llvm.ptr -> i64
        %401 = arith.constant 0 : i32
        %403 = arith.extsi %401 : i32 to i64
        %402 = arith.cmpi ne, %400, %403 : i64
        scf.yield %402 : i1
      } else {
        %404 = arith.constant false
        scf.yield %404 : i1
      }
      cf.cond_br %399, ^bb61, ^bb62
      ^bb61:
        %406 = llvm.load %378 : !llvm.ptr -> i32
        %407 = arith.extsi %406 : i32 to i64
        %408 = llvm.getelementptr %349[%407] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %405 = llvm.load %408 : !llvm.ptr -> i64
        %409 = arith.extui %405 : i64 to i128
        %410 = llvm.load %395 : !llvm.ptr -> i64
        %411 = arith.extui %410 : i64 to i128
        %413 = arith.trunci %409 : i128 to i64
        %414 = arith.trunci %411 : i128 to i64
        %412 = arith.addi %413, %414 : i64
        %415 = arith.extsi %412 : i64 to i128
        %416 = arith.trunci %415 : i128 to i64
        %417 = llvm.load %378 : !llvm.ptr -> i32
        %418 = arith.extsi %417 : i32 to i64
        %419 = llvm.getelementptr %349[%418] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %416, %419 : i64, !llvm.ptr
        %420 = arith.constant 64 : i32
        %422 = arith.trunci %415 : i128 to i64
        %423 = arith.extsi %420 : i32 to i64
        %421 = arith.shrsi %422, %423 : i64
        llvm.store %421, %395 : i64, !llvm.ptr
        %424 = llvm.load %378 : !llvm.ptr -> i32
        %425 = arith.constant 1 : i32
        %426 = arith.addi %424, %425 : i32
        llvm.store %426, %378 : i32, !llvm.ptr
        cf.br ^bb60
      ^bb62:
      func.call @bn_add(%343, %349, %331, %arg2) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      func.call @bn_mul(%325, %319, %343, %arg2) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
      func.call @bn_copy(%319, %325, %arg2) : (!llvm.ptr, !llvm.ptr, i32) -> ()
      %430 = llvm.load %370 : !llvm.ptr -> i32
      %431 = arith.constant 1 : i32
      %432 = arith.addi %430, %431 : i32
      llvm.store %432, %370 : i32, !llvm.ptr
      cf.br ^bb54
    ^bb56:
    func.call @bn_copy(%arg0, %319, %arg2) : (!llvm.ptr, !llvm.ptr, i32) -> ()
    func.call @free(%319) : (!llvm.ptr) -> ()
    func.call @free(%325) : (!llvm.ptr) -> ()
    func.call @free(%331) : (!llvm.ptr) -> ()
    func.call @free(%337) : (!llvm.ptr) -> ()
    func.call @free(%343) : (!llvm.ptr) -> ()
    func.call @free(%349) : (!llvm.ptr) -> ()
    func.return
  }
  // Module static: inv_key
  llvm.mlir.global internal @inv_key() {addr_space = 0 : i32} : !llvm.ptr {
    %440 = llvm.mlir.zero : !llvm.ptr
    llvm.return %440 : !llvm.ptr
  }
  // Module static: inv_val
  llvm.mlir.global internal @inv_val() {addr_space = 0 : i32} : !llvm.ptr {
    %441 = llvm.mlir.zero : !llvm.ptr
    llvm.return %441 : !llvm.ptr
  }
  // Module static: inv_cache_n
  llvm.mlir.global internal @inv_cache_n(0 : i32) : i32
  func.func @inv_odd(%arg0: i64, %arg1: i32) -> i32 {
    %442 = arith.constant 0 : i32
    %443 = llvm.mlir.constant(1 : i64) : i64
    %444 = llvm.alloca %443 x i32 : (i64) -> !llvm.ptr
    llvm.store %442, %444 : i32, !llvm.ptr
    cf.br ^bb63
    ^bb63:
    %445 = llvm.load %444 : !llvm.ptr -> i32
    %446 = llvm.mlir.addressof @inv_cache_n : !llvm.ptr
    %447 = llvm.load %446 : !llvm.ptr -> i32
    %448 = arith.cmpi slt, %445, %447 : i32
    cf.cond_br %448, ^bb64, ^bb65
    ^bb64:
      %450 = llvm.mlir.addressof @inv_key : !llvm.ptr
      %451 = llvm.load %450 : !llvm.ptr -> !llvm.ptr
      %452 = llvm.load %444 : !llvm.ptr -> i32
      %453 = arith.extsi %452 : i32 to i64
      %454 = llvm.getelementptr %451[%453] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %449 = llvm.load %454 : !llvm.ptr -> i64
      %455 = arith.cmpi eq, %449, %arg0 : i64
      cf.cond_br %455, ^bb66, ^bb67
      ^bb66:
        %456 = llvm.load %444 : !llvm.ptr -> i32
        func.return %456 : i32
      ^bb67:
        cf.br ^bb68
      ^bb68:
      %457 = llvm.load %444 : !llvm.ptr -> i32
      %458 = arith.constant 1 : i32
      %459 = arith.addi %457, %458 : i32
      llvm.store %459, %444 : i32, !llvm.ptr
      cf.br ^bb63
    ^bb65:
    %461 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %462 = llvm.load %461 : !llvm.ptr -> i32
    %463 = arith.extsi %462 : i32 to i64
    %464 = arith.constant 8 : i32
    %465 = arith.extsi %464 : i32 to i64
    %460 = func.call @calloc(%463, %465) : (i64, i64) -> !llvm.ptr
    func.call @bn_from_u64(%460, %arg0, %arg1) : (!llvm.ptr, i64, i32) -> ()
    %467 = llvm.mlir.addressof @inv_cache_n : !llvm.ptr
    %468 = llvm.load %467 : !llvm.ptr -> i32
    # String concatenation: !llvm.ptr + i64
    func.call @bn_inv_odd(%470, %460, %arg1) : (!llvm.ptr, !llvm.ptr, i32) -> ()
    %471 = llvm.mlir.addressof @inv_key : !llvm.ptr
    %472 = llvm.load %471 : !llvm.ptr -> !llvm.ptr
    %473 = arith.extsi %468 : i32 to i64
    %474 = llvm.getelementptr %472[%473] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %arg0, %474 : i64, !llvm.ptr
    %475 = llvm.mlir.addressof @inv_cache_n : !llvm.ptr
    %476 = llvm.load %475 : !llvm.ptr -> i32
    %477 = arith.constant 1 : i32
    %478 = arith.addi %476, %477 : i32
    %479 = llvm.mlir.addressof @inv_cache_n : !llvm.ptr
    llvm.store %478, %479 : i32, !llvm.ptr
    func.call @free(%460) : (!llvm.ptr) -> ()
    func.return %468 : i32
  }
  func.func @u_of(%arg0: i64) -> i64 {
    %482 = arith.constant 4 : i32
    %483 = arith.constant 4 : i32
    %484 = arith.extsi %482 : i32 to i64
    %485 = arith.extsi %483 : i32 to i64
    %481 = func.call @calloc(%484, %485) : (i64, i64) -> !llvm.ptr
    %486 = arith.constant 256 : i32
    %487 = arith.constant 0 : i32
    %488 = arith.extsi %487 : i32 to i64
    %489 = llvm.getelementptr %481[%488] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %486, %489 : i32, !llvm.ptr
    %490 = arith.constant 512 : i32
    %491 = arith.constant 1 : i32
    %492 = arith.extsi %491 : i32 to i64
    %493 = llvm.getelementptr %481[%492] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %490, %493 : i32, !llvm.ptr
    %494 = arith.constant 1024 : i32
    %495 = arith.constant 2 : i32
    %496 = arith.extsi %495 : i32 to i64
    %497 = llvm.getelementptr %481[%496] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %494, %497 : i32, !llvm.ptr
    %498 = arith.constant 2048 : i32
    %499 = arith.constant 3 : i32
    %500 = arith.extsi %499 : i32 to i64
    %501 = llvm.getelementptr %481[%500] : (!llvm.ptr, i64) -> !llvm.ptr, i32
    llvm.store %498, %501 : i32, !llvm.ptr
    %503 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %504 = llvm.load %503 : !llvm.ptr -> i32
    %505 = arith.extsi %504 : i32 to i64
    %506 = arith.constant 8 : i32
    %507 = arith.extsi %506 : i32 to i64
    %502 = func.call @calloc(%505, %507) : (i64, i64) -> !llvm.ptr
    %509 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %510 = llvm.load %509 : !llvm.ptr -> i32
    %511 = arith.extsi %510 : i32 to i64
    %512 = arith.constant 8 : i32
    %513 = arith.extsi %512 : i32 to i64
    %508 = func.call @calloc(%511, %513) : (i64, i64) -> !llvm.ptr
    %515 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %516 = llvm.load %515 : !llvm.ptr -> i32
    %517 = arith.extsi %516 : i32 to i64
    %518 = arith.constant 8 : i32
    %519 = arith.extsi %518 : i32 to i64
    %514 = func.call @calloc(%517, %519) : (i64, i64) -> !llvm.ptr
    %521 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %522 = llvm.load %521 : !llvm.ptr -> i32
    %523 = arith.extsi %522 : i32 to i64
    %524 = arith.constant 8 : i32
    %525 = arith.extsi %524 : i32 to i64
    %520 = func.call @calloc(%523, %525) : (i64, i64) -> !llvm.ptr
    %527 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %528 = llvm.load %527 : !llvm.ptr -> i32
    %529 = arith.extsi %528 : i32 to i64
    %530 = arith.constant 8 : i32
    %531 = arith.extsi %530 : i32 to i64
    %526 = func.call @calloc(%529, %531) : (i64, i64) -> !llvm.ptr
    %533 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %534 = llvm.load %533 : !llvm.ptr -> i32
    %535 = arith.extsi %534 : i32 to i64
    %536 = arith.constant 8 : i32
    %537 = arith.extsi %536 : i32 to i64
    %532 = func.call @calloc(%535, %537) : (i64, i64) -> !llvm.ptr
    %538 = arith.constant 0 : i32
    %539 = llvm.mlir.constant(1 : i64) : i64
    %540 = llvm.alloca %539 x i32 : (i64) -> !llvm.ptr
    llvm.store %538, %540 : i32, !llvm.ptr
    cf.br ^bb69
    ^bb69:
    %541 = llvm.load %540 : !llvm.ptr -> i32
    %542 = arith.constant 4 : i32
    %543 = arith.cmpi slt, %541, %542 : i32
    cf.cond_br %543, ^bb70, ^bb71
    ^bb70:
      %545 = llvm.load %540 : !llvm.ptr -> i32
      %546 = arith.extsi %545 : i32 to i64
      %547 = llvm.getelementptr %481[%546] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %544 = llvm.load %547 : !llvm.ptr -> i32
      %548 = arith.constant 64 : i32
      %549 = arith.divsi %544, %548 : i32
      %550 = arith.constant 0 : i32
      %551 = llvm.mlir.addressof @inv_cache_n : !llvm.ptr
      llvm.store %550, %551 : i32, !llvm.ptr
      %552 = arith.constant 1 : i32
      %554 = arith.extsi %552 : i32 to i64
      %553 = arith.addi %arg0, %554 : i64
      %555 = llvm.mlir.constant(1 : i64) : i64
      %556 = llvm.alloca %555 x i64 : (i64) -> !llvm.ptr
      llvm.store %553, %556 : i64, !llvm.ptr
      %557 = llvm.load %556 : !llvm.ptr -> i64
      %559 = llvm.load %556 : !llvm.ptr -> i64
      %558 = func.call @popcount64(%559) : (i64) -> i64
      %560 = arith.addi %557, %558 : i64
      %561 = llvm.mlir.constant(1 : i64) : i64
      %562 = llvm.alloca %561 x i64 : (i64) -> !llvm.ptr
      llvm.store %560, %562 : i64, !llvm.ptr
      %564 = arith.constant 1 : i32
      %565 = arith.extsi %564 : i32 to i64
      func.call @bn_from_u64(%502, %565, %549) : (!llvm.ptr, i64, i32) -> ()
      %566 = arith.constant 0 : i1
      %567 = llvm.mlir.constant(1 : i64) : i64
      %568 = llvm.alloca %567 x i1 : (i64) -> !llvm.ptr
      llvm.store %566, %568 : i1, !llvm.ptr
      %569 = arith.constant 0 : i32
      %570 = arith.extsi %569 : i32 to i64
      %571 = llvm.mlir.constant(1 : i64) : i64
      %572 = llvm.alloca %571 x i64 : (i64) -> !llvm.ptr
      llvm.store %570, %572 : i64, !llvm.ptr
      func.call @bn_zero(%508, %549) : (!llvm.ptr, i32) -> ()
      %574 = arith.constant 1 : i32
      %575 = llvm.mlir.constant(1 : i64) : i64
      %576 = llvm.alloca %575 x i32 : (i64) -> !llvm.ptr
      llvm.store %574, %576 : i32, !llvm.ptr
      cf.br ^bb72
      ^bb72:
      %577 = llvm.load %576 : !llvm.ptr -> i32
      %578 = arith.constant 220 : i32
      %579 = arith.cmpi sle, %577, %578 : i32
      cf.cond_br %579, ^bb73, ^bb74
      ^bb73:
        %580 = llvm.load %568 : !llvm.ptr -> i1
        %582 = arith.constant 1 : i1
        %581 = arith.xori %580, %582 : i1
        cf.cond_br %581, ^bb75, ^bb76
        ^bb75:
          %584 = llvm.load %562 : !llvm.ptr -> i64
          llvm.store %584, %572 : i64, !llvm.ptr
          func.call @bn_copy(%508, %502, %549) : (!llvm.ptr, !llvm.ptr, i32) -> ()
          %586 = arith.constant 1 : i1
          llvm.store %586, %568 : i1, !llvm.ptr
          cf.br ^bb77
        ^bb76:
          %587 = llvm.load %562 : !llvm.ptr -> i64
          %588 = llvm.load %572 : !llvm.ptr -> i64
          %589 = arith.cmpi slt, %587, %588 : i64
          cf.cond_br %589, ^bb78, ^bb79
          ^bb78:
            %590 = llvm.load %572 : !llvm.ptr -> i64
            %591 = llvm.load %562 : !llvm.ptr -> i64
            %592 = arith.subi %590, %591 : i64
            %593 = arith.extsi %544 : i32 to i64
            %594 = arith.cmpi slt, %592, %593 : i64
            cf.cond_br %594, ^bb81, ^bb82
            ^bb81:
              %596 = arith.trunci %592 : i64 to i32
              func.call @bn_shl(%508, %508, %596, %549) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
              cf.br ^bb83
            ^bb82:
              func.call @bn_zero(%508, %549) : (!llvm.ptr, i32) -> ()
              cf.br ^bb83
            ^bb83:
            %598 = llvm.load %562 : !llvm.ptr -> i64
            llvm.store %598, %572 : i64, !llvm.ptr
            func.call @bn_add(%508, %508, %502, %549) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
            cf.br ^bb80
          ^bb79:
            %600 = llvm.load %562 : !llvm.ptr -> i64
            %601 = llvm.load %572 : !llvm.ptr -> i64
            %602 = arith.subi %600, %601 : i64
            %603 = arith.extsi %544 : i32 to i64
            %604 = arith.cmpi slt, %602, %603 : i64
            cf.cond_br %604, ^bb84, ^bb85
            ^bb84:
              %606 = arith.trunci %602 : i64 to i32
              func.call @bn_shl(%514, %502, %606, %549) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
              func.call @bn_add(%508, %508, %514, %549) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
              cf.br ^bb86
            ^bb85:
              cf.br ^bb86
            ^bb86:
            cf.br ^bb80
          ^bb80:
          cf.br ^bb77
        ^bb77:
        %608 = func.call @bn_is_zero(%508, %549) : (!llvm.ptr, i32) -> i1
        cf.cond_br %608, ^bb87, ^bb88
        ^bb87:
          cf.br ^bb74
        ^bb88:
          cf.br ^bb89
        ^bb89:
        %609 = llvm.load %572 : !llvm.ptr -> i64
        %610 = func.call @bn_v2(%508, %549) : (!llvm.ptr, i32) -> i32
        %611 = arith.extsi %610 : i32 to i64
        %612 = arith.addi %609, %611 : i64
        %613 = llvm.load %576 : !llvm.ptr -> i32
        %614 = arith.extsi %613 : i32 to i64
        %615 = arith.addi %arg0, %614 : i64
        %616 = arith.constant 1 : i32
        %618 = arith.extsi %616 : i32 to i64
        %617 = arith.addi %615, %618 : i64
        %619 = arith.cmpi slt, %612, %617 : i64
        cf.cond_br %619, ^bb90, ^bb91
        ^bb90:
          func.call @free(%481) : (!llvm.ptr) -> ()
          func.call @free(%502) : (!llvm.ptr) -> ()
          func.call @free(%508) : (!llvm.ptr) -> ()
          func.call @free(%514) : (!llvm.ptr) -> ()
          func.call @free(%520) : (!llvm.ptr) -> ()
          func.call @free(%526) : (!llvm.ptr) -> ()
          func.call @free(%532) : (!llvm.ptr) -> ()
          func.return %612 : i64
        ^bb91:
          cf.br ^bb92
        ^bb92:
        %627 = llvm.load %556 : !llvm.ptr -> i64
        %628 = arith.constant 1 : i32
        %630 = arith.extsi %628 : i32 to i64
        %629 = arith.addi %627, %630 : i64
        %631 = func.call @ctz64(%629) : (i64) -> i32
        %633 = arith.extsi %631 : i32 to i64
        %632 = arith.shrui %629, %633 : i64
        %634 = func.call @inv_odd(%632, %549) : (i64, i32) -> i32
        # String concatenation: !llvm.ptr + i64
        %637 = arith.constant 2 : i32
        %638 = llvm.load %556 : !llvm.ptr -> i64
        %640 = arith.extsi %637 : i32 to i64
        %639 = arith.muli %640, %638 : i64
        %641 = arith.constant 1 : i32
        %643 = arith.extsi %641 : i32 to i64
        %642 = arith.addi %639, %643 : i64
        %645 = arith.constant 0 : i64
        %644 = arith.subi %645, %642 : i64
        func.call @bn_from_i64(%532, %644, %549) : (!llvm.ptr, i64, i32) -> ()
        func.call @bn_mul(%520, %532, %635, %549) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
        func.call @bn_mul(%526, %502, %520, %549) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i32) -> ()
        func.call @bn_copy(%502, %526, %549) : (!llvm.ptr, !llvm.ptr, i32) -> ()
        %649 = llvm.load %562 : !llvm.ptr -> i64
        %650 = arith.constant 2 : i32
        %652 = arith.extsi %650 : i32 to i64
        %651 = arith.addi %649, %652 : i64
        %653 = arith.extsi %631 : i32 to i64
        %654 = arith.subi %651, %653 : i64
        llvm.store %654, %562 : i64, !llvm.ptr
        llvm.store %629, %556 : i64, !llvm.ptr
        %655 = llvm.load %562 : !llvm.ptr -> i64
        %656 = llvm.load %556 : !llvm.ptr -> i64
        %658 = llvm.load %556 : !llvm.ptr -> i64
        %657 = func.call @popcount64(%658) : (i64) -> i64
        %659 = arith.addi %656, %657 : i64
        %660 = arith.cmpi ne, %655, %659 : i64
        cf.cond_br %660, ^bb93, ^bb94
        ^bb93:
          func.call @free(%481) : (!llvm.ptr) -> ()
          func.call @free(%502) : (!llvm.ptr) -> ()
          func.call @free(%508) : (!llvm.ptr) -> ()
          func.call @free(%514) : (!llvm.ptr) -> ()
          func.call @free(%520) : (!llvm.ptr) -> ()
          func.call @free(%526) : (!llvm.ptr) -> ()
          func.call @free(%532) : (!llvm.ptr) -> ()
          %668 = arith.constant 1 : i32
          %670 = arith.constant 0 : i32
          %669 = arith.subi %670, %668 : i32
          %671 = arith.extsi %669 : i32 to i64
          func.return %671 : i64
        ^bb94:
          cf.br ^bb95
        ^bb95:
        %672 = llvm.load %576 : !llvm.ptr -> i32
        %673 = arith.constant 1 : i32
        %674 = arith.addi %672, %673 : i32
        llvm.store %674, %576 : i32, !llvm.ptr
        cf.br ^bb72
      ^bb74:
      %675 = llvm.load %540 : !llvm.ptr -> i32
      %676 = arith.constant 1 : i32
      %677 = arith.addi %675, %676 : i32
      llvm.store %677, %540 : i32, !llvm.ptr
      cf.br ^bb69
    ^bb71:
    func.call @free(%481) : (!llvm.ptr) -> ()
    func.call @free(%502) : (!llvm.ptr) -> ()
    func.call @free(%508) : (!llvm.ptr) -> ()
    func.call @free(%514) : (!llvm.ptr) -> ()
    func.call @free(%520) : (!llvm.ptr) -> ()
    func.call @free(%526) : (!llvm.ptr) -> ()
    func.call @free(%532) : (!llvm.ptr) -> ()
    %685 = arith.constant 1 : i32
    %687 = arith.constant 0 : i32
    %686 = arith.subi %687, %685 : i32
    %688 = arith.extsi %686 : i32 to i64
    func.return %688 : i64
  }
  func.func @main() -> i32 {
    %690 = arith.constant 256 : i32
    %691 = arith.constant 8 : i32
    %692 = arith.extsi %690 : i32 to i64
    %693 = arith.extsi %691 : i32 to i64
    %689 = func.call @calloc(%692, %693) : (i64, i64) -> !llvm.ptr
    %694 = llvm.mlir.addressof @inv_key : !llvm.ptr
    llvm.store %689, %694 : !llvm.ptr, !llvm.ptr
    %696 = arith.constant 256 : i32
    %697 = llvm.mlir.addressof @MAXLIMBS : !llvm.ptr
    %698 = llvm.load %697 : !llvm.ptr -> i32
    %699 = arith.extsi %698 : i32 to i64
    %701 = arith.extsi %696 : i32 to i64
    %700 = arith.muli %701, %699 : i64
    %702 = arith.constant 8 : i32
    %703 = arith.extsi %702 : i32 to i64
    %695 = func.call @calloc(%700, %703) : (i64, i64) -> !llvm.ptr
    %704 = llvm.mlir.addressof @inv_val : !llvm.ptr
    llvm.store %695, %704 : !llvm.ptr, !llvm.ptr
    %705 = arith.constant 0 : i32
    %706 = arith.extsi %705 : i32 to i64
    %707 = llvm.mlir.constant(1 : i64) : i64
    %708 = llvm.alloca %707 x i64 : (i64) -> !llvm.ptr
    llvm.store %706, %708 : i64, !llvm.ptr
    %709 = arith.constant 1 : i32
    %710 = arith.extsi %709 : i32 to i64
    %711 = llvm.mlir.constant(1 : i64) : i64
    %712 = llvm.alloca %711 x i64 : (i64) -> !llvm.ptr
    llvm.store %710, %712 : i64, !llvm.ptr
    cf.br ^bb96
    ^bb96:
    %713 = llvm.load %712 : !llvm.ptr -> i64
    %714 = arith.constant 10000 : i32
    %716 = arith.extsi %714 : i32 to i64
    %715 = arith.cmpi sle, %713, %716 : i64
    cf.cond_br %715, ^bb97, ^bb98
    ^bb97:
      %717 = llvm.load %712 : !llvm.ptr -> i64
      %718 = llvm.load %712 : !llvm.ptr -> i64
      %719 = arith.muli %717, %718 : i64
      %720 = llvm.load %712 : !llvm.ptr -> i64
      %721 = arith.muli %719, %720 : i64
      %722 = llvm.load %708 : !llvm.ptr -> i64
      %723 = func.call @u_of(%721) : (i64) -> i64
      %724 = arith.addi %722, %723 : i64
      llvm.store %724, %708 : i64, !llvm.ptr
      %725 = llvm.load %712 : !llvm.ptr -> i64
      %726 = arith.constant 1 : i32
      %728 = arith.extsi %726 : i32 to i64
      %727 = arith.addi %725, %728 : i64
      llvm.store %727, %712 : i64, !llvm.ptr
      cf.br ^bb96
    ^bb98:
    %729 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %730 = llvm.load %708 : !llvm.ptr -> i64
    %731 = llvm.call @printf(%729, %730) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %733 = llvm.mlir.addressof @inv_key : !llvm.ptr
    %734 = llvm.load %733 : !llvm.ptr -> !llvm.ptr
    func.call @free(%734) : (!llvm.ptr) -> ()
    %736 = llvm.mlir.addressof @inv_val : !llvm.ptr
    %737 = llvm.load %736 : !llvm.ptr -> !llvm.ptr
    func.call @free(%737) : (!llvm.ptr) -> ()
    %738 = arith.constant 0 : i32
    func.return %738 : i32
  }
}