Problem 852

S(50) rounded to 6 decimals. Pure Flow port of native/p852.c.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 852: Coins in a Box
# S(50) rounded to 6 decimals.
# Pure Flow port of native/p852.c.

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

const MAX_FLIPS: i64 = 180
const N_MAX: i64 = 50

function stop_value(p: f64) -> f64 {
    if p >= 0.5 {
        return 70.0 * p - 50.0
    }
    return 20.0 - 70.0 * p
}

function gcd_int(a0: i64, b0: i64) -> i64 {
    let mut a: i64 = a0
    let mut b: i64 = b0
    while b != 0 {
        let t: i64 = a % b
        a = b
        b = t
    }
    return a
}

function compute_g_for_fraction(a: i64, b: i64, pow3: ptr<f64>, inv2: ptr<f64>) -> f64 {
    if a <= 0 || a >= b { return 20.0 }

    let p0: f64 = (a as f64) / (b as f64)
    let odds0: f64 = p0 / (1.0 - p0)

    let next_row: ptr<f64> = calloc(MAX_FLIPS + 2, 8)
    let curr_row: ptr<f64> = calloc(MAX_FLIPS + 2, 8)

    # Initialize at n = MAX_FLIPS with forced stop
    let mut base: f64 = odds0 * inv2[MAX_FLIPS]
    let mut h: i64 = 0
    while h <= MAX_FLIPS {
        let odds: f64 = base * pow3[h]
        let p: f64 = odds / (1.0 + odds)
        next_row[h] = stop_value(p)
        h = h + 1
    }

    # Backward induction
    let mut n: i64 = MAX_FLIPS - 1
    while n >= 0 {
        base = odds0 * inv2[n]
        let mut h2: i64 = 0
        while h2 <= n {
            let odds: f64 = base * pow3[h2]
            let p: f64 = odds / (1.0 + odds)
            let stop_v: f64 = stop_value(p)
            let qh: f64 = 0.5 + 0.25 * p
            let cont_v: f64 = -1.0 + qh * next_row[h2 + 1] + (1.0 - qh) * next_row[h2]
            if stop_v >= cont_v {
                curr_row[h2] = stop_v
            } else {
                curr_row[h2] = cont_v
            }
            h2 = h2 + 1
        }
        # Copy curr_row into next_row
        let mut i: i64 = 0
        while i <= MAX_FLIPS + 1 {
            next_row[i] = curr_row[i]
            i = i + 1
        }
        n = n - 1
    }

    let result: f64 = next_row[0]
    free(next_row)
    free(curr_row)
    return result
}

# g_cache as flat array: index (b, a) -> b * (max_b+1) + a
# g_done as flat array of i8
function main() -> i32 {
    let n: i64 = N_MAX

    # Precompute pow3 and inv2
    let pow3: ptr<f64> = malloc((MAX_FLIPS + 1) * 8)
    let inv2: ptr<f64> = malloc((MAX_FLIPS + 1) * 8)
    pow3[0] = 1.0
    inv2[0] = 1.0
    let mut i: i64 = 1
    while i <= MAX_FLIPS {
        pow3[i] = pow3[i - 1] * 3.0
        inv2[i] = inv2[i - 1] * 0.5
        i = i + 1
    }

    # Collect all needed (a, b) fractions
    # Max b = 2*n = 100. a ranges 0..b.
    # Use flat arrays: g_cache_flat[b * stride + a], g_done_flat[b * stride + a]
    let max_b: i64 = 2 * n
    let stride: i64 = max_b + 1
    let g_cache_flat: ptr<f64> = calloc((max_b + 1) * stride, 8)
    let g_done_flat: ptr<i8> = calloc((max_b + 1) * stride, 1)

    let mut u: i64 = 0
    while u <= n {
        let mut f: i64 = 0
        while f <= n {
            let total: i64 = u + f
            if total == 0 {
                f = f + 1
                continue
            }
            let g: i64 = gcd_int(u, total)
            let a: i64 = u / g
            let bb: i64 = total / g
            let idx: i64 = bb * stride + a
            if g_done_flat[idx] == 0 {
                g_cache_flat[idx] = compute_g_for_fraction(a, bb, pow3, inv2)
                g_done_flat[idx] = 1
            }
            f = f + 1
        }
        u = u + 1
    }

    # V[u][f] as flat array: (n+1) * (n+1)
    let V_flat: ptr<f64> = calloc((n + 1) * (n + 1), 8)

    # Fill by increasing total = u+f
    let mut total: i64 = 1
    while total <= 2 * n {
        let mut u_min: i64 = total - n
        if u_min < 0 { u_min = 0 }
        let mut u_max: i64 = n
        if total < u_max { u_max = total }
        let mut uu: i64 = u_min
        while uu <= u_max {
            let f: i64 = total - uu
            let g: i64 = gcd_int(uu, total)
            let immediate: f64 = g_cache_flat[(total / g) * stride + (uu / g)]
            let mut exp_next: f64 = 0.0
            if uu != 0 {
                exp_next = exp_next + ((uu as f64) / (total as f64)) * V_flat[(uu - 1) * (n + 1) + f]
            }
            if f != 0 {
                exp_next = exp_next + ((f as f64) / (total as f64)) * V_flat[uu * (n + 1) + (f - 1)]
            }
            V_flat[uu * (n + 1) + f] = immediate + exp_next
            uu = uu + 1
        }
        total = total + 1
    }

    let ans: f64 = V_flat[n * (n + 1) + n]

    free(g_cache_flat)
    free(g_done_flat)
    free(V_flat)
    free(pow3)
    free(inv2)

    printf("%.6f\n", ans)
    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; }

