Problem 431
Sum of horizontal offsets x where wasted silo volume is an integer square.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^3) | O(n log log n) |
|---|
| Space complexity | O(n) | O(n) |
|---|
| Approach | Flow solution | Sieve or enumeration |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 431
# Sum of horizontal offsets x where wasted silo volume is an integer square.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function sin(x: f64) -> f64
function cos(x: f64) -> f64
function sqrt(x: f64) -> f64
function tan(x: f64) -> f64
}
function wasted(x: f64, R: f64, tanal: f64, nodes: ptr<f64>, weights: ptr<f64>, nq: i64) -> f64 {
let mut s: f64 = 0.0
let mut i: i64 = 0
while i < nq {
let theta: f64 = nodes[i]
let sn: f64 = sin(theta)
let cn: f64 = cos(theta)
let mut rad: f64 = R * R - (x * sn) * (x * sn)
if rad < 0.0 { rad = 0.0 }
let rmax: f64 = -x * cn + sqrt(rad)
s = s + weights[i] * rmax * rmax * rmax
i = i + 1
}
return tanal * (2.0 / 3.0) * s
}
function main() -> i32 {
let PI: f64 = 3.14159265358979323846
let R: f64 = 6.0
let alpha: f64 = 40.0 * PI / 180.0
let tanal: f64 = tan(alpha)
# 64-point Gauss-Legendre on [0, pi]
let NQ: i64 = 64
let nodes: ptr<f64> = calloc(NQ, 8)
let weights: ptr<f64> = calloc(NQ, 8)
if nodes == null || weights == null { return 1 }
let mut i: i64 = 0
let m: i64 = (NQ + 1) / 2
while i < m {
let mut z: f64 = cos(PI * ((i as f64) + 0.75) / ((NQ as f64) + 0.5))
while true {
let mut p1: f64 = 1.0
let mut p2: f64 = 0.0
let mut k: i64 = 1
while k <= NQ {
let p3: f64 = p2
p2 = p1
p1 = (((2 * k - 1) as f64) * z * p2 - ((k - 1) as f64) * p3) / (k as f64)
k = k + 1
}
let pp: f64 = (NQ as f64) * (z * p1 - p2) / (z * z - 1.0)
let z1: f64 = z
z = z1 - p1 / pp
let mut dz: f64 = z - z1
if dz < 0.0 { dz = -dz }
if dz < 1.0e-15 { break }
}
let mut p1b: f64 = 1.0
let mut p2b: f64 = 0.0
let mut kb: i64 = 1
while kb <= NQ {
let p3b: f64 = p2b
p2b = p1b
p1b = (((2 * kb - 1) as f64) * z * p2b - ((kb - 1) as f64) * p3b) / (kb as f64)
kb = kb + 1
}
let ppb: f64 = (NQ as f64) * (z * p1b - p2b) / (z * z - 1.0)
let w: f64 = 2.0 / ((1.0 - z * z) * ppb * ppb)
# map [-1,1] -> [0, pi]
let mid: f64 = PI * 0.5
let half: f64 = PI * 0.5
nodes[i] = mid + half * (-z)
nodes[NQ - 1 - i] = mid + half * z
weights[i] = half * w
weights[NQ - 1 - i] = half * w
i = i + 1
}
let v0: f64 = wasted(0.0, R, tanal, nodes, weights, NQ)
let vR: f64 = wasted(R, R, tanal, nodes, weights, NQ)
let mut n_min: i64 = 0
while ((n_min * n_min) as f64) < v0 - 1.0e-12 {
n_min = n_min + 1
}
let mut n_max: i64 = 0
while (((n_max + 1) * (n_max + 1)) as f64) <= vR + 1.0e-12 {
n_max = n_max + 1
}
let mut total: f64 = 0.0
let mut n: i64 = n_min
while n <= n_max {
let target: f64 = (n * n) as f64
let mut lo: f64 = 0.0
let mut hi: f64 = R
let mut it: i64 = 0
while it < 70 {
let mid: f64 = (lo + hi) * 0.5
let fmid: f64 = wasted(mid, R, tanal, nodes, weights, NQ) - target
if fmid >= 0.0 {
hi = mid
} else {
lo = mid
}
it = it + 1
}
total = total + (lo + hi) * 0.5
n = n + 1
}
printf("%.9f\n", total)
free(weights)
free(nodes)
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 wasted_f64_f64_f64_ptr_f64_ptr_f64_i64(double x, double R, double tanal, double* nodes, double* weights, int64_t nq);
int32_t main(void);
double wasted_f64_f64_f64_ptr_f64_ptr_f64_i64(double x, double R, double tanal, double* nodes, double* weights, int64_t nq) {
double s = 0.0;
int64_t i = 0;
while (i < nq) {
double theta = nodes[i];
double sn = sin(theta);
double cn = cos(theta);
double rad = ((R * R) - ((x * sn) * (x * sn)));
if (rad < 0.0) {
rad = 0.0;
}
double rmax = (((-x) * cn) + sqrt(rad));
s = (s + (((weights[i] * rmax) * rmax) * rmax));
i = (i + 1);
}
return ((tanal * (2.0 / 3.0)) * s);
}
int32_t main(void) {
double PI = 3.14159265358979323846;
double R = 6.0;
double alpha = ((40.0 * PI) / 180.0);
double tanal = tan(alpha);
int64_t NQ = 64;
double* nodes = (double*)(calloc(NQ, 8));
double* weights = (double*)(calloc(NQ, 8));
if ((nodes == NULL || weights == NULL)) {
return 1;
}
int64_t i = 0;
int64_t m = FLOW_CHECKED_DIV(((NQ + 1)), (2));
while (i < m) {
double z = cos(((PI * (((double)(i)) + 0.75)) / (((double)(NQ)) + 0.5)));
while (1) {
double p1 = 1.0;
double p2 = 0.0;
int64_t k = 1;
while (k <= NQ) {
double p3 = p2;
p2 = p1;
p1 = ((((((double)(((2 * k) - 1))) * z) * p2) - (((double)((k - 1))) * p3)) / ((double)(k)));
k = (k + 1);
}
double pp = ((((double)(NQ)) * ((z * p1) - p2)) / ((z * z) - 1.0));
double z1 = z;
z = (z1 - (p1 / pp));
double dz = (z - z1);
if (dz < 0.0) {
dz = (-dz);
}
if (dz < 1.0e-15) {
break;
}
}
double p1b = 1.0;
double p2b = 0.0;
int64_t kb = 1;
while (kb <= NQ) {
double p3b = p2b;
p2b = p1b;
p1b = ((((((double)(((2 * kb) - 1))) * z) * p2b) - (((double)((kb - 1))) * p3b)) / ((double)(kb)));
kb = (kb + 1);
}
double ppb = ((((double)(NQ)) * ((z * p1b) - p2b)) / ((z * z) - 1.0));
double w = (2.0 / (((1.0 - (z * z)) * ppb) * ppb));
double mid = (PI * 0.5);
double half = (PI * 0.5);
nodes[i] = (mid + (half * (-z)));
nodes[((NQ - 1) - i)] = (mid + (half * z));
weights[i] = (half * w);
weights[((NQ - 1) - i)] = (half * w);
i = (i + 1);
}
double v0 = wasted_f64_f64_f64_ptr_f64_ptr_f64_i64(0.0, R, tanal, nodes, weights, NQ);
double vR = wasted_f64_f64_f64_ptr_f64_ptr_f64_i64(R, R, tanal, nodes, weights, NQ);
int64_t n_min = 0;
while (((double)((n_min * n_min))) < (v0 - 1.0e-12)) {
n_min = (n_min + 1);
}
int64_t n_max = 0;
while (((double)(((n_max + 1) * (n_max + 1)))) <= (vR + 1.0e-12)) {
n_max = (n_max + 1);
}
double total = 0.0;
int64_t n = n_min;
while (n <= n_max) {
double target = ((double)((n * n)));
double lo = 0.0;
double hi = R;
int64_t it = 0;
while (it < 70) {
double mid = ((lo + hi) * 0.5);
double fmid = (wasted_f64_f64_f64_ptr_f64_ptr_f64_i64(mid, R, tanal, nodes, weights, NQ) - target);
if (fmid >= 0.0) {
hi = mid;
} else {
lo = mid;
}
it = (it + 1);
}
total = (total + ((lo + hi) * 0.5));
n = (n + 1);
}
printf("%.9f\n", total);
free(weights);
free(nodes);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.9f\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 @sin(f64) -> f64
func.func private @cos(f64) -> f64
func.func private @sqrt(f64) -> f64
func.func private @tan(f64) -> f64
func.func @wasted(%arg0: f64, %arg1: f64, %arg2: f64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i64) -> f64 {
%0 = arith.constant 0.0 : f32
%1 = arith.extf %0 : f32 to f64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x f64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : f64, !llvm.ptr
%4 = arith.constant 0 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%8 = llvm.load %7 : !llvm.ptr -> i64
%9 = arith.cmpi slt, %8, %arg5 : i64
cf.cond_br %9, ^bb1, ^bb2
^bb1:
%11 = llvm.load %7 : !llvm.ptr -> i64
%12 = llvm.getelementptr %arg3[%11] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%10 = llvm.load %12 : !llvm.ptr -> f64
%13 = math.sin %10 : f64
%14 = math.cos %10 : f64
%15 = arith.mulf %arg1, %arg1 : f64
%16 = arith.mulf %arg0, %13 : f64
%17 = arith.mulf %arg0, %13 : f64
%18 = arith.mulf %16, %17 : f64
%19 = arith.subf %15, %18 : f64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x f64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : f64, !llvm.ptr
%22 = llvm.load %21 : !llvm.ptr -> f64
%23 = arith.constant 0.0 : f32
%25 = arith.extf %23 : f32 to f64
%24 = arith.cmpf olt, %22, %25 : f64
cf.cond_br %24, ^bb3, ^bb4
^bb3:
%26 = arith.constant 0.0 : f32
%27 = arith.extf %26 : f32 to f64
llvm.store %27, %21 : f64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%28 = arith.negf %arg0 : f64
%29 = arith.mulf %28, %14 : f64
%30 = llvm.load %21 : !llvm.ptr -> f64
%31 = math.sqrt %30 : f64
%32 = arith.addf %29, %31 : f64
%33 = llvm.load %3 : !llvm.ptr -> f64
%35 = llvm.load %7 : !llvm.ptr -> i64
%36 = llvm.getelementptr %arg4[%35] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%34 = llvm.load %36 : !llvm.ptr -> f64
%37 = arith.mulf %34, %32 : f64
%38 = arith.mulf %37, %32 : f64
%39 = arith.mulf %38, %32 : f64
%40 = arith.addf %33, %39 : f64
llvm.store %40, %3 : f64, !llvm.ptr
%41 = llvm.load %7 : !llvm.ptr -> i64
%42 = arith.constant 1 : i32
%44 = arith.extsi %42 : i32 to i64
%43 = arith.addi %41, %44 : i64
llvm.store %43, %7 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%45 = arith.constant 2.0 : f32
%46 = arith.constant 3.0 : f32
%47 = arith.divf %45, %46 : f32
%49 = arith.extf %47 : f32 to f64
%48 = arith.mulf %arg2, %49 : f64
%50 = llvm.load %3 : !llvm.ptr -> f64
%51 = arith.mulf %48, %50 : f64
func.return %51 : f64
}
func.func @main() -> i32 {
%52 = arith.constant 3.14159265358979323846 : f32
%53 = arith.extf %52 : f32 to f64
%54 = arith.constant 6.0 : f32
%55 = arith.extf %54 : f32 to f64
%56 = arith.constant 40.0 : f32
%58 = arith.extf %56 : f32 to f64
%57 = arith.mulf %58, %53 : f64
%59 = arith.constant 180.0 : f32
%61 = arith.extf %59 : f32 to f64
%60 = arith.divf %57, %61 : f64
%62 = math.tan %60 : f64
%63 = arith.constant 64 : i32
%64 = arith.extsi %63 : i32 to i64
%66 = arith.constant 8 : i32
%67 = arith.extsi %66 : i32 to i64
%65 = func.call @calloc(%64, %67) : (i64, i64) -> !llvm.ptr
%69 = arith.constant 8 : i32
%70 = arith.extsi %69 : i32 to i64
%68 = func.call @calloc(%64, %70) : (i64, i64) -> !llvm.ptr
%71 = llvm.mlir.zero : !llvm.ptr
%72 = llvm.icmp "eq" %65, %71 : !llvm.ptr
%73 = scf.if %72 -> (i1) {
%74 = arith.constant true
scf.yield %74 : i1
} else {
%75 = llvm.mlir.zero : !llvm.ptr
%76 = llvm.icmp "eq" %68, %75 : !llvm.ptr
scf.yield %76 : i1
}
cf.cond_br %73, ^bb6, ^bb7
^bb6:
%77 = arith.constant 1 : i32
func.return %77 : i32
^bb7:
cf.br ^bb8
^bb8:
%78 = arith.constant 0 : i32
%79 = arith.extsi %78 : i32 to i64
%80 = llvm.mlir.constant(1 : i64) : i64
%81 = llvm.alloca %80 x i64 : (i64) -> !llvm.ptr
llvm.store %79, %81 : i64, !llvm.ptr
%82 = arith.constant 1 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.addi %64, %84 : i64
%85 = arith.constant 2 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.divsi %83, %87 : i64
cf.br ^bb9
^bb9:
%88 = llvm.load %81 : !llvm.ptr -> i64
%89 = arith.cmpi slt, %88, %86 : i64
cf.cond_br %89, ^bb10, ^bb11
^bb10:
%90 = llvm.load %81 : !llvm.ptr -> i64
%91 = arith.sitofp %90 : i64 to f64
%92 = arith.constant 0.75 : f32
%94 = arith.extf %92 : f32 to f64
%93 = arith.addf %91, %94 : f64
%95 = arith.mulf %53, %93 : f64
%96 = arith.sitofp %64 : i64 to f64
%97 = arith.constant 0.5 : f32
%99 = arith.extf %97 : f32 to f64
%98 = arith.addf %96, %99 : f64
%100 = arith.divf %95, %98 : f64
%101 = math.cos %100 : f64
%102 = llvm.mlir.constant(1 : i64) : i64
%103 = llvm.alloca %102 x f64 : (i64) -> !llvm.ptr
llvm.store %101, %103 : f64, !llvm.ptr
cf.br ^bb12
^bb12:
%104 = arith.constant 1 : i1
cf.cond_br %104, ^bb13, ^bb14
^bb13:
%105 = arith.constant 1.0 : f32
%106 = arith.extf %105 : f32 to f64
%107 = llvm.mlir.constant(1 : i64) : i64
%108 = llvm.alloca %107 x f64 : (i64) -> !llvm.ptr
llvm.store %106, %108 : f64, !llvm.ptr
%109 = arith.constant 0.0 : f32
%110 = arith.extf %109 : f32 to f64
%111 = llvm.mlir.constant(1 : i64) : i64
%112 = llvm.alloca %111 x f64 : (i64) -> !llvm.ptr
llvm.store %110, %112 : f64, !llvm.ptr
%113 = arith.constant 1 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.mlir.constant(1 : i64) : i64
%116 = llvm.alloca %115 x i64 : (i64) -> !llvm.ptr
llvm.store %114, %116 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%117 = llvm.load %116 : !llvm.ptr -> i64
%118 = arith.cmpi sle, %117, %64 : i64
cf.cond_br %118, ^bb16, ^bb17
^bb16:
%119 = llvm.load %112 : !llvm.ptr -> f64
%120 = llvm.load %108 : !llvm.ptr -> f64
llvm.store %120, %112 : f64, !llvm.ptr
%121 = arith.constant 2 : i32
%122 = llvm.load %116 : !llvm.ptr -> i64
%124 = arith.extsi %121 : i32 to i64
%123 = arith.muli %124, %122 : i64
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.subi %123, %127 : i64
%128 = arith.sitofp %126 : i64 to f64
%129 = llvm.load %103 : !llvm.ptr -> f64
%130 = arith.mulf %128, %129 : f64
%131 = llvm.load %112 : !llvm.ptr -> f64
%132 = arith.mulf %130, %131 : f64
%133 = llvm.load %116 : !llvm.ptr -> i64
%134 = arith.constant 1 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.subi %133, %136 : i64
%137 = arith.sitofp %135 : i64 to f64
%138 = arith.mulf %137, %119 : f64
%139 = arith.subf %132, %138 : f64
%140 = llvm.load %116 : !llvm.ptr -> i64
%141 = arith.sitofp %140 : i64 to f64
%142 = arith.divf %139, %141 : f64
llvm.store %142, %108 : f64, !llvm.ptr
%143 = llvm.load %116 : !llvm.ptr -> i64
%144 = arith.constant 1 : i32
%146 = arith.extsi %144 : i32 to i64
%145 = arith.addi %143, %146 : i64
llvm.store %145, %116 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%147 = arith.sitofp %64 : i64 to f64
%148 = llvm.load %103 : !llvm.ptr -> f64
%149 = llvm.load %108 : !llvm.ptr -> f64
%150 = arith.mulf %148, %149 : f64
%151 = llvm.load %112 : !llvm.ptr -> f64
%152 = arith.subf %150, %151 : f64
%153 = arith.mulf %147, %152 : f64
%154 = llvm.load %103 : !llvm.ptr -> f64
%155 = llvm.load %103 : !llvm.ptr -> f64
%156 = arith.mulf %154, %155 : f64
%157 = arith.constant 1.0 : f32
%159 = arith.extf %157 : f32 to f64
%158 = arith.subf %156, %159 : f64
%160 = arith.divf %153, %158 : f64
%161 = llvm.load %103 : !llvm.ptr -> f64
%162 = llvm.load %108 : !llvm.ptr -> f64
%163 = arith.divf %162, %160 : f64
%164 = arith.subf %161, %163 : f64
llvm.store %164, %103 : f64, !llvm.ptr
%165 = llvm.load %103 : !llvm.ptr -> f64
%166 = arith.subf %165, %161 : f64
%167 = llvm.mlir.constant(1 : i64) : i64
%168 = llvm.alloca %167 x f64 : (i64) -> !llvm.ptr
llvm.store %166, %168 : f64, !llvm.ptr
%169 = llvm.load %168 : !llvm.ptr -> f64
%170 = arith.constant 0.0 : f32
%172 = arith.extf %170 : f32 to f64
%171 = arith.cmpf olt, %169, %172 : f64
cf.cond_br %171, ^bb18, ^bb19
^bb18:
%173 = llvm.load %168 : !llvm.ptr -> f64
%174 = arith.negf %173 : f64
llvm.store %174, %168 : f64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%175 = llvm.load %168 : !llvm.ptr -> f64
%176 = arith.constant 0 : f32
%178 = arith.extf %176 : f32 to f64
%177 = arith.cmpf olt, %175, %178 : f64
cf.cond_br %177, ^bb21, ^bb22
^bb21:
cf.br ^bb14
^bb22:
cf.br ^bb23
^bb23:
cf.br ^bb12
^bb14:
%179 = arith.constant 1.0 : f32
%180 = arith.extf %179 : f32 to f64
%181 = llvm.mlir.constant(1 : i64) : i64
%182 = llvm.alloca %181 x f64 : (i64) -> !llvm.ptr
llvm.store %180, %182 : f64, !llvm.ptr
%183 = arith.constant 0.0 : f32
%184 = arith.extf %183 : f32 to f64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x f64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : f64, !llvm.ptr
%187 = arith.constant 1 : i32
%188 = arith.extsi %187 : i32 to i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %188, %190 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%191 = llvm.load %190 : !llvm.ptr -> i64
%192 = arith.cmpi sle, %191, %64 : i64
cf.cond_br %192, ^bb25, ^bb26
^bb25:
%193 = llvm.load %186 : !llvm.ptr -> f64
%194 = llvm.load %182 : !llvm.ptr -> f64
llvm.store %194, %186 : f64, !llvm.ptr
%195 = arith.constant 2 : i32
%196 = llvm.load %190 : !llvm.ptr -> i64
%198 = arith.extsi %195 : i32 to i64
%197 = arith.muli %198, %196 : i64
%199 = arith.constant 1 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.subi %197, %201 : i64
%202 = arith.sitofp %200 : i64 to f64
%203 = llvm.load %103 : !llvm.ptr -> f64
%204 = arith.mulf %202, %203 : f64
%205 = llvm.load %186 : !llvm.ptr -> f64
%206 = arith.mulf %204, %205 : f64
%207 = llvm.load %190 : !llvm.ptr -> i64
%208 = arith.constant 1 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.subi %207, %210 : i64
%211 = arith.sitofp %209 : i64 to f64
%212 = arith.mulf %211, %193 : f64
%213 = arith.subf %206, %212 : f64
%214 = llvm.load %190 : !llvm.ptr -> i64
%215 = arith.sitofp %214 : i64 to f64
%216 = arith.divf %213, %215 : f64
llvm.store %216, %182 : f64, !llvm.ptr
%217 = llvm.load %190 : !llvm.ptr -> i64
%218 = arith.constant 1 : i32
%220 = arith.extsi %218 : i32 to i64
%219 = arith.addi %217, %220 : i64
llvm.store %219, %190 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%221 = arith.sitofp %64 : i64 to f64
%222 = llvm.load %103 : !llvm.ptr -> f64
%223 = llvm.load %182 : !llvm.ptr -> f64
%224 = arith.mulf %222, %223 : f64
%225 = llvm.load %186 : !llvm.ptr -> f64
%226 = arith.subf %224, %225 : f64
%227 = arith.mulf %221, %226 : f64
%228 = llvm.load %103 : !llvm.ptr -> f64
%229 = llvm.load %103 : !llvm.ptr -> f64
%230 = arith.mulf %228, %229 : f64
%231 = arith.constant 1.0 : f32
%233 = arith.extf %231 : f32 to f64
%232 = arith.subf %230, %233 : f64
%234 = arith.divf %227, %232 : f64
%235 = arith.constant 2.0 : f32
%236 = arith.constant 1.0 : f32
%237 = llvm.load %103 : !llvm.ptr -> f64
%238 = llvm.load %103 : !llvm.ptr -> f64
%239 = arith.mulf %237, %238 : f64
%241 = arith.extf %236 : f32 to f64
%240 = arith.subf %241, %239 : f64
%242 = arith.mulf %240, %234 : f64
%243 = arith.mulf %242, %234 : f64
%245 = arith.extf %235 : f32 to f64
%244 = arith.divf %245, %243 : f64
%246 = arith.constant 0.5 : f32
%248 = arith.extf %246 : f32 to f64
%247 = arith.mulf %53, %248 : f64
%249 = arith.constant 0.5 : f32
%251 = arith.extf %249 : f32 to f64
%250 = arith.mulf %53, %251 : f64
%252 = llvm.load %103 : !llvm.ptr -> f64
%253 = arith.negf %252 : f64
%254 = arith.mulf %250, %253 : f64
%255 = arith.addf %247, %254 : f64
%256 = llvm.load %81 : !llvm.ptr -> i64
%257 = llvm.getelementptr %65[%256] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %255, %257 : f64, !llvm.ptr
%258 = llvm.load %103 : !llvm.ptr -> f64
%259 = arith.mulf %250, %258 : f64
%260 = arith.addf %247, %259 : f64
%261 = arith.constant 1 : i32
%263 = arith.extsi %261 : i32 to i64
%262 = arith.subi %64, %263 : i64
%264 = llvm.load %81 : !llvm.ptr -> i64
%265 = arith.subi %262, %264 : i64
%266 = llvm.getelementptr %65[%265] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %260, %266 : f64, !llvm.ptr
%267 = arith.mulf %250, %244 : f64
%268 = llvm.load %81 : !llvm.ptr -> i64
%269 = llvm.getelementptr %68[%268] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %267, %269 : f64, !llvm.ptr
%270 = arith.mulf %250, %244 : f64
%271 = arith.constant 1 : i32
%273 = arith.extsi %271 : i32 to i64
%272 = arith.subi %64, %273 : i64
%274 = llvm.load %81 : !llvm.ptr -> i64
%275 = arith.subi %272, %274 : i64
%276 = llvm.getelementptr %68[%275] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %270, %276 : f64, !llvm.ptr
%277 = llvm.load %81 : !llvm.ptr -> i64
%278 = arith.constant 1 : i32
%280 = arith.extsi %278 : i32 to i64
%279 = arith.addi %277, %280 : i64
llvm.store %279, %81 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%282 = arith.constant 0.0 : f32
%283 = arith.extf %282 : f32 to f64
%281 = func.call @wasted(%283, %55, %62, %65, %68, %64) : (f64, f64, f64, !llvm.ptr, !llvm.ptr, i64) -> f64
%284 = func.call @wasted(%55, %55, %62, %65, %68, %64) : (f64, f64, f64, !llvm.ptr, !llvm.ptr, i64) -> f64
%285 = arith.constant 0 : i32
%286 = arith.extsi %285 : i32 to i64
%287 = llvm.mlir.constant(1 : i64) : i64
%288 = llvm.alloca %287 x i64 : (i64) -> !llvm.ptr
llvm.store %286, %288 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%289 = llvm.load %288 : !llvm.ptr -> i64
%290 = llvm.load %288 : !llvm.ptr -> i64
%291 = arith.muli %289, %290 : i64
%292 = arith.sitofp %291 : i64 to f64
%293 = arith.constant 0 : f32
%295 = arith.extf %293 : f32 to f64
%294 = arith.subf %281, %295 : f64
%296 = arith.cmpf olt, %292, %294 : f64
cf.cond_br %296, ^bb28, ^bb29
^bb28:
%297 = llvm.load %288 : !llvm.ptr -> i64
%298 = arith.constant 1 : i32
%300 = arith.extsi %298 : i32 to i64
%299 = arith.addi %297, %300 : i64
llvm.store %299, %288 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%301 = arith.constant 0 : i32
%302 = arith.extsi %301 : i32 to i64
%303 = llvm.mlir.constant(1 : i64) : i64
%304 = llvm.alloca %303 x i64 : (i64) -> !llvm.ptr
llvm.store %302, %304 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%305 = llvm.load %304 : !llvm.ptr -> i64
%306 = arith.constant 1 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.addi %305, %308 : i64
%309 = llvm.load %304 : !llvm.ptr -> i64
%310 = arith.constant 1 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.addi %309, %312 : i64
%313 = arith.muli %307, %311 : i64
%314 = arith.sitofp %313 : i64 to f64
%315 = arith.constant 0 : f32
%317 = arith.extf %315 : f32 to f64
%316 = arith.addf %284, %317 : f64
%318 = arith.cmpf ole, %314, %316 : f64
cf.cond_br %318, ^bb31, ^bb32
^bb31:
%319 = llvm.load %304 : !llvm.ptr -> i64
%320 = arith.constant 1 : i32
%322 = arith.extsi %320 : i32 to i64
%321 = arith.addi %319, %322 : i64
llvm.store %321, %304 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%323 = arith.constant 0.0 : f32
%324 = arith.extf %323 : f32 to f64
%325 = llvm.mlir.constant(1 : i64) : i64
%326 = llvm.alloca %325 x f64 : (i64) -> !llvm.ptr
llvm.store %324, %326 : f64, !llvm.ptr
%327 = llvm.load %288 : !llvm.ptr -> i64
%328 = llvm.mlir.constant(1 : i64) : i64
%329 = llvm.alloca %328 x i64 : (i64) -> !llvm.ptr
llvm.store %327, %329 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%330 = llvm.load %329 : !llvm.ptr -> i64
%331 = llvm.load %304 : !llvm.ptr -> i64
%332 = arith.cmpi sle, %330, %331 : i64
cf.cond_br %332, ^bb34, ^bb35
^bb34:
%333 = llvm.load %329 : !llvm.ptr -> i64
%334 = llvm.load %329 : !llvm.ptr -> i64
%335 = arith.muli %333, %334 : i64
%336 = arith.sitofp %335 : i64 to f64
%337 = arith.constant 0.0 : f32
%338 = arith.extf %337 : f32 to f64
%339 = llvm.mlir.constant(1 : i64) : i64
%340 = llvm.alloca %339 x f64 : (i64) -> !llvm.ptr
llvm.store %338, %340 : f64, !llvm.ptr
%341 = llvm.mlir.constant(1 : i64) : i64
%342 = llvm.alloca %341 x f64 : (i64) -> !llvm.ptr
llvm.store %55, %342 : f64, !llvm.ptr
%343 = arith.constant 0 : i32
%344 = arith.extsi %343 : i32 to i64
%345 = llvm.mlir.constant(1 : i64) : i64
%346 = llvm.alloca %345 x i64 : (i64) -> !llvm.ptr
llvm.store %344, %346 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%347 = llvm.load %346 : !llvm.ptr -> i64
%348 = arith.constant 70 : i32
%350 = arith.extsi %348 : i32 to i64
%349 = arith.cmpi slt, %347, %350 : i64
cf.cond_br %349, ^bb37, ^bb38
^bb37:
%351 = llvm.load %340 : !llvm.ptr -> f64
%352 = llvm.load %342 : !llvm.ptr -> f64
%353 = arith.addf %351, %352 : f64
%354 = arith.constant 0.5 : f32
%356 = arith.extf %354 : f32 to f64
%355 = arith.mulf %353, %356 : f64
%357 = func.call @wasted(%355, %55, %62, %65, %68, %64) : (f64, f64, f64, !llvm.ptr, !llvm.ptr, i64) -> f64
%358 = arith.subf %357, %336 : f64
%359 = arith.constant 0.0 : f32
%361 = arith.extf %359 : f32 to f64
%360 = arith.cmpf oge, %358, %361 : f64
cf.cond_br %360, ^bb39, ^bb40
^bb39:
llvm.store %355, %342 : f64, !llvm.ptr
cf.br ^bb41
^bb40:
llvm.store %355, %340 : f64, !llvm.ptr
cf.br ^bb41
^bb41:
%362 = llvm.load %346 : !llvm.ptr -> i64
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.addi %362, %365 : i64
llvm.store %364, %346 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%366 = llvm.load %326 : !llvm.ptr -> f64
%367 = llvm.load %340 : !llvm.ptr -> f64
%368 = llvm.load %342 : !llvm.ptr -> f64
%369 = arith.addf %367, %368 : f64
%370 = arith.constant 0.5 : f32
%372 = arith.extf %370 : f32 to f64
%371 = arith.mulf %369, %372 : f64
%373 = arith.addf %366, %371 : f64
llvm.store %373, %326 : f64, !llvm.ptr
%374 = llvm.load %329 : !llvm.ptr -> i64
%375 = arith.constant 1 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.addi %374, %377 : i64
llvm.store %376, %329 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%378 = llvm.mlir.addressof @str_0 : !llvm.ptr
%379 = llvm.load %326 : !llvm.ptr -> f64
%380 = llvm.call @printf(%378, %379) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64) -> i32
func.call @free(%68) : (!llvm.ptr) -> ()
func.call @free(%65) : (!llvm.ptr) -> ()
%383 = arith.constant 0 : i32
func.return %383 : i32
}
}