Problem 463
Weird recurrence — S(3^37) mod 10^9 via aligned binary blocks.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log n) |
|---|
| Space complexity | O(1) | O(n) |
|---|
| Approach | Flow solution | Modular DP or matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 463
# Weird recurrence — S(3^37) mod 10^9 via aligned binary blocks.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function mat_pow(e0: i64, mod: i64, out: ptr<i64>) -> void {
# A = [[1,1],[-3,5]]
let mut r00: i64 = 1
let mut r01: i64 = 0
let mut r10: i64 = 0
let mut r11: i64 = 1
let mut b00: i64 = 1
let mut b01: i64 = 1
let mut b10: i64 = (-3 % mod + mod) % mod
let mut b11: i64 = 5
let mut e: i64 = e0
while e > 0 {
if e % 2 == 1 {
let n00: i64 = ((r00 * b00 + r01 * b10) % mod + mod) % mod
let n01: i64 = ((r00 * b01 + r01 * b11) % mod + mod) % mod
let n10: i64 = ((r10 * b00 + r11 * b10) % mod + mod) % mod
let n11: i64 = ((r10 * b01 + r11 * b11) % mod + mod) % mod
r00 = n00; r01 = n01; r10 = n10; r11 = n11
}
let c00: i64 = ((b00 * b00 + b01 * b10) % mod + mod) % mod
let c01: i64 = ((b00 * b01 + b01 * b11) % mod + mod) % mod
let c10: i64 = ((b10 * b00 + b11 * b10) % mod + mod) % mod
let c11: i64 = ((b10 * b01 + b11 * b11) % mod + mod) % mod
b00 = c00; b01 = c01; b10 = c10; b11 = c11
e = e / 2
}
out[0] = r00; out[1] = r01; out[2] = r10; out[3] = r11
}
function vk(k0: i64, mod: i64, out: ptr<i64>) -> void {
if k0 == 1 {
out[0] = 1
out[1] = 3
return
}
let mut a: i64 = 1
let mut b: i64 = 3
let mut bits: i32 = 0
let mut t: i64 = k0
while t > 0 {
bits = bits + 1
t = t / 2
}
let mut bi: i32 = bits - 2
while bi >= 0 {
let bit: i64 = (k0 >> bi) & 1
if bit == 0 {
b = ((-a + 2 * b) % mod + mod) % mod
} else {
let na: i64 = b
b = ((-2 * a + 3 * b) % mod + mod) % mod
a = na
}
bi = bi - 1
}
out[0] = a % mod
out[1] = b % mod
}
function main() -> i32 {
let MOD: i64 = 1000000000
let buf: ptr<i64> = calloc(4, 8)
let pbuf: ptr<i64> = calloc(4, 8)
if buf == null || pbuf == null { return 1 }
let mut n: i64 = 1
let mut i: i32 = 0
while i < 37 {
n = n * 3
i = i + 1
}
let mut res: i64 = 0
let mut pos: i64 = 1
while pos <= n {
let remaining: i64 = n - pos + 1
let mut tz: i32 = 0
let mut pp: i64 = pos
while pp % 2 == 0 {
tz = tz + 1
pp = pp / 2
}
let mut rem_bits: i32 = 0
let mut rr: i64 = remaining
while rr > 0 {
rem_bits = rem_bits + 1
rr = rr / 2
}
let mut d: i32 = tz
if rem_bits - 1 < d { d = rem_bits - 1 }
let size: i64 = (1 as i64) << d
let k: i64 = pos / size
vk(k, MOD, buf)
mat_pow(d as i64, MOD, pbuf)
let add: i64 = ((pbuf[0] * buf[0] + pbuf[1] * buf[1]) % MOD + MOD) % MOD
res = (res + add) % MOD
pos = pos + size
}
printf("%lld\n", res)
free(pbuf)
free(buf)
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 mat_pow_i64_i64_ptr_i64(int64_t e0, int64_t mod, int64_t* out);
void vk_i64_i64_ptr_i64(int64_t k0, int64_t mod, int64_t* out);
int32_t main(void);
void mat_pow_i64_i64_ptr_i64(int64_t e0, int64_t mod, int64_t* out) {
int64_t r00 = 1;
int64_t r01 = 0;
int64_t r10 = 0;
int64_t r11 = 1;
int64_t b00 = 1;
int64_t b01 = 1;
int64_t b10 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((-3)), (mod)) + mod)), (mod));
int64_t b11 = 5;
int64_t e = e0;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
int64_t n00 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((r00 * b00) + (r01 * b10))), (mod)) + mod)), (mod));
int64_t n01 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((r00 * b01) + (r01 * b11))), (mod)) + mod)), (mod));
int64_t n10 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((r10 * b00) + (r11 * b10))), (mod)) + mod)), (mod));
int64_t n11 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((r10 * b01) + (r11 * b11))), (mod)) + mod)), (mod));
r00 = n00;
r01 = n01;
r10 = n10;
r11 = n11;
}
int64_t c00 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((b00 * b00) + (b01 * b10))), (mod)) + mod)), (mod));
int64_t c01 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((b00 * b01) + (b01 * b11))), (mod)) + mod)), (mod));
int64_t c10 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((b10 * b00) + (b11 * b10))), (mod)) + mod)), (mod));
int64_t c11 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((b10 * b01) + (b11 * b11))), (mod)) + mod)), (mod));
b00 = c00;
b01 = c01;
b10 = c10;
b11 = c11;
e = FLOW_CHECKED_DIV((e), (2));
}
out[0] = r00;
out[1] = r01;
out[2] = r10;
out[3] = r11;
}
void vk_i64_i64_ptr_i64(int64_t k0, int64_t mod, int64_t* out) {
if (k0 == 1) {
out[0] = 1;
out[1] = 3;
return;
}
int64_t a = 1;
int64_t b = 3;
int32_t bits = 0;
int64_t t = k0;
while (t > 0) {
bits = (bits + 1);
t = FLOW_CHECKED_DIV((t), (2));
}
int32_t bi = (bits - 2);
while (bi >= 0) {
int64_t bit = (FLOW_CHECKED_SHR((k0), (bi)) & 1);
if (bit == 0) {
b = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((-a) + (2 * b))), (mod)) + mod)), (mod));
} else {
int64_t na = b;
b = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((-2) * a) + (3 * b))), (mod)) + mod)), (mod));
a = na;
}
bi = (bi - 1);
}
out[0] = FLOW_CHECKED_MOD((a), (mod));
out[1] = FLOW_CHECKED_MOD((b), (mod));
}
int32_t main(void) {
int64_t MOD = 1000000000;
int64_t* buf = (int64_t*)(calloc(4, 8));
int64_t* pbuf = (int64_t*)(calloc(4, 8));
if ((buf == NULL || pbuf == NULL)) {
return 1;
}
int64_t n = 1;
int32_t i = 0;
while (i < 37) {
n = (n * 3);
i = (i + 1);
}
int64_t res = 0;
int64_t pos = 1;
while (pos <= n) {
int64_t remaining = ((n - pos) + 1);
int32_t tz = 0;
int64_t pp = pos;
while (FLOW_CHECKED_MOD((pp), (2)) == 0) {
tz = (tz + 1);
pp = FLOW_CHECKED_DIV((pp), (2));
}
int32_t rem_bits = 0;
int64_t rr = remaining;
while (rr > 0) {
rem_bits = (rem_bits + 1);
rr = FLOW_CHECKED_DIV((rr), (2));
}
int32_t d = tz;
if ((rem_bits - 1) < d) {
d = (rem_bits - 1);
}
int64_t size = FLOW_CHECKED_SHL((((int64_t)(1))), (d));
int64_t k = FLOW_CHECKED_DIV((pos), (size));
vk_i64_i64_ptr_i64(k, MOD, buf);
mat_pow_i64_i64_ptr_i64(((int64_t)(d)), MOD, pbuf);
int64_t add = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((pbuf[0] * buf[0]) + (pbuf[1] * buf[1]))), (MOD)) + MOD)), (MOD));
res = FLOW_CHECKED_MOD(((res + add)), (MOD));
pos = (pos + size);
}
printf("%lld\n", res);
free(pbuf);
free(buf);
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 @mat_pow(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr) -> () {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.constant 0 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
%8 = arith.constant 0 : i32
%9 = arith.extsi %8 : i32 to i64
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
llvm.store %9, %11 : i64, !llvm.ptr
%12 = arith.constant 1 : i32
%13 = arith.extsi %12 : i32 to i64
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
llvm.store %13, %15 : i64, !llvm.ptr
%16 = arith.constant 1 : i32
%17 = arith.extsi %16 : i32 to i64
%18 = llvm.mlir.constant(1 : i64) : i64
%19 = llvm.alloca %18 x i64 : (i64) -> !llvm.ptr
llvm.store %17, %19 : i64, !llvm.ptr
%20 = arith.constant 1 : i32
%21 = arith.extsi %20 : i32 to i64
%22 = llvm.mlir.constant(1 : i64) : i64
%23 = llvm.alloca %22 x i64 : (i64) -> !llvm.ptr
llvm.store %21, %23 : i64, !llvm.ptr
%24 = arith.constant 3 : i32
%26 = arith.constant 0 : i32
%25 = arith.subi %26, %24 : i32
%28 = arith.extsi %25 : i32 to i64
%27 = arith.remsi %28, %arg1 : i64
%29 = arith.addi %27, %arg1 : i64
%30 = arith.remsi %29, %arg1 : i64
%31 = llvm.mlir.constant(1 : i64) : i64
%32 = llvm.alloca %31 x i64 : (i64) -> !llvm.ptr
llvm.store %30, %32 : i64, !llvm.ptr
%33 = arith.constant 5 : i32
%34 = arith.extsi %33 : i32 to i64
%35 = llvm.mlir.constant(1 : i64) : i64
%36 = llvm.alloca %35 x i64 : (i64) -> !llvm.ptr
llvm.store %34, %36 : i64, !llvm.ptr
%37 = llvm.mlir.constant(1 : i64) : i64
%38 = llvm.alloca %37 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %38 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%39 = llvm.load %38 : !llvm.ptr -> i64
%40 = arith.constant 0 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.cmpi sgt, %39, %42 : i64
cf.cond_br %41, ^bb1, ^bb2
^bb1:
%43 = llvm.load %38 : !llvm.ptr -> i64
%44 = arith.constant 2 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.remsi %43, %46 : i64
%47 = arith.constant 1 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.cmpi eq, %45, %49 : i64
cf.cond_br %48, ^bb3, ^bb4
^bb3:
%50 = llvm.load %3 : !llvm.ptr -> i64
%51 = llvm.load %19 : !llvm.ptr -> i64
%52 = arith.muli %50, %51 : i64
%53 = llvm.load %7 : !llvm.ptr -> i64
%54 = llvm.load %32 : !llvm.ptr -> i64
%55 = arith.muli %53, %54 : i64
%56 = arith.addi %52, %55 : i64
%57 = arith.remsi %56, %arg1 : i64
%58 = arith.addi %57, %arg1 : i64
%59 = arith.remsi %58, %arg1 : i64
%60 = llvm.load %3 : !llvm.ptr -> i64
%61 = llvm.load %23 : !llvm.ptr -> i64
%62 = arith.muli %60, %61 : i64
%63 = llvm.load %7 : !llvm.ptr -> i64
%64 = llvm.load %36 : !llvm.ptr -> i64
%65 = arith.muli %63, %64 : i64
%66 = arith.addi %62, %65 : i64
%67 = arith.remsi %66, %arg1 : i64
%68 = arith.addi %67, %arg1 : i64
%69 = arith.remsi %68, %arg1 : i64
%70 = llvm.load %11 : !llvm.ptr -> i64
%71 = llvm.load %19 : !llvm.ptr -> i64
%72 = arith.muli %70, %71 : i64
%73 = llvm.load %15 : !llvm.ptr -> i64
%74 = llvm.load %32 : !llvm.ptr -> i64
%75 = arith.muli %73, %74 : i64
%76 = arith.addi %72, %75 : i64
%77 = arith.remsi %76, %arg1 : i64
%78 = arith.addi %77, %arg1 : i64
%79 = arith.remsi %78, %arg1 : i64
%80 = llvm.load %11 : !llvm.ptr -> i64
%81 = llvm.load %23 : !llvm.ptr -> i64
%82 = arith.muli %80, %81 : i64
%83 = llvm.load %15 : !llvm.ptr -> i64
%84 = llvm.load %36 : !llvm.ptr -> i64
%85 = arith.muli %83, %84 : i64
%86 = arith.addi %82, %85 : i64
%87 = arith.remsi %86, %arg1 : i64
%88 = arith.addi %87, %arg1 : i64
%89 = arith.remsi %88, %arg1 : i64
llvm.store %59, %3 : i64, !llvm.ptr
llvm.store %69, %7 : i64, !llvm.ptr
llvm.store %79, %11 : i64, !llvm.ptr
llvm.store %89, %15 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%90 = llvm.load %19 : !llvm.ptr -> i64
%91 = llvm.load %19 : !llvm.ptr -> i64
%92 = arith.muli %90, %91 : i64
%93 = llvm.load %23 : !llvm.ptr -> i64
%94 = llvm.load %32 : !llvm.ptr -> i64
%95 = arith.muli %93, %94 : i64
%96 = arith.addi %92, %95 : i64
%97 = arith.remsi %96, %arg1 : i64
%98 = arith.addi %97, %arg1 : i64
%99 = arith.remsi %98, %arg1 : i64
%100 = llvm.load %19 : !llvm.ptr -> i64
%101 = llvm.load %23 : !llvm.ptr -> i64
%102 = arith.muli %100, %101 : i64
%103 = llvm.load %23 : !llvm.ptr -> i64
%104 = llvm.load %36 : !llvm.ptr -> i64
%105 = arith.muli %103, %104 : i64
%106 = arith.addi %102, %105 : i64
%107 = arith.remsi %106, %arg1 : i64
%108 = arith.addi %107, %arg1 : i64
%109 = arith.remsi %108, %arg1 : i64
%110 = llvm.load %32 : !llvm.ptr -> i64
%111 = llvm.load %19 : !llvm.ptr -> i64
%112 = arith.muli %110, %111 : i64
%113 = llvm.load %36 : !llvm.ptr -> i64
%114 = llvm.load %32 : !llvm.ptr -> i64
%115 = arith.muli %113, %114 : i64
%116 = arith.addi %112, %115 : i64
%117 = arith.remsi %116, %arg1 : i64
%118 = arith.addi %117, %arg1 : i64
%119 = arith.remsi %118, %arg1 : i64
%120 = llvm.load %32 : !llvm.ptr -> i64
%121 = llvm.load %23 : !llvm.ptr -> i64
%122 = arith.muli %120, %121 : i64
%123 = llvm.load %36 : !llvm.ptr -> i64
%124 = llvm.load %36 : !llvm.ptr -> i64
%125 = arith.muli %123, %124 : i64
%126 = arith.addi %122, %125 : i64
%127 = arith.remsi %126, %arg1 : i64
%128 = arith.addi %127, %arg1 : i64
%129 = arith.remsi %128, %arg1 : i64
llvm.store %99, %19 : i64, !llvm.ptr
llvm.store %109, %23 : i64, !llvm.ptr
llvm.store %119, %32 : i64, !llvm.ptr
llvm.store %129, %36 : i64, !llvm.ptr
%130 = llvm.load %38 : !llvm.ptr -> i64
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.divsi %130, %133 : i64
llvm.store %132, %38 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%134 = llvm.load %3 : !llvm.ptr -> i64
%135 = arith.constant 0 : i32
%136 = arith.extsi %135 : i32 to i64
%137 = llvm.getelementptr %arg2[%136] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %134, %137 : i64, !llvm.ptr
%138 = llvm.load %7 : !llvm.ptr -> i64
%139 = arith.constant 1 : i32
%140 = arith.extsi %139 : i32 to i64
%141 = llvm.getelementptr %arg2[%140] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %138, %141 : i64, !llvm.ptr
%142 = llvm.load %11 : !llvm.ptr -> i64
%143 = arith.constant 2 : i32
%144 = arith.extsi %143 : i32 to i64
%145 = llvm.getelementptr %arg2[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %142, %145 : i64, !llvm.ptr
%146 = llvm.load %15 : !llvm.ptr -> i64
%147 = arith.constant 3 : i32
%148 = arith.extsi %147 : i32 to i64
%149 = llvm.getelementptr %arg2[%148] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %146, %149 : i64, !llvm.ptr
func.return
}
func.func @vk(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr) -> () {
%150 = arith.constant 1 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.cmpi eq, %arg0, %152 : i64
cf.cond_br %151, ^bb6, ^bb7
^bb6:
%153 = arith.constant 1 : i32
%154 = arith.constant 0 : i32
%155 = arith.extsi %153 : i32 to i64
%156 = arith.extsi %154 : i32 to i64
%157 = llvm.getelementptr %arg2[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %155, %157 : i64, !llvm.ptr
%158 = arith.constant 3 : i32
%159 = arith.constant 1 : i32
%160 = arith.extsi %158 : i32 to i64
%161 = arith.extsi %159 : i32 to i64
%162 = llvm.getelementptr %arg2[%161] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %160, %162 : i64, !llvm.ptr
func.return
^bb7:
cf.br ^bb8
^bb8:
%163 = arith.constant 1 : i32
%164 = arith.extsi %163 : i32 to i64
%165 = llvm.mlir.constant(1 : i64) : i64
%166 = llvm.alloca %165 x i64 : (i64) -> !llvm.ptr
llvm.store %164, %166 : i64, !llvm.ptr
%167 = arith.constant 3 : i32
%168 = arith.extsi %167 : i32 to i64
%169 = llvm.mlir.constant(1 : i64) : i64
%170 = llvm.alloca %169 x i64 : (i64) -> !llvm.ptr
llvm.store %168, %170 : i64, !llvm.ptr
%171 = arith.constant 0 : i32
%172 = llvm.mlir.constant(1 : i64) : i64
%173 = llvm.alloca %172 x i32 : (i64) -> !llvm.ptr
llvm.store %171, %173 : i32, !llvm.ptr
%174 = llvm.mlir.constant(1 : i64) : i64
%175 = llvm.alloca %174 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %175 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%176 = llvm.load %175 : !llvm.ptr -> i64
%177 = arith.constant 0 : i32
%179 = arith.extsi %177 : i32 to i64
%178 = arith.cmpi sgt, %176, %179 : i64
cf.cond_br %178, ^bb10, ^bb11
^bb10:
%180 = llvm.load %173 : !llvm.ptr -> i32
%181 = arith.constant 1 : i32
%182 = arith.addi %180, %181 : i32
llvm.store %182, %173 : i32, !llvm.ptr
%183 = llvm.load %175 : !llvm.ptr -> i64
%184 = arith.constant 2 : i32
%186 = arith.extsi %184 : i32 to i64
%185 = arith.divsi %183, %186 : i64
llvm.store %185, %175 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%187 = llvm.load %173 : !llvm.ptr -> i32
%188 = arith.constant 2 : i32
%189 = arith.subi %187, %188 : i32
%190 = llvm.mlir.constant(1 : i64) : i64
%191 = llvm.alloca %190 x i32 : (i64) -> !llvm.ptr
llvm.store %189, %191 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%192 = llvm.load %191 : !llvm.ptr -> i32
%193 = arith.constant 0 : i32
%194 = arith.cmpi sge, %192, %193 : i32
cf.cond_br %194, ^bb13, ^bb14
^bb13:
%195 = llvm.load %191 : !llvm.ptr -> i32
%197 = arith.extsi %195 : i32 to i64
%196 = arith.shrsi %arg0, %197 : i64
%198 = arith.constant 1 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.andi %196, %200 : i64
%201 = arith.constant 0 : i32
%203 = arith.extsi %201 : i32 to i64
%202 = arith.cmpi eq, %199, %203 : i64
cf.cond_br %202, ^bb15, ^bb16
^bb15:
%204 = llvm.load %166 : !llvm.ptr -> i64
%206 = arith.constant 0 : i64
%205 = arith.subi %206, %204 : i64
%207 = arith.constant 2 : i32
%208 = llvm.load %170 : !llvm.ptr -> i64
%210 = arith.extsi %207 : i32 to i64
%209 = arith.muli %210, %208 : i64
%211 = arith.addi %205, %209 : i64
%212 = arith.remsi %211, %arg1 : i64
%213 = arith.addi %212, %arg1 : i64
%214 = arith.remsi %213, %arg1 : i64
llvm.store %214, %170 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
%215 = llvm.load %170 : !llvm.ptr -> i64
%216 = arith.constant 2 : i32
%218 = arith.constant 0 : i32
%217 = arith.subi %218, %216 : i32
%219 = llvm.load %166 : !llvm.ptr -> i64
%221 = arith.extsi %217 : i32 to i64
%220 = arith.muli %221, %219 : i64
%222 = arith.constant 3 : i32
%223 = llvm.load %170 : !llvm.ptr -> i64
%225 = arith.extsi %222 : i32 to i64
%224 = arith.muli %225, %223 : i64
%226 = arith.addi %220, %224 : i64
%227 = arith.remsi %226, %arg1 : i64
%228 = arith.addi %227, %arg1 : i64
%229 = arith.remsi %228, %arg1 : i64
llvm.store %229, %170 : i64, !llvm.ptr
llvm.store %215, %166 : i64, !llvm.ptr
cf.br ^bb17
^bb17:
%230 = llvm.load %191 : !llvm.ptr -> i32
%231 = arith.constant 1 : i32
%232 = arith.subi %230, %231 : i32
llvm.store %232, %191 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%233 = llvm.load %166 : !llvm.ptr -> i64
%234 = arith.remsi %233, %arg1 : i64
%235 = arith.constant 0 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.getelementptr %arg2[%236] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %234, %237 : i64, !llvm.ptr
%238 = llvm.load %170 : !llvm.ptr -> i64
%239 = arith.remsi %238, %arg1 : i64
%240 = arith.constant 1 : i32
%241 = arith.extsi %240 : i32 to i64
%242 = llvm.getelementptr %arg2[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %239, %242 : i64, !llvm.ptr
func.return
}
func.func @main() -> i32 {
%243 = arith.constant 1000000000 : i32
%244 = arith.extsi %243 : i32 to i64
%246 = arith.constant 4 : i32
%247 = arith.constant 8 : i32
%248 = arith.extsi %246 : i32 to i64
%249 = arith.extsi %247 : i32 to i64
%245 = func.call @calloc(%248, %249) : (i64, i64) -> !llvm.ptr
%251 = arith.constant 4 : i32
%252 = arith.constant 8 : 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.zero : !llvm.ptr
%256 = llvm.icmp "eq" %245, %255 : !llvm.ptr
%257 = scf.if %256 -> (i1) {
%258 = arith.constant true
scf.yield %258 : i1
} else {
%259 = llvm.mlir.zero : !llvm.ptr
%260 = llvm.icmp "eq" %250, %259 : !llvm.ptr
scf.yield %260 : i1
}
cf.cond_br %257, ^bb18, ^bb19
^bb18:
%261 = arith.constant 1 : i32
func.return %261 : i32
^bb19:
cf.br ^bb20
^bb20:
%262 = arith.constant 1 : i32
%263 = arith.extsi %262 : i32 to i64
%264 = llvm.mlir.constant(1 : i64) : i64
%265 = llvm.alloca %264 x i64 : (i64) -> !llvm.ptr
llvm.store %263, %265 : i64, !llvm.ptr
%266 = arith.constant 0 : i32
%267 = llvm.mlir.constant(1 : i64) : i64
%268 = llvm.alloca %267 x i32 : (i64) -> !llvm.ptr
llvm.store %266, %268 : i32, !llvm.ptr
cf.br ^bb21
^bb21:
%269 = llvm.load %268 : !llvm.ptr -> i32
%270 = arith.constant 37 : i32
%271 = arith.cmpi slt, %269, %270 : i32
cf.cond_br %271, ^bb22, ^bb23
^bb22:
%272 = llvm.load %265 : !llvm.ptr -> i64
%273 = arith.constant 3 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.muli %272, %275 : i64
llvm.store %274, %265 : i64, !llvm.ptr
%276 = llvm.load %268 : !llvm.ptr -> i32
%277 = arith.constant 1 : i32
%278 = arith.addi %276, %277 : i32
llvm.store %278, %268 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%279 = arith.constant 0 : i32
%280 = arith.extsi %279 : i32 to i64
%281 = llvm.mlir.constant(1 : i64) : i64
%282 = llvm.alloca %281 x i64 : (i64) -> !llvm.ptr
llvm.store %280, %282 : i64, !llvm.ptr
%283 = arith.constant 1 : i32
%284 = arith.extsi %283 : i32 to i64
%285 = llvm.mlir.constant(1 : i64) : i64
%286 = llvm.alloca %285 x i64 : (i64) -> !llvm.ptr
llvm.store %284, %286 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%287 = llvm.load %286 : !llvm.ptr -> i64
%288 = llvm.load %265 : !llvm.ptr -> i64
%289 = arith.cmpi sle, %287, %288 : i64
cf.cond_br %289, ^bb25, ^bb26
^bb25:
%290 = llvm.load %265 : !llvm.ptr -> i64
%291 = llvm.load %286 : !llvm.ptr -> i64
%292 = arith.subi %290, %291 : i64
%293 = arith.constant 1 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.addi %292, %295 : i64
%296 = arith.constant 0 : i32
%297 = llvm.mlir.constant(1 : i64) : i64
%298 = llvm.alloca %297 x i32 : (i64) -> !llvm.ptr
llvm.store %296, %298 : i32, !llvm.ptr
%299 = llvm.load %286 : !llvm.ptr -> i64
%300 = llvm.mlir.constant(1 : i64) : i64
%301 = llvm.alloca %300 x i64 : (i64) -> !llvm.ptr
llvm.store %299, %301 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%302 = llvm.load %301 : !llvm.ptr -> i64
%303 = arith.constant 2 : i32
%305 = arith.extsi %303 : i32 to i64
%304 = arith.remsi %302, %305 : i64
%306 = arith.constant 0 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.cmpi eq, %304, %308 : i64
cf.cond_br %307, ^bb28, ^bb29
^bb28:
%309 = llvm.load %298 : !llvm.ptr -> i32
%310 = arith.constant 1 : i32
%311 = arith.addi %309, %310 : i32
llvm.store %311, %298 : i32, !llvm.ptr
%312 = llvm.load %301 : !llvm.ptr -> i64
%313 = arith.constant 2 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.divsi %312, %315 : i64
llvm.store %314, %301 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%316 = arith.constant 0 : i32
%317 = llvm.mlir.constant(1 : i64) : i64
%318 = llvm.alloca %317 x i32 : (i64) -> !llvm.ptr
llvm.store %316, %318 : i32, !llvm.ptr
%319 = llvm.mlir.constant(1 : i64) : i64
%320 = llvm.alloca %319 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %320 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%321 = llvm.load %320 : !llvm.ptr -> i64
%322 = arith.constant 0 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.cmpi sgt, %321, %324 : i64
cf.cond_br %323, ^bb31, ^bb32
^bb31:
%325 = llvm.load %318 : !llvm.ptr -> i32
%326 = arith.constant 1 : i32
%327 = arith.addi %325, %326 : i32
llvm.store %327, %318 : i32, !llvm.ptr
%328 = llvm.load %320 : !llvm.ptr -> i64
%329 = arith.constant 2 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.divsi %328, %331 : i64
llvm.store %330, %320 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%332 = llvm.load %298 : !llvm.ptr -> i32
%333 = llvm.mlir.constant(1 : i64) : i64
%334 = llvm.alloca %333 x i32 : (i64) -> !llvm.ptr
llvm.store %332, %334 : i32, !llvm.ptr
%335 = llvm.load %318 : !llvm.ptr -> i32
%336 = arith.constant 1 : i32
%337 = arith.subi %335, %336 : i32
%338 = llvm.load %334 : !llvm.ptr -> i32
%339 = arith.cmpi slt, %337, %338 : i32
cf.cond_br %339, ^bb33, ^bb34
^bb33:
%340 = llvm.load %318 : !llvm.ptr -> i32
%341 = arith.constant 1 : i32
%342 = arith.subi %340, %341 : i32
llvm.store %342, %334 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%343 = arith.constant 1 : i32
%344 = arith.extsi %343 : i32 to i64
%345 = llvm.load %334 : !llvm.ptr -> i32
%347 = arith.extsi %345 : i32 to i64
%346 = arith.shli %344, %347 : i64
%348 = llvm.load %286 : !llvm.ptr -> i64
%349 = arith.divsi %348, %346 : i64
func.call @vk(%349, %244, %245) : (i64, i64, !llvm.ptr) -> ()
%352 = llvm.load %334 : !llvm.ptr -> i32
%353 = arith.extsi %352 : i32 to i64
func.call @mat_pow(%353, %244, %250) : (i64, i64, !llvm.ptr) -> ()
%355 = arith.constant 0 : i32
%356 = arith.extsi %355 : i32 to i64
%357 = llvm.getelementptr %250[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%354 = llvm.load %357 : !llvm.ptr -> i64
%359 = arith.constant 0 : i32
%360 = arith.extsi %359 : i32 to i64
%361 = llvm.getelementptr %245[%360] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%358 = llvm.load %361 : !llvm.ptr -> i64
%362 = arith.muli %354, %358 : i64
%364 = arith.constant 1 : i32
%365 = arith.extsi %364 : i32 to i64
%366 = llvm.getelementptr %250[%365] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%363 = llvm.load %366 : !llvm.ptr -> i64
%368 = arith.constant 1 : i32
%369 = arith.extsi %368 : i32 to i64
%370 = llvm.getelementptr %245[%369] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%367 = llvm.load %370 : !llvm.ptr -> i64
%371 = arith.muli %363, %367 : i64
%372 = arith.addi %362, %371 : i64
%373 = arith.remsi %372, %244 : i64
%374 = arith.addi %373, %244 : i64
%375 = arith.remsi %374, %244 : i64
%376 = llvm.load %282 : !llvm.ptr -> i64
%377 = arith.addi %376, %375 : i64
%378 = arith.remsi %377, %244 : i64
llvm.store %378, %282 : i64, !llvm.ptr
%379 = llvm.load %286 : !llvm.ptr -> i64
%380 = arith.addi %379, %346 : i64
llvm.store %380, %286 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%381 = llvm.mlir.addressof @str_0 : !llvm.ptr
%382 = llvm.load %282 : !llvm.ptr -> i64
%383 = llvm.call @printf(%381, %382) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%250) : (!llvm.ptr) -> ()
func.call @free(%245) : (!llvm.ptr) -> ()
%386 = arith.constant 0 : i32
func.return %386 : i32
}
}