Problem 461
Almost Pi — meet-in-the-middle over pair sums of exp(k/n)-1.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 461
# Almost Pi — meet-in-the-middle over pair sums of exp(k/n)-1.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function exp(x: f64) -> f64
function log(x: f64) -> f64
function acos(x: f64) -> f64
function fabs(x: f64) -> f64
function floor(x: f64) -> f64
}
const N: i64 = 10000
const PAIR_CAP: i64 = 73000000
function merge_f(sums: ptr<f64>, sqs: ptr<i32>, tmp_s: ptr<f64>, tmp_q: ptr<i32>, lo: i64, mid: i64, hi: i64) -> void {
let mut i: i64 = lo
let mut j: i64 = mid
let mut k: i64 = lo
while i < mid && j < hi {
if sums[i] <= sums[j] {
tmp_s[k] = sums[i]
tmp_q[k] = sqs[i]
i = i + 1
} else {
tmp_s[k] = sums[j]
tmp_q[k] = sqs[j]
j = j + 1
}
k = k + 1
}
while i < mid {
tmp_s[k] = sums[i]
tmp_q[k] = sqs[i]
i = i + 1
k = k + 1
}
while j < hi {
tmp_s[k] = sums[j]
tmp_q[k] = sqs[j]
j = j + 1
k = k + 1
}
i = lo
while i < hi {
sums[i] = tmp_s[i]
sqs[i] = tmp_q[i]
i = i + 1
}
}
function merge_sort_f(sums: ptr<f64>, sqs: ptr<i32>, tmp_s: ptr<f64>, tmp_q: ptr<i32>, lo: i64, hi: i64) -> void {
if hi - lo <= 1 { return }
let mid: i64 = (lo + hi) / 2
merge_sort_f(sums, sqs, tmp_s, tmp_q, lo, mid)
merge_sort_f(sums, sqs, tmp_s, tmp_q, mid, hi)
merge_f(sums, sqs, tmp_s, tmp_q, lo, mid, hi)
}
function main() -> i32 {
let PI: f64 = acos(-1.0)
let kmax: i64 = floor(N as f64 * log(1.0 + PI)) as i64
let f: ptr<f64> = calloc(kmax + 1, 8)
let sums: ptr<f64> = calloc(PAIR_CAP, 8)
let sqs: ptr<i32> = calloc(PAIR_CAP, 4)
let tmp_s: ptr<f64> = calloc(PAIR_CAP, 8)
let tmp_q: ptr<i32> = calloc(PAIR_CAP, 4)
if f == null || sums == null || sqs == null || tmp_s == null || tmp_q == null { return 1 }
let mut k: i64 = 0
while k <= kmax {
f[k] = exp((k as f64) / (N as f64)) - 1.0
k = k + 1
}
let mut np: i64 = 0
let mut i: i64 = 0
while i <= kmax {
let mut j: i64 = i
while j <= kmax {
let s: f64 = f[i] + f[j]
if s > PI { break }
if np >= PAIR_CAP { return 1 }
sums[np] = s
sqs[np] = ((i * i + j * j) as i32)
np = np + 1
j = j + 1
}
i = i + 1
}
merge_sort_f(sums, sqs, tmp_s, tmp_q, 0, np)
let mut best_err: f64 = 1.0e300
let mut best_g: i64 = 9223372036854775807
let mut jj: i64 = np - 1
i = 0
while i < np {
while jj >= 0 && sums[i] + sums[jj] > PI {
jj = jj - 1
}
if jj >= 0 {
let err: f64 = PI - (sums[i] + sums[jj])
let g: i64 = (sqs[i] as i64) + (sqs[jj] as i64)
if err < best_err - 1.0e-18 {
best_err = err
best_g = g
} else {
if fabs(err - best_err) <= 1.0e-18 && g < best_g {
best_g = g
}
}
}
if jj + 1 < np {
let err2: f64 = (sums[i] + sums[jj + 1]) - PI
let g2: i64 = (sqs[i] as i64) + (sqs[jj + 1] as i64)
if err2 < best_err - 1.0e-18 {
best_err = err2
best_g = g2
} else {
if fabs(err2 - best_err) <= 1.0e-18 && g2 < best_g {
best_g = g2
}
}
}
i = i + 1
}
printf("%lld\n", best_g)
free(tmp_q)
free(tmp_s)
free(sqs)
free(sums)
free(f)
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 acos(double x);
void merge_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64_i64(double* sums, int32_t* sqs, double* tmp_s, int32_t* tmp_q, int64_t lo, int64_t mid, int64_t hi);
void merge_sort_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64(double* sums, int32_t* sqs, double* tmp_s, int32_t* tmp_q, int64_t lo, int64_t hi);
int32_t main(void);
static const int64_t N = 10000;
static const int64_t PAIR_CAP = 73000000;
void merge_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64_i64(double* sums, int32_t* sqs, double* tmp_s, int32_t* tmp_q, int64_t lo, int64_t mid, int64_t hi) {
int64_t i = lo;
int64_t j = mid;
int64_t k = lo;
while ((i < mid && j < hi)) {
if (sums[i] <= sums[j]) {
tmp_s[k] = sums[i];
tmp_q[k] = sqs[i];
i = (i + 1);
} else {
tmp_s[k] = sums[j];
tmp_q[k] = sqs[j];
j = (j + 1);
}
k = (k + 1);
}
while (i < mid) {
tmp_s[k] = sums[i];
tmp_q[k] = sqs[i];
i = (i + 1);
k = (k + 1);
}
while (j < hi) {
tmp_s[k] = sums[j];
tmp_q[k] = sqs[j];
j = (j + 1);
k = (k + 1);
}
i = lo;
while (i < hi) {
sums[i] = tmp_s[i];
sqs[i] = tmp_q[i];
i = (i + 1);
}
}
void merge_sort_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64(double* sums, int32_t* sqs, double* tmp_s, int32_t* tmp_q, int64_t lo, int64_t hi) {
if ((hi - lo) <= 1) {
return;
}
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
merge_sort_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64(sums, sqs, tmp_s, tmp_q, lo, mid);
merge_sort_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64(sums, sqs, tmp_s, tmp_q, mid, hi);
merge_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64_i64(sums, sqs, tmp_s, tmp_q, lo, mid, hi);
}
int32_t main(void) {
double PI = acos((-1.0));
int64_t kmax = ((int64_t)(floor((((double)(N)) * log((1.0 + PI))))));
double* f = (double*)(calloc((kmax + 1), 8));
double* sums = (double*)(calloc(PAIR_CAP, 8));
int32_t* sqs = (int32_t*)(calloc(PAIR_CAP, 4));
double* tmp_s = (double*)(calloc(PAIR_CAP, 8));
int32_t* tmp_q = (int32_t*)(calloc(PAIR_CAP, 4));
if (((((f == NULL || sums == NULL) || sqs == NULL) || tmp_s == NULL) || tmp_q == NULL)) {
return 1;
}
int64_t k = 0;
while (k <= kmax) {
f[k] = (exp((((double)(k)) / ((double)(N)))) - 1.0);
k = (k + 1);
}
int64_t np = 0;
int64_t i = 0;
while (i <= kmax) {
int64_t j = i;
while (j <= kmax) {
double s = (f[i] + f[j]);
if (s > PI) {
break;
}
if (np >= PAIR_CAP) {
return 1;
}
sums[np] = s;
sqs[np] = ((int32_t)(((i * i) + (j * j))));
np = (np + 1);
j = (j + 1);
}
i = (i + 1);
}
merge_sort_f_ptr_f64_ptr_i32_ptr_f64_ptr_i32_i64_i64(sums, sqs, tmp_s, tmp_q, 0, np);
double best_err = 1.0e300;
int64_t best_g = 9223372036854775807;
int64_t jj = (np - 1);
i = 0;
while (i < np) {
while ((jj >= 0 && (sums[i] + sums[jj]) > PI)) {
jj = (jj - 1);
}
if (jj >= 0) {
double err = (PI - (sums[i] + sums[jj]));
int64_t g = (((int64_t)(sqs[i])) + ((int64_t)(sqs[jj])));
if (err < (best_err - 1.0e-18)) {
best_err = err;
best_g = g;
} else {
if ((fabs((err - best_err)) <= 1.0e-18 && g < best_g)) {
best_g = g;
}
}
}
if ((jj + 1) < np) {
double err2 = ((sums[i] + sums[(jj + 1)]) - PI);
int64_t g2 = (((int64_t)(sqs[i])) + ((int64_t)(sqs[(jj + 1)])));
if (err2 < (best_err - 1.0e-18)) {
best_err = err2;
best_g = g2;
} else {
if ((fabs((err2 - best_err)) <= 1.0e-18 && g2 < best_g)) {
best_g = g2;
}
}
}
i = (i + 1);
}
printf("%lld\n", best_g);
free(tmp_q);
free(tmp_s);
free(sqs);
free(sums);
free(f);
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 @free(!llvm.ptr) -> ()
func.func private @exp(f64) -> f64
func.func private @log(f64) -> f64
func.func private @acos(f64) -> f64
func.func private @fabs(f64) -> f64
func.func private @floor(f64) -> f64
// Constant: N
llvm.mlir.global internal constant @N(10000 : i64) : i64
// Constant: PAIR_CAP
llvm.mlir.global internal constant @PAIR_CAP(73000000 : i64) : i64
func.func @merge_f(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64, %arg5: i64, %arg6: i64) -> () {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg5, %3 : i64, !llvm.ptr
%4 = llvm.mlir.constant(1 : i64) : i64
%5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
llvm.store %arg4, %5 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%6 = llvm.load %1 : !llvm.ptr -> i64
%7 = arith.cmpi slt, %6, %arg5 : i64
%8 = scf.if %7 -> (i1) {
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.cmpi slt, %9, %arg6 : i64
scf.yield %10 : i1
} else {
%11 = arith.constant false
scf.yield %11 : i1
}
cf.cond_br %8, ^bb1, ^bb2
^bb1:
%13 = llvm.load %1 : !llvm.ptr -> i64
%14 = llvm.getelementptr %arg0[%13] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%12 = llvm.load %14 : !llvm.ptr -> f64
%16 = llvm.load %3 : !llvm.ptr -> i64
%17 = llvm.getelementptr %arg0[%16] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%15 = llvm.load %17 : !llvm.ptr -> f64
%18 = arith.cmpf ole, %12, %15 : f64
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%20 = llvm.load %1 : !llvm.ptr -> i64
%21 = llvm.getelementptr %arg0[%20] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%19 = llvm.load %21 : !llvm.ptr -> f64
%22 = llvm.load %5 : !llvm.ptr -> i64
%23 = llvm.getelementptr %arg2[%22] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %19, %23 : f64, !llvm.ptr
%25 = llvm.load %1 : !llvm.ptr -> i64
%26 = llvm.getelementptr %arg1[%25] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%24 = llvm.load %26 : !llvm.ptr -> i32
%27 = llvm.load %5 : !llvm.ptr -> i64
%28 = llvm.getelementptr %arg3[%27] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %24, %28 : i32, !llvm.ptr
%29 = llvm.load %1 : !llvm.ptr -> i64
%30 = arith.constant 1 : i32
%32 = arith.extsi %30 : i32 to i64
%31 = arith.addi %29, %32 : i64
llvm.store %31, %1 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
%34 = llvm.load %3 : !llvm.ptr -> i64
%35 = llvm.getelementptr %arg0[%34] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%33 = llvm.load %35 : !llvm.ptr -> f64
%36 = llvm.load %5 : !llvm.ptr -> i64
%37 = llvm.getelementptr %arg2[%36] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %33, %37 : f64, !llvm.ptr
%39 = llvm.load %3 : !llvm.ptr -> i64
%40 = llvm.getelementptr %arg1[%39] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%38 = llvm.load %40 : !llvm.ptr -> i32
%41 = llvm.load %5 : !llvm.ptr -> i64
%42 = llvm.getelementptr %arg3[%41] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %38, %42 : i32, !llvm.ptr
%43 = llvm.load %3 : !llvm.ptr -> i64
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.addi %43, %46 : i64
llvm.store %45, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb5:
%47 = llvm.load %5 : !llvm.ptr -> i64
%48 = arith.constant 1 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.addi %47, %50 : i64
llvm.store %49, %5 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
cf.br ^bb6
^bb6:
%51 = llvm.load %1 : !llvm.ptr -> i64
%52 = arith.cmpi slt, %51, %arg5 : i64
cf.cond_br %52, ^bb7, ^bb8
^bb7:
%54 = llvm.load %1 : !llvm.ptr -> i64
%55 = llvm.getelementptr %arg0[%54] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%53 = llvm.load %55 : !llvm.ptr -> f64
%56 = llvm.load %5 : !llvm.ptr -> i64
%57 = llvm.getelementptr %arg2[%56] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %53, %57 : f64, !llvm.ptr
%59 = llvm.load %1 : !llvm.ptr -> i64
%60 = llvm.getelementptr %arg1[%59] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%58 = llvm.load %60 : !llvm.ptr -> i32
%61 = llvm.load %5 : !llvm.ptr -> i64
%62 = llvm.getelementptr %arg3[%61] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %58, %62 : i32, !llvm.ptr
%63 = llvm.load %1 : !llvm.ptr -> i64
%64 = arith.constant 1 : i32
%66 = arith.extsi %64 : i32 to i64
%65 = arith.addi %63, %66 : i64
llvm.store %65, %1 : i64, !llvm.ptr
%67 = llvm.load %5 : !llvm.ptr -> i64
%68 = arith.constant 1 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.addi %67, %70 : i64
llvm.store %69, %5 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
cf.br ^bb9
^bb9:
%71 = llvm.load %3 : !llvm.ptr -> i64
%72 = arith.cmpi slt, %71, %arg6 : i64
cf.cond_br %72, ^bb10, ^bb11
^bb10:
%74 = llvm.load %3 : !llvm.ptr -> i64
%75 = llvm.getelementptr %arg0[%74] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%73 = llvm.load %75 : !llvm.ptr -> f64
%76 = llvm.load %5 : !llvm.ptr -> i64
%77 = llvm.getelementptr %arg2[%76] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %73, %77 : f64, !llvm.ptr
%79 = llvm.load %3 : !llvm.ptr -> i64
%80 = llvm.getelementptr %arg1[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%78 = llvm.load %80 : !llvm.ptr -> i32
%81 = llvm.load %5 : !llvm.ptr -> i64
%82 = llvm.getelementptr %arg3[%81] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %78, %82 : i32, !llvm.ptr
%83 = llvm.load %3 : !llvm.ptr -> i64
%84 = arith.constant 1 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.addi %83, %86 : i64
llvm.store %85, %3 : i64, !llvm.ptr
%87 = llvm.load %5 : !llvm.ptr -> i64
%88 = arith.constant 1 : i32
%90 = arith.extsi %88 : i32 to i64
%89 = arith.addi %87, %90 : i64
llvm.store %89, %5 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
llvm.store %arg4, %1 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%91 = llvm.load %1 : !llvm.ptr -> i64
%92 = arith.cmpi slt, %91, %arg6 : i64
cf.cond_br %92, ^bb13, ^bb14
^bb13:
%94 = llvm.load %1 : !llvm.ptr -> i64
%95 = llvm.getelementptr %arg2[%94] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%93 = llvm.load %95 : !llvm.ptr -> f64
%96 = llvm.load %1 : !llvm.ptr -> i64
%97 = llvm.getelementptr %arg0[%96] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %93, %97 : f64, !llvm.ptr
%99 = llvm.load %1 : !llvm.ptr -> i64
%100 = llvm.getelementptr %arg3[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%98 = llvm.load %100 : !llvm.ptr -> i32
%101 = llvm.load %1 : !llvm.ptr -> i64
%102 = llvm.getelementptr %arg1[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %98, %102 : i32, !llvm.ptr
%103 = llvm.load %1 : !llvm.ptr -> i64
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.addi %103, %106 : i64
llvm.store %105, %1 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
func.return
}
func.func @merge_sort_f(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i64, %arg5: i64) -> () {
%107 = arith.subi %arg5, %arg4 : i64
%108 = arith.constant 1 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.cmpi sle, %107, %110 : i64
cf.cond_br %109, ^bb15, ^bb16
^bb15:
func.return
^bb16:
cf.br ^bb17
^bb17:
%111 = arith.addi %arg4, %arg5 : i64
%112 = arith.constant 2 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.divsi %111, %114 : i64
func.call @merge_sort_f(%arg0, %arg1, %arg2, %arg3, %arg4, %113) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> ()
func.call @merge_sort_f(%arg0, %arg1, %arg2, %arg3, %113, %arg5) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> ()
func.call @merge_f(%arg0, %arg1, %arg2, %arg3, %arg4, %113, %arg5) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64, i64) -> ()
func.return
}
func.func @main() -> i32 {
%119 = arith.constant 1.0 : f32
%120 = arith.negf %119 : f32
%121 = arith.extf %120 : f32 to f64
%118 = func.call @acos(%121) : (f64) -> f64
%123 = llvm.mlir.addressof @N : !llvm.ptr
%124 = llvm.load %123 : !llvm.ptr -> i64
%125 = arith.sitofp %124 : i64 to f64
%126 = arith.constant 1.0 : f32
%128 = arith.extf %126 : f32 to f64
%127 = arith.addf %128, %118 : f64
%129 = math.log %127 : f64
%130 = arith.mulf %125, %129 : f64
%122 = func.call @floor(%130) : (f64) -> f64
%131 = arith.fptosi %122 : f64 to i64
%133 = arith.constant 1 : i32
%135 = arith.extsi %133 : i32 to i64
%134 = arith.addi %131, %135 : i64
%136 = arith.constant 8 : i32
%137 = arith.extsi %136 : i32 to i64
%132 = func.call @calloc(%134, %137) : (i64, i64) -> !llvm.ptr
%139 = llvm.mlir.addressof @PAIR_CAP : !llvm.ptr
%140 = llvm.load %139 : !llvm.ptr -> i64
%141 = arith.constant 8 : i32
%142 = arith.extsi %141 : i32 to i64
%138 = func.call @calloc(%140, %142) : (i64, i64) -> !llvm.ptr
%144 = llvm.mlir.addressof @PAIR_CAP : !llvm.ptr
%145 = llvm.load %144 : !llvm.ptr -> i64
%146 = arith.constant 4 : i32
%147 = arith.extsi %146 : i32 to i64
%143 = func.call @calloc(%145, %147) : (i64, i64) -> !llvm.ptr
%149 = llvm.mlir.addressof @PAIR_CAP : !llvm.ptr
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = arith.constant 8 : i32
%152 = arith.extsi %151 : i32 to i64
%148 = func.call @calloc(%150, %152) : (i64, i64) -> !llvm.ptr
%154 = llvm.mlir.addressof @PAIR_CAP : !llvm.ptr
%155 = llvm.load %154 : !llvm.ptr -> i64
%156 = arith.constant 4 : i32
%157 = arith.extsi %156 : i32 to i64
%153 = func.call @calloc(%155, %157) : (i64, i64) -> !llvm.ptr
%158 = llvm.mlir.zero : !llvm.ptr
%159 = llvm.icmp "eq" %132, %158 : !llvm.ptr
%160 = scf.if %159 -> (i1) {
%161 = arith.constant true
scf.yield %161 : i1
} else {
%162 = llvm.mlir.zero : !llvm.ptr
%163 = llvm.icmp "eq" %138, %162 : !llvm.ptr
scf.yield %163 : i1
}
%164 = scf.if %160 -> (i1) {
%165 = arith.constant true
scf.yield %165 : i1
} else {
%166 = llvm.mlir.zero : !llvm.ptr
%167 = llvm.icmp "eq" %143, %166 : !llvm.ptr
scf.yield %167 : i1
}
%168 = scf.if %164 -> (i1) {
%169 = arith.constant true
scf.yield %169 : i1
} else {
%170 = llvm.mlir.zero : !llvm.ptr
%171 = llvm.icmp "eq" %148, %170 : !llvm.ptr
scf.yield %171 : i1
}
%172 = scf.if %168 -> (i1) {
%173 = arith.constant true
scf.yield %173 : i1
} else {
%174 = llvm.mlir.zero : !llvm.ptr
%175 = llvm.icmp "eq" %153, %174 : !llvm.ptr
scf.yield %175 : i1
}
cf.cond_br %172, ^bb18, ^bb19
^bb18:
%176 = arith.constant 1 : i32
func.return %176 : i32
^bb19:
cf.br ^bb20
^bb20:
%177 = arith.constant 0 : i32
%178 = arith.extsi %177 : i32 to i64
%179 = llvm.mlir.constant(1 : i64) : i64
%180 = llvm.alloca %179 x i64 : (i64) -> !llvm.ptr
llvm.store %178, %180 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%181 = llvm.load %180 : !llvm.ptr -> i64
%182 = arith.cmpi sle, %181, %131 : i64
cf.cond_br %182, ^bb22, ^bb23
^bb22:
%183 = llvm.load %180 : !llvm.ptr -> i64
%184 = arith.sitofp %183 : i64 to f64
%185 = llvm.mlir.addressof @N : !llvm.ptr
%186 = llvm.load %185 : !llvm.ptr -> i64
%187 = arith.sitofp %186 : i64 to f64
%188 = arith.divf %184, %187 : f64
%189 = math.exp %188 : f64
%190 = arith.constant 1.0 : f32
%192 = arith.extf %190 : f32 to f64
%191 = arith.subf %189, %192 : f64
%193 = llvm.load %180 : !llvm.ptr -> i64
%194 = llvm.getelementptr %132[%193] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %191, %194 : f64, !llvm.ptr
%195 = llvm.load %180 : !llvm.ptr -> i64
%196 = arith.constant 1 : i32
%198 = arith.extsi %196 : i32 to i64
%197 = arith.addi %195, %198 : i64
llvm.store %197, %180 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%199 = arith.constant 0 : i32
%200 = arith.extsi %199 : i32 to i64
%201 = llvm.mlir.constant(1 : i64) : i64
%202 = llvm.alloca %201 x i64 : (i64) -> !llvm.ptr
llvm.store %200, %202 : i64, !llvm.ptr
%203 = arith.constant 0 : i32
%204 = arith.extsi %203 : i32 to i64
%205 = llvm.mlir.constant(1 : i64) : i64
%206 = llvm.alloca %205 x i64 : (i64) -> !llvm.ptr
llvm.store %204, %206 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%207 = llvm.load %206 : !llvm.ptr -> i64
%208 = arith.cmpi sle, %207, %131 : i64
cf.cond_br %208, ^bb25, ^bb26
^bb25:
%209 = llvm.load %206 : !llvm.ptr -> i64
%210 = llvm.mlir.constant(1 : i64) : i64
%211 = llvm.alloca %210 x i64 : (i64) -> !llvm.ptr
llvm.store %209, %211 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%212 = llvm.load %211 : !llvm.ptr -> i64
%213 = arith.cmpi sle, %212, %131 : i64
cf.cond_br %213, ^bb28, ^bb29
^bb28:
%215 = llvm.load %206 : !llvm.ptr -> i64
%216 = llvm.getelementptr %132[%215] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%214 = llvm.load %216 : !llvm.ptr -> f64
%218 = llvm.load %211 : !llvm.ptr -> i64
%219 = llvm.getelementptr %132[%218] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%217 = llvm.load %219 : !llvm.ptr -> f64
%220 = arith.addf %214, %217 : f64
%221 = arith.cmpf ogt, %220, %118 : f64
cf.cond_br %221, ^bb30, ^bb31
^bb30:
cf.br ^bb29
^bb31:
cf.br ^bb32
^bb32:
%222 = llvm.load %202 : !llvm.ptr -> i64
%223 = llvm.mlir.addressof @PAIR_CAP : !llvm.ptr
%224 = llvm.load %223 : !llvm.ptr -> i64
%225 = arith.cmpi sge, %222, %224 : i64
cf.cond_br %225, ^bb33, ^bb34
^bb33:
%226 = arith.constant 1 : i32
func.return %226 : i32
^bb34:
cf.br ^bb35
^bb35:
%227 = llvm.load %202 : !llvm.ptr -> i64
%228 = llvm.getelementptr %138[%227] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %220, %228 : f64, !llvm.ptr
%229 = llvm.load %206 : !llvm.ptr -> i64
%230 = llvm.load %206 : !llvm.ptr -> i64
%231 = arith.muli %229, %230 : i64
%232 = llvm.load %211 : !llvm.ptr -> i64
%233 = llvm.load %211 : !llvm.ptr -> i64
%234 = arith.muli %232, %233 : i64
%235 = arith.addi %231, %234 : i64
%236 = arith.trunci %235 : i64 to i32
%237 = llvm.load %202 : !llvm.ptr -> i64
%238 = llvm.getelementptr %143[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %236, %238 : i32, !llvm.ptr
%239 = llvm.load %202 : !llvm.ptr -> i64
%240 = arith.constant 1 : i32
%242 = arith.extsi %240 : i32 to i64
%241 = arith.addi %239, %242 : i64
llvm.store %241, %202 : i64, !llvm.ptr
%243 = llvm.load %211 : !llvm.ptr -> i64
%244 = arith.constant 1 : i32
%246 = arith.extsi %244 : i32 to i64
%245 = arith.addi %243, %246 : i64
llvm.store %245, %211 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%247 = llvm.load %206 : !llvm.ptr -> i64
%248 = arith.constant 1 : i32
%250 = arith.extsi %248 : i32 to i64
%249 = arith.addi %247, %250 : i64
llvm.store %249, %206 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%252 = arith.constant 0 : i32
%253 = llvm.load %202 : !llvm.ptr -> i64
%254 = arith.extsi %252 : i32 to i64
func.call @merge_sort_f(%138, %143, %148, %153, %254, %253) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i64, i64) -> ()
%255 = arith.constant 1000000000000000052504760255204420248704468581108159154915854115511802457988908195786371375080447864043704443832883878176942523235360430575644792184786706982848387200926575803737830233794788090059368953234970799945081119038967640880074652742780142494579258788820056842838115669472196386865459400540160 : f32
%256 = arith.extf %255 : f32 to f64
%257 = llvm.mlir.constant(1 : i64) : i64
%258 = llvm.alloca %257 x f64 : (i64) -> !llvm.ptr
llvm.store %256, %258 : f64, !llvm.ptr
%259 = arith.constant 9223372032559808511 : i32
%260 = arith.extsi %259 : i32 to i64
%261 = llvm.mlir.constant(1 : i64) : i64
%262 = llvm.alloca %261 x i64 : (i64) -> !llvm.ptr
llvm.store %260, %262 : i64, !llvm.ptr
%263 = llvm.load %202 : !llvm.ptr -> i64
%264 = arith.constant 1 : i32
%266 = arith.extsi %264 : i32 to i64
%265 = arith.subi %263, %266 : i64
%267 = llvm.mlir.constant(1 : i64) : i64
%268 = llvm.alloca %267 x i64 : (i64) -> !llvm.ptr
llvm.store %265, %268 : i64, !llvm.ptr
%269 = arith.constant 0 : i32
%270 = arith.extsi %269 : i32 to i64
llvm.store %270, %206 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%271 = llvm.load %206 : !llvm.ptr -> i64
%272 = llvm.load %202 : !llvm.ptr -> i64
%273 = arith.cmpi slt, %271, %272 : i64
cf.cond_br %273, ^bb37, ^bb38
^bb37:
cf.br ^bb39
^bb39:
%274 = llvm.load %268 : !llvm.ptr -> i64
%275 = arith.constant 0 : i32
%277 = arith.extsi %275 : i32 to i64
%276 = arith.cmpi sge, %274, %277 : i64
%278 = scf.if %276 -> (i1) {
%280 = llvm.load %206 : !llvm.ptr -> i64
%281 = llvm.getelementptr %138[%280] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%279 = llvm.load %281 : !llvm.ptr -> f64
%283 = llvm.load %268 : !llvm.ptr -> i64
%284 = llvm.getelementptr %138[%283] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%282 = llvm.load %284 : !llvm.ptr -> f64
%285 = arith.addf %279, %282 : f64
%286 = arith.cmpf ogt, %285, %118 : f64
scf.yield %286 : i1
} else {
%287 = arith.constant false
scf.yield %287 : i1
}
cf.cond_br %278, ^bb40, ^bb41
^bb40:
%288 = llvm.load %268 : !llvm.ptr -> i64
%289 = arith.constant 1 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.subi %288, %291 : i64
llvm.store %290, %268 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
%292 = llvm.load %268 : !llvm.ptr -> i64
%293 = arith.constant 0 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.cmpi sge, %292, %295 : i64
cf.cond_br %294, ^bb42, ^bb43
^bb42:
%297 = llvm.load %206 : !llvm.ptr -> i64
%298 = llvm.getelementptr %138[%297] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%296 = llvm.load %298 : !llvm.ptr -> f64
%300 = llvm.load %268 : !llvm.ptr -> i64
%301 = llvm.getelementptr %138[%300] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%299 = llvm.load %301 : !llvm.ptr -> f64
%302 = arith.addf %296, %299 : f64
%303 = arith.subf %118, %302 : f64
%305 = llvm.load %206 : !llvm.ptr -> i64
%306 = llvm.getelementptr %143[%305] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%304 = llvm.load %306 : !llvm.ptr -> i32
%307 = arith.extsi %304 : i32 to i64
%309 = llvm.load %268 : !llvm.ptr -> i64
%310 = llvm.getelementptr %143[%309] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%308 = llvm.load %310 : !llvm.ptr -> i32
%311 = arith.extsi %308 : i32 to i64
%312 = arith.addi %307, %311 : i64
%313 = llvm.load %258 : !llvm.ptr -> f64
%314 = arith.constant 0 : f32
%316 = arith.extf %314 : f32 to f64
%315 = arith.subf %313, %316 : f64
%317 = arith.cmpf olt, %303, %315 : f64
cf.cond_br %317, ^bb45, ^bb46
^bb45:
llvm.store %303, %258 : f64, !llvm.ptr
llvm.store %312, %262 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
%318 = llvm.load %258 : !llvm.ptr -> f64
%319 = arith.subf %303, %318 : f64
%320 = math.absf %319 : f64
%321 = arith.constant 0 : f32
%323 = arith.extf %321 : f32 to f64
%322 = arith.cmpf ole, %320, %323 : f64
%324 = scf.if %322 -> (i1) {
%325 = llvm.load %262 : !llvm.ptr -> i64
%326 = arith.cmpi slt, %312, %325 : i64
scf.yield %326 : i1
} else {
%327 = arith.constant false
scf.yield %327 : i1
}
cf.cond_br %324, ^bb48, ^bb49
^bb48:
llvm.store %312, %262 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
cf.br ^bb47
^bb47:
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%328 = llvm.load %268 : !llvm.ptr -> i64
%329 = arith.constant 1 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.addi %328, %331 : i64
%332 = llvm.load %202 : !llvm.ptr -> i64
%333 = arith.cmpi slt, %330, %332 : i64
cf.cond_br %333, ^bb51, ^bb52
^bb51:
%335 = llvm.load %206 : !llvm.ptr -> i64
%336 = llvm.getelementptr %138[%335] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%334 = llvm.load %336 : !llvm.ptr -> f64
%338 = llvm.load %268 : !llvm.ptr -> i64
%339 = arith.constant 1 : i32
%341 = arith.extsi %339 : i32 to i64
%340 = arith.addi %338, %341 : i64
%342 = llvm.getelementptr %138[%340] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%337 = llvm.load %342 : !llvm.ptr -> f64
%343 = arith.addf %334, %337 : f64
%344 = arith.subf %343, %118 : f64
%346 = llvm.load %206 : !llvm.ptr -> i64
%347 = llvm.getelementptr %143[%346] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%345 = llvm.load %347 : !llvm.ptr -> i32
%348 = arith.extsi %345 : i32 to i64
%350 = llvm.load %268 : !llvm.ptr -> i64
%351 = arith.constant 1 : i32
%353 = arith.extsi %351 : i32 to i64
%352 = arith.addi %350, %353 : i64
%354 = llvm.getelementptr %143[%352] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%349 = llvm.load %354 : !llvm.ptr -> i32
%355 = arith.extsi %349 : i32 to i64
%356 = arith.addi %348, %355 : i64
%357 = llvm.load %258 : !llvm.ptr -> f64
%358 = arith.constant 0 : f32
%360 = arith.extf %358 : f32 to f64
%359 = arith.subf %357, %360 : f64
%361 = arith.cmpf olt, %344, %359 : f64
cf.cond_br %361, ^bb54, ^bb55
^bb54:
llvm.store %344, %258 : f64, !llvm.ptr
llvm.store %356, %262 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
%362 = llvm.load %258 : !llvm.ptr -> f64
%363 = arith.subf %344, %362 : f64
%364 = math.absf %363 : f64
%365 = arith.constant 0 : f32
%367 = arith.extf %365 : f32 to f64
%366 = arith.cmpf ole, %364, %367 : f64
%368 = scf.if %366 -> (i1) {
%369 = llvm.load %262 : !llvm.ptr -> i64
%370 = arith.cmpi slt, %356, %369 : i64
scf.yield %370 : i1
} else {
%371 = arith.constant false
scf.yield %371 : i1
}
cf.cond_br %368, ^bb57, ^bb58
^bb57:
llvm.store %356, %262 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
cf.br ^bb56
^bb56:
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
%372 = llvm.load %206 : !llvm.ptr -> i64
%373 = arith.constant 1 : i32
%375 = arith.extsi %373 : i32 to i64
%374 = arith.addi %372, %375 : i64
llvm.store %374, %206 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%376 = llvm.mlir.addressof @str_0 : !llvm.ptr
%377 = llvm.load %262 : !llvm.ptr -> i64
%378 = llvm.call @printf(%376, %377) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%153) : (!llvm.ptr) -> ()
func.call @free(%148) : (!llvm.ptr) -> ()
func.call @free(%143) : (!llvm.ptr) -> ()
func.call @free(%138) : (!llvm.ptr) -> ()
func.call @free(%132) : (!llvm.ptr) -> ()
%384 = arith.constant 0 : i32
func.return %384 : i32
}
}