← All problems Problem 835
Supernatural Triangles - S(10^(10^10)) mod 1234567891. Pure Flow port of the native C solver.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)O(n^2)Space complexity O(1)O(n^2)Approach Flow solution Bottom-up DP Verdict Suboptimal
Flow source
# Project Euler 835
# Supernatural Triangles - S(10^(10^10)) mod 1234567891.
# Pure Flow port of the native C solver.
extern {
function sqrt(x: f64) -> f64
function log(x: f64) -> f64
function floor(x: f64) -> f64
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1234567891
function mmul(a: i64, b: i64) -> i64 {
return ((a as i128) * (b as i128) % (MOD as i128)) as i64
}
function mpow(base: i64, exp: i64) -> i64 {
let mut result: i64 = 1 % MOD
let mut b: i64 = base % MOD
if b < 0 { b = b + MOD }
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 { result = mmul(result, b) }
b = mmul(b, b)
e = e / 2
}
return result
}
function egcd(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0 % MOD
if a < 0 { a = a + MOD }
let mut b: i64 = MOD
let mut x0: i64 = 1
let mut x1: i64 = 0
while b != 0 {
let q: i64 = a / b
let t: i64 = b
b = a % b
a = t
let t2: i64 = x1
x1 = x0 - q * x1
x0 = t2
}
return ((x0 % MOD) + MOD) % MOD
}
function modinv(a: i64) -> i64 {
return egcd(a, MOD)
}
# ---- Family B ----
function sum_family_B(E: i64) -> i64 {
let M: i64 = E / 2
let n: i64 = (5 * mpow(10, M - 1)) % MOD
let n2: i64 = mmul(n, n)
let n3: i64 = mmul(n2, n)
let INV3: i64 = modinv(3)
let sum_t_all: i64 = n2
let sum_t2_all: i64 = mmul((4 * n3 % MOD - n % MOD + MOD) % MOD, INV3)
return (sum_t_all + sum_t2_all - 2 + MOD) % MOD
}
# ---- Family A: matrix exponentiation ----
function mat_mul(A: ptr<i64>, B: ptr<i64>, C: ptr<i64>) -> void {
let tmp: ptr<i64> = calloc(9, 8)
let mut i: i32 = 0
while i < 3 {
let mut j: i32 = 0
while j < 3 {
let mut s: i128 = 0
let mut k: i32 = 0
while k < 3 {
s = s + (A[i * 3 + k] as i128) * (B[k * 3 + j] as i128)
k = k + 1
}
tmp[i * 3 + j] = (s % (MOD as i128)) as i64
j = j + 1
}
i = i + 1
}
let mut i2: i32 = 0
while i2 < 9 {
C[i2] = tmp[i2]
i2 = i2 + 1
}
free(tmp)
}
function mat_pow(M: ptr<i64>, exp: i64, R: ptr<i64>) -> void {
let result: ptr<i64> = calloc(9, 8)
result[0] = 1; result[1] = 0; result[2] = 0
result[3] = 0; result[4] = 1; result[5] = 0
result[6] = 0; result[7] = 0; result[8] = 1
let base: ptr<i64> = calloc(9, 8)
let mut i: i32 = 0
while i < 9 {
base[i] = M[i]
i = i + 1
}
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 { mat_mul(result, base, result) }
mat_mul(base, base, base)
e = e / 2
}
let mut i2: i32 = 0
while i2 < 9 {
R[i2] = result[i2]
i2 = i2 + 1
}
free(result)
free(base)
}
function pell_max_index(E: i64) -> i64 {
let alpha: f64 = 3.0 + 2.0 * sqrt(2.0)
let A_coeff: f64 = (4.0 + 3.0 * sqrt(2.0)) / 4.0
let log10_alpha: f64 = log(alpha) / log(10.0)
let log10_A: f64 = log(A_coeff) / log(10.0)
let x: f64 = ((E as f64) - log10_A) / log10_alpha
let mut n: i64 = x as i64
# Adjust for floating point rounding
while n > 0 {
if (log10_A + (n as f64) * log10_alpha) >= (E as f64) {
n = n - 1
} else {
break
}
}
while (log10_A + ((n + 1) as f64) * log10_alpha) < (E as f64) {
n = n + 1
}
if n < 1 { return 0 }
return n
}
function sum_family_A(n: i64) -> i64 {
if n <= 0 { return 0 }
if n == 1 { return 12 % MOD }
# State: [P_k, P_{k-1}, S_k]^T
# P_{k+1} = 6*P_k - P_{k-1}
# S_{k+1} = S_k + P_{k+1}
let mat: ptr<i64> = calloc(9, 8)
mat[0] = 6; mat[1] = MOD - 1; mat[2] = 0
mat[3] = 1; mat[4] = 0; mat[5] = 0
mat[6] = 6; mat[7] = MOD - 1; mat[8] = 1
let P: ptr<i64> = calloc(9, 8)
mat_pow(mat, n - 1, P)
# v1 = [12, 2, 12]^T (k=1)
let v: ptr<i64> = calloc(3, 8)
v[0] = 12; v[1] = 2; v[2] = 12
let result: ptr<i64> = calloc(3, 8)
let mut i: i32 = 0
while i < 3 {
let mut s: i128 = 0
let mut j: i32 = 0
while j < 3 {
s = s + (P[i * 3 + j] as i128) * (v[j] as i128)
j = j + 1
}
result[i] = (s % (MOD as i128)) as i64
i = i + 1
}
let ans: i64 = result[2] % MOD
free(mat)
free(P)
free(v)
free(result)
return ans
}
function main() -> i32 {
let E: i64 = 10000000000
let sumB: i64 = sum_family_B(E)
let nA: i64 = pell_max_index(E)
let sumA: i64 = sum_family_A(nA)
let ans: i64 = (sumA + sumB - 12 + MOD) % MOD
printf("%lld\n", ans)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t mmul_i64_i64(int64_t a, int64_t b);
int64_t mpow_i64_i64(int64_t base, int64_t exp);
int64_t egcd_i64_i64(int64_t a0, int64_t b0);
int64_t modinv_i64(int64_t a);
int64_t sum_family_B_i64(int64_t E);
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* B, int64_t* C);
void mat_pow_ptr_i64_i64_ptr_i64(int64_t* M, int64_t exp, int64_t* R);
int64_t pell_max_index_i64(int64_t E);
int64_t sum_family_A_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 1234567891;
int64_t mmul_i64_i64(int64_t a, int64_t b) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(MOD))))));
}
int64_t mpow_i64_i64(int64_t base, int64_t exp) {
int64_t result = FLOW_CHECKED_MOD((1), (MOD));
int64_t b = FLOW_CHECKED_MOD((base), (MOD));
if (b < 0) {
b = (b + MOD);
}
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mmul_i64_i64(result, b);
}
b = mmul_i64_i64(b, b);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
int64_t egcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = FLOW_CHECKED_MOD((a0), (MOD));
if (a < 0) {
a = (a + MOD);
}
int64_t b = MOD;
int64_t x0 = 1;
int64_t x1 = 0;
while (b != 0) {
int64_t q = FLOW_CHECKED_DIV((a), (b));
int64_t t = b;
b = FLOW_CHECKED_MOD((a), (b));
a = t;
int64_t t2 = x1;
x1 = (x0 - (q * x1));
x0 = t2;
}
return FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((x0), (MOD)) + MOD)), (MOD));
}
int64_t modinv_i64(int64_t a) {
return egcd_i64_i64(a, MOD);
}
int64_t sum_family_B_i64(int64_t E) {
int64_t M = FLOW_CHECKED_DIV((E), (2));
int64_t n = FLOW_CHECKED_MOD(((5 * mpow_i64_i64(10, (M - 1)))), (MOD));
int64_t n2 = mmul_i64_i64(n, n);
int64_t n3 = mmul_i64_i64(n2, n);
int64_t INV3 = modinv_i64(3);
int64_t sum_t_all = n2;
int64_t sum_t2_all = mmul_i64_i64(FLOW_CHECKED_MOD((((FLOW_CHECKED_MOD(((4 * n3)), (MOD)) - FLOW_CHECKED_MOD((n), (MOD))) + MOD)), (MOD)), INV3);
return FLOW_CHECKED_MOD(((((sum_t_all + sum_t2_all) - 2) + MOD)), (MOD));
}
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* A, int64_t* B, int64_t* C) {
int64_t* tmp = (int64_t*)(calloc(9, 8));
int32_t i = 0;
while (i < 3) {
int32_t j = 0;
while (j < 3) {
__int128 s = 0;
int32_t k = 0;
while (k < 3) {
s = (s + (((__int128)(A[((i * 3) + k)])) * ((__int128)(B[((k * 3) + j)]))));
k = (k + 1);
}
tmp[((i * 3) + j)] = ((int64_t)(FLOW_CHECKED_MOD((s), (((__int128)(MOD))))));
j = (j + 1);
}
i = (i + 1);
}
int32_t i2 = 0;
while (i2 < 9) {
C[i2] = tmp[i2];
i2 = (i2 + 1);
}
free(tmp);
}
void mat_pow_ptr_i64_i64_ptr_i64(int64_t* M, int64_t exp, int64_t* R) {
int64_t* result = (int64_t*)(calloc(9, 8));
result[0] = 1;
result[1] = 0;
result[2] = 0;
result[3] = 0;
result[4] = 1;
result[5] = 0;
result[6] = 0;
result[7] = 0;
result[8] = 1;
int64_t* base = (int64_t*)(calloc(9, 8));
int32_t i = 0;
while (i < 9) {
base[i] = M[i];
i = (i + 1);
}
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
mat_mul_ptr_i64_ptr_i64_ptr_i64(result, base, result);
}
mat_mul_ptr_i64_ptr_i64_ptr_i64(base, base, base);
e = FLOW_CHECKED_DIV((e), (2));
}
int32_t i2 = 0;
while (i2 < 9) {
R[i2] = result[i2];
i2 = (i2 + 1);
}
free(result);
free(base);
}
int64_t pell_max_index_i64(int64_t E) {
double alpha = (3.0 + (2.0 * sqrt(2.0)));
double A_coeff = ((4.0 + (3.0 * sqrt(2.0))) / 4.0);
double log10_alpha = (log(alpha) / log(10.0));
double log10_A = (log(A_coeff) / log(10.0));
double x = ((((double)(E)) - log10_A) / log10_alpha);
int64_t n = ((int64_t)(x));
while (n > 0) {
if ((log10_A + (((double)(n)) * log10_alpha)) >= ((double)(E))) {
n = (n - 1);
} else {
break;
}
}
while ((log10_A + (((double)((n + 1))) * log10_alpha)) < ((double)(E))) {
n = (n + 1);
}
if (n < 1) {
return 0;
}
return n;
}
int64_t sum_family_A_i64(int64_t n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return FLOW_CHECKED_MOD((12), (MOD));
}
int64_t* mat = (int64_t*)(calloc(9, 8));
mat[0] = 6;
mat[1] = (MOD - 1);
mat[2] = 0;
mat[3] = 1;
mat[4] = 0;
mat[5] = 0;
mat[6] = 6;
mat[7] = (MOD - 1);
mat[8] = 1;
int64_t* P = (int64_t*)(calloc(9, 8));
mat_pow_ptr_i64_i64_ptr_i64(mat, (n - 1), P);
int64_t* v = (int64_t*)(calloc(3, 8));
v[0] = 12;
v[1] = 2;
v[2] = 12;
int64_t* result = (int64_t*)(calloc(3, 8));
int32_t i = 0;
while (i < 3) {
__int128 s = 0;
int32_t j = 0;
while (j < 3) {
s = (s + (((__int128)(P[((i * 3) + j)])) * ((__int128)(v[j]))));
j = (j + 1);
}
result[i] = ((int64_t)(FLOW_CHECKED_MOD((s), (((__int128)(MOD))))));
i = (i + 1);
}
int64_t ans = FLOW_CHECKED_MOD((result[2]), (MOD));
free(mat);
free(P);
free(v);
free(result);
return ans;
}
int32_t main(void) {
int64_t E = 10000000000;
int64_t sumB = sum_family_B_i64(E);
int64_t nA = pell_max_index_i64(E);
int64_t sumA = sum_family_A_i64(nA);
int64_t ans = FLOW_CHECKED_MOD(((((sumA + sumB) - 12) + MOD)), (MOD));
printf("%lld\n", ans);
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 @sqrt(f64) -> f64
func.func private @log(f64) -> f64
func.func private @floor(f64) -> f64
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1234567891 : i64) : i64
func.func @mmul(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.extsi %arg0 : i64 to i128
%1 = arith.extsi %arg1 : i64 to i128
%3 = arith.trunci %0 : i128 to i64
%4 = arith.trunci %1 : i128 to i64
%2 = arith.muli %3, %4 : i64
%5 = llvm.mlir.addressof @MOD : !llvm.ptr
%6 = llvm.load %5 : !llvm.ptr -> i64
%7 = arith.extsi %6 : i64 to i128
%9 = arith.trunci %7 : i128 to i64
%8 = arith.remsi %2, %9 : i64
func.return %8 : i64
}
func.func @mpow(%arg0: i64, %arg1: i64) -> i64 {
%10 = arith.constant 1 : i32
%11 = llvm.mlir.addressof @MOD : !llvm.ptr
%12 = llvm.load %11 : !llvm.ptr -> i64
%14 = arith.extsi %10 : i32 to i64
%13 = arith.remsi %14, %12 : i64
%15 = llvm.mlir.constant(1 : i64) : i64
%16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
llvm.store %13, %16 : i64, !llvm.ptr
%17 = llvm.mlir.addressof @MOD : !llvm.ptr
%18 = llvm.load %17 : !llvm.ptr -> i64
%19 = arith.remsi %arg0, %18 : i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
%22 = llvm.load %21 : !llvm.ptr -> i64
%23 = arith.constant 0 : i32
%25 = arith.extsi %23 : i32 to i64
%24 = arith.cmpi slt, %22, %25 : i64
cf.cond_br %24, ^bb0, ^bb1
^bb0:
%26 = llvm.load %21 : !llvm.ptr -> i64
%27 = llvm.mlir.addressof @MOD : !llvm.ptr
%28 = llvm.load %27 : !llvm.ptr -> i64
%29 = arith.addi %26, %28 : i64
llvm.store %29, %21 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 0 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.cmpi sgt, %32, %35 : i64
cf.cond_br %34, ^bb4, ^bb5
^bb4:
%36 = llvm.load %31 : !llvm.ptr -> i64
%37 = arith.constant 2 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.remsi %36, %39 : i64
%40 = arith.constant 1 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.cmpi eq, %38, %42 : i64
cf.cond_br %41, ^bb6, ^bb7
^bb6:
%44 = llvm.load %16 : !llvm.ptr -> i64
%45 = llvm.load %21 : !llvm.ptr -> i64
%43 = func.call @mmul(%44, %45) : (i64, i64) -> i64
llvm.store %43, %16 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%47 = llvm.load %21 : !llvm.ptr -> i64
%48 = llvm.load %21 : !llvm.ptr -> i64
%46 = func.call @mmul(%47, %48) : (i64, i64) -> i64
llvm.store %46, %21 : i64, !llvm.ptr
%49 = llvm.load %31 : !llvm.ptr -> i64
%50 = arith.constant 2 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.divsi %49, %52 : i64
llvm.store %51, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%53 = llvm.load %16 : !llvm.ptr -> i64
func.return %53 : i64
}
func.func @egcd(%arg0: i64, %arg1: i64) -> i64 {
%54 = llvm.mlir.addressof @MOD : !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.remsi %arg0, %55 : i64
%57 = llvm.mlir.constant(1 : i64) : i64
%58 = llvm.alloca %57 x i64 : (i64) -> !llvm.ptr
llvm.store %56, %58 : i64, !llvm.ptr
%59 = llvm.load %58 : !llvm.ptr -> i64
%60 = arith.constant 0 : i32
%62 = arith.extsi %60 : i32 to i64
%61 = arith.cmpi slt, %59, %62 : i64
cf.cond_br %61, ^bb9, ^bb10
^bb9:
%63 = llvm.load %58 : !llvm.ptr -> i64
%64 = llvm.mlir.addressof @MOD : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.addi %63, %65 : i64
llvm.store %66, %58 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%67 = llvm.mlir.addressof @MOD : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = llvm.mlir.constant(1 : i64) : i64
%70 = llvm.alloca %69 x i64 : (i64) -> !llvm.ptr
llvm.store %68, %70 : i64, !llvm.ptr
%71 = arith.constant 1 : i32
%72 = arith.extsi %71 : i32 to i64
%73 = llvm.mlir.constant(1 : i64) : i64
%74 = llvm.alloca %73 x i64 : (i64) -> !llvm.ptr
llvm.store %72, %74 : i64, !llvm.ptr
%75 = arith.constant 0 : i32
%76 = arith.extsi %75 : i32 to i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%79 = llvm.load %70 : !llvm.ptr -> i64
%80 = arith.constant 0 : i32
%82 = arith.extsi %80 : i32 to i64
%81 = arith.cmpi ne, %79, %82 : i64
cf.cond_br %81, ^bb13, ^bb14
^bb13:
%83 = llvm.load %58 : !llvm.ptr -> i64
%84 = llvm.load %70 : !llvm.ptr -> i64
%85 = arith.divsi %83, %84 : i64
%86 = llvm.load %70 : !llvm.ptr -> i64
%87 = llvm.load %58 : !llvm.ptr -> i64
%88 = llvm.load %70 : !llvm.ptr -> i64
%89 = arith.remsi %87, %88 : i64
llvm.store %89, %70 : i64, !llvm.ptr
llvm.store %86, %58 : i64, !llvm.ptr
%90 = llvm.load %78 : !llvm.ptr -> i64
%91 = llvm.load %74 : !llvm.ptr -> i64
%92 = llvm.load %78 : !llvm.ptr -> i64
%93 = arith.muli %85, %92 : i64
%94 = arith.subi %91, %93 : i64
llvm.store %94, %78 : i64, !llvm.ptr
llvm.store %90, %74 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%95 = llvm.load %74 : !llvm.ptr -> i64
%96 = llvm.mlir.addressof @MOD : !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> i64
%98 = arith.remsi %95, %97 : i64
%99 = llvm.mlir.addressof @MOD : !llvm.ptr
%100 = llvm.load %99 : !llvm.ptr -> i64
%101 = arith.addi %98, %100 : i64
%102 = llvm.mlir.addressof @MOD : !llvm.ptr
%103 = llvm.load %102 : !llvm.ptr -> i64
%104 = arith.remsi %101, %103 : i64
func.return %104 : i64
}
func.func @modinv(%arg0: i64) -> i64 {
%106 = llvm.mlir.addressof @MOD : !llvm.ptr
%107 = llvm.load %106 : !llvm.ptr -> i64
%105 = func.call @egcd(%arg0, %107) : (i64, i64) -> i64
func.return %105 : i64
}
func.func @sum_family_B(%arg0: i64) -> i64 {
%108 = arith.constant 2 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.divsi %arg0, %110 : i64
%111 = arith.constant 5 : i32
%113 = arith.constant 10 : i32
%114 = arith.constant 1 : i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.subi %109, %116 : i64
%117 = arith.extsi %113 : i32 to i64
%112 = func.call @mpow(%117, %115) : (i64, i64) -> i64
%119 = arith.extsi %111 : i32 to i64
%118 = arith.muli %119, %112 : i64
%120 = llvm.mlir.addressof @MOD : !llvm.ptr
%121 = llvm.load %120 : !llvm.ptr -> i64
%122 = arith.remsi %118, %121 : i64
%123 = func.call @mmul(%122, %122) : (i64, i64) -> i64
%124 = func.call @mmul(%123, %122) : (i64, i64) -> i64
%126 = arith.constant 3 : i32
%127 = arith.extsi %126 : i32 to i64
%125 = func.call @modinv(%127) : (i64) -> i64
%129 = arith.constant 4 : i32
%131 = arith.extsi %129 : i32 to i64
%130 = arith.muli %131, %124 : i64
%132 = llvm.mlir.addressof @MOD : !llvm.ptr
%133 = llvm.load %132 : !llvm.ptr -> i64
%134 = arith.remsi %130, %133 : i64
%135 = llvm.mlir.addressof @MOD : !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> i64
%137 = arith.remsi %122, %136 : i64
%138 = arith.subi %134, %137 : i64
%139 = llvm.mlir.addressof @MOD : !llvm.ptr
%140 = llvm.load %139 : !llvm.ptr -> i64
%141 = arith.addi %138, %140 : i64
%142 = llvm.mlir.addressof @MOD : !llvm.ptr
%143 = llvm.load %142 : !llvm.ptr -> i64
%144 = arith.remsi %141, %143 : i64
%128 = func.call @mmul(%144, %125) : (i64, i64) -> i64
%145 = arith.addi %123, %128 : i64
%146 = arith.constant 2 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.subi %145, %148 : i64
%149 = llvm.mlir.addressof @MOD : !llvm.ptr
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = arith.addi %147, %150 : i64
%152 = llvm.mlir.addressof @MOD : !llvm.ptr
%153 = llvm.load %152 : !llvm.ptr -> i64
%154 = arith.remsi %151, %153 : i64
func.return %154 : i64
}
func.func @mat_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%156 = arith.constant 9 : i32
%157 = arith.constant 8 : i32
%158 = arith.extsi %156 : i32 to i64
%159 = arith.extsi %157 : i32 to i64
%155 = func.call @calloc(%158, %159) : (i64, i64) -> !llvm.ptr
%160 = arith.constant 0 : i32
%161 = llvm.mlir.constant(1 : i64) : i64
%162 = llvm.alloca %161 x i32 : (i64) -> !llvm.ptr
llvm.store %160, %162 : i32, !llvm.ptr
cf.br ^bb15
^bb15:
%163 = llvm.load %162 : !llvm.ptr -> i32
%164 = arith.constant 3 : i32
%165 = arith.cmpi slt, %163, %164 : i32
cf.cond_br %165, ^bb16, ^bb17
^bb16:
%166 = arith.constant 0 : i32
%167 = llvm.mlir.constant(1 : i64) : i64
%168 = llvm.alloca %167 x i32 : (i64) -> !llvm.ptr
llvm.store %166, %168 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%169 = llvm.load %168 : !llvm.ptr -> i32
%170 = arith.constant 3 : i32
%171 = arith.cmpi slt, %169, %170 : i32
cf.cond_br %171, ^bb19, ^bb20
^bb19:
%172 = arith.constant 0 : i32
%173 = arith.extsi %172 : i32 to i128
%174 = llvm.mlir.constant(1 : i64) : i64
%175 = llvm.alloca %174 x i128 : (i64) -> !llvm.ptr
llvm.store %173, %175 : i128, !llvm.ptr
%176 = arith.constant 0 : i32
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i32 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i32, !llvm.ptr
cf.br ^bb21
^bb21:
%179 = llvm.load %178 : !llvm.ptr -> i32
%180 = arith.constant 3 : i32
%181 = arith.cmpi slt, %179, %180 : i32
cf.cond_br %181, ^bb22, ^bb23
^bb22:
%182 = llvm.load %175 : !llvm.ptr -> i128
%184 = llvm.load %162 : !llvm.ptr -> i32
%185 = arith.constant 3 : i32
%186 = arith.muli %184, %185 : i32
%187 = llvm.load %178 : !llvm.ptr -> i32
%188 = arith.addi %186, %187 : i32
%189 = arith.extsi %188 : i32 to i64
%190 = llvm.getelementptr %arg0[%189] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%183 = llvm.load %190 : !llvm.ptr -> i64
%191 = arith.extsi %183 : i64 to i128
%193 = llvm.load %178 : !llvm.ptr -> i32
%194 = arith.constant 3 : i32
%195 = arith.muli %193, %194 : i32
%196 = llvm.load %168 : !llvm.ptr -> i32
%197 = arith.addi %195, %196 : i32
%198 = arith.extsi %197 : i32 to i64
%199 = llvm.getelementptr %arg1[%198] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%192 = llvm.load %199 : !llvm.ptr -> i64
%200 = arith.extsi %192 : i64 to i128
%202 = arith.trunci %191 : i128 to i64
%203 = arith.trunci %200 : i128 to i64
%201 = arith.muli %202, %203 : i64
%205 = arith.trunci %182 : i128 to i64
%204 = arith.addi %205, %201 : i64
%206 = arith.extsi %204 : i64 to i128
llvm.store %206, %175 : i128, !llvm.ptr
%207 = llvm.load %178 : !llvm.ptr -> i32
%208 = arith.constant 1 : i32
%209 = arith.addi %207, %208 : i32
llvm.store %209, %178 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%210 = llvm.load %175 : !llvm.ptr -> i128
%211 = llvm.mlir.addressof @MOD : !llvm.ptr
%212 = llvm.load %211 : !llvm.ptr -> i64
%213 = arith.extsi %212 : i64 to i128
%215 = arith.trunci %210 : i128 to i64
%216 = arith.trunci %213 : i128 to i64
%214 = arith.remsi %215, %216 : i64
%217 = llvm.load %162 : !llvm.ptr -> i32
%218 = arith.constant 3 : i32
%219 = arith.muli %217, %218 : i32
%220 = llvm.load %168 : !llvm.ptr -> i32
%221 = arith.addi %219, %220 : i32
%222 = arith.extsi %221 : i32 to i64
%223 = llvm.getelementptr %155[%222] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %214, %223 : i64, !llvm.ptr
%224 = llvm.load %168 : !llvm.ptr -> i32
%225 = arith.constant 1 : i32
%226 = arith.addi %224, %225 : i32
llvm.store %226, %168 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%227 = llvm.load %162 : !llvm.ptr -> i32
%228 = arith.constant 1 : i32
%229 = arith.addi %227, %228 : i32
llvm.store %229, %162 : i32, !llvm.ptr
cf.br ^bb15
^bb17:
%230 = arith.constant 0 : i32
%231 = llvm.mlir.constant(1 : i64) : i64
%232 = llvm.alloca %231 x i32 : (i64) -> !llvm.ptr
llvm.store %230, %232 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%233 = llvm.load %232 : !llvm.ptr -> i32
%234 = arith.constant 9 : i32
%235 = arith.cmpi slt, %233, %234 : i32
cf.cond_br %235, ^bb25, ^bb26
^bb25:
%237 = llvm.load %232 : !llvm.ptr -> i32
%238 = arith.extsi %237 : i32 to i64
%239 = llvm.getelementptr %155[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%236 = llvm.load %239 : !llvm.ptr -> i64
%240 = llvm.load %232 : !llvm.ptr -> i32
%241 = arith.extsi %240 : i32 to i64
%242 = llvm.getelementptr %arg2[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %236, %242 : i64, !llvm.ptr
%243 = llvm.load %232 : !llvm.ptr -> i32
%244 = arith.constant 1 : i32
%245 = arith.addi %243, %244 : i32
llvm.store %245, %232 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
func.call @free(%155) : (!llvm.ptr) -> ()
func.return
}
func.func @mat_pow(%arg0: !llvm.ptr, %arg1: i64, %arg2: !llvm.ptr) -> () {
%248 = arith.constant 9 : i32
%249 = arith.constant 8 : i32
%250 = arith.extsi %248 : i32 to i64
%251 = arith.extsi %249 : i32 to i64
%247 = func.call @calloc(%250, %251) : (i64, i64) -> !llvm.ptr
%252 = arith.constant 1 : i32
%253 = arith.constant 0 : i32
%254 = arith.extsi %252 : i32 to i64
%255 = arith.extsi %253 : i32 to i64
%256 = llvm.getelementptr %247[%255] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %254, %256 : i64, !llvm.ptr
%257 = arith.constant 0 : i32
%258 = arith.constant 1 : i32
%259 = arith.extsi %257 : i32 to i64
%260 = arith.extsi %258 : i32 to i64
%261 = llvm.getelementptr %247[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %259, %261 : i64, !llvm.ptr
%262 = arith.constant 0 : i32
%263 = arith.constant 2 : i32
%264 = arith.extsi %262 : i32 to i64
%265 = arith.extsi %263 : i32 to i64
%266 = llvm.getelementptr %247[%265] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %264, %266 : i64, !llvm.ptr
%267 = arith.constant 0 : i32
%268 = arith.constant 3 : i32
%269 = arith.extsi %267 : i32 to i64
%270 = arith.extsi %268 : i32 to i64
%271 = llvm.getelementptr %247[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %269, %271 : i64, !llvm.ptr
%272 = arith.constant 1 : i32
%273 = arith.constant 4 : i32
%274 = arith.extsi %272 : i32 to i64
%275 = arith.extsi %273 : i32 to i64
%276 = llvm.getelementptr %247[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %274, %276 : i64, !llvm.ptr
%277 = arith.constant 0 : i32
%278 = arith.constant 5 : i32
%279 = arith.extsi %277 : i32 to i64
%280 = arith.extsi %278 : i32 to i64
%281 = llvm.getelementptr %247[%280] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %279, %281 : i64, !llvm.ptr
%282 = arith.constant 0 : i32
%283 = arith.constant 6 : i32
%284 = arith.extsi %282 : i32 to i64
%285 = arith.extsi %283 : i32 to i64
%286 = llvm.getelementptr %247[%285] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %284, %286 : i64, !llvm.ptr
%287 = arith.constant 0 : i32
%288 = arith.constant 7 : i32
%289 = arith.extsi %287 : i32 to i64
%290 = arith.extsi %288 : i32 to i64
%291 = llvm.getelementptr %247[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %289, %291 : i64, !llvm.ptr
%292 = arith.constant 1 : i32
%293 = arith.constant 8 : i32
%294 = arith.extsi %292 : i32 to i64
%295 = arith.extsi %293 : i32 to i64
%296 = llvm.getelementptr %247[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %294, %296 : i64, !llvm.ptr
%298 = arith.constant 9 : i32
%299 = arith.constant 8 : i32
%300 = arith.extsi %298 : i32 to i64
%301 = arith.extsi %299 : i32 to i64
%297 = func.call @calloc(%300, %301) : (i64, i64) -> !llvm.ptr
%302 = arith.constant 0 : i32
%303 = llvm.mlir.constant(1 : i64) : i64
%304 = llvm.alloca %303 x i32 : (i64) -> !llvm.ptr
llvm.store %302, %304 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%305 = llvm.load %304 : !llvm.ptr -> i32
%306 = arith.constant 9 : i32
%307 = arith.cmpi slt, %305, %306 : i32
cf.cond_br %307, ^bb28, ^bb29
^bb28:
%309 = llvm.load %304 : !llvm.ptr -> i32
%310 = arith.extsi %309 : i32 to i64
%311 = llvm.getelementptr %arg0[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%308 = llvm.load %311 : !llvm.ptr -> i64
%312 = llvm.load %304 : !llvm.ptr -> i32
%313 = arith.extsi %312 : i32 to i64
%314 = llvm.getelementptr %297[%313] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %308, %314 : i64, !llvm.ptr
%315 = llvm.load %304 : !llvm.ptr -> i32
%316 = arith.constant 1 : i32
%317 = arith.addi %315, %316 : i32
llvm.store %317, %304 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%318 = llvm.mlir.constant(1 : i64) : i64
%319 = llvm.alloca %318 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %319 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%320 = llvm.load %319 : !llvm.ptr -> i64
%321 = arith.constant 0 : i32
%323 = arith.extsi %321 : i32 to i64
%322 = arith.cmpi sgt, %320, %323 : i64
cf.cond_br %322, ^bb31, ^bb32
^bb31:
%324 = llvm.load %319 : !llvm.ptr -> i64
%325 = arith.constant 2 : i32
%327 = arith.extsi %325 : i32 to i64
%326 = arith.remsi %324, %327 : i64
%328 = arith.constant 1 : i32
%330 = arith.extsi %328 : i32 to i64
%329 = arith.cmpi eq, %326, %330 : i64
cf.cond_br %329, ^bb33, ^bb34
^bb33:
func.call @mat_mul(%247, %297, %247) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
func.call @mat_mul(%297, %297, %297) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%333 = llvm.load %319 : !llvm.ptr -> i64
%334 = arith.constant 2 : i32
%336 = arith.extsi %334 : i32 to i64
%335 = arith.divsi %333, %336 : i64
llvm.store %335, %319 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%337 = arith.constant 0 : i32
%338 = llvm.mlir.constant(1 : i64) : i64
%339 = llvm.alloca %338 x i32 : (i64) -> !llvm.ptr
llvm.store %337, %339 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%340 = llvm.load %339 : !llvm.ptr -> i32
%341 = arith.constant 9 : i32
%342 = arith.cmpi slt, %340, %341 : i32
cf.cond_br %342, ^bb37, ^bb38
^bb37:
%344 = llvm.load %339 : !llvm.ptr -> i32
%345 = arith.extsi %344 : i32 to i64
%346 = llvm.getelementptr %247[%345] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%343 = llvm.load %346 : !llvm.ptr -> i64
%347 = llvm.load %339 : !llvm.ptr -> i32
%348 = arith.extsi %347 : i32 to i64
%349 = llvm.getelementptr %arg2[%348] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %343, %349 : i64, !llvm.ptr
%350 = llvm.load %339 : !llvm.ptr -> i32
%351 = arith.constant 1 : i32
%352 = arith.addi %350, %351 : i32
llvm.store %352, %339 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
func.call @free(%247) : (!llvm.ptr) -> ()
func.call @free(%297) : (!llvm.ptr) -> ()
func.return
}
func.func @pell_max_index(%arg0: i64) -> i64 {
%355 = arith.constant 3.0 : f32
%356 = arith.constant 2.0 : f32
%357 = arith.constant 2.0 : f32
%358 = math.sqrt %357 : f32
%360 = arith.extf %356 : f32 to f64
%359 = arith.mulf %360, %358 : f64
%362 = arith.extf %355 : f32 to f64
%361 = arith.addf %362, %359 : f64
%363 = arith.constant 4.0 : f32
%364 = arith.constant 3.0 : f32
%365 = arith.constant 2.0 : f32
%366 = math.sqrt %365 : f32
%368 = arith.extf %364 : f32 to f64
%367 = arith.mulf %368, %366 : f64
%370 = arith.extf %363 : f32 to f64
%369 = arith.addf %370, %367 : f64
%371 = arith.constant 4.0 : f32
%373 = arith.extf %371 : f32 to f64
%372 = arith.divf %369, %373 : f64
%374 = math.log %361 : f64
%375 = arith.constant 10.0 : f32
%376 = math.log %375 : f32
%377 = arith.divf %374, %376 : f64
%378 = math.log %372 : f64
%379 = arith.constant 10.0 : f32
%380 = math.log %379 : f32
%381 = arith.divf %378, %380 : f64
%382 = arith.sitofp %arg0 : i64 to f64
%383 = arith.subf %382, %381 : f64
%384 = arith.divf %383, %377 : f64
%385 = arith.fptosi %384 : f64 to i64
%386 = llvm.mlir.constant(1 : i64) : i64
%387 = llvm.alloca %386 x i64 : (i64) -> !llvm.ptr
llvm.store %385, %387 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%388 = llvm.load %387 : !llvm.ptr -> i64
%389 = arith.constant 0 : i32
%391 = arith.extsi %389 : i32 to i64
%390 = arith.cmpi sgt, %388, %391 : i64
cf.cond_br %390, ^bb40, ^bb41
^bb40:
%392 = llvm.load %387 : !llvm.ptr -> i64
%393 = arith.sitofp %392 : i64 to f64
%394 = arith.mulf %393, %377 : f64
%395 = arith.addf %381, %394 : f64
%396 = arith.sitofp %arg0 : i64 to f64
%397 = arith.cmpf oge, %395, %396 : f64
cf.cond_br %397, ^bb42, ^bb43
^bb42:
%398 = llvm.load %387 : !llvm.ptr -> i64
%399 = arith.constant 1 : i32
%401 = arith.extsi %399 : i32 to i64
%400 = arith.subi %398, %401 : i64
llvm.store %400, %387 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb41
^bb44:
cf.br ^bb39
^bb41:
cf.br ^bb45
^bb45:
%402 = llvm.load %387 : !llvm.ptr -> i64
%403 = arith.constant 1 : i32
%405 = arith.extsi %403 : i32 to i64
%404 = arith.addi %402, %405 : i64
%406 = arith.sitofp %404 : i64 to f64
%407 = arith.mulf %406, %377 : f64
%408 = arith.addf %381, %407 : f64
%409 = arith.sitofp %arg0 : i64 to f64
%410 = arith.cmpf olt, %408, %409 : f64
cf.cond_br %410, ^bb46, ^bb47
^bb46:
%411 = llvm.load %387 : !llvm.ptr -> i64
%412 = arith.constant 1 : i32
%414 = arith.extsi %412 : i32 to i64
%413 = arith.addi %411, %414 : i64
llvm.store %413, %387 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%415 = llvm.load %387 : !llvm.ptr -> i64
%416 = arith.constant 1 : i32
%418 = arith.extsi %416 : i32 to i64
%417 = arith.cmpi slt, %415, %418 : i64
cf.cond_br %417, ^bb48, ^bb49
^bb48:
%419 = arith.constant 0 : i32
%420 = arith.extsi %419 : i32 to i64
func.return %420 : i64
^bb49:
cf.br ^bb50
^bb50:
%421 = llvm.load %387 : !llvm.ptr -> i64
func.return %421 : i64
}
func.func @sum_family_A(%arg0: i64) -> i64 {
%422 = arith.constant 0 : i32
%424 = arith.extsi %422 : i32 to i64
%423 = arith.cmpi sle, %arg0, %424 : i64
cf.cond_br %423, ^bb51, ^bb52
^bb51:
%425 = arith.constant 0 : i32
%426 = arith.extsi %425 : i32 to i64
func.return %426 : i64
^bb52:
cf.br ^bb53
^bb53:
%427 = arith.constant 1 : i32
%429 = arith.extsi %427 : i32 to i64
%428 = arith.cmpi eq, %arg0, %429 : i64
cf.cond_br %428, ^bb54, ^bb55
^bb54:
%430 = arith.constant 12 : i32
%431 = llvm.mlir.addressof @MOD : !llvm.ptr
%432 = llvm.load %431 : !llvm.ptr -> i64
%434 = arith.extsi %430 : i32 to i64
%433 = arith.remsi %434, %432 : i64
func.return %433 : i64
^bb55:
cf.br ^bb56
^bb56:
%436 = arith.constant 9 : i32
%437 = arith.constant 8 : i32
%438 = arith.extsi %436 : i32 to i64
%439 = arith.extsi %437 : i32 to i64
%435 = func.call @calloc(%438, %439) : (i64, i64) -> !llvm.ptr
%440 = arith.constant 6 : i32
%441 = arith.constant 0 : i32
%442 = arith.extsi %440 : i32 to i64
%443 = arith.extsi %441 : i32 to i64
%444 = llvm.getelementptr %435[%443] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %442, %444 : i64, !llvm.ptr
%445 = llvm.mlir.addressof @MOD : !llvm.ptr
%446 = llvm.load %445 : !llvm.ptr -> i64
%447 = arith.constant 1 : i32
%449 = arith.extsi %447 : i32 to i64
%448 = arith.subi %446, %449 : i64
%450 = arith.constant 1 : i32
%451 = arith.extsi %450 : i32 to i64
%452 = llvm.getelementptr %435[%451] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %448, %452 : i64, !llvm.ptr
%453 = arith.constant 0 : i32
%454 = arith.constant 2 : i32
%455 = arith.extsi %453 : i32 to i64
%456 = arith.extsi %454 : i32 to i64
%457 = llvm.getelementptr %435[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %455, %457 : i64, !llvm.ptr
%458 = arith.constant 1 : i32
%459 = arith.constant 3 : i32
%460 = arith.extsi %458 : i32 to i64
%461 = arith.extsi %459 : i32 to i64
%462 = llvm.getelementptr %435[%461] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %460, %462 : i64, !llvm.ptr
%463 = arith.constant 0 : i32
%464 = arith.constant 4 : i32
%465 = arith.extsi %463 : i32 to i64
%466 = arith.extsi %464 : i32 to i64
%467 = llvm.getelementptr %435[%466] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %465, %467 : i64, !llvm.ptr
%468 = arith.constant 0 : i32
%469 = arith.constant 5 : i32
%470 = arith.extsi %468 : i32 to i64
%471 = arith.extsi %469 : i32 to i64
%472 = llvm.getelementptr %435[%471] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %470, %472 : i64, !llvm.ptr
%473 = arith.constant 6 : i32
%474 = arith.constant 6 : i32
%475 = arith.extsi %473 : i32 to i64
%476 = arith.extsi %474 : i32 to i64
%477 = llvm.getelementptr %435[%476] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %475, %477 : i64, !llvm.ptr
%478 = llvm.mlir.addressof @MOD : !llvm.ptr
%479 = llvm.load %478 : !llvm.ptr -> i64
%480 = arith.constant 1 : i32
%482 = arith.extsi %480 : i32 to i64
%481 = arith.subi %479, %482 : i64
%483 = arith.constant 7 : i32
%484 = arith.extsi %483 : i32 to i64
%485 = llvm.getelementptr %435[%484] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %481, %485 : i64, !llvm.ptr
%486 = arith.constant 1 : i32
%487 = arith.constant 8 : i32
%488 = arith.extsi %486 : i32 to i64
%489 = arith.extsi %487 : i32 to i64
%490 = llvm.getelementptr %435[%489] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %488, %490 : i64, !llvm.ptr
%492 = arith.constant 9 : i32
%493 = arith.constant 8 : i32
%494 = arith.extsi %492 : i32 to i64
%495 = arith.extsi %493 : i32 to i64
%491 = func.call @calloc(%494, %495) : (i64, i64) -> !llvm.ptr
%497 = arith.constant 1 : i32
%499 = arith.extsi %497 : i32 to i64
%498 = arith.subi %arg0, %499 : i64
func.call @mat_pow(%435, %498, %491) : (!llvm.ptr, i64, !llvm.ptr) -> ()
%501 = arith.constant 3 : i32
%502 = arith.constant 8 : i32
%503 = arith.extsi %501 : i32 to i64
%504 = arith.extsi %502 : i32 to i64
%500 = func.call @calloc(%503, %504) : (i64, i64) -> !llvm.ptr
%505 = arith.constant 12 : i32
%506 = arith.constant 0 : i32
%507 = arith.extsi %505 : i32 to i64
%508 = arith.extsi %506 : i32 to i64
%509 = llvm.getelementptr %500[%508] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %507, %509 : i64, !llvm.ptr
%510 = arith.constant 2 : i32
%511 = arith.constant 1 : i32
%512 = arith.extsi %510 : i32 to i64
%513 = arith.extsi %511 : i32 to i64
%514 = llvm.getelementptr %500[%513] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %512, %514 : i64, !llvm.ptr
%515 = arith.constant 12 : i32
%516 = arith.constant 2 : i32
%517 = arith.extsi %515 : i32 to i64
%518 = arith.extsi %516 : i32 to i64
%519 = llvm.getelementptr %500[%518] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %517, %519 : i64, !llvm.ptr
%521 = arith.constant 3 : i32
%522 = arith.constant 8 : i32
%523 = arith.extsi %521 : i32 to i64
%524 = arith.extsi %522 : i32 to i64
%520 = func.call @calloc(%523, %524) : (i64, i64) -> !llvm.ptr
%525 = arith.constant 0 : i32
%526 = llvm.mlir.constant(1 : i64) : i64
%527 = llvm.alloca %526 x i32 : (i64) -> !llvm.ptr
llvm.store %525, %527 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%528 = llvm.load %527 : !llvm.ptr -> i32
%529 = arith.constant 3 : i32
%530 = arith.cmpi slt, %528, %529 : i32
cf.cond_br %530, ^bb58, ^bb59
^bb58:
%531 = arith.constant 0 : i32
%532 = arith.extsi %531 : i32 to i128
%533 = llvm.mlir.constant(1 : i64) : i64
%534 = llvm.alloca %533 x i128 : (i64) -> !llvm.ptr
llvm.store %532, %534 : i128, !llvm.ptr
%535 = arith.constant 0 : i32
%536 = llvm.mlir.constant(1 : i64) : i64
%537 = llvm.alloca %536 x i32 : (i64) -> !llvm.ptr
llvm.store %535, %537 : i32, !llvm.ptr
cf.br ^bb60
^bb60:
%538 = llvm.load %537 : !llvm.ptr -> i32
%539 = arith.constant 3 : i32
%540 = arith.cmpi slt, %538, %539 : i32
cf.cond_br %540, ^bb61, ^bb62
^bb61:
%541 = llvm.load %534 : !llvm.ptr -> i128
%543 = llvm.load %527 : !llvm.ptr -> i32
%544 = arith.constant 3 : i32
%545 = arith.muli %543, %544 : i32
%546 = llvm.load %537 : !llvm.ptr -> i32
%547 = arith.addi %545, %546 : i32
%548 = arith.extsi %547 : i32 to i64
%549 = llvm.getelementptr %491[%548] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%542 = llvm.load %549 : !llvm.ptr -> i64
%550 = arith.extsi %542 : i64 to i128
%552 = llvm.load %537 : !llvm.ptr -> i32
%553 = arith.extsi %552 : i32 to i64
%554 = llvm.getelementptr %500[%553] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%551 = llvm.load %554 : !llvm.ptr -> i64
%555 = arith.extsi %551 : i64 to i128
%557 = arith.trunci %550 : i128 to i64
%558 = arith.trunci %555 : i128 to i64
%556 = arith.muli %557, %558 : i64
%560 = arith.trunci %541 : i128 to i64
%559 = arith.addi %560, %556 : i64
%561 = arith.extsi %559 : i64 to i128
llvm.store %561, %534 : i128, !llvm.ptr
%562 = llvm.load %537 : !llvm.ptr -> i32
%563 = arith.constant 1 : i32
%564 = arith.addi %562, %563 : i32
llvm.store %564, %537 : i32, !llvm.ptr
cf.br ^bb60
^bb62:
%565 = llvm.load %534 : !llvm.ptr -> i128
%566 = llvm.mlir.addressof @MOD : !llvm.ptr
%567 = llvm.load %566 : !llvm.ptr -> i64
%568 = arith.extsi %567 : i64 to i128
%570 = arith.trunci %565 : i128 to i64
%571 = arith.trunci %568 : i128 to i64
%569 = arith.remsi %570, %571 : i64
%572 = llvm.load %527 : !llvm.ptr -> i32
%573 = arith.extsi %572 : i32 to i64
%574 = llvm.getelementptr %520[%573] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %569, %574 : i64, !llvm.ptr
%575 = llvm.load %527 : !llvm.ptr -> i32
%576 = arith.constant 1 : i32
%577 = arith.addi %575, %576 : i32
llvm.store %577, %527 : i32, !llvm.ptr
cf.br ^bb57
^bb59:
%579 = arith.constant 2 : i32
%580 = arith.extsi %579 : i32 to i64
%581 = llvm.getelementptr %520[%580] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%578 = llvm.load %581 : !llvm.ptr -> i64
%582 = llvm.mlir.addressof @MOD : !llvm.ptr
%583 = llvm.load %582 : !llvm.ptr -> i64
%584 = arith.remsi %578, %583 : i64
func.call @free(%435) : (!llvm.ptr) -> ()
func.call @free(%491) : (!llvm.ptr) -> ()
func.call @free(%500) : (!llvm.ptr) -> ()
func.call @free(%520) : (!llvm.ptr) -> ()
func.return %584 : i64
}
func.func @main() -> i32 {
%589 = arith.constant 5705032704 : i32
%590 = arith.extsi %589 : i32 to i64
%591 = func.call @sum_family_B(%590) : (i64) -> i64
%592 = func.call @pell_max_index(%590) : (i64) -> i64
%593 = func.call @sum_family_A(%592) : (i64) -> i64
%594 = arith.addi %593, %591 : i64
%595 = arith.constant 12 : i32
%597 = arith.extsi %595 : i32 to i64
%596 = arith.subi %594, %597 : i64
%598 = llvm.mlir.addressof @MOD : !llvm.ptr
%599 = llvm.load %598 : !llvm.ptr -> i64
%600 = arith.addi %596, %599 : i64
%601 = llvm.mlir.addressof @MOD : !llvm.ptr
%602 = llvm.load %601 : !llvm.ptr -> i64
%603 = arith.remsi %600, %602 : i64
%604 = llvm.mlir.addressof @str_0 : !llvm.ptr
%605 = llvm.call @printf(%604, %603) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%606 = arith.constant 0 : i32
func.return %606 : i32
}
}