← All problems Problem 930
Compute G(12, 12) = sum_{n=2..12} sum_{m=2..12} F(n, m) where F(n, m) = sum_{k != 0} 1/(1 - lambda_k) and lambda_k are eigenvalues of the random walk on (Z_n)^(m-1). The eigenvalues are parametrized by frequency vectors k in (Z_n)^(m-1). We enumerate compositions of d = m-1 into n parts (counts of each residue), computing sum_cos and sum_mod, with multinomial multiplicity. Output in scientific notation with 12 decimal places, no '+' in exponent.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 930: The Gathering
# Compute G(12, 12) = sum_{n=2..12} sum_{m=2..12} F(n, m)
# where F(n, m) = sum_{k != 0} 1/(1 - lambda_k)
# and lambda_k are eigenvalues of the random walk on (Z_n)^(m-1).
#
# The eigenvalues are parametrized by frequency vectors k in (Z_n)^(m-1).
# We enumerate compositions of d = m-1 into n parts (counts of each residue),
# computing sum_cos and sum_mod, with multinomial multiplicity.
#
# Output in scientific notation with 12 decimal places, no '+' in exponent.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function cos(x: f64) -> f64
}
# Global state for F(n, m) computation.
let mut g_n: i32 = 0
let mut g_d: i32 = 0
let mut g_cos_table: ptr<f64> = null as ptr<f64>
let mut g_kah_total: f64 = 0.0
let mut g_kah_c: f64 = 0.0
let mut g_binom: ptr<i32> = null as ptr<i32>
function init_binom() {
for n in 0..12 {
g_binom[n * 12 + 0] = 1
for k in 1..(n + 1) {
let mut val: i32 = g_binom[(n - 1) * 12 + k - 1]
if k <= n - 1 {
val = val + g_binom[(n - 1) * 12 + k]
}
g_binom[n * 12 + k] = val
}
}
}
function rec(r: i32, remaining: i32, mult: i32, sum_cos: f64, sum_mod: i32, any_nonzero: bool) {
if r == g_n - 1 {
let cnt: i32 = remaining
let sum_cos2: f64 = sum_cos + (cnt as f64) * g_cos_table[r]
let sum_mod2: i32 = (sum_mod + cnt * r) % g_n
let any2: bool = any_nonzero || (cnt > 0 && r != 0)
if !any2 {
return
}
let lam: f64 = (sum_cos2 + g_cos_table[sum_mod2]) / ((g_d + 1) as f64)
let term: f64 = (mult as f64) / (1.0 - lam)
# Kahan add
let y: f64 = term - g_kah_c
let t: f64 = g_kah_total + y
g_kah_c = (t - g_kah_total) - y
g_kah_total = t
return
}
let cr: f64 = g_cos_table[r]
for cnt in 0..(remaining + 1) {
let new_mult: i32 = mult * g_binom[remaining * 12 + cnt]
let new_sum_cos: f64 = sum_cos + (cnt as f64) * cr
let new_sum_mod: i32 = (sum_mod + cnt * r) % g_n
let new_any: bool = any_nonzero || (cnt > 0 && r != 0)
rec(r + 1, remaining - cnt, new_mult, new_sum_cos, new_sum_mod, new_any)
}
}
function F(n: i32, m: i32) -> f64 {
let d: i32 = m - 1
g_n = n
g_d = d
g_kah_total = 0.0
g_kah_c = 0.0
let PI: f64 = 3.14159265358979323846
for r in 0..n {
g_cos_table[r] = cos(2.0 * PI * (r as f64) / (n as f64))
}
rec(0, d, 1, 0.0, 0, false)
return g_kah_total
}
function main() -> i32 {
g_binom = calloc(144, 4)
g_cos_table = calloc(16, 8)
if g_binom == null || g_cos_table == null {
return 1
}
init_binom()
# G(12, 12) with Kahan summation.
let mut kah_total: f64 = 0.0
let mut kah_c: f64 = 0.0
for n in 2..13 {
for m in 2..13 {
let val: f64 = F(n, m)
let y: f64 = val - kah_c
let t: f64 = kah_total + y
kah_c = (t - kah_total) - y
kah_total = t
}
}
let ans: f64 = kah_total
# Format as %.12e without '+' in exponent.
let mut mant: f64 = ans
let mut ex: i64 = 0
while mant >= 10.0 {
mant = mant / 10.0
ex = ex + 1
}
while mant < 1.0 && mant > 0.0 {
mant = mant * 10.0
ex = ex - 1
}
printf("%.12fe%lld\n", mant, ex)
free(g_cos_table)
free(g_binom)
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; }
void init_binom(void);
void rec_i32_i32_i32_f64_i32_bool(int32_t r, int32_t remaining, int32_t mult, double sum_cos, int32_t sum_mod, bool any_nonzero);
double F_i32_i32(int32_t n, int32_t m);
int32_t main(void);
/* Module statics */
static int32_t g_n = 0;
static int32_t g_d = 0;
static double* g_cos_table = ((double*)(NULL));
static double g_kah_total = 0.0;
static double g_kah_c = 0.0;
static int32_t* g_binom = ((int32_t*)(NULL));
void init_binom(void) {
int32_t __flow_step_1 = 1;
for (int32_t n = 0; (0 <= 12) ? n < 12 : n > 12; n += (0 <= 12) ? 1 : -1) {
g_binom[((n * 12) + 0)] = 1;
int32_t __flow_step_2 = 1;
for (int32_t k = 1; (1 <= (n + 1)) ? k < (n + 1) : k > (n + 1); k += (1 <= (n + 1)) ? 1 : -1) {
int32_t val = g_binom[((((n - 1) * 12) + k) - 1)];
if (k <= (n - 1)) {
val = (val + g_binom[(((n - 1) * 12) + k)]);
}
g_binom[((n * 12) + k)] = val;
}
}
}
void rec_i32_i32_i32_f64_i32_bool(int32_t r, int32_t remaining, int32_t mult, double sum_cos, int32_t sum_mod, bool any_nonzero) {
if (r == (g_n - 1)) {
int32_t cnt = remaining;
double sum_cos2 = (sum_cos + (((double)(cnt)) * g_cos_table[r]));
int32_t sum_mod2 = FLOW_CHECKED_MOD(((sum_mod + (cnt * r))), (g_n));
bool any2 = (any_nonzero || (cnt > 0 && r != 0));
if ((!(any2))) {
return;
}
double lam = ((sum_cos2 + g_cos_table[sum_mod2]) / ((double)((g_d + 1))));
double term = (((double)(mult)) / (1.0 - lam));
double y = (term - g_kah_c);
double t = (g_kah_total + y);
g_kah_c = ((t - g_kah_total) - y);
g_kah_total = t;
return;
}
double cr = g_cos_table[r];
int32_t __flow_step_3 = 1;
for (int32_t cnt = 0; (0 <= (remaining + 1)) ? cnt < (remaining + 1) : cnt > (remaining + 1); cnt += (0 <= (remaining + 1)) ? 1 : -1) {
int32_t new_mult = (mult * g_binom[((remaining * 12) + cnt)]);
double new_sum_cos = (sum_cos + (((double)(cnt)) * cr));
int32_t new_sum_mod = FLOW_CHECKED_MOD(((sum_mod + (cnt * r))), (g_n));
bool new_any = (any_nonzero || (cnt > 0 && r != 0));
rec_i32_i32_i32_f64_i32_bool((r + 1), (remaining - cnt), new_mult, new_sum_cos, new_sum_mod, new_any);
}
}
double F_i32_i32(int32_t n, int32_t m) {
int32_t d = (m - 1);
g_n = n;
g_d = d;
g_kah_total = 0.0;
g_kah_c = 0.0;
double PI = 3.14159265358979323846;
int32_t __flow_step_4 = 1;
for (int32_t r = 0; (0 <= n) ? r < n : r > n; r += (0 <= n) ? 1 : -1) {
g_cos_table[r] = cos((((2.0 * PI) * ((double)(r))) / ((double)(n))));
}
rec_i32_i32_i32_f64_i32_bool(0, d, 1, 0.0, 0, 0);
return g_kah_total;
}
int32_t main(void) {
g_binom = calloc(144, 4);
g_cos_table = calloc(16, 8);
if ((g_binom == NULL || g_cos_table == NULL)) {
return 1;
}
init_binom();
double kah_total = 0.0;
double kah_c = 0.0;
int32_t __flow_step_5 = 1;
for (int32_t n = 2; (2 <= 13) ? n < 13 : n > 13; n += (2 <= 13) ? 1 : -1) {
int32_t __flow_step_6 = 1;
for (int32_t m = 2; (2 <= 13) ? m < 13 : m > 13; m += (2 <= 13) ? 1 : -1) {
double val = F_i32_i32(n, m);
double y = (val - kah_c);
double t = (kah_total + y);
kah_c = ((t - kah_total) - y);
kah_total = t;
}
}
double ans = kah_total;
double mant = ans;
int64_t ex = 0;
while (mant >= 10.0) {
mant = (mant / 10.0);
ex = (ex + 1);
}
while ((mant < 1.0 && mant > 0.0)) {
mant = (mant * 10.0);
ex = (ex - 1);
}
printf("%.12fe%lld\n", mant, ex);
free(g_cos_table);
free(g_binom);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.12fe%lld\n\00") {addr_space = 0 : i32} : !llvm.array<12 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @cos(f64) -> f64
// Module static: g_n
llvm.mlir.global internal @g_n(0 : i32) : i32
// Module static: g_d
llvm.mlir.global internal @g_d(0 : i32) : i32
// Module static: g_cos_table
llvm.mlir.global internal @g_cos_table() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: g_kah_total
llvm.mlir.global internal @g_kah_total(0.0 : f64) : f64
// Module static: g_kah_c
llvm.mlir.global internal @g_kah_c(0.0 : f64) : f64
// Module static: g_binom
llvm.mlir.global internal @g_binom() {addr_space = 0 : i32} : !llvm.ptr {
%1 = llvm.mlir.zero : !llvm.ptr
llvm.return %1 : !llvm.ptr
}
func.func @init_binom() -> () {
%2 = arith.constant 0 : i32
%3 = arith.constant 12 : i32
%4 = arith.index_cast %2 : i32 to index
%5 = arith.index_cast %3 : i32 to index
%7 = arith.constant 1 : index
%8 = arith.constant -1 : index
%9 = arith.cmpi sle, %4, %5 : index
%6 = arith.select %9, %7, %8 : index
cf.br ^bb0(%4 : index)
^bb0(%10: index):
%11 = arith.cmpi slt, %10, %5 : index
%12 = arith.cmpi sgt, %10, %5 : index
%13 = arith.select %9, %11, %12 : i1
cf.cond_br %13, ^bb1(%10 : index), ^bb2(%10 : index)
^bb1(%14: index):
%15 = arith.constant 1 : i32
%16 = llvm.mlir.addressof @g_binom : !llvm.ptr
%17 = llvm.load %16 : !llvm.ptr -> !llvm.ptr
%18 = arith.constant 12 : i32
%20 = arith.index_cast %14 : index to i32
%19 = arith.muli %20, %18 : i32
%21 = arith.constant 0 : i32
%22 = arith.addi %19, %21 : i32
%23 = arith.extsi %22 : i32 to i64
%24 = llvm.getelementptr %17[%23] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %15, %24 : i32, !llvm.ptr
%25 = arith.constant 1 : i32
%26 = arith.constant 1 : i32
%28 = arith.index_cast %14 : index to i32
%27 = arith.addi %28, %26 : i32
%29 = arith.index_cast %25 : i32 to index
%30 = arith.index_cast %27 : i32 to index
%32 = arith.constant 1 : index
%33 = arith.constant -1 : index
%34 = arith.cmpi sle, %29, %30 : index
%31 = arith.select %34, %32, %33 : index
cf.br ^bb3(%29 : index)
^bb3(%35: index):
%36 = arith.cmpi slt, %35, %30 : index
%37 = arith.cmpi sgt, %35, %30 : index
%38 = arith.select %34, %36, %37 : i1
cf.cond_br %38, ^bb4(%35 : index), ^bb5(%35 : index)
^bb4(%39: index):
%41 = llvm.mlir.addressof @g_binom : !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> !llvm.ptr
%43 = arith.constant 1 : i32
%45 = arith.index_cast %14 : index to i32
%44 = arith.subi %45, %43 : i32
%46 = arith.constant 12 : i32
%47 = arith.muli %44, %46 : i32
%49 = arith.index_cast %39 : index to i32
%48 = arith.addi %47, %49 : i32
%50 = arith.constant 1 : i32
%51 = arith.subi %48, %50 : i32
%52 = arith.extsi %51 : i32 to i64
%53 = llvm.getelementptr %42[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%40 = llvm.load %53 : !llvm.ptr -> i32
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i32 : (i64) -> !llvm.ptr
llvm.store %40, %55 : i32, !llvm.ptr
%56 = arith.constant 1 : i32
%58 = arith.index_cast %14 : index to i32
%57 = arith.subi %58, %56 : i32
%60 = arith.index_cast %39 : index to i32
%59 = arith.cmpi sle, %60, %57 : i32
cf.cond_br %59, ^bb6, ^bb7
^bb6:
%61 = llvm.load %55 : !llvm.ptr -> i32
%63 = llvm.mlir.addressof @g_binom : !llvm.ptr
%64 = llvm.load %63 : !llvm.ptr -> !llvm.ptr
%65 = arith.constant 1 : i32
%67 = arith.index_cast %14 : index to i32
%66 = arith.subi %67, %65 : i32
%68 = arith.constant 12 : i32
%69 = arith.muli %66, %68 : i32
%71 = arith.index_cast %39 : index to i32
%70 = arith.addi %69, %71 : i32
%72 = arith.extsi %70 : i32 to i64
%73 = llvm.getelementptr %64[%72] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%62 = llvm.load %73 : !llvm.ptr -> i32
%74 = arith.addi %61, %62 : i32
llvm.store %74, %55 : i32, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%75 = llvm.load %55 : !llvm.ptr -> i32
%76 = llvm.mlir.addressof @g_binom : !llvm.ptr
%77 = llvm.load %76 : !llvm.ptr -> !llvm.ptr
%78 = arith.constant 12 : i32
%80 = arith.index_cast %14 : index to i32
%79 = arith.muli %80, %78 : i32
%82 = arith.index_cast %39 : index to i32
%81 = arith.addi %79, %82 : i32
%83 = arith.extsi %81 : i32 to i64
%84 = llvm.getelementptr %77[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %75, %84 : i32, !llvm.ptr
%85 = arith.addi %39, %31 : index
cf.br ^bb3(%85 : index)
^bb5(%86: index):
%87 = arith.addi %14, %6 : index
cf.br ^bb0(%87 : index)
^bb2(%88: index):
func.return
}
func.func @rec(%arg0: i32, %arg1: i32, %arg2: i32, %arg3: f64, %arg4: i32, %arg5: i1) -> () {
%89 = llvm.mlir.addressof @g_n : !llvm.ptr
%90 = llvm.load %89 : !llvm.ptr -> i32
%91 = arith.constant 1 : i32
%92 = arith.subi %90, %91 : i32
%93 = arith.cmpi eq, %arg0, %92 : i32
cf.cond_br %93, ^bb9, ^bb10
^bb9:
%94 = arith.sitofp %arg1 : i32 to f64
%96 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> !llvm.ptr
%98 = arith.extsi %arg0 : i32 to i64
%99 = llvm.getelementptr %97[%98] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%95 = llvm.load %99 : !llvm.ptr -> f64
%100 = arith.mulf %94, %95 : f64
%101 = arith.addf %arg3, %100 : f64
%102 = arith.muli %arg1, %arg0 : i32
%103 = arith.addi %arg4, %102 : i32
%104 = llvm.mlir.addressof @g_n : !llvm.ptr
%105 = llvm.load %104 : !llvm.ptr -> i32
%106 = arith.remsi %103, %105 : i32
%107 = scf.if %arg5 -> (i1) {
%108 = arith.constant true
scf.yield %108 : i1
} else {
%109 = arith.constant 0 : i32
%110 = arith.cmpi sgt, %arg1, %109 : i32
%111 = scf.if %110 -> (i1) {
%112 = arith.constant 0 : i32
%113 = arith.cmpi ne, %arg0, %112 : i32
scf.yield %113 : i1
} else {
%114 = arith.constant false
scf.yield %114 : i1
}
scf.yield %111 : i1
}
%116 = arith.constant 1 : i1
%115 = arith.xori %107, %116 : i1
cf.cond_br %115, ^bb12, ^bb13
^bb12:
func.return
^bb13:
cf.br ^bb14
^bb14:
%119 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%120 = llvm.load %119 : !llvm.ptr -> !llvm.ptr
%121 = arith.extsi %106 : i32 to i64
%122 = llvm.getelementptr %120[%121] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%118 = llvm.load %122 : !llvm.ptr -> f64
%123 = arith.addf %101, %118 : f64
%124 = llvm.mlir.addressof @g_d : !llvm.ptr
%125 = llvm.load %124 : !llvm.ptr -> i32
%126 = arith.constant 1 : i32
%127 = arith.addi %125, %126 : i32
%128 = arith.sitofp %127 : i32 to f64
%129 = arith.divf %123, %128 : f64
%130 = arith.sitofp %arg2 : i32 to f64
%131 = arith.constant 1.0 : f32
%133 = arith.extf %131 : f32 to f64
%132 = arith.subf %133, %129 : f64
%134 = arith.divf %130, %132 : f64
%135 = llvm.mlir.addressof @g_kah_c : !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> f64
%137 = arith.subf %134, %136 : f64
%138 = llvm.mlir.addressof @g_kah_total : !llvm.ptr
%139 = llvm.load %138 : !llvm.ptr -> f64
%140 = arith.addf %139, %137 : f64
%141 = llvm.mlir.addressof @g_kah_total : !llvm.ptr
%142 = llvm.load %141 : !llvm.ptr -> f64
%143 = arith.subf %140, %142 : f64
%144 = arith.subf %143, %137 : f64
%145 = llvm.mlir.addressof @g_kah_c : !llvm.ptr
llvm.store %144, %145 : f64, !llvm.ptr
%146 = llvm.mlir.addressof @g_kah_total : !llvm.ptr
llvm.store %140, %146 : f64, !llvm.ptr
func.return
^bb10:
cf.br ^bb11
^bb11:
%148 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%149 = llvm.load %148 : !llvm.ptr -> !llvm.ptr
%150 = arith.extsi %arg0 : i32 to i64
%151 = llvm.getelementptr %149[%150] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%147 = llvm.load %151 : !llvm.ptr -> f64
%152 = arith.constant 0 : i32
%153 = arith.constant 1 : i32
%154 = arith.addi %arg1, %153 : i32
%155 = arith.index_cast %152 : i32 to index
%156 = arith.index_cast %154 : i32 to index
%158 = arith.constant 1 : index
%159 = arith.constant -1 : index
%160 = arith.cmpi sle, %155, %156 : index
%157 = arith.select %160, %158, %159 : index
cf.br ^bb15(%155 : index)
^bb15(%161: index):
%162 = arith.cmpi slt, %161, %156 : index
%163 = arith.cmpi sgt, %161, %156 : index
%164 = arith.select %160, %162, %163 : i1
cf.cond_br %164, ^bb16(%161 : index), ^bb17(%161 : index)
^bb16(%165: index):
%167 = llvm.mlir.addressof @g_binom : !llvm.ptr
%168 = llvm.load %167 : !llvm.ptr -> !llvm.ptr
%169 = arith.constant 12 : i32
%170 = arith.muli %arg1, %169 : i32
%172 = arith.index_cast %165 : index to i32
%171 = arith.addi %170, %172 : i32
%173 = arith.extsi %171 : i32 to i64
%174 = llvm.getelementptr %168[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%166 = llvm.load %174 : !llvm.ptr -> i32
%175 = arith.muli %arg2, %166 : i32
%177 = arith.index_cast %165 : index to i64
%176 = arith.sitofp %177 : i64 to f64
%178 = arith.mulf %176, %147 : f64
%179 = arith.addf %arg3, %178 : f64
%181 = arith.index_cast %165 : index to i32
%180 = arith.muli %181, %arg0 : i32
%182 = arith.addi %arg4, %180 : i32
%183 = llvm.mlir.addressof @g_n : !llvm.ptr
%184 = llvm.load %183 : !llvm.ptr -> i32
%185 = arith.remsi %182, %184 : i32
%186 = scf.if %arg5 -> (i1) {
%187 = arith.constant true
scf.yield %187 : i1
} else {
%188 = arith.constant 0 : i32
%190 = arith.index_cast %165 : index to i32
%189 = arith.cmpi sgt, %190, %188 : i32
%191 = scf.if %189 -> (i1) {
%192 = arith.constant 0 : i32
%193 = arith.cmpi ne, %arg0, %192 : i32
scf.yield %193 : i1
} else {
%194 = arith.constant false
scf.yield %194 : i1
}
scf.yield %191 : i1
}
%196 = arith.constant 1 : i32
%197 = arith.addi %arg0, %196 : i32
%199 = arith.index_cast %165 : index to i32
%198 = arith.subi %arg1, %199 : i32
func.call @rec(%197, %198, %175, %179, %185, %186) : (i32, i32, i32, f64, i32, i1) -> ()
%200 = arith.addi %165, %157 : index
cf.br ^bb15(%200 : index)
^bb17(%201: index):
func.return
}
func.func @F(%arg0: i32, %arg1: i32) -> f64 {
%202 = arith.constant 1 : i32
%203 = arith.subi %arg1, %202 : i32
%204 = llvm.mlir.addressof @g_n : !llvm.ptr
llvm.store %arg0, %204 : i32, !llvm.ptr
%205 = llvm.mlir.addressof @g_d : !llvm.ptr
llvm.store %203, %205 : i32, !llvm.ptr
%206 = arith.constant 0.0 : f32
%207 = arith.extf %206 : f32 to f64
%208 = llvm.mlir.addressof @g_kah_total : !llvm.ptr
llvm.store %207, %208 : f64, !llvm.ptr
%209 = arith.constant 0.0 : f32
%210 = arith.extf %209 : f32 to f64
%211 = llvm.mlir.addressof @g_kah_c : !llvm.ptr
llvm.store %210, %211 : f64, !llvm.ptr
%212 = arith.constant 3.14159265358979323846 : f32
%213 = arith.extf %212 : f32 to f64
%214 = arith.constant 0 : i32
%215 = arith.index_cast %214 : i32 to index
%216 = arith.index_cast %arg0 : i32 to index
%218 = arith.constant 1 : index
%219 = arith.constant -1 : index
%220 = arith.cmpi sle, %215, %216 : index
%217 = arith.select %220, %218, %219 : index
cf.br ^bb18(%215 : index)
^bb18(%221: index):
%222 = arith.cmpi slt, %221, %216 : index
%223 = arith.cmpi sgt, %221, %216 : index
%224 = arith.select %220, %222, %223 : i1
cf.cond_br %224, ^bb19(%221 : index), ^bb20(%221 : index)
^bb19(%225: index):
%226 = arith.constant 2.0 : f32
%228 = arith.extf %226 : f32 to f64
%227 = arith.mulf %228, %213 : f64
%230 = arith.index_cast %225 : index to i64
%229 = arith.sitofp %230 : i64 to f64
%231 = arith.mulf %227, %229 : f64
%232 = arith.sitofp %arg0 : i32 to f64
%233 = arith.divf %231, %232 : f64
%234 = math.cos %233 : f64
%235 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%236 = llvm.load %235 : !llvm.ptr -> !llvm.ptr
%237 = arith.index_cast %225 : index to i64
%238 = llvm.getelementptr %236[%237] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %234, %238 : f64, !llvm.ptr
%239 = arith.addi %225, %217 : index
cf.br ^bb18(%239 : index)
^bb20(%240: index):
%242 = arith.constant 0 : i32
%243 = arith.constant 1 : i32
%244 = arith.constant 0.0 : f32
%245 = arith.constant 0 : i32
%246 = arith.constant 0 : i1
%247 = arith.extf %244 : f32 to f64
func.call @rec(%242, %203, %243, %247, %245, %246) : (i32, i32, i32, f64, i32, i1) -> ()
%248 = llvm.mlir.addressof @g_kah_total : !llvm.ptr
%249 = llvm.load %248 : !llvm.ptr -> f64
func.return %249 : f64
}
func.func @main() -> i32 {
%251 = arith.constant 144 : i32
%252 = arith.constant 4 : i32
%253 = arith.extsi %251 : i32 to i64
%254 = arith.extsi %252 : i32 to i64
%250 = func.call @calloc(%253, %254) : (i64, i64) -> !llvm.ptr
%255 = llvm.mlir.addressof @g_binom : !llvm.ptr
llvm.store %250, %255 : !llvm.ptr, !llvm.ptr
%257 = arith.constant 16 : i32
%258 = arith.constant 8 : i32
%259 = arith.extsi %257 : i32 to i64
%260 = arith.extsi %258 : i32 to i64
%256 = func.call @calloc(%259, %260) : (i64, i64) -> !llvm.ptr
%261 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
llvm.store %256, %261 : !llvm.ptr, !llvm.ptr
%262 = llvm.mlir.addressof @g_binom : !llvm.ptr
%263 = llvm.load %262 : !llvm.ptr -> !llvm.ptr
%264 = llvm.mlir.zero : !llvm.ptr
%265 = llvm.icmp "eq" %263, %264 : !llvm.ptr
%266 = scf.if %265 -> (i1) {
%267 = arith.constant true
scf.yield %267 : i1
} else {
%268 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%269 = llvm.load %268 : !llvm.ptr -> !llvm.ptr
%270 = llvm.mlir.zero : !llvm.ptr
%271 = llvm.icmp "eq" %269, %270 : !llvm.ptr
scf.yield %271 : i1
}
cf.cond_br %266, ^bb21, ^bb22
^bb21:
%272 = arith.constant 1 : i32
func.return %272 : i32
^bb22:
cf.br ^bb23
^bb23:
func.call @init_binom() : () -> ()
%274 = arith.constant 0.0 : f32
%275 = arith.extf %274 : f32 to f64
%276 = llvm.mlir.constant(1 : i64) : i64
%277 = llvm.alloca %276 x f64 : (i64) -> !llvm.ptr
llvm.store %275, %277 : f64, !llvm.ptr
%278 = arith.constant 0.0 : f32
%279 = arith.extf %278 : f32 to f64
%280 = llvm.mlir.constant(1 : i64) : i64
%281 = llvm.alloca %280 x f64 : (i64) -> !llvm.ptr
llvm.store %279, %281 : f64, !llvm.ptr
%282 = arith.constant 2 : i32
%283 = arith.constant 13 : i32
%284 = arith.index_cast %282 : i32 to index
%285 = arith.index_cast %283 : i32 to index
%287 = arith.constant 1 : index
%288 = arith.constant -1 : index
%289 = arith.cmpi sle, %284, %285 : index
%286 = arith.select %289, %287, %288 : index
cf.br ^bb24(%284 : index)
^bb24(%290: index):
%291 = arith.cmpi slt, %290, %285 : index
%292 = arith.cmpi sgt, %290, %285 : index
%293 = arith.select %289, %291, %292 : i1
cf.cond_br %293, ^bb25(%290 : index), ^bb26(%290 : index)
^bb25(%294: index):
%295 = arith.constant 2 : i32
%296 = arith.constant 13 : i32
%297 = arith.index_cast %295 : i32 to index
%298 = arith.index_cast %296 : i32 to index
%300 = arith.constant 1 : index
%301 = arith.constant -1 : index
%302 = arith.cmpi sle, %297, %298 : index
%299 = arith.select %302, %300, %301 : index
cf.br ^bb27(%297 : index)
^bb27(%303: index):
%304 = arith.cmpi slt, %303, %298 : index
%305 = arith.cmpi sgt, %303, %298 : index
%306 = arith.select %302, %304, %305 : i1
cf.cond_br %306, ^bb28(%303 : index), ^bb29(%303 : index)
^bb28(%307: index):
%309 = arith.index_cast %294 : index to i32
%310 = arith.index_cast %307 : index to i32
%308 = func.call @F(%309, %310) : (i32, i32) -> f64
%311 = llvm.load %281 : !llvm.ptr -> f64
%312 = arith.subf %308, %311 : f64
%313 = llvm.load %277 : !llvm.ptr -> f64
%314 = arith.addf %313, %312 : f64
%315 = llvm.load %277 : !llvm.ptr -> f64
%316 = arith.subf %314, %315 : f64
%317 = arith.subf %316, %312 : f64
llvm.store %317, %281 : f64, !llvm.ptr
llvm.store %314, %277 : f64, !llvm.ptr
%318 = arith.addi %307, %299 : index
cf.br ^bb27(%318 : index)
^bb29(%319: index):
%320 = arith.addi %294, %286 : index
cf.br ^bb24(%320 : index)
^bb26(%321: index):
%322 = llvm.load %277 : !llvm.ptr -> f64
%323 = llvm.mlir.constant(1 : i64) : i64
%324 = llvm.alloca %323 x f64 : (i64) -> !llvm.ptr
llvm.store %322, %324 : f64, !llvm.ptr
%325 = arith.constant 0 : i32
%326 = arith.extsi %325 : i32 to i64
%327 = llvm.mlir.constant(1 : i64) : i64
%328 = llvm.alloca %327 x i64 : (i64) -> !llvm.ptr
llvm.store %326, %328 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%329 = llvm.load %324 : !llvm.ptr -> f64
%330 = arith.constant 10.0 : f32
%332 = arith.extf %330 : f32 to f64
%331 = arith.cmpf oge, %329, %332 : f64
cf.cond_br %331, ^bb31, ^bb32
^bb31:
%333 = llvm.load %324 : !llvm.ptr -> f64
%334 = arith.constant 10.0 : f32
%336 = arith.extf %334 : f32 to f64
%335 = arith.divf %333, %336 : f64
llvm.store %335, %324 : f64, !llvm.ptr
%337 = llvm.load %328 : !llvm.ptr -> i64
%338 = arith.constant 1 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.addi %337, %340 : i64
llvm.store %339, %328 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
cf.br ^bb33
^bb33:
%341 = llvm.load %324 : !llvm.ptr -> f64
%342 = arith.constant 1.0 : f32
%344 = arith.extf %342 : f32 to f64
%343 = arith.cmpf olt, %341, %344 : f64
%345 = scf.if %343 -> (i1) {
%346 = llvm.load %324 : !llvm.ptr -> f64
%347 = arith.constant 0.0 : f32
%349 = arith.extf %347 : f32 to f64
%348 = arith.cmpf ogt, %346, %349 : f64
scf.yield %348 : i1
} else {
%350 = arith.constant false
scf.yield %350 : i1
}
cf.cond_br %345, ^bb34, ^bb35
^bb34:
%351 = llvm.load %324 : !llvm.ptr -> f64
%352 = arith.constant 10.0 : f32
%354 = arith.extf %352 : f32 to f64
%353 = arith.mulf %351, %354 : f64
llvm.store %353, %324 : f64, !llvm.ptr
%355 = llvm.load %328 : !llvm.ptr -> i64
%356 = arith.constant 1 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.subi %355, %358 : i64
llvm.store %357, %328 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%359 = llvm.mlir.addressof @str_0 : !llvm.ptr
%360 = llvm.load %324 : !llvm.ptr -> f64
%361 = llvm.load %328 : !llvm.ptr -> i64
%362 = llvm.call @printf(%359, %360, %361) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64, i64) -> i32
%364 = llvm.mlir.addressof @g_cos_table : !llvm.ptr
%365 = llvm.load %364 : !llvm.ptr -> !llvm.ptr
func.call @free(%365) : (!llvm.ptr) -> ()
%367 = llvm.mlir.addressof @g_binom : !llvm.ptr
%368 = llvm.load %367 : !llvm.ptr -> !llvm.ptr
func.call @free(%368) : (!llvm.ptr) -> ()
%369 = arith.constant 0 : i32
func.return %369 : i32
}
}