Problem 778
Freshman Product: F(234567,765432) mod 10^9+9.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^3) | O(n log n) |
|---|
| Space complexity | O(1) | O(n) |
|---|
| Approach | Flow solution | Modular DP or matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 778
# Freshman Product: F(234567,765432) mod 10^9+9.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(p: ptr<void>, v: i32, n: i64) -> ptr<void>
}
const MOD: i64 = 1000000009
function mat_mul(C: ptr<i64>, A: ptr<i64>, B: ptr<i64>) -> void {
let T: ptr<i64> = calloc(100, 8)
memset(T, 0, 800)
let mut i: i32 = 0
while i < 10 {
let mut k: i32 = 0
while k < 10 {
if A[i * 10 + k] != 0 {
let mut j: i32 = 0
while j < 10 {
T[i * 10 + j] = (T[i * 10 + j] + A[i * 10 + k] * B[k * 10 + j]) % MOD
j = j + 1
}
}
k = k + 1
}
i = i + 1
}
let mut idx: i32 = 0
while idx < 100 {
C[idx] = T[idx]
idx = idx + 1
}
free(T)
}
function mat_pow(R: ptr<i64>, A0: ptr<i64>, exp: i64) -> void {
let A: ptr<i64> = calloc(100, 8)
let mut idx: i32 = 0
while idx < 100 {
A[idx] = A0[idx]
idx = idx + 1
}
memset(R, 0, 800)
let mut i: i32 = 0
while i < 10 {
R[i * 10 + i] = 1
i = i + 1
}
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 {
mat_mul(R, R, A)
}
mat_mul(A, A, A)
e = e / 2
}
free(A)
}
function digit_counts(n: i64, pos: i32, counts: ptr<i64>) -> void {
let mut base: i64 = 1
let mut i: i32 = 0
while i < pos {
base = base * 10
i = i + 1
}
let higher: i64 = n / (base * 10)
let cur: i64 = (n / base) % 10
let lower: i64 = n % base
let mut d: i32 = 0
while d < 10 {
counts[d] = higher * base
d = d + 1
}
d = 0
while d < cur {
counts[d] = counts[d] + base
d = d + 1
}
counts[cur] = counts[cur] + lower + 1
}
function main() -> i32 {
let R: i64 = 234567
let M: i64 = 765432
let mut max_digits: i32 = 0
let mut t: i64 = M
while t > 0 {
max_digits = max_digits + 1
t = t / 10
}
let mut ans: i64 = 0
let mut pow10: i64 = 1
let counts: ptr<i64> = calloc(10, 8)
let A: ptr<i64> = calloc(100, 8)
let P: ptr<i64> = calloc(100, 8)
let mut pos: i32 = 0
while pos < max_digits {
digit_counts(M, pos, counts)
memset(A, 0, 800)
let mut s: i32 = 0
while s < 10 {
let mut d: i32 = 0
while d < 10 {
let tt: i32 = (s * d) % 10
A[s * 10 + tt] = (A[s * 10 + tt] + counts[d]) % MOD
d = d + 1
}
s = s + 1
}
mat_pow(P, A, R)
let mut digit_sum: i64 = 0
let mut digit: i32 = 0
while digit < 10 {
digit_sum = (digit_sum + (digit as i64) * P[10 + digit]) % MOD
digit = digit + 1
}
ans = (ans + digit_sum * pow10) % MOD
pow10 = pow10 * 10 % MOD
pos = pos + 1
}
printf("%lld\n", ans)
free(counts)
free(A)
free(P)
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_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* C, int64_t* A, int64_t* B);
void mat_pow_ptr_i64_ptr_i64_i64(int64_t* R, int64_t* A0, int64_t exp);
void digit_counts_i64_i32_ptr_i64(int64_t n, int32_t pos, int64_t* counts);
int32_t main(void);
static const int64_t MOD = 1000000009;
void mat_mul_ptr_i64_ptr_i64_ptr_i64(int64_t* C, int64_t* A, int64_t* B) {
int64_t* T = (int64_t*)(calloc(100, 8));
memset(T, 0, 800);
int32_t i = 0;
while (i < 10) {
int32_t k = 0;
while (k < 10) {
if (A[((i * 10) + k)] != 0) {
int32_t j = 0;
while (j < 10) {
T[((i * 10) + j)] = FLOW_CHECKED_MOD(((T[((i * 10) + j)] + (A[((i * 10) + k)] * B[((k * 10) + j)]))), (MOD));
j = (j + 1);
}
}
k = (k + 1);
}
i = (i + 1);
}
int32_t idx = 0;
while (idx < 100) {
C[idx] = T[idx];
idx = (idx + 1);
}
free(T);
}
void mat_pow_ptr_i64_ptr_i64_i64(int64_t* R, int64_t* A0, int64_t exp) {
int64_t* A = (int64_t*)(calloc(100, 8));
int32_t idx = 0;
while (idx < 100) {
A[idx] = A0[idx];
idx = (idx + 1);
}
memset(R, 0, 800);
int32_t i = 0;
while (i < 10) {
R[((i * 10) + i)] = 1;
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(R, R, A);
}
mat_mul_ptr_i64_ptr_i64_ptr_i64(A, A, A);
e = FLOW_CHECKED_DIV((e), (2));
}
free(A);
}
void digit_counts_i64_i32_ptr_i64(int64_t n, int32_t pos, int64_t* counts) {
int64_t base = 1;
int32_t i = 0;
while (i < pos) {
base = (base * 10);
i = (i + 1);
}
int64_t higher = FLOW_CHECKED_DIV((n), ((base * 10)));
int64_t cur = FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((n), (base))), (10));
int64_t lower = FLOW_CHECKED_MOD((n), (base));
int32_t d = 0;
while (d < 10) {
counts[d] = (higher * base);
d = (d + 1);
}
d = 0;
while (d < cur) {
counts[d] = (counts[d] + base);
d = (d + 1);
}
counts[cur] = ((counts[cur] + lower) + 1);
}
int32_t main(void) {
int64_t R = 234567;
int64_t M = 765432;
int32_t max_digits = 0;
int64_t t = M;
while (t > 0) {
max_digits = (max_digits + 1);
t = FLOW_CHECKED_DIV((t), (10));
}
int64_t ans = 0;
int64_t pow10 = 1;
int64_t* counts = (int64_t*)(calloc(10, 8));
int64_t* A = (int64_t*)(calloc(100, 8));
int64_t* P = (int64_t*)(calloc(100, 8));
int32_t pos = 0;
while (pos < max_digits) {
digit_counts_i64_i32_ptr_i64(M, pos, counts);
memset(A, 0, 800);
int32_t s = 0;
while (s < 10) {
int32_t d = 0;
while (d < 10) {
int32_t tt = FLOW_CHECKED_MOD(((s * d)), (10));
A[((s * 10) + tt)] = FLOW_CHECKED_MOD(((A[((s * 10) + tt)] + counts[d])), (MOD));
d = (d + 1);
}
s = (s + 1);
}
mat_pow_ptr_i64_ptr_i64_i64(P, A, R);
int64_t digit_sum = 0;
int32_t digit = 0;
while (digit < 10) {
digit_sum = FLOW_CHECKED_MOD(((digit_sum + (((int64_t)(digit)) * P[(10 + digit)]))), (MOD));
digit = (digit + 1);
}
ans = FLOW_CHECKED_MOD(((ans + (digit_sum * pow10))), (MOD));
pow10 = FLOW_CHECKED_MOD(((pow10 * 10)), (MOD));
pos = (pos + 1);
}
printf("%lld\n", ans);
free(counts);
free(A);
free(P);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @memset(!llvm.ptr, i32, i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000009 : i64) : i64
func.func @mat_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%1 = arith.constant 100 : i32
%2 = arith.constant 8 : i32
%3 = arith.extsi %1 : i32 to i64
%4 = arith.extsi %2 : i32 to i64
%0 = func.call @calloc(%3, %4) : (i64, i64) -> !llvm.ptr
%6 = arith.constant 0 : i32
%7 = arith.constant 800 : i32
%8 = arith.extsi %7 : i32 to i64
%5 = func.call @memset(%0, %6, %8) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%9 = arith.constant 0 : i32
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i32 : (i64) -> !llvm.ptr
llvm.store %9, %11 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%12 = llvm.load %11 : !llvm.ptr -> i32
%13 = arith.constant 10 : i32
%14 = arith.cmpi slt, %12, %13 : i32
cf.cond_br %14, ^bb1, ^bb2
^bb1:
%15 = arith.constant 0 : i32
%16 = llvm.mlir.constant(1 : i64) : i64
%17 = llvm.alloca %16 x i32 : (i64) -> !llvm.ptr
llvm.store %15, %17 : i32, !llvm.ptr
cf.br ^bb3
^bb3:
%18 = llvm.load %17 : !llvm.ptr -> i32
%19 = arith.constant 10 : i32
%20 = arith.cmpi slt, %18, %19 : i32
cf.cond_br %20, ^bb4, ^bb5
^bb4:
%22 = llvm.load %11 : !llvm.ptr -> i32
%23 = arith.constant 10 : i32
%24 = arith.muli %22, %23 : i32
%25 = llvm.load %17 : !llvm.ptr -> i32
%26 = arith.addi %24, %25 : i32
%27 = arith.extsi %26 : i32 to i64
%28 = llvm.getelementptr %arg1[%27] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%21 = llvm.load %28 : !llvm.ptr -> i64
%29 = arith.constant 0 : i32
%31 = arith.extsi %29 : i32 to i64
%30 = arith.cmpi ne, %21, %31 : i64
cf.cond_br %30, ^bb6, ^bb7
^bb6:
%32 = arith.constant 0 : i32
%33 = llvm.mlir.constant(1 : i64) : i64
%34 = llvm.alloca %33 x i32 : (i64) -> !llvm.ptr
llvm.store %32, %34 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%35 = llvm.load %34 : !llvm.ptr -> i32
%36 = arith.constant 10 : i32
%37 = arith.cmpi slt, %35, %36 : i32
cf.cond_br %37, ^bb10, ^bb11
^bb10:
%39 = llvm.load %11 : !llvm.ptr -> i32
%40 = arith.constant 10 : i32
%41 = arith.muli %39, %40 : i32
%42 = llvm.load %34 : !llvm.ptr -> i32
%43 = arith.addi %41, %42 : i32
%44 = arith.extsi %43 : i32 to i64
%45 = llvm.getelementptr %0[%44] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%38 = llvm.load %45 : !llvm.ptr -> i64
%47 = llvm.load %11 : !llvm.ptr -> i32
%48 = arith.constant 10 : i32
%49 = arith.muli %47, %48 : i32
%50 = llvm.load %17 : !llvm.ptr -> i32
%51 = arith.addi %49, %50 : i32
%52 = arith.extsi %51 : i32 to i64
%53 = llvm.getelementptr %arg1[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%46 = llvm.load %53 : !llvm.ptr -> i64
%55 = llvm.load %17 : !llvm.ptr -> i32
%56 = arith.constant 10 : i32
%57 = arith.muli %55, %56 : i32
%58 = llvm.load %34 : !llvm.ptr -> i32
%59 = arith.addi %57, %58 : i32
%60 = arith.extsi %59 : i32 to i64
%61 = llvm.getelementptr %arg2[%60] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%54 = llvm.load %61 : !llvm.ptr -> i64
%62 = arith.muli %46, %54 : i64
%63 = arith.addi %38, %62 : i64
%64 = llvm.mlir.addressof @MOD : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.remsi %63, %65 : i64
%67 = llvm.load %11 : !llvm.ptr -> i32
%68 = arith.constant 10 : i32
%69 = arith.muli %67, %68 : i32
%70 = llvm.load %34 : !llvm.ptr -> i32
%71 = arith.addi %69, %70 : i32
%72 = arith.extsi %71 : i32 to i64
%73 = llvm.getelementptr %0[%72] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %66, %73 : i64, !llvm.ptr
%74 = llvm.load %34 : !llvm.ptr -> i32
%75 = arith.constant 1 : i32
%76 = arith.addi %74, %75 : i32
llvm.store %76, %34 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%77 = llvm.load %17 : !llvm.ptr -> i32
%78 = arith.constant 1 : i32
%79 = arith.addi %77, %78 : i32
llvm.store %79, %17 : i32, !llvm.ptr
cf.br ^bb3
^bb5:
%80 = llvm.load %11 : !llvm.ptr -> i32
%81 = arith.constant 1 : i32
%82 = arith.addi %80, %81 : i32
llvm.store %82, %11 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
%83 = arith.constant 0 : i32
%84 = llvm.mlir.constant(1 : i64) : i64
%85 = llvm.alloca %84 x i32 : (i64) -> !llvm.ptr
llvm.store %83, %85 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%86 = llvm.load %85 : !llvm.ptr -> i32
%87 = arith.constant 100 : i32
%88 = arith.cmpi slt, %86, %87 : i32
cf.cond_br %88, ^bb13, ^bb14
^bb13:
%90 = llvm.load %85 : !llvm.ptr -> i32
%91 = arith.extsi %90 : i32 to i64
%92 = llvm.getelementptr %0[%91] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%89 = llvm.load %92 : !llvm.ptr -> i64
%93 = llvm.load %85 : !llvm.ptr -> i32
%94 = arith.extsi %93 : i32 to i64
%95 = llvm.getelementptr %arg0[%94] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %89, %95 : i64, !llvm.ptr
%96 = llvm.load %85 : !llvm.ptr -> i32
%97 = arith.constant 1 : i32
%98 = arith.addi %96, %97 : i32
llvm.store %98, %85 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
func.call @free(%0) : (!llvm.ptr) -> ()
func.return
}
func.func @mat_pow(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i64) -> () {
%101 = arith.constant 100 : i32
%102 = arith.constant 8 : i32
%103 = arith.extsi %101 : i32 to i64
%104 = arith.extsi %102 : i32 to i64
%100 = func.call @calloc(%103, %104) : (i64, i64) -> !llvm.ptr
%105 = arith.constant 0 : i32
%106 = llvm.mlir.constant(1 : i64) : i64
%107 = llvm.alloca %106 x i32 : (i64) -> !llvm.ptr
llvm.store %105, %107 : i32, !llvm.ptr
cf.br ^bb15
^bb15:
%108 = llvm.load %107 : !llvm.ptr -> i32
%109 = arith.constant 100 : i32
%110 = arith.cmpi slt, %108, %109 : i32
cf.cond_br %110, ^bb16, ^bb17
^bb16:
%112 = llvm.load %107 : !llvm.ptr -> i32
%113 = arith.extsi %112 : i32 to i64
%114 = llvm.getelementptr %arg1[%113] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%111 = llvm.load %114 : !llvm.ptr -> i64
%115 = llvm.load %107 : !llvm.ptr -> i32
%116 = arith.extsi %115 : i32 to i64
%117 = llvm.getelementptr %100[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %111, %117 : i64, !llvm.ptr
%118 = llvm.load %107 : !llvm.ptr -> i32
%119 = arith.constant 1 : i32
%120 = arith.addi %118, %119 : i32
llvm.store %120, %107 : i32, !llvm.ptr
cf.br ^bb15
^bb17:
%122 = arith.constant 0 : i32
%123 = arith.constant 800 : i32
%124 = arith.extsi %123 : i32 to i64
%121 = func.call @memset(%arg0, %122, %124) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%125 = arith.constant 0 : i32
%126 = llvm.mlir.constant(1 : i64) : i64
%127 = llvm.alloca %126 x i32 : (i64) -> !llvm.ptr
llvm.store %125, %127 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%128 = llvm.load %127 : !llvm.ptr -> i32
%129 = arith.constant 10 : i32
%130 = arith.cmpi slt, %128, %129 : i32
cf.cond_br %130, ^bb19, ^bb20
^bb19:
%131 = arith.constant 1 : i32
%132 = llvm.load %127 : !llvm.ptr -> i32
%133 = arith.constant 10 : i32
%134 = arith.muli %132, %133 : i32
%135 = llvm.load %127 : !llvm.ptr -> i32
%136 = arith.addi %134, %135 : i32
%137 = arith.extsi %131 : i32 to i64
%138 = arith.extsi %136 : i32 to i64
%139 = llvm.getelementptr %arg0[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %137, %139 : i64, !llvm.ptr
%140 = llvm.load %127 : !llvm.ptr -> i32
%141 = arith.constant 1 : i32
%142 = arith.addi %140, %141 : i32
llvm.store %142, %127 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%143 = llvm.mlir.constant(1 : i64) : i64
%144 = llvm.alloca %143 x i64 : (i64) -> !llvm.ptr
llvm.store %arg2, %144 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%145 = llvm.load %144 : !llvm.ptr -> i64
%146 = arith.constant 0 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.cmpi sgt, %145, %148 : i64
cf.cond_br %147, ^bb22, ^bb23
^bb22:
%149 = llvm.load %144 : !llvm.ptr -> i64
%150 = arith.constant 2 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.remsi %149, %152 : i64
%153 = arith.constant 1 : i32
%155 = arith.extsi %153 : i32 to i64
%154 = arith.cmpi eq, %151, %155 : i64
cf.cond_br %154, ^bb24, ^bb25
^bb24:
func.call @mat_mul(%arg0, %arg0, %100) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
func.call @mat_mul(%100, %100, %100) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%158 = llvm.load %144 : !llvm.ptr -> i64
%159 = arith.constant 2 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.divsi %158, %161 : i64
llvm.store %160, %144 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
func.call @free(%100) : (!llvm.ptr) -> ()
func.return
}
func.func @digit_counts(%arg0: i64, %arg1: i32, %arg2: !llvm.ptr) -> () {
%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 0 : i32
%168 = llvm.mlir.constant(1 : i64) : i64
%169 = llvm.alloca %168 x i32 : (i64) -> !llvm.ptr
llvm.store %167, %169 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%170 = llvm.load %169 : !llvm.ptr -> i32
%171 = arith.cmpi slt, %170, %arg1 : i32
cf.cond_br %171, ^bb28, ^bb29
^bb28:
%172 = llvm.load %166 : !llvm.ptr -> i64
%173 = arith.constant 10 : i32
%175 = arith.extsi %173 : i32 to i64
%174 = arith.muli %172, %175 : i64
llvm.store %174, %166 : i64, !llvm.ptr
%176 = llvm.load %169 : !llvm.ptr -> i32
%177 = arith.constant 1 : i32
%178 = arith.addi %176, %177 : i32
llvm.store %178, %169 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%179 = llvm.load %166 : !llvm.ptr -> i64
%180 = arith.constant 10 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.muli %179, %182 : i64
%183 = arith.divsi %arg0, %181 : i64
%184 = llvm.load %166 : !llvm.ptr -> i64
%185 = arith.divsi %arg0, %184 : i64
%186 = arith.constant 10 : i32
%188 = arith.extsi %186 : i32 to i64
%187 = arith.remsi %185, %188 : i64
%189 = llvm.load %166 : !llvm.ptr -> i64
%190 = arith.remsi %arg0, %189 : i64
%191 = arith.constant 0 : i32
%192 = llvm.mlir.constant(1 : i64) : i64
%193 = llvm.alloca %192 x i32 : (i64) -> !llvm.ptr
llvm.store %191, %193 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%194 = llvm.load %193 : !llvm.ptr -> i32
%195 = arith.constant 10 : i32
%196 = arith.cmpi slt, %194, %195 : i32
cf.cond_br %196, ^bb31, ^bb32
^bb31:
%197 = llvm.load %166 : !llvm.ptr -> i64
%198 = arith.muli %183, %197 : i64
%199 = llvm.load %193 : !llvm.ptr -> i32
%200 = arith.extsi %199 : i32 to i64
%201 = llvm.getelementptr %arg2[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %198, %201 : i64, !llvm.ptr
%202 = llvm.load %193 : !llvm.ptr -> i32
%203 = arith.constant 1 : i32
%204 = arith.addi %202, %203 : i32
llvm.store %204, %193 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
%205 = arith.constant 0 : i32
llvm.store %205, %193 : i32, !llvm.ptr
cf.br ^bb33
^bb33:
%206 = llvm.load %193 : !llvm.ptr -> i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.cmpi slt, %208, %187 : i64
cf.cond_br %207, ^bb34, ^bb35
^bb34:
%210 = llvm.load %193 : !llvm.ptr -> i32
%211 = arith.extsi %210 : i32 to i64
%212 = llvm.getelementptr %arg2[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%209 = llvm.load %212 : !llvm.ptr -> i64
%213 = llvm.load %166 : !llvm.ptr -> i64
%214 = arith.addi %209, %213 : i64
%215 = llvm.load %193 : !llvm.ptr -> i32
%216 = arith.extsi %215 : i32 to i64
%217 = llvm.getelementptr %arg2[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %214, %217 : i64, !llvm.ptr
%218 = llvm.load %193 : !llvm.ptr -> i32
%219 = arith.constant 1 : i32
%220 = arith.addi %218, %219 : i32
llvm.store %220, %193 : i32, !llvm.ptr
cf.br ^bb33
^bb35:
%222 = llvm.getelementptr %arg2[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%221 = llvm.load %222 : !llvm.ptr -> i64
%223 = arith.addi %221, %190 : i64
%224 = arith.constant 1 : i32
%226 = arith.extsi %224 : i32 to i64
%225 = arith.addi %223, %226 : i64
%227 = llvm.getelementptr %arg2[%187] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %225, %227 : i64, !llvm.ptr
func.return
}
func.func @main() -> i32 {
%228 = arith.constant 234567 : i32
%229 = arith.extsi %228 : i32 to i64
%230 = arith.constant 765432 : i32
%231 = arith.extsi %230 : i32 to i64
%232 = arith.constant 0 : i32
%233 = llvm.mlir.constant(1 : i64) : i64
%234 = llvm.alloca %233 x i32 : (i64) -> !llvm.ptr
llvm.store %232, %234 : i32, !llvm.ptr
%235 = llvm.mlir.constant(1 : i64) : i64
%236 = llvm.alloca %235 x i64 : (i64) -> !llvm.ptr
llvm.store %231, %236 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%237 = llvm.load %236 : !llvm.ptr -> i64
%238 = arith.constant 0 : i32
%240 = arith.extsi %238 : i32 to i64
%239 = arith.cmpi sgt, %237, %240 : i64
cf.cond_br %239, ^bb37, ^bb38
^bb37:
%241 = llvm.load %234 : !llvm.ptr -> i32
%242 = arith.constant 1 : i32
%243 = arith.addi %241, %242 : i32
llvm.store %243, %234 : i32, !llvm.ptr
%244 = llvm.load %236 : !llvm.ptr -> i64
%245 = arith.constant 10 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.divsi %244, %247 : i64
llvm.store %246, %236 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%248 = arith.constant 0 : i32
%249 = arith.extsi %248 : i32 to i64
%250 = llvm.mlir.constant(1 : i64) : i64
%251 = llvm.alloca %250 x i64 : (i64) -> !llvm.ptr
llvm.store %249, %251 : i64, !llvm.ptr
%252 = arith.constant 1 : i32
%253 = arith.extsi %252 : i32 to i64
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x i64 : (i64) -> !llvm.ptr
llvm.store %253, %255 : i64, !llvm.ptr
%257 = arith.constant 10 : 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
%262 = arith.constant 100 : i32
%263 = arith.constant 8 : i32
%264 = arith.extsi %262 : i32 to i64
%265 = arith.extsi %263 : i32 to i64
%261 = func.call @calloc(%264, %265) : (i64, i64) -> !llvm.ptr
%267 = arith.constant 100 : i32
%268 = arith.constant 8 : i32
%269 = arith.extsi %267 : i32 to i64
%270 = arith.extsi %268 : i32 to i64
%266 = func.call @calloc(%269, %270) : (i64, i64) -> !llvm.ptr
%271 = arith.constant 0 : i32
%272 = llvm.mlir.constant(1 : i64) : i64
%273 = llvm.alloca %272 x i32 : (i64) -> !llvm.ptr
llvm.store %271, %273 : i32, !llvm.ptr
cf.br ^bb39
^bb39:
%274 = llvm.load %273 : !llvm.ptr -> i32
%275 = llvm.load %234 : !llvm.ptr -> i32
%276 = arith.cmpi slt, %274, %275 : i32
cf.cond_br %276, ^bb40, ^bb41
^bb40:
%278 = llvm.load %273 : !llvm.ptr -> i32
func.call @digit_counts(%231, %278, %256) : (i64, i32, !llvm.ptr) -> ()
%280 = arith.constant 0 : i32
%281 = arith.constant 800 : i32
%282 = arith.extsi %281 : i32 to i64
%279 = func.call @memset(%261, %280, %282) : (!llvm.ptr, i32, i64) -> !llvm.ptr
%283 = arith.constant 0 : i32
%284 = llvm.mlir.constant(1 : i64) : i64
%285 = llvm.alloca %284 x i32 : (i64) -> !llvm.ptr
llvm.store %283, %285 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%286 = llvm.load %285 : !llvm.ptr -> i32
%287 = arith.constant 10 : i32
%288 = arith.cmpi slt, %286, %287 : i32
cf.cond_br %288, ^bb43, ^bb44
^bb43:
%289 = arith.constant 0 : i32
%290 = llvm.mlir.constant(1 : i64) : i64
%291 = llvm.alloca %290 x i32 : (i64) -> !llvm.ptr
llvm.store %289, %291 : i32, !llvm.ptr
cf.br ^bb45
^bb45:
%292 = llvm.load %291 : !llvm.ptr -> i32
%293 = arith.constant 10 : i32
%294 = arith.cmpi slt, %292, %293 : i32
cf.cond_br %294, ^bb46, ^bb47
^bb46:
%295 = llvm.load %285 : !llvm.ptr -> i32
%296 = llvm.load %291 : !llvm.ptr -> i32
%297 = arith.muli %295, %296 : i32
%298 = arith.constant 10 : i32
%299 = arith.remsi %297, %298 : i32
%301 = llvm.load %285 : !llvm.ptr -> i32
%302 = arith.constant 10 : i32
%303 = arith.muli %301, %302 : i32
%304 = arith.addi %303, %299 : i32
%305 = arith.extsi %304 : i32 to i64
%306 = llvm.getelementptr %261[%305] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%300 = llvm.load %306 : !llvm.ptr -> i64
%308 = llvm.load %291 : !llvm.ptr -> i32
%309 = arith.extsi %308 : i32 to i64
%310 = llvm.getelementptr %256[%309] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%307 = llvm.load %310 : !llvm.ptr -> i64
%311 = arith.addi %300, %307 : i64
%312 = llvm.mlir.addressof @MOD : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> i64
%314 = arith.remsi %311, %313 : i64
%315 = llvm.load %285 : !llvm.ptr -> i32
%316 = arith.constant 10 : i32
%317 = arith.muli %315, %316 : i32
%318 = arith.addi %317, %299 : i32
%319 = arith.extsi %318 : i32 to i64
%320 = llvm.getelementptr %261[%319] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %314, %320 : i64, !llvm.ptr
%321 = llvm.load %291 : !llvm.ptr -> i32
%322 = arith.constant 1 : i32
%323 = arith.addi %321, %322 : i32
llvm.store %323, %291 : i32, !llvm.ptr
cf.br ^bb45
^bb47:
%324 = llvm.load %285 : !llvm.ptr -> i32
%325 = arith.constant 1 : i32
%326 = arith.addi %324, %325 : i32
llvm.store %326, %285 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
func.call @mat_pow(%266, %261, %229) : (!llvm.ptr, !llvm.ptr, i64) -> ()
%328 = arith.constant 0 : i32
%329 = arith.extsi %328 : i32 to i64
%330 = llvm.mlir.constant(1 : i64) : i64
%331 = llvm.alloca %330 x i64 : (i64) -> !llvm.ptr
llvm.store %329, %331 : i64, !llvm.ptr
%332 = arith.constant 0 : i32
%333 = llvm.mlir.constant(1 : i64) : i64
%334 = llvm.alloca %333 x i32 : (i64) -> !llvm.ptr
llvm.store %332, %334 : i32, !llvm.ptr
cf.br ^bb48
^bb48:
%335 = llvm.load %334 : !llvm.ptr -> i32
%336 = arith.constant 10 : i32
%337 = arith.cmpi slt, %335, %336 : i32
cf.cond_br %337, ^bb49, ^bb50
^bb49:
%338 = llvm.load %331 : !llvm.ptr -> i64
%339 = llvm.load %334 : !llvm.ptr -> i32
%340 = arith.extsi %339 : i32 to i64
%342 = arith.constant 10 : i32
%343 = llvm.load %334 : !llvm.ptr -> i32
%344 = arith.addi %342, %343 : i32
%345 = arith.extsi %344 : i32 to i64
%346 = llvm.getelementptr %266[%345] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%341 = llvm.load %346 : !llvm.ptr -> i64
%347 = arith.muli %340, %341 : i64
%348 = arith.addi %338, %347 : i64
%349 = llvm.mlir.addressof @MOD : !llvm.ptr
%350 = llvm.load %349 : !llvm.ptr -> i64
%351 = arith.remsi %348, %350 : i64
llvm.store %351, %331 : i64, !llvm.ptr
%352 = llvm.load %334 : !llvm.ptr -> i32
%353 = arith.constant 1 : i32
%354 = arith.addi %352, %353 : i32
llvm.store %354, %334 : i32, !llvm.ptr
cf.br ^bb48
^bb50:
%355 = llvm.load %251 : !llvm.ptr -> i64
%356 = llvm.load %331 : !llvm.ptr -> i64
%357 = llvm.load %255 : !llvm.ptr -> i64
%358 = arith.muli %356, %357 : i64
%359 = arith.addi %355, %358 : i64
%360 = llvm.mlir.addressof @MOD : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> i64
%362 = arith.remsi %359, %361 : i64
llvm.store %362, %251 : i64, !llvm.ptr
%363 = llvm.load %255 : !llvm.ptr -> i64
%364 = arith.constant 10 : i32
%366 = arith.extsi %364 : i32 to i64
%365 = arith.muli %363, %366 : i64
%367 = llvm.mlir.addressof @MOD : !llvm.ptr
%368 = llvm.load %367 : !llvm.ptr -> i64
%369 = arith.remsi %365, %368 : i64
llvm.store %369, %255 : i64, !llvm.ptr
%370 = llvm.load %273 : !llvm.ptr -> i32
%371 = arith.constant 1 : i32
%372 = arith.addi %370, %371 : i32
llvm.store %372, %273 : i32, !llvm.ptr
cf.br ^bb39
^bb41:
%373 = llvm.mlir.addressof @str_0 : !llvm.ptr
%374 = llvm.load %251 : !llvm.ptr -> i64
%375 = llvm.call @printf(%373, %374) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%256) : (!llvm.ptr) -> ()
func.call @free(%261) : (!llvm.ptr) -> ()
func.call @free(%266) : (!llvm.ptr) -> ()
%379 = arith.constant 0 : i32
func.return %379 : i32
}
}