double stop_value_f64(double p);
int64_t gcd_int_i64_i64(int64_t a0, int64_t b0);
double compute_g_for_fraction_i64_i64_ptr_f64_ptr_f64(int64_t a, int64_t b, double* pow3, double* inv2);
int32_t main(void);

static const int64_t MAX_FLIPS = 180;
static const int64_t N_MAX = 50;




double stop_value_f64(double p) {
    if (p >= 0.5) {
        return ((70.0 * p) - 50.0);
    }
    return (20.0 - (70.0 * p));
}

int64_t gcd_int_i64_i64(int64_t a0, int64_t b0) {
    int64_t a = a0;
    int64_t b = b0;
    while (b != 0) {
        int64_t t = FLOW_CHECKED_MOD((a), (b));
        a = b;
        b = t;
    }
    return a;
}

double compute_g_for_fraction_i64_i64_ptr_f64_ptr_f64(int64_t a, int64_t b, double* pow3, double* inv2) {
    if ((a <= 0 || a >= b)) {
        return 20.0;
    }
    double p0 = (((double)(a)) / ((double)(b)));
    double odds0 = (p0 / (1.0 - p0));
    double* next_row = (double*)(calloc((MAX_FLIPS + 2), 8));
    double* curr_row = (double*)(calloc((MAX_FLIPS + 2), 8));
    double base = (odds0 * inv2[MAX_FLIPS]);
    int64_t h = 0;
    while (h <= MAX_FLIPS) {
        double odds = (base * pow3[h]);
        double p = (odds / (1.0 + odds));
        next_row[h] = stop_value_f64(p);
        h = (h + 1);
    }
    int64_t n = (MAX_FLIPS - 1);
    while (n >= 0) {
        base = (odds0 * inv2[n]);
        int64_t h2 = 0;
        while (h2 <= n) {
            double odds = (base * pow3[h2]);
            double p = (odds / (1.0 + odds));
            double stop_v = stop_value_f64(p);
            double qh = (0.5 + (0.25 * p));
            double cont_v = (((-1.0) + (qh * next_row[(h2 + 1)])) + ((1.0 - qh) * next_row[h2]));
            if (stop_v >= cont_v) {
                curr_row[h2] = stop_v;
            } else {
                curr_row[h2] = cont_v;
            }
            h2 = (h2 + 1);
        }
        int64_t i = 0;
        while (i <= (MAX_FLIPS + 1)) {
            next_row[i] = curr_row[i];
            i = (i + 1);
        }
        n = (n - 1);
    }
    double result = next_row[0];
    free(next_row);
    free(curr_row);
    return result;
}

