Problem 666
Polymorphic bacteria extinction probability via branching-process fixed point.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n * s^2) |
|---|
| Space complexity | O(n^2) | O(s^2) |
|---|
| Approach | Flow solution | Markov chain or DP over states |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 666
# Polymorphic bacteria extinction probability via branching-process fixed point.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let k: i64 = 500
let m: i64 = 10
let MOD: i64 = 10007
let N: i64 = k * m
let r: ptr<i32> = calloc(N, 4)
if r == null { return 1 }
r[0] = 306
let mut n: i64 = 1
while n < N {
let x: i64 = r[n - 1] as i64
r[n] = ((x * x) % MOD) as i32
n = n + 1
}
let a0: ptr<f64> = calloc(k, 8)
let a1: ptr<f64> = calloc(k, 8)
let a2: ptr<f64> = calloc(k, 8)
let a3: ptr<f64> = calloc(k, 8)
let a4: ptr<f64> = calloc(k, 8)
let mut_to: ptr<i32> = calloc(k, 4)
let split_to: ptr<i32> = calloc(k, 4)
let spawn_to: ptr<i32> = calloc(k, 4)
if a0 == null || a1 == null || a2 == null || a3 == null || a4 == null { return 1 }
let inv_m: f64 = 1.0 / (m as f64)
let mut i: i64 = 0
while i < k {
let mut c0: i64 = 0
let mut c1: i64 = 0
let mut c2: i64 = 0
let mut c3: i64 = 0
let mut c4: i64 = 0
let base: i64 = i * m
let mut j: i64 = 0
while j < m {
let q: i64 = (r[base + j] as i64) % 5
if q == 0 { c0 = c0 + 1 }
elif q == 1 { c1 = c1 + 1 }
elif q == 2 { c2 = c2 + 1 }
elif q == 3 { c3 = c3 + 1 }
else { c4 = c4 + 1 }
j = j + 1
}
a0[i] = (c0 as f64) * inv_m
a1[i] = (c1 as f64) * inv_m
a2[i] = (c2 as f64) * inv_m
a3[i] = (c3 as f64) * inv_m
a4[i] = (c4 as f64) * inv_m
mut_to[i] = ((2 * i) % k) as i32
split_to[i] = (((i * i) + 1) % k) as i32
spawn_to[i] = ((i + 1) % k) as i32
i = i + 1
}
let p: ptr<f64> = calloc(k, 8)
let newp: ptr<f64> = calloc(k, 8)
let mut iter: i64 = 0
while iter < 2000000 {
let mut max_delta: f64 = 0.0
i = 0
while i < k {
let pi: f64 = p[i]
let pm: f64 = p[mut_to[i] as i64]
let ps: f64 = p[split_to[i] as i64]
let psp: f64 = p[spawn_to[i] as i64]
let val: f64 = a0[i] + a1[i] * (pi * pi) + a2[i] * pm + a3[i] * (ps * ps * ps) + a4[i] * (pi * psp)
newp[i] = val
let mut d: f64 = val - pi
if d < 0.0 { d = 0.0 - d }
if d > max_delta { max_delta = d }
i = i + 1
}
i = 0
while i < k {
p[i] = newp[i]
i = i + 1
}
if max_delta < 1.0e-14 { break }
iter = iter + 1
}
printf("%.8f\n", p[0])
free(r)
free(a0)
free(a1)
free(a2)
free(a3)
free(a4)
free(mut_to)
free(split_to)
free(spawn_to)
free(p)
free(newp)
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; }
int32_t main(void);
int32_t main(void) {
int64_t k = 500;
int64_t m = 10;
int64_t MOD = 10007;
int64_t N = (k * m);
int32_t* r = (int32_t*)(calloc(N, 4));
if (r == NULL) {
return 1;
}
r[0] = 306;
int64_t n = 1;
while (n < N) {
int64_t x = ((int64_t)(r[(n - 1)]));
r[n] = ((int32_t)(FLOW_CHECKED_MOD(((x * x)), (MOD))));
n = (n + 1);
}
double* a0 = (double*)(calloc(k, 8));
double* a1 = (double*)(calloc(k, 8));
double* a2 = (double*)(calloc(k, 8));
double* a3 = (double*)(calloc(k, 8));
double* a4 = (double*)(calloc(k, 8));
int32_t* mut_to = (int32_t*)(calloc(k, 4));
int32_t* split_to = (int32_t*)(calloc(k, 4));
int32_t* spawn_to = (int32_t*)(calloc(k, 4));
if (((((a0 == NULL || a1 == NULL) || a2 == NULL) || a3 == NULL) || a4 == NULL)) {
return 1;
}
double inv_m = (1.0 / ((double)(m)));
int64_t i = 0;
while (i < k) {
int64_t c0 = 0;
int64_t c1 = 0;
int64_t c2 = 0;
int64_t c3 = 0;
int64_t c4 = 0;
int64_t base = (i * m);
int64_t j = 0;
while (j < m) {
int64_t q = FLOW_CHECKED_MOD((((int64_t)(r[(base + j)]))), (5));
if (q == 0) {
c0 = (c0 + 1);
} else if (q == 1) {
c1 = (c1 + 1);
} else if (q == 2) {
c2 = (c2 + 1);
} else if (q == 3) {
c3 = (c3 + 1);
} else {
c4 = (c4 + 1);
}
j = (j + 1);
}
a0[i] = (((double)(c0)) * inv_m);
a1[i] = (((double)(c1)) * inv_m);
a2[i] = (((double)(c2)) * inv_m);
a3[i] = (((double)(c3)) * inv_m);
a4[i] = (((double)(c4)) * inv_m);
mut_to[i] = ((int32_t)(FLOW_CHECKED_MOD(((2 * i)), (k))));
split_to[i] = ((int32_t)(FLOW_CHECKED_MOD((((i * i) + 1)), (k))));
spawn_to[i] = ((int32_t)(FLOW_CHECKED_MOD(((i + 1)), (k))));
i = (i + 1);
}
double* p = (double*)(calloc(k, 8));
double* newp = (double*)(calloc(k, 8));
int64_t iter = 0;
while (iter < 2000000) {
double max_delta = 0.0;
i = 0;
while (i < k) {
double pi = p[i];
double pm = p[((int64_t)(mut_to[i]))];
double ps = p[((int64_t)(split_to[i]))];
double psp = p[((int64_t)(spawn_to[i]))];
double val = ((((a0[i] + (a1[i] * (pi * pi))) + (a2[i] * pm)) + (a3[i] * ((ps * ps) * ps))) + (a4[i] * (pi * psp)));
newp[i] = val;
double d = (val - pi);
if (d < 0.0) {
d = (0.0 - d);
}
if (d > max_delta) {
max_delta = d;
}
i = (i + 1);
}
i = 0;
while (i < k) {
p[i] = newp[i];
i = (i + 1);
}
if (max_delta < 1.0e-14) {
break;
}
iter = (iter + 1);
}
printf("%.8f\n", p[0]);
free(r);
free(a0);
free(a1);
free(a2);
free(a3);
free(a4);
free(mut_to);
free(split_to);
free(spawn_to);
free(p);
free(newp);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.8f\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 @main() -> i32 {
%0 = arith.constant 500 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 10 : i32
%3 = arith.extsi %2 : i32 to i64
%4 = arith.constant 10007 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = arith.muli %1, %3 : i64
%8 = arith.constant 4 : i32
%9 = arith.extsi %8 : i32 to i64
%7 = func.call @calloc(%6, %9) : (i64, i64) -> !llvm.ptr
%10 = llvm.mlir.zero : !llvm.ptr
%11 = llvm.icmp "eq" %7, %10 : !llvm.ptr
cf.cond_br %11, ^bb0, ^bb1
^bb0:
%12 = arith.constant 1 : i32
func.return %12 : i32
^bb1:
cf.br ^bb2
^bb2:
%13 = arith.constant 306 : i32
%14 = arith.constant 0 : i32
%15 = arith.extsi %14 : i32 to i64
%16 = llvm.getelementptr %7[%15] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %13, %16 : i32, !llvm.ptr
%17 = arith.constant 1 : i32
%18 = arith.extsi %17 : i32 to i64
%19 = llvm.mlir.constant(1 : i64) : i64
%20 = llvm.alloca %19 x i64 : (i64) -> !llvm.ptr
llvm.store %18, %20 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%21 = llvm.load %20 : !llvm.ptr -> i64
%22 = arith.cmpi slt, %21, %6 : i64
cf.cond_br %22, ^bb4, ^bb5
^bb4:
%24 = llvm.load %20 : !llvm.ptr -> i64
%25 = arith.constant 1 : i32
%27 = arith.extsi %25 : i32 to i64
%26 = arith.subi %24, %27 : i64
%28 = llvm.getelementptr %7[%26] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%23 = llvm.load %28 : !llvm.ptr -> i32
%29 = arith.extsi %23 : i32 to i64
%30 = arith.muli %29, %29 : i64
%31 = arith.remsi %30, %5 : i64
%32 = arith.trunci %31 : i64 to i32
%33 = llvm.load %20 : !llvm.ptr -> i64
%34 = llvm.getelementptr %7[%33] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %32, %34 : i32, !llvm.ptr
%35 = llvm.load %20 : !llvm.ptr -> i64
%36 = arith.constant 1 : i32
%38 = arith.extsi %36 : i32 to i64
%37 = arith.addi %35, %38 : i64
llvm.store %37, %20 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%40 = arith.constant 8 : i32
%41 = arith.extsi %40 : i32 to i64
%39 = func.call @calloc(%1, %41) : (i64, i64) -> !llvm.ptr
%43 = arith.constant 8 : i32
%44 = arith.extsi %43 : i32 to i64
%42 = func.call @calloc(%1, %44) : (i64, i64) -> !llvm.ptr
%46 = arith.constant 8 : i32
%47 = arith.extsi %46 : i32 to i64
%45 = func.call @calloc(%1, %47) : (i64, i64) -> !llvm.ptr
%49 = arith.constant 8 : i32
%50 = arith.extsi %49 : i32 to i64
%48 = func.call @calloc(%1, %50) : (i64, i64) -> !llvm.ptr
%52 = arith.constant 8 : i32
%53 = arith.extsi %52 : i32 to i64
%51 = func.call @calloc(%1, %53) : (i64, i64) -> !llvm.ptr
%55 = arith.constant 4 : i32
%56 = arith.extsi %55 : i32 to i64
%54 = func.call @calloc(%1, %56) : (i64, i64) -> !llvm.ptr
%58 = arith.constant 4 : i32
%59 = arith.extsi %58 : i32 to i64
%57 = func.call @calloc(%1, %59) : (i64, i64) -> !llvm.ptr
%61 = arith.constant 4 : i32
%62 = arith.extsi %61 : i32 to i64
%60 = func.call @calloc(%1, %62) : (i64, i64) -> !llvm.ptr
%63 = llvm.mlir.zero : !llvm.ptr
%64 = llvm.icmp "eq" %39, %63 : !llvm.ptr
%65 = scf.if %64 -> (i1) {
%66 = arith.constant true
scf.yield %66 : i1
} else {
%67 = llvm.mlir.zero : !llvm.ptr
%68 = llvm.icmp "eq" %42, %67 : !llvm.ptr
scf.yield %68 : i1
}
%69 = scf.if %65 -> (i1) {
%70 = arith.constant true
scf.yield %70 : i1
} else {
%71 = llvm.mlir.zero : !llvm.ptr
%72 = llvm.icmp "eq" %45, %71 : !llvm.ptr
scf.yield %72 : i1
}
%73 = scf.if %69 -> (i1) {
%74 = arith.constant true
scf.yield %74 : i1
} else {
%75 = llvm.mlir.zero : !llvm.ptr
%76 = llvm.icmp "eq" %48, %75 : !llvm.ptr
scf.yield %76 : i1
}
%77 = scf.if %73 -> (i1) {
%78 = arith.constant true
scf.yield %78 : i1
} else {
%79 = llvm.mlir.zero : !llvm.ptr
%80 = llvm.icmp "eq" %51, %79 : !llvm.ptr
scf.yield %80 : i1
}
cf.cond_br %77, ^bb6, ^bb7
^bb6:
%81 = arith.constant 1 : i32
func.return %81 : i32
^bb7:
cf.br ^bb8
^bb8:
%82 = arith.constant 1.0 : f32
%83 = arith.sitofp %3 : i64 to f64
%85 = arith.extf %82 : f32 to f64
%84 = arith.divf %85, %83 : f64
%86 = arith.constant 0 : i32
%87 = arith.extsi %86 : i32 to i64
%88 = llvm.mlir.constant(1 : i64) : i64
%89 = llvm.alloca %88 x i64 : (i64) -> !llvm.ptr
llvm.store %87, %89 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%90 = llvm.load %89 : !llvm.ptr -> i64
%91 = arith.cmpi slt, %90, %1 : i64
cf.cond_br %91, ^bb10, ^bb11
^bb10:
%92 = arith.constant 0 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.constant 0 : i32
%97 = arith.extsi %96 : i32 to i64
%98 = llvm.mlir.constant(1 : i64) : i64
%99 = llvm.alloca %98 x i64 : (i64) -> !llvm.ptr
llvm.store %97, %99 : i64, !llvm.ptr
%100 = arith.constant 0 : i32
%101 = arith.extsi %100 : i32 to i64
%102 = llvm.mlir.constant(1 : i64) : i64
%103 = llvm.alloca %102 x i64 : (i64) -> !llvm.ptr
llvm.store %101, %103 : i64, !llvm.ptr
%104 = arith.constant 0 : i32
%105 = arith.extsi %104 : i32 to i64
%106 = llvm.mlir.constant(1 : i64) : i64
%107 = llvm.alloca %106 x i64 : (i64) -> !llvm.ptr
llvm.store %105, %107 : i64, !llvm.ptr
%108 = arith.constant 0 : i32
%109 = arith.extsi %108 : i32 to i64
%110 = llvm.mlir.constant(1 : i64) : i64
%111 = llvm.alloca %110 x i64 : (i64) -> !llvm.ptr
llvm.store %109, %111 : i64, !llvm.ptr
%112 = llvm.load %89 : !llvm.ptr -> i64
%113 = arith.muli %112, %3 : i64
%114 = arith.constant 0 : i32
%115 = arith.extsi %114 : i32 to i64
%116 = llvm.mlir.constant(1 : i64) : i64
%117 = llvm.alloca %116 x i64 : (i64) -> !llvm.ptr
llvm.store %115, %117 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%118 = llvm.load %117 : !llvm.ptr -> i64
%119 = arith.cmpi slt, %118, %3 : i64
cf.cond_br %119, ^bb13, ^bb14
^bb13:
%121 = llvm.load %117 : !llvm.ptr -> i64
%122 = arith.addi %113, %121 : i64
%123 = llvm.getelementptr %7[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%120 = llvm.load %123 : !llvm.ptr -> i32
%124 = arith.extsi %120 : i32 to i64
%125 = arith.constant 5 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.remsi %124, %127 : i64
%128 = arith.constant 0 : i32
%130 = arith.extsi %128 : i32 to i64
%129 = arith.cmpi eq, %126, %130 : i64
cf.cond_br %129, ^bb15, ^bb16
^bb15:
%131 = llvm.load %95 : !llvm.ptr -> i64
%132 = arith.constant 1 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.addi %131, %134 : i64
llvm.store %133, %95 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
%135 = arith.constant 1 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.cmpi eq, %126, %137 : i64
cf.cond_br %136, ^bb19, ^bb18
^bb19:
%138 = llvm.load %99 : !llvm.ptr -> i64
%139 = arith.constant 1 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.addi %138, %141 : i64
llvm.store %140, %99 : i64, !llvm.ptr
cf.br ^bb17
^bb18:
%142 = arith.constant 2 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %126, %144 : i64
cf.cond_br %143, ^bb21, ^bb20
^bb21:
%145 = llvm.load %103 : !llvm.ptr -> i64
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.addi %145, %148 : i64
llvm.store %147, %103 : i64, !llvm.ptr
cf.br ^bb17
^bb20:
%149 = arith.constant 3 : i32
%151 = arith.extsi %149 : i32 to i64
%150 = arith.cmpi eq, %126, %151 : i64
cf.cond_br %150, ^bb23, ^bb22
^bb23:
%152 = llvm.load %107 : !llvm.ptr -> i64
%153 = arith.constant 1 : i32
%155 = arith.extsi %153 : i32 to i64
%154 = arith.addi %152, %155 : i64
llvm.store %154, %107 : i64, !llvm.ptr
cf.br ^bb17
^bb22:
%156 = llvm.load %111 : !llvm.ptr -> i64
%157 = arith.constant 1 : i32
%159 = arith.extsi %157 : i32 to i64
%158 = arith.addi %156, %159 : i64
llvm.store %158, %111 : i64, !llvm.ptr
cf.br ^bb17
^bb17:
%160 = llvm.load %117 : !llvm.ptr -> i64
%161 = arith.constant 1 : i32
%163 = arith.extsi %161 : i32 to i64
%162 = arith.addi %160, %163 : i64
llvm.store %162, %117 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%164 = llvm.load %95 : !llvm.ptr -> i64
%165 = arith.sitofp %164 : i64 to f64
%166 = arith.mulf %165, %84 : f64
%167 = llvm.load %89 : !llvm.ptr -> i64
%168 = llvm.getelementptr %39[%167] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %166, %168 : f64, !llvm.ptr
%169 = llvm.load %99 : !llvm.ptr -> i64
%170 = arith.sitofp %169 : i64 to f64
%171 = arith.mulf %170, %84 : f64
%172 = llvm.load %89 : !llvm.ptr -> i64
%173 = llvm.getelementptr %42[%172] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %171, %173 : f64, !llvm.ptr
%174 = llvm.load %103 : !llvm.ptr -> i64
%175 = arith.sitofp %174 : i64 to f64
%176 = arith.mulf %175, %84 : f64
%177 = llvm.load %89 : !llvm.ptr -> i64
%178 = llvm.getelementptr %45[%177] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %176, %178 : f64, !llvm.ptr
%179 = llvm.load %107 : !llvm.ptr -> i64
%180 = arith.sitofp %179 : i64 to f64
%181 = arith.mulf %180, %84 : f64
%182 = llvm.load %89 : !llvm.ptr -> i64
%183 = llvm.getelementptr %48[%182] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %181, %183 : f64, !llvm.ptr
%184 = llvm.load %111 : !llvm.ptr -> i64
%185 = arith.sitofp %184 : i64 to f64
%186 = arith.mulf %185, %84 : f64
%187 = llvm.load %89 : !llvm.ptr -> i64
%188 = llvm.getelementptr %51[%187] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %186, %188 : f64, !llvm.ptr
%189 = arith.constant 2 : i32
%190 = llvm.load %89 : !llvm.ptr -> i64
%192 = arith.extsi %189 : i32 to i64
%191 = arith.muli %192, %190 : i64
%193 = arith.remsi %191, %1 : i64
%194 = arith.trunci %193 : i64 to i32
%195 = llvm.load %89 : !llvm.ptr -> i64
%196 = llvm.getelementptr %54[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %194, %196 : i32, !llvm.ptr
%197 = llvm.load %89 : !llvm.ptr -> i64
%198 = llvm.load %89 : !llvm.ptr -> i64
%199 = arith.muli %197, %198 : i64
%200 = arith.constant 1 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.addi %199, %202 : i64
%203 = arith.remsi %201, %1 : i64
%204 = arith.trunci %203 : i64 to i32
%205 = llvm.load %89 : !llvm.ptr -> i64
%206 = llvm.getelementptr %57[%205] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %204, %206 : i32, !llvm.ptr
%207 = llvm.load %89 : !llvm.ptr -> i64
%208 = arith.constant 1 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.addi %207, %210 : i64
%211 = arith.remsi %209, %1 : i64
%212 = arith.trunci %211 : i64 to i32
%213 = llvm.load %89 : !llvm.ptr -> i64
%214 = llvm.getelementptr %60[%213] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %212, %214 : i32, !llvm.ptr
%215 = llvm.load %89 : !llvm.ptr -> i64
%216 = arith.constant 1 : i32
%218 = arith.extsi %216 : i32 to i64
%217 = arith.addi %215, %218 : i64
llvm.store %217, %89 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%220 = arith.constant 8 : i32
%221 = arith.extsi %220 : i32 to i64
%219 = func.call @calloc(%1, %221) : (i64, i64) -> !llvm.ptr
%223 = arith.constant 8 : i32
%224 = arith.extsi %223 : i32 to i64
%222 = func.call @calloc(%1, %224) : (i64, i64) -> !llvm.ptr
%225 = arith.constant 0 : i32
%226 = arith.extsi %225 : i32 to i64
%227 = llvm.mlir.constant(1 : i64) : i64
%228 = llvm.alloca %227 x i64 : (i64) -> !llvm.ptr
llvm.store %226, %228 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%229 = llvm.load %228 : !llvm.ptr -> i64
%230 = arith.constant 2000000 : i32
%232 = arith.extsi %230 : i32 to i64
%231 = arith.cmpi slt, %229, %232 : i64
cf.cond_br %231, ^bb25, ^bb26
^bb25:
%233 = arith.constant 0.0 : f32
%234 = arith.extf %233 : f32 to f64
%235 = llvm.mlir.constant(1 : i64) : i64
%236 = llvm.alloca %235 x f64 : (i64) -> !llvm.ptr
llvm.store %234, %236 : f64, !llvm.ptr
%237 = arith.constant 0 : i32
%238 = arith.extsi %237 : i32 to i64
llvm.store %238, %89 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%239 = llvm.load %89 : !llvm.ptr -> i64
%240 = arith.cmpi slt, %239, %1 : i64
cf.cond_br %240, ^bb28, ^bb29
^bb28:
%242 = llvm.load %89 : !llvm.ptr -> i64
%243 = llvm.getelementptr %219[%242] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%241 = llvm.load %243 : !llvm.ptr -> f64
%246 = llvm.load %89 : !llvm.ptr -> i64
%247 = llvm.getelementptr %54[%246] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%245 = llvm.load %247 : !llvm.ptr -> i32
%248 = arith.extsi %245 : i32 to i64
%249 = llvm.getelementptr %219[%248] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%244 = llvm.load %249 : !llvm.ptr -> f64
%252 = llvm.load %89 : !llvm.ptr -> i64
%253 = llvm.getelementptr %57[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%251 = llvm.load %253 : !llvm.ptr -> i32
%254 = arith.extsi %251 : i32 to i64
%255 = llvm.getelementptr %219[%254] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%250 = llvm.load %255 : !llvm.ptr -> f64
%258 = llvm.load %89 : !llvm.ptr -> i64
%259 = llvm.getelementptr %60[%258] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%257 = llvm.load %259 : !llvm.ptr -> i32
%260 = arith.extsi %257 : i32 to i64
%261 = llvm.getelementptr %219[%260] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%256 = llvm.load %261 : !llvm.ptr -> f64
%263 = llvm.load %89 : !llvm.ptr -> i64
%264 = llvm.getelementptr %39[%263] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%262 = llvm.load %264 : !llvm.ptr -> f64
%266 = llvm.load %89 : !llvm.ptr -> i64
%267 = llvm.getelementptr %42[%266] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%265 = llvm.load %267 : !llvm.ptr -> f64
%268 = arith.mulf %241, %241 : f64
%269 = arith.mulf %265, %268 : f64
%270 = arith.addf %262, %269 : f64
%272 = llvm.load %89 : !llvm.ptr -> i64
%273 = llvm.getelementptr %45[%272] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%271 = llvm.load %273 : !llvm.ptr -> f64
%274 = arith.mulf %271, %244 : f64
%275 = arith.addf %270, %274 : f64
%277 = llvm.load %89 : !llvm.ptr -> i64
%278 = llvm.getelementptr %48[%277] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%276 = llvm.load %278 : !llvm.ptr -> f64
%279 = arith.mulf %250, %250 : f64
%280 = arith.mulf %279, %250 : f64
%281 = arith.mulf %276, %280 : f64
%282 = arith.addf %275, %281 : f64
%284 = llvm.load %89 : !llvm.ptr -> i64
%285 = llvm.getelementptr %51[%284] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%283 = llvm.load %285 : !llvm.ptr -> f64
%286 = arith.mulf %241, %256 : f64
%287 = arith.mulf %283, %286 : f64
%288 = arith.addf %282, %287 : f64
%289 = llvm.load %89 : !llvm.ptr -> i64
%290 = llvm.getelementptr %222[%289] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %288, %290 : f64, !llvm.ptr
%291 = arith.subf %288, %241 : f64
%292 = llvm.mlir.constant(1 : i64) : i64
%293 = llvm.alloca %292 x f64 : (i64) -> !llvm.ptr
llvm.store %291, %293 : f64, !llvm.ptr
%294 = llvm.load %293 : !llvm.ptr -> f64
%295 = arith.constant 0.0 : f32
%297 = arith.extf %295 : f32 to f64
%296 = arith.cmpf olt, %294, %297 : f64
cf.cond_br %296, ^bb30, ^bb31
^bb30:
%298 = arith.constant 0.0 : f32
%299 = llvm.load %293 : !llvm.ptr -> f64
%301 = arith.extf %298 : f32 to f64
%300 = arith.subf %301, %299 : f64
llvm.store %300, %293 : f64, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%302 = llvm.load %293 : !llvm.ptr -> f64
%303 = llvm.load %236 : !llvm.ptr -> f64
%304 = arith.cmpf ogt, %302, %303 : f64
cf.cond_br %304, ^bb33, ^bb34
^bb33:
%305 = llvm.load %293 : !llvm.ptr -> f64
llvm.store %305, %236 : f64, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%306 = llvm.load %89 : !llvm.ptr -> i64
%307 = arith.constant 1 : i32
%309 = arith.extsi %307 : i32 to i64
%308 = arith.addi %306, %309 : i64
llvm.store %308, %89 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%310 = arith.constant 0 : i32
%311 = arith.extsi %310 : i32 to i64
llvm.store %311, %89 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%312 = llvm.load %89 : !llvm.ptr -> i64
%313 = arith.cmpi slt, %312, %1 : i64
cf.cond_br %313, ^bb37, ^bb38
^bb37:
%315 = llvm.load %89 : !llvm.ptr -> i64
%316 = llvm.getelementptr %222[%315] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%314 = llvm.load %316 : !llvm.ptr -> f64
%317 = llvm.load %89 : !llvm.ptr -> i64
%318 = llvm.getelementptr %219[%317] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %314, %318 : f64, !llvm.ptr
%319 = llvm.load %89 : !llvm.ptr -> i64
%320 = arith.constant 1 : i32
%322 = arith.extsi %320 : i32 to i64
%321 = arith.addi %319, %322 : i64
llvm.store %321, %89 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%323 = llvm.load %236 : !llvm.ptr -> f64
%324 = arith.constant 0 : f32
%326 = arith.extf %324 : f32 to f64
%325 = arith.cmpf olt, %323, %326 : f64
cf.cond_br %325, ^bb39, ^bb40
^bb39:
cf.br ^bb26
^bb40:
cf.br ^bb41
^bb41:
%327 = llvm.load %228 : !llvm.ptr -> i64
%328 = arith.constant 1 : i32
%330 = arith.extsi %328 : i32 to i64
%329 = arith.addi %327, %330 : i64
llvm.store %329, %228 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%331 = llvm.mlir.addressof @str_0 : !llvm.ptr
%333 = arith.constant 0 : i32
%334 = arith.extsi %333 : i32 to i64
%335 = llvm.getelementptr %219[%334] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%332 = llvm.load %335 : !llvm.ptr -> f64
%336 = llvm.call @printf(%331, %332) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64) -> i32
func.call @free(%7) : (!llvm.ptr) -> ()
func.call @free(%39) : (!llvm.ptr) -> ()
func.call @free(%42) : (!llvm.ptr) -> ()
func.call @free(%45) : (!llvm.ptr) -> ()
func.call @free(%48) : (!llvm.ptr) -> ()
func.call @free(%51) : (!llvm.ptr) -> ()
func.call @free(%54) : (!llvm.ptr) -> ()
func.call @free(%57) : (!llvm.ptr) -> ()
func.call @free(%60) : (!llvm.ptr) -> ()
func.call @free(%219) : (!llvm.ptr) -> ()
func.call @free(%222) : (!llvm.ptr) -> ()
%348 = arith.constant 0 : i32
func.return %348 : i32
}
}