int32_t main(void) {
    int64_t n = N_MAX;
    double* pow3 = (double*)(malloc(((MAX_FLIPS + 1) * 8)));
    double* inv2 = (double*)(malloc(((MAX_FLIPS + 1) * 8)));
    pow3[0] = 1.0;
    inv2[0] = 1.0;
    int64_t i = 1;
    while (i <= MAX_FLIPS) {
        pow3[i] = (pow3[(i - 1)] * 3.0);
        inv2[i] = (inv2[(i - 1)] * 0.5);
        i = (i + 1);
    }
    int64_t max_b = (2 * n);
    int64_t stride = (max_b + 1);
    double* g_cache_flat = (double*)(calloc(((max_b + 1) * stride), 8));
    int8_t* g_done_flat = (int8_t*)(calloc(((max_b + 1) * stride), 1));
    int64_t u = 0;
    while (u <= n) {
        int64_t f = 0;
        while (f <= n) {
            int64_t total = (u + f);
            if (total == 0) {
                f = (f + 1);
                continue;
            }
            int64_t g = gcd_int_i64_i64(u, total);
            int64_t a = FLOW_CHECKED_DIV((u), (g));
            int64_t bb = FLOW_CHECKED_DIV((total), (g));
            int64_t idx = ((bb * stride) + a);
            if (g_done_flat[idx] == 0) {
                g_cache_flat[idx] = compute_g_for_fraction_i64_i64_ptr_f64_ptr_f64(a, bb, pow3, inv2);
                g_done_flat[idx] = 1;
            }
            f = (f + 1);
        }
        u = (u + 1);
    }
    double* V_flat = (double*)(calloc(((n + 1) * (n + 1)), 8));
    int64_t total = 1;
    while (total <= (2 * n)) {
        int64_t u_min = (total - n);
        if (u_min < 0) {
            u_min = 0;
        }
        int64_t u_max = n;
        if (total < u_max) {
            u_max = total;
        }
        int64_t uu = u_min;
        while (uu <= u_max) {
            int64_t f = (total - uu);
            int64_t g = gcd_int_i64_i64(uu, total);
            double immediate = g_cache_flat[((FLOW_CHECKED_DIV((total), (g)) * stride) + FLOW_CHECKED_DIV((uu), (g)))];
            double exp_next = 0.0;
            if (uu != 0) {
                exp_next = (exp_next + ((((double)(uu)) / ((double)(total))) * V_flat[(((uu - 1) * (n + 1)) + f)]));
            }
            if (f != 0) {
                exp_next = (exp_next + ((((double)(f)) / ((double)(total))) * V_flat[((uu * (n + 1)) + (f - 1))]));
            }
            V_flat[((uu * (n + 1)) + f)] = (immediate + exp_next);
            uu = (uu + 1);
        }
        total = (total + 1);
    }
    double ans = V_flat[((n * (n + 1)) + n)];
    free(g_cache_flat);
    free(g_done_flat);
    free(V_flat);
    free(pow3);
    free(inv2);
    printf("%.6f\n", ans);
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%.6f\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  func.func private @malloc(i64) -> !llvm.ptr
  // Constant: MAX_FLIPS
  llvm.mlir.global internal constant @MAX_FLIPS(180 : i64) : i64
  // Constant: N_MAX
  llvm.mlir.global internal constant @N_MAX(50 : i64) : i64
  func.func @stop_value(%arg0: f64) -> f64 {
    %0 = arith.constant 0.5 : f32
    %2 = arith.extf %0 : f32 to f64
    %1 = arith.cmpf oge, %arg0, %2 : f64
    cf.cond_br %1, ^bb0, ^bb1
    ^bb0:
      %3 = arith.constant 70.0 : f32
      %5 = arith.extf %3 : f32 to f64
      %4 = arith.mulf %5, %arg0 : f64
      %6 = arith.constant 50.0 : f32
      %8 = arith.extf %6 : f32 to f64
      %7 = arith.subf %4, %8 : f64
      func.return %7 : f64
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %9 = arith.constant 20.0 : f32
    %10 = arith.constant 70.0 : f32
    %12 = arith.extf %10 : f32 to f64
    %11 = arith.mulf %12, %arg0 : f64
    %14 = arith.extf %9 : f32 to f64
    %13 = arith.subf %14, %11 : f64
    func.return %13 : f64
  }
  func.func @gcd_int(%arg0: i64, %arg1: i64) -> i64 {
    %15 = llvm.mlir.constant(1 : i64) : i64
    %16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %16 : i64, !llvm.ptr
    %17 = llvm.mlir.constant(1 : i64) : i64
    %18 = llvm.alloca %17 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %18 : i64, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %19 = llvm.load %18 : !llvm.ptr -> i64
    %20 = arith.constant 0 : i32
    %22 = arith.extsi %20 : i32 to i64
    %21 = arith.cmpi ne, %19, %22 : i64
    cf.cond_br %21, ^bb4, ^bb5
    ^bb4:
      %23 = llvm.load %16 : !llvm.ptr -> i64
      %24 = llvm.load %18 : !llvm.ptr -> i64
      %25 = arith.remsi %23, %24 : i64
      %26 = llvm.load %18 : !llvm.ptr -> i64
      llvm.store %26, %16 : i64, !llvm.ptr
      llvm.store %25, %18 : i64, !llvm.ptr
      cf.br ^bb3
    ^bb5:
    %27 = llvm.load %16 : !llvm.ptr -> i64
    func.return %27 : i64
  }
  func.func @compute_g_for_fraction(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> f64 {
    %28 = arith.constant 0 : i32
    %30 = arith.extsi %28 : i32 to i64
    %29 = arith.cmpi sle, %arg0, %30 : i64
    %31 = scf.if %29 -> (i1) {
      %32 = arith.constant true
      scf.yield %32 : i1
    } else {
      %33 = arith.cmpi sge, %arg0, %arg1 : i64
      scf.yield %33 : i1
    }
    cf.cond_br %31, ^bb6, ^bb7
    ^bb6:
      %34 = arith.constant 20.0 : f32
      %35 = arith.extf %34 : f32 to f64
      func.return %35 : f64
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %36 = arith.sitofp %arg0 : i64 to f64
    %37 = arith.sitofp %arg1 : i64 to f64
    %38 = arith.divf %36, %37 : f64
    %39 = arith.constant 1.0 : f32
    %41 = arith.extf %39 : f32 to f64
    %40 = arith.subf %41, %38 : f64
    %42 = arith.divf %38, %40 : f64
    %44 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %45 = llvm.load %44 : !llvm.ptr -> i64
    %46 = arith.constant 2 : i32
    %48 = arith.extsi %46 : i32 to i64
    %47 = arith.addi %45, %48 : i64
    %49 = arith.constant 8 : i32
    %50 = arith.extsi %49 : i32 to i64
    %43 = func.call @calloc(%47, %50) : (i64, i64) -> !llvm.ptr
    %52 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %53 = llvm.load %52 : !llvm.ptr -> i64
    %54 = arith.constant 2 : i32
    %56 = arith.extsi %54 : i32 to i64
    %55 = arith.addi %53, %56 : i64
    %57 = arith.constant 8 : i32
    %58 = arith.extsi %57 : i32 to i64
    %51 = func.call @calloc(%55, %58) : (i64, i64) -> !llvm.ptr
    %60 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %61 = llvm.load %60 : !llvm.ptr -> i64
    %62 = llvm.getelementptr %arg3[%61] : (!llvm.ptr, i64) -> !llvm.ptr, f64
    %59 = llvm.load %62 : !llvm.ptr -> f64
    %63 = arith.mulf %42, %59 : f64
    %64 = llvm.mlir.constant(1 : i64) : i64
    %65 = llvm.alloca %64 x f64 : (i64) -> !llvm.ptr
    llvm.store %63, %65 : f64, !llvm.ptr
    %66 = arith.constant 0 : i32
    %67 = arith.extsi %66 : i32 to i64
    %68 = llvm.mlir.constant(1 : i64) : i64
    %69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
    llvm.store %67, %69 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %70 = llvm.load %69 : !llvm.ptr -> i64
    %71 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %72 = llvm.load %71 : !llvm.ptr -> i64
    %73 = arith.cmpi sle, %70, %72 : i64
    cf.cond_br %73, ^bb10, ^bb11
    ^bb10:
      %74 = llvm.load %65 : !llvm.ptr -> f64
      %76 = llvm.load %69 : !llvm.ptr -> i64
      %77 = llvm.getelementptr %arg2[%76] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      %75 = llvm.load %77 : !llvm.ptr -> f64
      %78 = arith.mulf %74, %75 : f64
      %79 = arith.constant 1.0 : f32
      %81 = arith.extf %79 : f32 to f64
      %80 = arith.addf %81, %78 : f64
      %82 = arith.divf %78, %80 : f64
      %83 = func.call @stop_value(%82) : (f64) -> f64
      %84 = llvm.load %69 : !llvm.ptr -> i64
      %85 = llvm.getelementptr %43[%84] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      llvm.store %83, %85 : f64, !llvm.ptr
      %86 = llvm.load %69 : !llvm.ptr -> i64
      %87 = arith.constant 1 : i32
      %89 = arith.extsi %87 : i32 to i64
      %88 = arith.addi %86, %89 : i64
      llvm.store %88, %69 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %90 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %91 = llvm.load %90 : !llvm.ptr -> i64
    %92 = arith.constant 1 : i32
    %94 = arith.extsi %92 : i32 to i64
    %93 = arith.subi %91, %94 : i64
    %95 = llvm.mlir.constant(1 : i64) : i64
    %96 = llvm.alloca %95 x i64 : (i64) -> !llvm.ptr
    llvm.store %93, %96 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %97 = llvm.load %96 : !llvm.ptr -> i64
    %98 = arith.constant 0 : i32
    %100 = arith.extsi %98 : i32 to i64
    %99 = arith.cmpi sge, %97, %100 : i64
    cf.cond_br %99, ^bb13, ^bb14
    ^bb13:
      %102 = llvm.load %96 : !llvm.ptr -> i64
      %103 = llvm.getelementptr %arg3[%102] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      %101 = llvm.load %103 : !llvm.ptr -> f64
      %104 = arith.mulf %42, %101 : f64
      llvm.store %104, %65 : f64, !llvm.ptr
      %105 = arith.constant 0 : i32
      %106 = arith.extsi %105 : i32 to i64
      %107 = llvm.mlir.constant(1 : i64) : i64
      %108 = llvm.alloca %107 x i64 : (i64) -> !llvm.ptr
      llvm.store %106, %108 : i64, !llvm.ptr
      cf.br ^bb15
      ^bb15:
      %109 = llvm.load %108 : !llvm.ptr -> i64
      %110 = llvm.load %96 : !llvm.ptr -> i64
      %111 = arith.cmpi sle, %109, %110 : i64
      cf.cond_br %111, ^bb16, ^bb17
      ^bb16:
        %112 = llvm.load %65 : !llvm.ptr -> f64
        %114 = llvm.load %108 : !llvm.ptr -> i64
        %115 = llvm.getelementptr %arg2[%114] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        %113 = llvm.load %115 : !llvm.ptr -> f64
        %116 = arith.mulf %112, %113 : f64
        %117 = arith.constant 1.0 : f32
        %119 = arith.extf %117 : f32 to f64
        %118 = arith.addf %119, %116 : f64
        %120 = arith.divf %116, %118 : f64
        %121 = func.call @stop_value(%120) : (f64) -> f64
        %122 = arith.constant 0.5 : f32
        %123 = arith.constant 0.25 : f32
        %125 = arith.extf %123 : f32 to f64
        %124 = arith.mulf %125, %120 : f64
        %127 = arith.extf %122 : f32 to f64
        %126 = arith.addf %127, %124 : f64
        %128 = arith.constant 1.0 : f32
        %129 = arith.negf %128 : f32
        %131 = llvm.load %108 : !llvm.ptr -> i64
        %132 = arith.constant 1 : i32
        %134 = arith.extsi %132 : i32 to i64
        %133 = arith.addi %131, %134 : i64
        %135 = llvm.getelementptr %43[%133] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        %130 = llvm.load %135 : !llvm.ptr -> f64
        %136 = arith.mulf %126, %130 : f64
        %138 = arith.extf %129 : f32 to f64
        %137 = arith.addf %138, %136 : f64
        %139 = arith.constant 1.0 : f32
        %141 = arith.extf %139 : f32 to f64
        %140 = arith.subf %141, %126 : f64
        %143 = llvm.load %108 : !llvm.ptr -> i64
        %144 = llvm.getelementptr %43[%143] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        %142 = llvm.load %144 : !llvm.ptr -> f64
        %145 = arith.mulf %140, %142 : f64
        %146 = arith.addf %137, %145 : f64
        %147 = arith.cmpf oge, %121, %146 : f64
        cf.cond_br %147, ^bb18, ^bb19
        ^bb18:
          %148 = llvm.load %108 : !llvm.ptr -> i64
          %149 = llvm.getelementptr %51[%148] : (!llvm.ptr, i64) -> !llvm.ptr, f64
          llvm.store %121, %149 : f64, !llvm.ptr
          cf.br ^bb20
        ^bb19:
          %150 = llvm.load %108 : !llvm.ptr -> i64
          %151 = llvm.getelementptr %51[%150] : (!llvm.ptr, i64) -> !llvm.ptr, f64
          llvm.store %146, %151 : f64, !llvm.ptr
          cf.br ^bb20
        ^bb20:
        %152 = llvm.load %108 : !llvm.ptr -> i64
        %153 = arith.constant 1 : i32
        %155 = arith.extsi %153 : i32 to i64
        %154 = arith.addi %152, %155 : i64
        llvm.store %154, %108 : i64, !llvm.ptr
        cf.br ^bb15
      ^bb17:
      %156 = arith.constant 0 : i32
      %157 = arith.extsi %156 : i32 to i64
      %158 = llvm.mlir.constant(1 : i64) : i64
      %159 = llvm.alloca %158 x i64 : (i64) -> !llvm.ptr
      llvm.store %157, %159 : i64, !llvm.ptr
      cf.br ^bb21
      ^bb21:
      %160 = llvm.load %159 : !llvm.ptr -> i64
      %161 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
      %162 = llvm.load %161 : !llvm.ptr -> i64
      %163 = arith.constant 1 : i32
      %165 = arith.extsi %163 : i32 to i64
      %164 = arith.addi %162, %165 : i64
      %166 = arith.cmpi sle, %160, %164 : i64
      cf.cond_br %166, ^bb22, ^bb23
      ^bb22:
        %168 = llvm.load %159 : !llvm.ptr -> i64
        %169 = llvm.getelementptr %51[%168] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        %167 = llvm.load %169 : !llvm.ptr -> f64
        %170 = llvm.load %159 : !llvm.ptr -> i64
        %171 = llvm.getelementptr %43[%170] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        llvm.store %167, %171 : f64, !llvm.ptr
        %172 = llvm.load %159 : !llvm.ptr -> i64
        %173 = arith.constant 1 : i32
        %175 = arith.extsi %173 : i32 to i64
        %174 = arith.addi %172, %175 : i64
        llvm.store %174, %159 : i64, !llvm.ptr
        cf.br ^bb21
      ^bb23:
      %176 = llvm.load %96 : !llvm.ptr -> i64
      %177 = arith.constant 1 : i32
      %179 = arith.extsi %177 : i32 to i64
      %178 = arith.subi %176, %179 : i64
      llvm.store %178, %96 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %181 = arith.constant 0 : i32
    %182 = arith.extsi %181 : i32 to i64
    %183 = llvm.getelementptr %43[%182] : (!llvm.ptr, i64) -> !llvm.ptr, f64
    %180 = llvm.load %183 : !llvm.ptr -> f64
    func.call @free(%43) : (!llvm.ptr) -> ()
    func.call @free(%51) : (!llvm.ptr) -> ()
    func.return %180 : f64
  }
  func.func @main() -> i32 {
    %186 = llvm.mlir.addressof @N_MAX : !llvm.ptr
    %187 = llvm.load %186 : !llvm.ptr -> i64
    %189 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %190 = llvm.load %189 : !llvm.ptr -> i64
    %191 = arith.constant 1 : i32
    %193 = arith.extsi %191 : i32 to i64
    %192 = arith.addi %190, %193 : i64
    %194 = arith.constant 8 : i32
    %196 = arith.extsi %194 : i32 to i64
    %195 = arith.muli %192, %196 : i64
    %188 = func.call @malloc(%195) : (i64) -> !llvm.ptr
    %198 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %199 = llvm.load %198 : !llvm.ptr -> i64
    %200 = arith.constant 1 : i32
    %202 = arith.extsi %200 : i32 to i64
    %201 = arith.addi %199, %202 : i64
    %203 = arith.constant 8 : i32
    %205 = arith.extsi %203 : i32 to i64
    %204 = arith.muli %201, %205 : i64
    %197 = func.call @malloc(%204) : (i64) -> !llvm.ptr
    %206 = arith.constant 1.0 : f32
    %207 = arith.constant 0 : i32
    %208 = arith.extf %206 : f32 to f64
    %209 = arith.extsi %207 : i32 to i64
    %210 = llvm.getelementptr %188[%209] : (!llvm.ptr, i64) -> !llvm.ptr, f64
    llvm.store %208, %210 : f64, !llvm.ptr
    %211 = arith.constant 1.0 : f32
    %212 = arith.constant 0 : i32
    %213 = arith.extf %211 : f32 to f64
    %214 = arith.extsi %212 : i32 to i64
    %215 = llvm.getelementptr %197[%214] : (!llvm.ptr, i64) -> !llvm.ptr, f64
    llvm.store %213, %215 : f64, !llvm.ptr
    %216 = arith.constant 1 : i32
    %217 = arith.extsi %216 : i32 to i64
    %218 = llvm.mlir.constant(1 : i64) : i64
    %219 = llvm.alloca %218 x i64 : (i64) -> !llvm.ptr
    llvm.store %217, %219 : i64, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %220 = llvm.load %219 : !llvm.ptr -> i64
    %221 = llvm.mlir.addressof @MAX_FLIPS : !llvm.ptr
    %222 = llvm.load %221 : !llvm.ptr -> i64
    %223 = arith.cmpi sle, %220, %222 : i64
    cf.cond_br %223, ^bb25, ^bb26
    ^bb25:
      %225 = llvm.load %219 : !llvm.ptr -> i64
      %226 = arith.constant 1 : i32
      %228 = arith.extsi %226 : i32 to i64
      %227 = arith.subi %225, %228 : i64
      %229 = llvm.getelementptr %188[%227] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      %224 = llvm.load %229 : !llvm.ptr -> f64
      %230 = arith.constant 3.0 : f32
      %232 = arith.extf %230 : f32 to f64
      %231 = arith.mulf %224, %232 : f64
      %233 = llvm.load %219 : !llvm.ptr -> i64
      %234 = llvm.getelementptr %188[%233] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      llvm.store %231, %234 : f64, !llvm.ptr
      %236 = llvm.load %219 : !llvm.ptr -> i64
      %237 = arith.constant 1 : i32
      %239 = arith.extsi %237 : i32 to i64
      %238 = arith.subi %236, %239 : i64
      %240 = llvm.getelementptr %197[%238] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      %235 = llvm.load %240 : !llvm.ptr -> f64
      %241 = arith.constant 0.5 : f32
      %243 = arith.extf %241 : f32 to f64
      %242 = arith.mulf %235, %243 : f64
      %244 = llvm.load %219 : !llvm.ptr -> i64
      %245 = llvm.getelementptr %197[%244] : (!llvm.ptr, i64) -> !llvm.ptr, f64
      llvm.store %242, %245 : f64, !llvm.ptr
      %246 = llvm.load %219 : !llvm.ptr -> i64
      %247 = arith.constant 1 : i32
      %249 = arith.extsi %247 : i32 to i64
      %248 = arith.addi %246, %249 : i64
      llvm.store %248, %219 : i64, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    %250 = arith.constant 2 : i32
    %252 = arith.extsi %250 : i32 to i64
    %251 = arith.muli %252, %187 : i64
    %253 = arith.constant 1 : i32
    %255 = arith.extsi %253 : i32 to i64
    %254 = arith.addi %251, %255 : i64
    %257 = arith.constant 1 : i32
    %259 = arith.extsi %257 : i32 to i64
    %258 = arith.addi %251, %259 : i64
    %260 = arith.muli %258, %254 : i64
    %261 = arith.constant 8 : i32
    %262 = arith.extsi %261 : i32 to i64
    %256 = func.call @calloc(%260, %262) : (i64, i64) -> !llvm.ptr
    %264 = arith.constant 1 : i32
    %266 = arith.extsi %264 : i32 to i64
    %265 = arith.addi %251, %266 : i64
    %267 = arith.muli %265, %254 : i64
    %268 = arith.constant 1 : i32
    %269 = arith.extsi %268 : i32 to i64
    %263 = func.call @calloc(%267, %269) : (i64, i64) -> !llvm.ptr
    %270 = arith.constant 0 : i32
    %271 = arith.extsi %270 : i32 to i64
    %272 = llvm.mlir.constant(1 : i64) : i64
    %273 = llvm.alloca %272 x i64 : (i64) -> !llvm.ptr
    llvm.store %271, %273 : i64, !llvm.ptr
    cf.br ^bb27
    ^bb27:
    %274 = llvm.load %273 : !llvm.ptr -> i64
    %275 = arith.cmpi sle, %274, %187 : i64
    cf.cond_br %275, ^bb28, ^bb29
    ^bb28:
      %276 = arith.constant 0 : i32
      %277 = arith.extsi %276 : i32 to i64
      %278 = llvm.mlir.constant(1 : i64) : i64
      %279 = llvm.alloca %278 x i64 : (i64) -> !llvm.ptr
      llvm.store %277, %279 : i64, !llvm.ptr
      cf.br ^bb30
      ^bb30:
      %280 = llvm.load %279 : !llvm.ptr -> i64
      %281 = arith.cmpi sle, %280, %187 : i64
      cf.cond_br %281, ^bb31, ^bb32
      ^bb31:
        %282 = llvm.load %273 : !llvm.ptr -> i64
        %283 = llvm.load %279 : !llvm.ptr -> i64
        %284 = arith.addi %282, %283 : i64
        %285 = arith.constant 0 : i32
        %287 = arith.extsi %285 : i32 to i64
        %286 = arith.cmpi eq, %284, %287 : i64
        cf.cond_br %286, ^bb33, ^bb34
        ^bb33:
          %288 = llvm.load %279 : !llvm.ptr -> i64
          %289 = arith.constant 1 : i32
          %291 = arith.extsi %289 : i32 to i64
          %290 = arith.addi %288, %291 : i64
          llvm.store %290, %279 : i64, !llvm.ptr
          cf.br ^bb30
        ^bb34:
          cf.br ^bb35
        ^bb35:
        %293 = llvm.load %273 : !llvm.ptr -> i64
        %292 = func.call @gcd_int(%293, %284) : (i64, i64) -> i64
        %294 = llvm.load %273 : !llvm.ptr -> i64
        %295 = arith.divsi %294, %292 : i64
        %296 = arith.divsi %284, %292 : i64
        %297 = arith.muli %296, %254 : i64
        %298 = arith.addi %297, %295 : i64
        %300 = llvm.getelementptr %263[%298] : (!llvm.ptr, i64) -> !llvm.ptr, i8
        %299 = llvm.load %300 : !llvm.ptr -> i8
        %301 = arith.constant 0 : i32
        %303 = arith.extsi %299 : i8 to i32
        %302 = arith.cmpi eq, %303, %301 : i32
        cf.cond_br %302, ^bb36, ^bb37
        ^bb36:
          %304 = func.call @compute_g_for_fraction(%295, %296, %188, %197) : (i64, i64, !llvm.ptr, !llvm.ptr) -> f64
          %305 = llvm.getelementptr %256[%298] : (!llvm.ptr, i64) -> !llvm.ptr, f64
          llvm.store %304, %305 : f64, !llvm.ptr
          %306 = arith.constant 1 : i32
          %307 = arith.trunci %306 : i32 to i8
          %308 = llvm.getelementptr %263[%298] : (!llvm.ptr, i64) -> !llvm.ptr, i8
          llvm.store %307, %308 : i8, !llvm.ptr
          cf.br ^bb38
        ^bb37:
          cf.br ^bb38
        ^bb38:
        %309 = llvm.load %279 : !llvm.ptr -> i64
        %310 = arith.constant 1 : i32
        %312 = arith.extsi %310 : i32 to i64
        %311 = arith.addi %309, %312 : i64
        llvm.store %311, %279 : i64, !llvm.ptr
        cf.br ^bb30
      ^bb32:
      %313 = llvm.load %273 : !llvm.ptr -> i64
      %314 = arith.constant 1 : i32
      %316 = arith.extsi %314 : i32 to i64
      %315 = arith.addi %313, %316 : i64
      llvm.store %315, %273 : i64, !llvm.ptr
      cf.br ^bb27
    ^bb29:
    %318 = arith.constant 1 : i32
    %320 = arith.extsi %318 : i32 to i64
    %319 = arith.addi %187, %320 : i64
    %321 = arith.constant 1 : i32
    %323 = arith.extsi %321 : i32 to i64
    %322 = arith.addi %187, %323 : i64
    %324 = arith.muli %319, %322 : i64
    %325 = arith.constant 8 : i32
    %326 = arith.extsi %325 : i32 to i64
    %317 = func.call @calloc(%324, %326) : (i64, i64) -> !llvm.ptr
    %327 = arith.constant 1 : i32
    %328 = arith.extsi %327 : i32 to i64
    %329 = llvm.mlir.constant(1 : i64) : i64
    %330 = llvm.alloca %329 x i64 : (i64) -> !llvm.ptr
    llvm.store %328, %330 : i64, !llvm.ptr
    cf.br ^bb39
    ^bb39:
    %331 = llvm.load %330 : !llvm.ptr -> i64
    %332 = arith.constant 2 : i32
    %334 = arith.extsi %332 : i32 to i64
    %333 = arith.muli %334, %187 : i64
    %335 = arith.cmpi sle, %331, %333 : i64
    cf.cond_br %335, ^bb40, ^bb41
    ^bb40:
      %336 = llvm.load %330 : !llvm.ptr -> i64
      %337 = arith.subi %336, %187 : i64
      %338 = llvm.mlir.constant(1 : i64) : i64
      %339 = llvm.alloca %338 x i64 : (i64) -> !llvm.ptr
      llvm.store %337, %339 : i64, !llvm.ptr
      %340 = llvm.load %339 : !llvm.ptr -> i64
      %341 = arith.constant 0 : i32
      %343 = arith.extsi %341 : i32 to i64
      %342 = arith.cmpi slt, %340, %343 : i64
      cf.cond_br %342, ^bb42, ^bb43
      ^bb42:
        %344 = arith.constant 0 : i32
        %345 = arith.extsi %344 : i32 to i64
        llvm.store %345, %339 : i64, !llvm.ptr
        cf.br ^bb44
      ^bb43:
        cf.br ^bb44
      ^bb44:
      %346 = llvm.mlir.constant(1 : i64) : i64
      %347 = llvm.alloca %346 x i64 : (i64) -> !llvm.ptr
      llvm.store %187, %347 : i64, !llvm.ptr
      %348 = llvm.load %330 : !llvm.ptr -> i64
      %349 = llvm.load %347 : !llvm.ptr -> i64
      %350 = arith.cmpi slt, %348, %349 : i64
      cf.cond_br %350, ^bb45, ^bb46
      ^bb45:
        %351 = llvm.load %330 : !llvm.ptr -> i64
        llvm.store %351, %347 : i64, !llvm.ptr
        cf.br ^bb47
      ^bb46:
        cf.br ^bb47
      ^bb47:
      %352 = llvm.load %339 : !llvm.ptr -> i64
      %353 = llvm.mlir.constant(1 : i64) : i64
      %354 = llvm.alloca %353 x i64 : (i64) -> !llvm.ptr
      llvm.store %352, %354 : i64, !llvm.ptr
      cf.br ^bb48
      ^bb48:
      %355 = llvm.load %354 : !llvm.ptr -> i64
      %356 = llvm.load %347 : !llvm.ptr -> i64
      %357 = arith.cmpi sle, %355, %356 : i64
      cf.cond_br %357, ^bb49, ^bb50
      ^bb49:
        %358 = llvm.load %330 : !llvm.ptr -> i64
        %359 = llvm.load %354 : !llvm.ptr -> i64
        %360 = arith.subi %358, %359 : i64
        %362 = llvm.load %354 : !llvm.ptr -> i64
        %363 = llvm.load %330 : !llvm.ptr -> i64
        %361 = func.call @gcd_int(%362, %363) : (i64, i64) -> i64
        %365 = llvm.load %330 : !llvm.ptr -> i64
        %366 = arith.divsi %365, %361 : i64
        %367 = arith.muli %366, %254 : i64
        %368 = llvm.load %354 : !llvm.ptr -> i64
        %369 = arith.divsi %368, %361 : i64
        %370 = arith.addi %367, %369 : i64
        %371 = llvm.getelementptr %256[%370] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        %364 = llvm.load %371 : !llvm.ptr -> f64
        %372 = arith.constant 0.0 : f32
        %373 = arith.extf %372 : f32 to f64
        %374 = llvm.mlir.constant(1 : i64) : i64
        %375 = llvm.alloca %374 x f64 : (i64) -> !llvm.ptr
        llvm.store %373, %375 : f64, !llvm.ptr
        %376 = llvm.load %354 : !llvm.ptr -> i64
        %377 = arith.constant 0 : i32
        %379 = arith.extsi %377 : i32 to i64
        %378 = arith.cmpi ne, %376, %379 : i64
        cf.cond_br %378, ^bb51, ^bb52
        ^bb51:
          %380 = llvm.load %375 : !llvm.ptr -> f64
          %381 = llvm.load %354 : !llvm.ptr -> i64
          %382 = arith.sitofp %381 : i64 to f64
          %383 = llvm.load %330 : !llvm.ptr -> i64
          %384 = arith.sitofp %383 : i64 to f64
          %385 = arith.divf %382, %384 : f64
          %387 = llvm.load %354 : !llvm.ptr -> i64
          %388 = arith.constant 1 : i32
          %390 = arith.extsi %388 : i32 to i64
          %389 = arith.subi %387, %390 : i64
          %391 = arith.constant 1 : i32
          %393 = arith.extsi %391 : i32 to i64
          %392 = arith.addi %187, %393 : i64
          %394 = arith.muli %389, %392 : i64
          %395 = arith.addi %394, %360 : i64
          %396 = llvm.getelementptr %317[%395] : (!llvm.ptr, i64) -> !llvm.ptr, f64
          %386 = llvm.load %396 : !llvm.ptr -> f64
          %397 = arith.mulf %385, %386 : f64
          %398 = arith.addf %380, %397 : f64
          llvm.store %398, %375 : f64, !llvm.ptr
          cf.br ^bb53
        ^bb52:
          cf.br ^bb53
        ^bb53:
        %399 = arith.constant 0 : i32
        %401 = arith.extsi %399 : i32 to i64
        %400 = arith.cmpi ne, %360, %401 : i64
        cf.cond_br %400, ^bb54, ^bb55
        ^bb54:
          %402 = llvm.load %375 : !llvm.ptr -> f64
          %403 = arith.sitofp %360 : i64 to f64
          %404 = llvm.load %330 : !llvm.ptr -> i64
          %405 = arith.sitofp %404 : i64 to f64
          %406 = arith.divf %403, %405 : f64
          %408 = llvm.load %354 : !llvm.ptr -> i64
          %409 = arith.constant 1 : i32
          %411 = arith.extsi %409 : i32 to i64
          %410 = arith.addi %187, %411 : i64
          %412 = arith.muli %408, %410 : i64
          %413 = arith.constant 1 : i32
          %415 = arith.extsi %413 : i32 to i64
          %414 = arith.subi %360, %415 : i64
          %416 = arith.addi %412, %414 : i64
          %417 = llvm.getelementptr %317[%416] : (!llvm.ptr, i64) -> !llvm.ptr, f64
          %407 = llvm.load %417 : !llvm.ptr -> f64
          %418 = arith.mulf %406, %407 : f64
          %419 = arith.addf %402, %418 : f64
          llvm.store %419, %375 : f64, !llvm.ptr
          cf.br ^bb56
        ^bb55:
          cf.br ^bb56
        ^bb56:
        %420 = llvm.load %375 : !llvm.ptr -> f64
        %421 = arith.addf %364, %420 : f64
        %422 = llvm.load %354 : !llvm.ptr -> i64
        %423 = arith.constant 1 : i32
        %425 = arith.extsi %423 : i32 to i64
        %424 = arith.addi %187, %425 : i64
        %426 = arith.muli %422, %424 : i64
        %427 = arith.addi %426, %360 : i64
        %428 = llvm.getelementptr %317[%427] : (!llvm.ptr, i64) -> !llvm.ptr, f64
        llvm.store %421, %428 : f64, !llvm.ptr
        %429 = llvm.load %354 : !llvm.ptr -> i64
        %430 = arith.constant 1 : i32
        %432 = arith.extsi %430 : i32 to i64
        %431 = arith.addi %429, %432 : i64
        llvm.store %431, %354 : i64, !llvm.ptr
        cf.br ^bb48
      ^bb50:
      %433 = llvm.load %330 : !llvm.ptr -> i64
      %434 = arith.constant 1 : i32
      %436 = arith.extsi %434 : i32 to i64
      %435 = arith.addi %433, %436 : i64
      llvm.store %435, %330 : i64, !llvm.ptr
      cf.br ^bb39
    ^bb41:
    %438 = arith.constant 1 : i32
    %440 = arith.extsi %438 : i32 to i64
    %439 = arith.addi %187, %440 : i64
    %441 = arith.muli %187, %439 : i64
    %442 = arith.addi %441, %187 : i64
    %443 = llvm.getelementptr %317[%442] : (!llvm.ptr, i64) -> !llvm.ptr, f64
    %437 = llvm.load %443 : !llvm.ptr -> f64
    func.call @free(%256) : (!llvm.ptr) -> ()
    func.call @free(%263) : (!llvm.ptr) -> ()
    func.call @free(%317) : (!llvm.ptr) -> ()
    func.call @free(%188) : (!llvm.ptr) -> ()
    func.call @free(%197) : (!llvm.ptr) -> ()
    %449 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %450 = llvm.call @printf(%449, %437) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64) -> i32
    %451 = arith.constant 0 : i32
    func.return %451 : i32
  }
}