← All problems Problem 831
Triple Product - first 10 base-7 digits of g(142857). Uses bignum arithmetic implemented in pure Flow for polynomial multiplication and exponentiation with large coefficients.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 831
# Triple Product - first 10 base-7 digits of g(142857).
# Uses bignum arithmetic implemented in pure Flow for polynomial
# multiplication and exponentiation with large coefficients.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const CAP: i32 = 25000
const DEG: i32 = 5
const BASE: i64 = 1000000000
# Set coefficient k to small int value
function coeff_set_int(digits: ptr<i32>, lengths: ptr<i32>, k: i32, val: i32) -> void {
if val == 0 {
lengths[k] = 0
return
}
digits[k * CAP] = val
lengths[k] = 1
}
# Copy coefficient sk from src to dk in dst
function coeff_copy(dd: ptr<i32>, dlen: ptr<i32>, dk: i32,
sd: ptr<i32>, slen: ptr<i32>, sk: i32) -> void {
let mut i: i32 = 0
while i < slen[sk] {
dd[dk * CAP + i] = sd[sk * CAP + i]
i = i + 1
}
dlen[dk] = slen[sk]
}
# dst[dk] = a[ak] + b[bk], dst can alias a
function coeff_add(dd: ptr<i32>, dlen: ptr<i32>, dk: i32,
ad: ptr<i32>, alen: ptr<i32>, ak: i32,
bd: ptr<i32>, blen: ptr<i32>, bk: i32) -> void {
let mut n: i32 = alen[ak]
if blen[bk] > n { n = blen[bk] }
let mut carry: i64 = 0
let mut i: i32 = 0
while i < n {
let mut s: i64 = carry
if i < alen[ak] { s = s + (ad[ak * CAP + i] as i64) }
if i < blen[bk] { s = s + (bd[bk * CAP + i] as i64) }
dd[dk * CAP + i] = (s % BASE) as i32
carry = s / BASE
i = i + 1
}
if carry > 0 {
dd[dk * CAP + i] = (carry) as i32
i = i + 1
}
dlen[dk] = i
}
# dst[dk] = a[ak] * b[bk], dst must not alias a or b
function coeff_mul(dd: ptr<i32>, dlen: ptr<i32>, dk: i32,
ad: ptr<i32>, alen: ptr<i32>, ak: i32,
bd: ptr<i32>, blen: ptr<i32>, bk: i32) -> void {
let alen_v: i32 = alen[ak]
let blen_v: i32 = blen[bk]
if alen_v == 0 || blen_v == 0 {
dlen[dk] = 0
return
}
let total: i32 = alen_v + blen_v
let mut i: i32 = 0
while i < total {
dd[dk * CAP + i] = 0
i = i + 1
}
i = 0
while i < alen_v {
let mut carry: i64 = 0
let mut j: i32 = 0
while j < blen_v {
let prod: i64 = (ad[ak * CAP + i] as i64) * (bd[bk * CAP + j] as i64)
+ (dd[dk * CAP + i + j] as i64) + carry
dd[dk * CAP + i + j] = (prod % BASE) as i32
carry = prod / BASE
j = j + 1
}
let mut pos: i32 = i + blen_v
while carry > 0 {
let val: i64 = (dd[dk * CAP + pos] as i64) + carry
dd[dk * CAP + pos] = (val % BASE) as i32
carry = val / BASE
pos = pos + 1
}
i = i + 1
}
dlen[dk] = total
while dlen[dk] > 0 && dd[dk * CAP + dlen[dk] - 1] == 0 {
dlen[dk] = dlen[dk] - 1
}
}
# b[bk] = b[bk] / divisor, return remainder
function coeff_divmod_small(bd: ptr<i32>, blen: ptr<i32>, bk: i32, divisor: i32) -> i32 {
let mut rem: i64 = 0
let mut i: i32 = blen[bk] - 1
while i >= 0 {
let cur: i64 = rem * BASE + (bd[bk * CAP + i] as i64)
bd[bk * CAP + i] = (cur / (divisor as i64)) as i32
rem = cur % (divisor as i64)
i = i - 1
}
while blen[bk] > 0 && bd[bk * CAP + blen[bk] - 1] == 0 {
blen[bk] = blen[bk] - 1
}
return (rem) as i32
}
# Check if coefficient k is nonzero
function coeff_nonzero(bd: ptr<i32>, blen: ptr<i32>, bk: i32) -> bool {
return blen[bk] != 0
}
# Copy entire polynomial (6 coefficients)
function poly_copy(dd: ptr<i32>, dlen: ptr<i32>, sd: ptr<i32>, slen: ptr<i32>) -> void {
let mut k: i32 = 0
while k <= DEG {
coeff_copy(dd, dlen, k, sd, slen, k)
k = k + 1
}
}
# poly_mul: dd = ad * bd (truncated to degree DEG)
# td is a temporary with at least 1 coefficient slot
function poly_mul(dd: ptr<i32>, dlen: ptr<i32>,
ad: ptr<i32>, alen: ptr<i32>,
bd: ptr<i32>, blen: ptr<i32>,
td: ptr<i32>, tlen: ptr<i32>) -> void {
let mut k: i32 = 0
while k <= DEG {
dlen[k] = 0
k = k + 1
}
k = 0
while k <= DEG {
let mut i: i32 = 0
while i <= k {
let j: i32 = k - i
if i <= DEG && j <= DEG {
coeff_mul(td, tlen, 0, ad, alen, i, bd, blen, j)
coeff_add(dd, dlen, k, dd, dlen, k, td, tlen, 0)
}
i = i + 1
}
k = k + 1
}
}
# poly_pow: rd = qd^exp (truncated to degree DEG)
# bd: base buffer, td1: temp output, td2: internal temp
function poly_pow(rd: ptr<i32>, rlen: ptr<i32>, qd: ptr<i32>, qlen: ptr<i32>,
exp0: i32, bd: ptr<i32>, blen: ptr<i32>,
td1: ptr<i32>, tlen1: ptr<i32>,
td2: ptr<i32>, tlen2: ptr<i32>) -> void {
coeff_set_int(rd, rlen, 0, 1)
let mut k: i32 = 1
while k <= DEG {
coeff_set_int(rd, rlen, k, 0)
k = k + 1
}
poly_copy(bd, blen, qd, qlen)
let mut e: i32 = exp0
while e > 0 {
if (e & 1) != 0 {
poly_mul(td1, tlen1, rd, rlen, bd, blen, td2, tlen2)
poly_copy(rd, rlen, td1, tlen1)
}
e = e >> 1
if e > 0 {
poly_mul(td1, tlen1, bd, blen, bd, blen, td2, tlen2)
poly_copy(bd, blen, td1, tlen1)
}
}
}
function main() -> i32 {
let m: i32 = 142857
let six_cap: i64 = (6 * CAP) as i64
let qd: ptr<i32> = calloc(six_cap, 4)
let qlen: ptr<i32> = calloc(6, 4)
let ad: ptr<i32> = calloc(six_cap, 4)
let alen: ptr<i32> = calloc(6, 4)
let qmd: ptr<i32> = calloc(six_cap, 4)
let qmlen: ptr<i32> = calloc(6, 4)
let aqmd: ptr<i32> = calloc(six_cap, 4)
let aqmlen: ptr<i32> = calloc(6, 4)
let bd: ptr<i32> = calloc(six_cap, 4)
let blen: ptr<i32> = calloc(6, 4)
let td1: ptr<i32> = calloc(six_cap, 4)
let tlen1: ptr<i32> = calloc(6, 4)
let td2: ptr<i32> = calloc((CAP) as i64, 4)
let tlen2: ptr<i32> = calloc(1, 4)
if qd == null || qlen == null || ad == null || alen == null
|| qmd == null || qmlen == null || aqmd == null || aqmlen == null
|| bd == null || blen == null || td1 == null || tlen1 == null
|| td2 == null || tlen2 == null { return 1 }
# Q = [1, 3, 5, 5, 3, 1]
coeff_set_int(qd, qlen, 0, 1)
coeff_set_int(qd, qlen, 1, 3)
coeff_set_int(qd, qlen, 2, 5)
coeff_set_int(qd, qlen, 3, 5)
coeff_set_int(qd, qlen, 4, 3)
coeff_set_int(qd, qlen, 5, 1)
# A = [1, 5, 10, 10, 5, 1]
coeff_set_int(ad, alen, 0, 1)
coeff_set_int(ad, alen, 1, 5)
coeff_set_int(ad, alen, 2, 10)
coeff_set_int(ad, alen, 3, 10)
coeff_set_int(ad, alen, 4, 5)
coeff_set_int(ad, alen, 5, 1)
# Qm = Q^m
poly_pow(qmd, qmlen, qd, qlen, m, bd, blen, td1, tlen1, td2, tlen2)
# AQm = A * Qm
poly_mul(aqmd, aqmlen, ad, alen, qmd, qmlen, td2, tlen2)
# Extract AQm[5] and convert to base 7
let cd: ptr<i32> = calloc((CAP) as i64, 4)
let clen: ptr<i32> = calloc(1, 4)
if cd == null || clen == null { return 1 }
coeff_copy(cd, clen, 0, aqmd, aqmlen, 5)
if coeff_nonzero(cd, clen, 0) == false {
printf("0000000000\n")
free(qd); free(qlen); free(ad); free(alen)
free(qmd); free(qmlen); free(aqmd); free(aqmlen)
free(bd); free(blen); free(td1); free(tlen1)
free(td2); free(tlen2); free(cd); free(clen)
return 0
}
# Convert to base 7
let digits7: ptr<i32> = calloc(250000, 4)
if digits7 == null { return 1 }
let mut n7: i32 = 0
while coeff_nonzero(cd, clen, 0) {
digits7[n7] = coeff_divmod_small(cd, clen, 0, 7)
n7 = n7 + 1
}
# Print first 10 digits (most significant first)
let mut o: i32 = 0
let mut i: i32 = n7 - 1
while i >= 0 && o < 10 {
printf("%lld", (digits7[i] as i64))
o = o + 1
i = i - 1
}
while o < 10 {
printf("0")
o = o + 1
}
printf("\n")
free(qd); free(qlen); free(ad); free(alen)
free(qmd); free(qmlen); free(aqmd); free(aqmlen)
free(bd); free(blen); free(td1); free(tlen1)
free(td2); free(tlen2); free(cd); free(clen); free(digits7)
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 coeff_set_int_ptr_i32_ptr_i32_i32_i32(int32_t* digits, int32_t* lengths, int32_t k, int32_t val);
void coeff_copy_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* sd, int32_t* slen, int32_t sk);
void coeff_add_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* ad, int32_t* alen, int32_t ak, int32_t* bd, int32_t* blen, int32_t bk);
void coeff_mul_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* ad, int32_t* alen, int32_t ak, int32_t* bd, int32_t* blen, int32_t bk);
int32_t coeff_divmod_small_ptr_i32_ptr_i32_i32_i32(int32_t* bd, int32_t* blen, int32_t bk, int32_t divisor);
bool coeff_nonzero_ptr_i32_ptr_i32_i32(int32_t* bd, int32_t* blen, int32_t bk);
void poly_copy_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* dd, int32_t* dlen, int32_t* sd, int32_t* slen);
void poly_mul_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* dd, int32_t* dlen, int32_t* ad, int32_t* alen, int32_t* bd, int32_t* blen, int32_t* td, int32_t* tlen);
void poly_pow_ptr_i32_ptr_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* rd, int32_t* rlen, int32_t* qd, int32_t* qlen, int32_t exp0, int32_t* bd, int32_t* blen, int32_t* td1, int32_t* tlen1, int32_t* td2, int32_t* tlen2);
int32_t main(void);
static const int32_t CAP = 25000;
static const int32_t DEG = 5;
static const int64_t BASE = 1000000000;
void coeff_set_int_ptr_i32_ptr_i32_i32_i32(int32_t* digits, int32_t* lengths, int32_t k, int32_t val) {
if (val == 0) {
lengths[k] = 0;
return;
}
digits[(k * CAP)] = val;
lengths[k] = 1;
}
void coeff_copy_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* sd, int32_t* slen, int32_t sk) {
int32_t i = 0;
while (i < slen[sk]) {
dd[((dk * CAP) + i)] = sd[((sk * CAP) + i)];
i = (i + 1);
}
dlen[dk] = slen[sk];
}
void coeff_add_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* ad, int32_t* alen, int32_t ak, int32_t* bd, int32_t* blen, int32_t bk) {
int32_t n = alen[ak];
if (blen[bk] > n) {
n = blen[bk];
}
int64_t carry = 0;
int32_t i = 0;
while (i < n) {
int64_t s = carry;
if (i < alen[ak]) {
s = (s + ((int64_t)(ad[((ak * CAP) + i)])));
}
if (i < blen[bk]) {
s = (s + ((int64_t)(bd[((bk * CAP) + i)])));
}
dd[((dk * CAP) + i)] = ((int32_t)(FLOW_CHECKED_MOD((s), (BASE))));
carry = FLOW_CHECKED_DIV((s), (BASE));
i = (i + 1);
}
if (carry > 0) {
dd[((dk * CAP) + i)] = ((int32_t)(carry));
i = (i + 1);
}
dlen[dk] = i;
}
void coeff_mul_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(int32_t* dd, int32_t* dlen, int32_t dk, int32_t* ad, int32_t* alen, int32_t ak, int32_t* bd, int32_t* blen, int32_t bk) {
int32_t alen_v = alen[ak];
int32_t blen_v = blen[bk];
if ((alen_v == 0 || blen_v == 0)) {
dlen[dk] = 0;
return;
}
int32_t total = (alen_v + blen_v);
int32_t i = 0;
while (i < total) {
dd[((dk * CAP) + i)] = 0;
i = (i + 1);
}
i = 0;
while (i < alen_v) {
int64_t carry = 0;
int32_t j = 0;
while (j < blen_v) {
int64_t prod = (((((int64_t)(ad[((ak * CAP) + i)])) * ((int64_t)(bd[((bk * CAP) + j)]))) + ((int64_t)(dd[(((dk * CAP) + i) + j)]))) + carry);
dd[(((dk * CAP) + i) + j)] = ((int32_t)(FLOW_CHECKED_MOD((prod), (BASE))));
carry = FLOW_CHECKED_DIV((prod), (BASE));
j = (j + 1);
}
int32_t pos = (i + blen_v);
while (carry > 0) {
int64_t val = (((int64_t)(dd[((dk * CAP) + pos)])) + carry);
dd[((dk * CAP) + pos)] = ((int32_t)(FLOW_CHECKED_MOD((val), (BASE))));
carry = FLOW_CHECKED_DIV((val), (BASE));
pos = (pos + 1);
}
i = (i + 1);
}
dlen[dk] = total;
while ((dlen[dk] > 0 && dd[(((dk * CAP) + dlen[dk]) - 1)] == 0)) {
dlen[dk] = (dlen[dk] - 1);
}
}
int32_t coeff_divmod_small_ptr_i32_ptr_i32_i32_i32(int32_t* bd, int32_t* blen, int32_t bk, int32_t divisor) {
int64_t rem = 0;
int32_t i = (blen[bk] - 1);
while (i >= 0) {
int64_t cur = ((rem * BASE) + ((int64_t)(bd[((bk * CAP) + i)])));
bd[((bk * CAP) + i)] = ((int32_t)(FLOW_CHECKED_DIV((cur), (((int64_t)(divisor))))));
rem = FLOW_CHECKED_MOD((cur), (((int64_t)(divisor))));
i = (i - 1);
}
while ((blen[bk] > 0 && bd[(((bk * CAP) + blen[bk]) - 1)] == 0)) {
blen[bk] = (blen[bk] - 1);
}
return ((int32_t)(rem));
}
bool coeff_nonzero_ptr_i32_ptr_i32_i32(int32_t* bd, int32_t* blen, int32_t bk) {
return blen[bk] != 0;
}
void poly_copy_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* dd, int32_t* dlen, int32_t* sd, int32_t* slen) {
int32_t k = 0;
while (k <= DEG) {
coeff_copy_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(dd, dlen, k, sd, slen, k);
k = (k + 1);
}
}
void poly_mul_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* dd, int32_t* dlen, int32_t* ad, int32_t* alen, int32_t* bd, int32_t* blen, int32_t* td, int32_t* tlen) {
int32_t k = 0;
while (k <= DEG) {
dlen[k] = 0;
k = (k + 1);
}
k = 0;
while (k <= DEG) {
int32_t i = 0;
while (i <= k) {
int32_t j = (k - i);
if ((i <= DEG && j <= DEG)) {
coeff_mul_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(td, tlen, 0, ad, alen, i, bd, blen, j);
coeff_add_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(dd, dlen, k, dd, dlen, k, td, tlen, 0);
}
i = (i + 1);
}
k = (k + 1);
}
}
void poly_pow_ptr_i32_ptr_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(int32_t* rd, int32_t* rlen, int32_t* qd, int32_t* qlen, int32_t exp0, int32_t* bd, int32_t* blen, int32_t* td1, int32_t* tlen1, int32_t* td2, int32_t* tlen2) {
coeff_set_int_ptr_i32_ptr_i32_i32_i32(rd, rlen, 0, 1);
int32_t k = 1;
while (k <= DEG) {
coeff_set_int_ptr_i32_ptr_i32_i32_i32(rd, rlen, k, 0);
k = (k + 1);
}
poly_copy_ptr_i32_ptr_i32_ptr_i32_ptr_i32(bd, blen, qd, qlen);
int32_t e = exp0;
while (e > 0) {
if ((e & 1) != 0) {
poly_mul_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(td1, tlen1, rd, rlen, bd, blen, td2, tlen2);
poly_copy_ptr_i32_ptr_i32_ptr_i32_ptr_i32(rd, rlen, td1, tlen1);
}
e = FLOW_CHECKED_SHR((e), (1));
if (e > 0) {
poly_mul_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(td1, tlen1, bd, blen, bd, blen, td2, tlen2);
poly_copy_ptr_i32_ptr_i32_ptr_i32_ptr_i32(bd, blen, td1, tlen1);
}
}
}
int32_t main(void) {
int32_t m = 142857;
int64_t six_cap = ((int64_t)((6 * CAP)));
int32_t* qd = (int32_t*)(calloc(six_cap, 4));
int32_t* qlen = (int32_t*)(calloc(6, 4));
int32_t* ad = (int32_t*)(calloc(six_cap, 4));
int32_t* alen = (int32_t*)(calloc(6, 4));
int32_t* qmd = (int32_t*)(calloc(six_cap, 4));
int32_t* qmlen = (int32_t*)(calloc(6, 4));
int32_t* aqmd = (int32_t*)(calloc(six_cap, 4));
int32_t* aqmlen = (int32_t*)(calloc(6, 4));
int32_t* bd = (int32_t*)(calloc(six_cap, 4));
int32_t* blen = (int32_t*)(calloc(6, 4));
int32_t* td1 = (int32_t*)(calloc(six_cap, 4));
int32_t* tlen1 = (int32_t*)(calloc(6, 4));
int32_t* td2 = (int32_t*)(calloc(((int64_t)(CAP)), 4));
int32_t* tlen2 = (int32_t*)(calloc(1, 4));
if ((((((((((((((qd == NULL || qlen == NULL) || ad == NULL) || alen == NULL) || qmd == NULL) || qmlen == NULL) || aqmd == NULL) || aqmlen == NULL) || bd == NULL) || blen == NULL) || td1 == NULL) || tlen1 == NULL) || td2 == NULL) || tlen2 == NULL)) {
return 1;
}
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 0, 1);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 1, 3);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 2, 5);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 3, 5);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 4, 3);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(qd, qlen, 5, 1);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 0, 1);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 1, 5);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 2, 10);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 3, 10);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 4, 5);
coeff_set_int_ptr_i32_ptr_i32_i32_i32(ad, alen, 5, 1);
poly_pow_ptr_i32_ptr_i32_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(qmd, qmlen, qd, qlen, m, bd, blen, td1, tlen1, td2, tlen2);
poly_mul_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32_ptr_i32(aqmd, aqmlen, ad, alen, qmd, qmlen, td2, tlen2);
int32_t* cd = (int32_t*)(calloc(((int64_t)(CAP)), 4));
int32_t* clen = (int32_t*)(calloc(1, 4));
if ((cd == NULL || clen == NULL)) {
return 1;
}
coeff_copy_ptr_i32_ptr_i32_i32_ptr_i32_ptr_i32_i32(cd, clen, 0, aqmd, aqmlen, 5);
if (coeff_nonzero_ptr_i32_ptr_i32_i32(cd, clen, 0) == 0) {
printf("0000000000\n");
free(qd);
free(qlen);
free(ad);
free(alen);
free(qmd);
free(qmlen);
free(aqmd);
free(aqmlen);
free(bd);
free(blen);
free(td1);
free(tlen1);
free(td2);
free(tlen2);
free(cd);
free(clen);
return 0;
}
int32_t* digits7 = (int32_t*)(calloc(250000, 4));
if (digits7 == NULL) {
return 1;
}
int32_t n7 = 0;
while (coeff_nonzero_ptr_i32_ptr_i32_i32(cd, clen, 0)) {
digits7[n7] = coeff_divmod_small_ptr_i32_ptr_i32_i32_i32(cd, clen, 0, 7);
n7 = (n7 + 1);
}
int32_t o = 0;
int32_t i = (n7 - 1);
while ((i >= 0 && o < 10)) {
printf("%lld", ((int64_t)(digits7[i])));
o = (o + 1);
i = (i - 1);
}
while (o < 10) {
printf("0");
o = (o + 1);
}
printf("\n");
free(qd);
free(qlen);
free(ad);
free(alen);
free(qmd);
free(qmlen);
free(aqmd);
free(aqmlen);
free(bd);
free(blen);
free(td1);
free(tlen1);
free(td2);
free(tlen2);
free(cd);
free(clen);
free(digits7);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("0000000000\n\00") {addr_space = 0 : i32} : !llvm.array<12 x i8>
llvm.mlir.global internal constant @str_1("%lld\00") {addr_space = 0 : i32} : !llvm.array<5 x i8>
llvm.mlir.global internal constant @str_2("0\00") {addr_space = 0 : i32} : !llvm.array<2 x i8>
llvm.mlir.global internal constant @str_3("\n\00") {addr_space = 0 : i32} : !llvm.array<2 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: CAP
llvm.mlir.global internal constant @CAP(25000 : i32) : i32
// Constant: DEG
llvm.mlir.global internal constant @DEG(5 : i32) : i32
// Constant: BASE
llvm.mlir.global internal constant @BASE(1000000000 : i64) : i64
func.func @coeff_set_int(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: i32) -> () {
%0 = arith.constant 0 : i32
%1 = arith.cmpi eq, %arg3, %0 : i32
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%2 = arith.constant 0 : i32
%3 = arith.extsi %arg2 : i32 to i64
%4 = llvm.getelementptr %arg1[%3] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %2, %4 : i32, !llvm.ptr
func.return
^bb1:
cf.br ^bb2
^bb2:
%5 = llvm.mlir.addressof @CAP : !llvm.ptr
%6 = llvm.load %5 : !llvm.ptr -> i32
%7 = arith.muli %arg2, %6 : i32
%8 = arith.extsi %7 : i32 to i64
%9 = llvm.getelementptr %arg0[%8] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %arg3, %9 : i32, !llvm.ptr
%10 = arith.constant 1 : i32
%11 = arith.extsi %arg2 : i32 to i64
%12 = llvm.getelementptr %arg1[%11] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %10, %12 : i32, !llvm.ptr
func.return
}
func.func @coeff_copy(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i32) -> () {
%13 = arith.constant 0 : i32
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i32 : (i64) -> !llvm.ptr
llvm.store %13, %15 : i32, !llvm.ptr
cf.br ^bb3
^bb3:
%16 = llvm.load %15 : !llvm.ptr -> i32
%18 = arith.extsi %arg5 : i32 to i64
%19 = llvm.getelementptr %arg4[%18] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%17 = llvm.load %19 : !llvm.ptr -> i32
%20 = arith.cmpi slt, %16, %17 : i32
cf.cond_br %20, ^bb4, ^bb5
^bb4:
%22 = llvm.mlir.addressof @CAP : !llvm.ptr
%23 = llvm.load %22 : !llvm.ptr -> i32
%24 = arith.muli %arg5, %23 : i32
%25 = llvm.load %15 : !llvm.ptr -> i32
%26 = arith.addi %24, %25 : i32
%27 = arith.extsi %26 : i32 to i64
%28 = llvm.getelementptr %arg3[%27] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%21 = llvm.load %28 : !llvm.ptr -> i32
%29 = llvm.mlir.addressof @CAP : !llvm.ptr
%30 = llvm.load %29 : !llvm.ptr -> i32
%31 = arith.muli %arg2, %30 : i32
%32 = llvm.load %15 : !llvm.ptr -> i32
%33 = arith.addi %31, %32 : i32
%34 = arith.extsi %33 : i32 to i64
%35 = llvm.getelementptr %arg0[%34] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %21, %35 : i32, !llvm.ptr
%36 = llvm.load %15 : !llvm.ptr -> i32
%37 = arith.constant 1 : i32
%38 = arith.addi %36, %37 : i32
llvm.store %38, %15 : i32, !llvm.ptr
cf.br ^bb3
^bb5:
%40 = arith.extsi %arg5 : i32 to i64
%41 = llvm.getelementptr %arg4[%40] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%39 = llvm.load %41 : !llvm.ptr -> i32
%42 = arith.extsi %arg2 : i32 to i64
%43 = llvm.getelementptr %arg1[%42] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %39, %43 : i32, !llvm.ptr
func.return
}
func.func @coeff_add(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i32, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: i32) -> () {
%45 = arith.extsi %arg5 : i32 to i64
%46 = llvm.getelementptr %arg4[%45] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%44 = llvm.load %46 : !llvm.ptr -> i32
%47 = llvm.mlir.constant(1 : i64) : i64
%48 = llvm.alloca %47 x i32 : (i64) -> !llvm.ptr
llvm.store %44, %48 : i32, !llvm.ptr
%50 = arith.extsi %arg8 : i32 to i64
%51 = llvm.getelementptr %arg7[%50] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%49 = llvm.load %51 : !llvm.ptr -> i32
%52 = llvm.load %48 : !llvm.ptr -> i32
%53 = arith.cmpi sgt, %49, %52 : i32
cf.cond_br %53, ^bb6, ^bb7
^bb6:
%55 = arith.extsi %arg8 : i32 to i64
%56 = llvm.getelementptr %arg7[%55] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%54 = llvm.load %56 : !llvm.ptr -> i32
llvm.store %54, %48 : i32, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%57 = arith.constant 0 : i32
%58 = arith.extsi %57 : i32 to i64
%59 = llvm.mlir.constant(1 : i64) : i64
%60 = llvm.alloca %59 x i64 : (i64) -> !llvm.ptr
llvm.store %58, %60 : i64, !llvm.ptr
%61 = arith.constant 0 : i32
%62 = llvm.mlir.constant(1 : i64) : i64
%63 = llvm.alloca %62 x i32 : (i64) -> !llvm.ptr
llvm.store %61, %63 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%64 = llvm.load %63 : !llvm.ptr -> i32
%65 = llvm.load %48 : !llvm.ptr -> i32
%66 = arith.cmpi slt, %64, %65 : i32
cf.cond_br %66, ^bb10, ^bb11
^bb10:
%67 = llvm.load %60 : !llvm.ptr -> i64
%68 = llvm.mlir.constant(1 : i64) : i64
%69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
llvm.store %67, %69 : i64, !llvm.ptr
%70 = llvm.load %63 : !llvm.ptr -> i32
%72 = arith.extsi %arg5 : i32 to i64
%73 = llvm.getelementptr %arg4[%72] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%71 = llvm.load %73 : !llvm.ptr -> i32
%74 = arith.cmpi slt, %70, %71 : i32
cf.cond_br %74, ^bb12, ^bb13
^bb12:
%75 = llvm.load %69 : !llvm.ptr -> i64
%77 = llvm.mlir.addressof @CAP : !llvm.ptr
%78 = llvm.load %77 : !llvm.ptr -> i32
%79 = arith.muli %arg5, %78 : i32
%80 = llvm.load %63 : !llvm.ptr -> i32
%81 = arith.addi %79, %80 : i32
%82 = arith.extsi %81 : i32 to i64
%83 = llvm.getelementptr %arg3[%82] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%76 = llvm.load %83 : !llvm.ptr -> i32
%84 = arith.extsi %76 : i32 to i64
%85 = arith.addi %75, %84 : i64
llvm.store %85, %69 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%86 = llvm.load %63 : !llvm.ptr -> i32
%88 = arith.extsi %arg8 : i32 to i64
%89 = llvm.getelementptr %arg7[%88] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%87 = llvm.load %89 : !llvm.ptr -> i32
%90 = arith.cmpi slt, %86, %87 : i32
cf.cond_br %90, ^bb15, ^bb16
^bb15:
%91 = llvm.load %69 : !llvm.ptr -> i64
%93 = llvm.mlir.addressof @CAP : !llvm.ptr
%94 = llvm.load %93 : !llvm.ptr -> i32
%95 = arith.muli %arg8, %94 : i32
%96 = llvm.load %63 : !llvm.ptr -> i32
%97 = arith.addi %95, %96 : i32
%98 = arith.extsi %97 : i32 to i64
%99 = llvm.getelementptr %arg6[%98] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%92 = llvm.load %99 : !llvm.ptr -> i32
%100 = arith.extsi %92 : i32 to i64
%101 = arith.addi %91, %100 : i64
llvm.store %101, %69 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%102 = llvm.load %69 : !llvm.ptr -> i64
%103 = llvm.mlir.addressof @BASE : !llvm.ptr
%104 = llvm.load %103 : !llvm.ptr -> i64
%105 = arith.remsi %102, %104 : i64
%106 = arith.trunci %105 : i64 to i32
%107 = llvm.mlir.addressof @CAP : !llvm.ptr
%108 = llvm.load %107 : !llvm.ptr -> i32
%109 = arith.muli %arg2, %108 : i32
%110 = llvm.load %63 : !llvm.ptr -> i32
%111 = arith.addi %109, %110 : i32
%112 = arith.extsi %111 : i32 to i64
%113 = llvm.getelementptr %arg0[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %106, %113 : i32, !llvm.ptr
%114 = llvm.load %69 : !llvm.ptr -> i64
%115 = llvm.mlir.addressof @BASE : !llvm.ptr
%116 = llvm.load %115 : !llvm.ptr -> i64
%117 = arith.divsi %114, %116 : i64
llvm.store %117, %60 : i64, !llvm.ptr
%118 = llvm.load %63 : !llvm.ptr -> i32
%119 = arith.constant 1 : i32
%120 = arith.addi %118, %119 : i32
llvm.store %120, %63 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
%121 = llvm.load %60 : !llvm.ptr -> i64
%122 = arith.constant 0 : i32
%124 = arith.extsi %122 : i32 to i64
%123 = arith.cmpi sgt, %121, %124 : i64
cf.cond_br %123, ^bb18, ^bb19
^bb18:
%125 = llvm.load %60 : !llvm.ptr -> i64
%126 = arith.trunci %125 : i64 to i32
%127 = llvm.mlir.addressof @CAP : !llvm.ptr
%128 = llvm.load %127 : !llvm.ptr -> i32
%129 = arith.muli %arg2, %128 : i32
%130 = llvm.load %63 : !llvm.ptr -> i32
%131 = arith.addi %129, %130 : i32
%132 = arith.extsi %131 : i32 to i64
%133 = llvm.getelementptr %arg0[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %126, %133 : i32, !llvm.ptr
%134 = llvm.load %63 : !llvm.ptr -> i32
%135 = arith.constant 1 : i32
%136 = arith.addi %134, %135 : i32
llvm.store %136, %63 : i32, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%137 = llvm.load %63 : !llvm.ptr -> i32
%138 = arith.extsi %arg2 : i32 to i64
%139 = llvm.getelementptr %arg1[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %137, %139 : i32, !llvm.ptr
func.return
}
func.func @coeff_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i32, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: i32) -> () {
%141 = arith.extsi %arg5 : i32 to i64
%142 = llvm.getelementptr %arg4[%141] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%140 = llvm.load %142 : !llvm.ptr -> i32
%144 = arith.extsi %arg8 : i32 to i64
%145 = llvm.getelementptr %arg7[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%143 = llvm.load %145 : !llvm.ptr -> i32
%146 = arith.constant 0 : i32
%147 = arith.cmpi eq, %140, %146 : i32
%148 = scf.if %147 -> (i1) {
%149 = arith.constant true
scf.yield %149 : i1
} else {
%150 = arith.constant 0 : i32
%151 = arith.cmpi eq, %143, %150 : i32
scf.yield %151 : i1
}
cf.cond_br %148, ^bb21, ^bb22
^bb21:
%152 = arith.constant 0 : i32
%153 = arith.extsi %arg2 : i32 to i64
%154 = llvm.getelementptr %arg1[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %152, %154 : i32, !llvm.ptr
func.return
^bb22:
cf.br ^bb23
^bb23:
%155 = arith.addi %140, %143 : i32
%156 = arith.constant 0 : i32
%157 = llvm.mlir.constant(1 : i64) : i64
%158 = llvm.alloca %157 x i32 : (i64) -> !llvm.ptr
llvm.store %156, %158 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%159 = llvm.load %158 : !llvm.ptr -> i32
%160 = arith.cmpi slt, %159, %155 : i32
cf.cond_br %160, ^bb25, ^bb26
^bb25:
%161 = arith.constant 0 : i32
%162 = llvm.mlir.addressof @CAP : !llvm.ptr
%163 = llvm.load %162 : !llvm.ptr -> i32
%164 = arith.muli %arg2, %163 : i32
%165 = llvm.load %158 : !llvm.ptr -> i32
%166 = arith.addi %164, %165 : i32
%167 = arith.extsi %166 : i32 to i64
%168 = llvm.getelementptr %arg0[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %161, %168 : i32, !llvm.ptr
%169 = llvm.load %158 : !llvm.ptr -> i32
%170 = arith.constant 1 : i32
%171 = arith.addi %169, %170 : i32
llvm.store %171, %158 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%172 = arith.constant 0 : i32
llvm.store %172, %158 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%173 = llvm.load %158 : !llvm.ptr -> i32
%174 = arith.cmpi slt, %173, %140 : i32
cf.cond_br %174, ^bb28, ^bb29
^bb28:
%175 = arith.constant 0 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i64, !llvm.ptr
%179 = arith.constant 0 : i32
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i32 : (i64) -> !llvm.ptr
llvm.store %179, %181 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%182 = llvm.load %181 : !llvm.ptr -> i32
%183 = arith.cmpi slt, %182, %143 : i32
cf.cond_br %183, ^bb31, ^bb32
^bb31:
%185 = llvm.mlir.addressof @CAP : !llvm.ptr
%186 = llvm.load %185 : !llvm.ptr -> i32
%187 = arith.muli %arg5, %186 : i32
%188 = llvm.load %158 : !llvm.ptr -> i32
%189 = arith.addi %187, %188 : i32
%190 = arith.extsi %189 : i32 to i64
%191 = llvm.getelementptr %arg3[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%184 = llvm.load %191 : !llvm.ptr -> i32
%192 = arith.extsi %184 : i32 to i64
%194 = llvm.mlir.addressof @CAP : !llvm.ptr
%195 = llvm.load %194 : !llvm.ptr -> i32
%196 = arith.muli %arg8, %195 : i32
%197 = llvm.load %181 : !llvm.ptr -> i32
%198 = arith.addi %196, %197 : i32
%199 = arith.extsi %198 : i32 to i64
%200 = llvm.getelementptr %arg6[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%193 = llvm.load %200 : !llvm.ptr -> i32
%201 = arith.extsi %193 : i32 to i64
%202 = arith.muli %192, %201 : i64
%204 = llvm.mlir.addressof @CAP : !llvm.ptr
%205 = llvm.load %204 : !llvm.ptr -> i32
%206 = arith.muli %arg2, %205 : i32
%207 = llvm.load %158 : !llvm.ptr -> i32
%208 = arith.addi %206, %207 : i32
%209 = llvm.load %181 : !llvm.ptr -> i32
%210 = arith.addi %208, %209 : i32
%211 = arith.extsi %210 : i32 to i64
%212 = llvm.getelementptr %arg0[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%203 = llvm.load %212 : !llvm.ptr -> i32
%213 = arith.extsi %203 : i32 to i64
%214 = arith.addi %202, %213 : i64
%215 = llvm.load %178 : !llvm.ptr -> i64
%216 = arith.addi %214, %215 : i64
%217 = llvm.mlir.addressof @BASE : !llvm.ptr
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.remsi %216, %218 : i64
%220 = arith.trunci %219 : i64 to i32
%221 = llvm.mlir.addressof @CAP : !llvm.ptr
%222 = llvm.load %221 : !llvm.ptr -> i32
%223 = arith.muli %arg2, %222 : i32
%224 = llvm.load %158 : !llvm.ptr -> i32
%225 = arith.addi %223, %224 : i32
%226 = llvm.load %181 : !llvm.ptr -> i32
%227 = arith.addi %225, %226 : i32
%228 = arith.extsi %227 : i32 to i64
%229 = llvm.getelementptr %arg0[%228] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %220, %229 : i32, !llvm.ptr
%230 = llvm.mlir.addressof @BASE : !llvm.ptr
%231 = llvm.load %230 : !llvm.ptr -> i64
%232 = arith.divsi %216, %231 : i64
llvm.store %232, %178 : i64, !llvm.ptr
%233 = llvm.load %181 : !llvm.ptr -> i32
%234 = arith.constant 1 : i32
%235 = arith.addi %233, %234 : i32
llvm.store %235, %181 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
%236 = llvm.load %158 : !llvm.ptr -> i32
%237 = arith.addi %236, %143 : i32
%238 = llvm.mlir.constant(1 : i64) : i64
%239 = llvm.alloca %238 x i32 : (i64) -> !llvm.ptr
llvm.store %237, %239 : i32, !llvm.ptr
cf.br ^bb33
^bb33:
%240 = llvm.load %178 : !llvm.ptr -> i64
%241 = arith.constant 0 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.cmpi sgt, %240, %243 : i64
cf.cond_br %242, ^bb34, ^bb35
^bb34:
%245 = llvm.mlir.addressof @CAP : !llvm.ptr
%246 = llvm.load %245 : !llvm.ptr -> i32
%247 = arith.muli %arg2, %246 : i32
%248 = llvm.load %239 : !llvm.ptr -> i32
%249 = arith.addi %247, %248 : i32
%250 = arith.extsi %249 : i32 to i64
%251 = llvm.getelementptr %arg0[%250] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%244 = llvm.load %251 : !llvm.ptr -> i32
%252 = arith.extsi %244 : i32 to i64
%253 = llvm.load %178 : !llvm.ptr -> i64
%254 = arith.addi %252, %253 : i64
%255 = llvm.mlir.addressof @BASE : !llvm.ptr
%256 = llvm.load %255 : !llvm.ptr -> i64
%257 = arith.remsi %254, %256 : i64
%258 = arith.trunci %257 : i64 to i32
%259 = llvm.mlir.addressof @CAP : !llvm.ptr
%260 = llvm.load %259 : !llvm.ptr -> i32
%261 = arith.muli %arg2, %260 : i32
%262 = llvm.load %239 : !llvm.ptr -> i32
%263 = arith.addi %261, %262 : i32
%264 = arith.extsi %263 : i32 to i64
%265 = llvm.getelementptr %arg0[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %258, %265 : i32, !llvm.ptr
%266 = llvm.mlir.addressof @BASE : !llvm.ptr
%267 = llvm.load %266 : !llvm.ptr -> i64
%268 = arith.divsi %254, %267 : i64
llvm.store %268, %178 : i64, !llvm.ptr
%269 = llvm.load %239 : !llvm.ptr -> i32
%270 = arith.constant 1 : i32
%271 = arith.addi %269, %270 : i32
llvm.store %271, %239 : i32, !llvm.ptr
cf.br ^bb33
^bb35:
%272 = llvm.load %158 : !llvm.ptr -> i32
%273 = arith.constant 1 : i32
%274 = arith.addi %272, %273 : i32
llvm.store %274, %158 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%275 = arith.extsi %arg2 : i32 to i64
%276 = llvm.getelementptr %arg1[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %155, %276 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%278 = arith.extsi %arg2 : i32 to i64
%279 = llvm.getelementptr %arg1[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%277 = llvm.load %279 : !llvm.ptr -> i32
%280 = arith.constant 0 : i32
%281 = arith.cmpi sgt, %277, %280 : i32
%282 = scf.if %281 -> (i1) {
%284 = llvm.mlir.addressof @CAP : !llvm.ptr
%285 = llvm.load %284 : !llvm.ptr -> i32
%286 = arith.muli %arg2, %285 : i32
%288 = arith.extsi %arg2 : i32 to i64
%289 = llvm.getelementptr %arg1[%288] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%287 = llvm.load %289 : !llvm.ptr -> i32
%290 = arith.addi %286, %287 : i32
%291 = arith.constant 1 : i32
%292 = arith.subi %290, %291 : i32
%293 = arith.extsi %292 : i32 to i64
%294 = llvm.getelementptr %arg0[%293] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%283 = llvm.load %294 : !llvm.ptr -> i32
%295 = arith.constant 0 : i32
%296 = arith.cmpi eq, %283, %295 : i32
scf.yield %296 : i1
} else {
%297 = arith.constant false
scf.yield %297 : i1
}
cf.cond_br %282, ^bb37, ^bb38
^bb37:
%299 = arith.extsi %arg2 : i32 to i64
%300 = llvm.getelementptr %arg1[%299] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%298 = llvm.load %300 : !llvm.ptr -> i32
%301 = arith.constant 1 : i32
%302 = arith.subi %298, %301 : i32
%303 = arith.extsi %arg2 : i32 to i64
%304 = llvm.getelementptr %arg1[%303] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %302, %304 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
func.return
}
func.func @coeff_divmod_small(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: i32) -> i32 {
%305 = arith.constant 0 : i32
%306 = arith.extsi %305 : i32 to i64
%307 = llvm.mlir.constant(1 : i64) : i64
%308 = llvm.alloca %307 x i64 : (i64) -> !llvm.ptr
llvm.store %306, %308 : i64, !llvm.ptr
%310 = arith.extsi %arg2 : i32 to i64
%311 = llvm.getelementptr %arg1[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%309 = llvm.load %311 : !llvm.ptr -> i32
%312 = arith.constant 1 : i32
%313 = arith.subi %309, %312 : i32
%314 = llvm.mlir.constant(1 : i64) : i64
%315 = llvm.alloca %314 x i32 : (i64) -> !llvm.ptr
llvm.store %313, %315 : i32, !llvm.ptr
cf.br ^bb39
^bb39:
%316 = llvm.load %315 : !llvm.ptr -> i32
%317 = arith.constant 0 : i32
%318 = arith.cmpi sge, %316, %317 : i32
cf.cond_br %318, ^bb40, ^bb41
^bb40:
%319 = llvm.load %308 : !llvm.ptr -> i64
%320 = llvm.mlir.addressof @BASE : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> i64
%322 = arith.muli %319, %321 : i64
%324 = llvm.mlir.addressof @CAP : !llvm.ptr
%325 = llvm.load %324 : !llvm.ptr -> i32
%326 = arith.muli %arg2, %325 : i32
%327 = llvm.load %315 : !llvm.ptr -> i32
%328 = arith.addi %326, %327 : i32
%329 = arith.extsi %328 : i32 to i64
%330 = llvm.getelementptr %arg0[%329] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%323 = llvm.load %330 : !llvm.ptr -> i32
%331 = arith.extsi %323 : i32 to i64
%332 = arith.addi %322, %331 : i64
%333 = arith.extsi %arg3 : i32 to i64
%334 = arith.divsi %332, %333 : i64
%335 = arith.trunci %334 : i64 to i32
%336 = llvm.mlir.addressof @CAP : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> i32
%338 = arith.muli %arg2, %337 : i32
%339 = llvm.load %315 : !llvm.ptr -> i32
%340 = arith.addi %338, %339 : i32
%341 = arith.extsi %340 : i32 to i64
%342 = llvm.getelementptr %arg0[%341] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %335, %342 : i32, !llvm.ptr
%343 = arith.extsi %arg3 : i32 to i64
%344 = arith.remsi %332, %343 : i64
llvm.store %344, %308 : i64, !llvm.ptr
%345 = llvm.load %315 : !llvm.ptr -> i32
%346 = arith.constant 1 : i32
%347 = arith.subi %345, %346 : i32
llvm.store %347, %315 : i32, !llvm.ptr
cf.br ^bb39
^bb41:
cf.br ^bb42
^bb42:
%349 = arith.extsi %arg2 : i32 to i64
%350 = llvm.getelementptr %arg1[%349] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%348 = llvm.load %350 : !llvm.ptr -> i32
%351 = arith.constant 0 : i32
%352 = arith.cmpi sgt, %348, %351 : i32
%353 = scf.if %352 -> (i1) {
%355 = llvm.mlir.addressof @CAP : !llvm.ptr
%356 = llvm.load %355 : !llvm.ptr -> i32
%357 = arith.muli %arg2, %356 : i32
%359 = arith.extsi %arg2 : i32 to i64
%360 = llvm.getelementptr %arg1[%359] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%358 = llvm.load %360 : !llvm.ptr -> i32
%361 = arith.addi %357, %358 : i32
%362 = arith.constant 1 : i32
%363 = arith.subi %361, %362 : i32
%364 = arith.extsi %363 : i32 to i64
%365 = llvm.getelementptr %arg0[%364] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%354 = llvm.load %365 : !llvm.ptr -> i32
%366 = arith.constant 0 : i32
%367 = arith.cmpi eq, %354, %366 : i32
scf.yield %367 : i1
} else {
%368 = arith.constant false
scf.yield %368 : i1
}
cf.cond_br %353, ^bb43, ^bb44
^bb43:
%370 = arith.extsi %arg2 : i32 to i64
%371 = llvm.getelementptr %arg1[%370] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%369 = llvm.load %371 : !llvm.ptr -> i32
%372 = arith.constant 1 : i32
%373 = arith.subi %369, %372 : i32
%374 = arith.extsi %arg2 : i32 to i64
%375 = llvm.getelementptr %arg1[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %373, %375 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
%376 = llvm.load %308 : !llvm.ptr -> i64
%377 = arith.trunci %376 : i64 to i32
func.return %377 : i32
}
func.func @coeff_nonzero(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32) -> i1 {
%379 = arith.extsi %arg2 : i32 to i64
%380 = llvm.getelementptr %arg1[%379] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%378 = llvm.load %380 : !llvm.ptr -> i32
%381 = arith.constant 0 : i32
%382 = arith.cmpi ne, %378, %381 : i32
func.return %382 : i1
}
func.func @poly_copy(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> () {
%383 = arith.constant 0 : i32
%384 = llvm.mlir.constant(1 : i64) : i64
%385 = llvm.alloca %384 x i32 : (i64) -> !llvm.ptr
llvm.store %383, %385 : i32, !llvm.ptr
cf.br ^bb45
^bb45:
%386 = llvm.load %385 : !llvm.ptr -> i32
%387 = llvm.mlir.addressof @DEG : !llvm.ptr
%388 = llvm.load %387 : !llvm.ptr -> i32
%389 = arith.cmpi sle, %386, %388 : i32
cf.cond_br %389, ^bb46, ^bb47
^bb46:
%391 = llvm.load %385 : !llvm.ptr -> i32
%392 = llvm.load %385 : !llvm.ptr -> i32
func.call @coeff_copy(%arg0, %arg1, %391, %arg2, %arg3, %392) : (!llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32) -> ()
%393 = llvm.load %385 : !llvm.ptr -> i32
%394 = arith.constant 1 : i32
%395 = arith.addi %393, %394 : i32
llvm.store %395, %385 : i32, !llvm.ptr
cf.br ^bb45
^bb47:
func.return
}
func.func @poly_mul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr) -> () {
%396 = arith.constant 0 : i32
%397 = llvm.mlir.constant(1 : i64) : i64
%398 = llvm.alloca %397 x i32 : (i64) -> !llvm.ptr
llvm.store %396, %398 : i32, !llvm.ptr
cf.br ^bb48
^bb48:
%399 = llvm.load %398 : !llvm.ptr -> i32
%400 = llvm.mlir.addressof @DEG : !llvm.ptr
%401 = llvm.load %400 : !llvm.ptr -> i32
%402 = arith.cmpi sle, %399, %401 : i32
cf.cond_br %402, ^bb49, ^bb50
^bb49:
%403 = arith.constant 0 : i32
%404 = llvm.load %398 : !llvm.ptr -> i32
%405 = arith.extsi %404 : i32 to i64
%406 = llvm.getelementptr %arg1[%405] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %403, %406 : i32, !llvm.ptr
%407 = llvm.load %398 : !llvm.ptr -> i32
%408 = arith.constant 1 : i32
%409 = arith.addi %407, %408 : i32
llvm.store %409, %398 : i32, !llvm.ptr
cf.br ^bb48
^bb50:
%410 = arith.constant 0 : i32
llvm.store %410, %398 : i32, !llvm.ptr
cf.br ^bb51
^bb51:
%411 = llvm.load %398 : !llvm.ptr -> i32
%412 = llvm.mlir.addressof @DEG : !llvm.ptr
%413 = llvm.load %412 : !llvm.ptr -> i32
%414 = arith.cmpi sle, %411, %413 : i32
cf.cond_br %414, ^bb52, ^bb53
^bb52:
%415 = arith.constant 0 : i32
%416 = llvm.mlir.constant(1 : i64) : i64
%417 = llvm.alloca %416 x i32 : (i64) -> !llvm.ptr
llvm.store %415, %417 : i32, !llvm.ptr
cf.br ^bb54
^bb54:
%418 = llvm.load %417 : !llvm.ptr -> i32
%419 = llvm.load %398 : !llvm.ptr -> i32
%420 = arith.cmpi sle, %418, %419 : i32
cf.cond_br %420, ^bb55, ^bb56
^bb55:
%421 = llvm.load %398 : !llvm.ptr -> i32
%422 = llvm.load %417 : !llvm.ptr -> i32
%423 = arith.subi %421, %422 : i32
%424 = llvm.load %417 : !llvm.ptr -> i32
%425 = llvm.mlir.addressof @DEG : !llvm.ptr
%426 = llvm.load %425 : !llvm.ptr -> i32
%427 = arith.cmpi sle, %424, %426 : i32
%428 = scf.if %427 -> (i1) {
%429 = llvm.mlir.addressof @DEG : !llvm.ptr
%430 = llvm.load %429 : !llvm.ptr -> i32
%431 = arith.cmpi sle, %423, %430 : i32
scf.yield %431 : i1
} else {
%432 = arith.constant false
scf.yield %432 : i1
}
cf.cond_br %428, ^bb57, ^bb58
^bb57:
%434 = arith.constant 0 : i32
%435 = llvm.load %417 : !llvm.ptr -> i32
func.call @coeff_mul(%arg6, %arg7, %434, %arg2, %arg3, %435, %arg4, %arg5, %423) : (!llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32) -> ()
%437 = llvm.load %398 : !llvm.ptr -> i32
%438 = llvm.load %398 : !llvm.ptr -> i32
%439 = arith.constant 0 : i32
func.call @coeff_add(%arg0, %arg1, %437, %arg0, %arg1, %438, %arg6, %arg7, %439) : (!llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32) -> ()
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%440 = llvm.load %417 : !llvm.ptr -> i32
%441 = arith.constant 1 : i32
%442 = arith.addi %440, %441 : i32
llvm.store %442, %417 : i32, !llvm.ptr
cf.br ^bb54
^bb56:
%443 = llvm.load %398 : !llvm.ptr -> i32
%444 = arith.constant 1 : i32
%445 = arith.addi %443, %444 : i32
llvm.store %445, %398 : i32, !llvm.ptr
cf.br ^bb51
^bb53:
func.return
}
func.func @poly_pow(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: i32, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: !llvm.ptr, %arg10: !llvm.ptr) -> () {
%447 = arith.constant 0 : i32
%448 = arith.constant 1 : i32
func.call @coeff_set_int(%arg0, %arg1, %447, %448) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%449 = arith.constant 1 : i32
%450 = llvm.mlir.constant(1 : i64) : i64
%451 = llvm.alloca %450 x i32 : (i64) -> !llvm.ptr
llvm.store %449, %451 : i32, !llvm.ptr
cf.br ^bb60
^bb60:
%452 = llvm.load %451 : !llvm.ptr -> i32
%453 = llvm.mlir.addressof @DEG : !llvm.ptr
%454 = llvm.load %453 : !llvm.ptr -> i32
%455 = arith.cmpi sle, %452, %454 : i32
cf.cond_br %455, ^bb61, ^bb62
^bb61:
%457 = llvm.load %451 : !llvm.ptr -> i32
%458 = arith.constant 0 : i32
func.call @coeff_set_int(%arg0, %arg1, %457, %458) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%459 = llvm.load %451 : !llvm.ptr -> i32
%460 = arith.constant 1 : i32
%461 = arith.addi %459, %460 : i32
llvm.store %461, %451 : i32, !llvm.ptr
cf.br ^bb60
^bb62:
func.call @poly_copy(%arg5, %arg6, %arg2, %arg3) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%463 = llvm.mlir.constant(1 : i64) : i64
%464 = llvm.alloca %463 x i32 : (i64) -> !llvm.ptr
llvm.store %arg4, %464 : i32, !llvm.ptr
cf.br ^bb63
^bb63:
%465 = llvm.load %464 : !llvm.ptr -> i32
%466 = arith.constant 0 : i32
%467 = arith.cmpi sgt, %465, %466 : i32
cf.cond_br %467, ^bb64, ^bb65
^bb64:
%468 = llvm.load %464 : !llvm.ptr -> i32
%469 = arith.constant 1 : i32
%470 = arith.andi %468, %469 : i32
%471 = arith.constant 0 : i32
%472 = arith.cmpi ne, %470, %471 : i32
cf.cond_br %472, ^bb66, ^bb67
^bb66:
func.call @poly_mul(%arg7, %arg8, %arg0, %arg1, %arg5, %arg6, %arg9, %arg10) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @poly_copy(%arg0, %arg1, %arg7, %arg8) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%475 = llvm.load %464 : !llvm.ptr -> i32
%476 = arith.constant 1 : i32
%477 = arith.shrsi %475, %476 : i32
llvm.store %477, %464 : i32, !llvm.ptr
%478 = llvm.load %464 : !llvm.ptr -> i32
%479 = arith.constant 0 : i32
%480 = arith.cmpi sgt, %478, %479 : i32
cf.cond_br %480, ^bb69, ^bb70
^bb69:
func.call @poly_mul(%arg7, %arg8, %arg5, %arg6, %arg5, %arg6, %arg9, %arg10) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @poly_copy(%arg5, %arg6, %arg7, %arg8) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
cf.br ^bb63
^bb65:
func.return
}
func.func @main() -> i32 {
%483 = arith.constant 142857 : i32
%484 = arith.constant 6 : i32
%485 = llvm.mlir.addressof @CAP : !llvm.ptr
%486 = llvm.load %485 : !llvm.ptr -> i32
%487 = arith.muli %484, %486 : i32
%488 = arith.extsi %487 : i32 to i64
%490 = arith.constant 4 : i32
%491 = arith.extsi %490 : i32 to i64
%489 = func.call @calloc(%488, %491) : (i64, i64) -> !llvm.ptr
%493 = arith.constant 6 : i32
%494 = arith.constant 4 : i32
%495 = arith.extsi %493 : i32 to i64
%496 = arith.extsi %494 : i32 to i64
%492 = func.call @calloc(%495, %496) : (i64, i64) -> !llvm.ptr
%498 = arith.constant 4 : i32
%499 = arith.extsi %498 : i32 to i64
%497 = func.call @calloc(%488, %499) : (i64, i64) -> !llvm.ptr
%501 = arith.constant 6 : i32
%502 = arith.constant 4 : 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
%506 = arith.constant 4 : i32
%507 = arith.extsi %506 : i32 to i64
%505 = func.call @calloc(%488, %507) : (i64, i64) -> !llvm.ptr
%509 = arith.constant 6 : i32
%510 = arith.constant 4 : i32
%511 = arith.extsi %509 : i32 to i64
%512 = arith.extsi %510 : i32 to i64
%508 = func.call @calloc(%511, %512) : (i64, i64) -> !llvm.ptr
%514 = arith.constant 4 : i32
%515 = arith.extsi %514 : i32 to i64
%513 = func.call @calloc(%488, %515) : (i64, i64) -> !llvm.ptr
%517 = arith.constant 6 : i32
%518 = arith.constant 4 : i32
%519 = arith.extsi %517 : i32 to i64
%520 = arith.extsi %518 : i32 to i64
%516 = func.call @calloc(%519, %520) : (i64, i64) -> !llvm.ptr
%522 = arith.constant 4 : i32
%523 = arith.extsi %522 : i32 to i64
%521 = func.call @calloc(%488, %523) : (i64, i64) -> !llvm.ptr
%525 = arith.constant 6 : i32
%526 = arith.constant 4 : i32
%527 = arith.extsi %525 : i32 to i64
%528 = arith.extsi %526 : i32 to i64
%524 = func.call @calloc(%527, %528) : (i64, i64) -> !llvm.ptr
%530 = arith.constant 4 : i32
%531 = arith.extsi %530 : i32 to i64
%529 = func.call @calloc(%488, %531) : (i64, i64) -> !llvm.ptr
%533 = arith.constant 6 : i32
%534 = arith.constant 4 : i32
%535 = arith.extsi %533 : i32 to i64
%536 = arith.extsi %534 : i32 to i64
%532 = func.call @calloc(%535, %536) : (i64, i64) -> !llvm.ptr
%538 = llvm.mlir.addressof @CAP : !llvm.ptr
%539 = llvm.load %538 : !llvm.ptr -> i32
%540 = arith.extsi %539 : i32 to i64
%541 = arith.constant 4 : i32
%542 = arith.extsi %541 : i32 to i64
%537 = func.call @calloc(%540, %542) : (i64, i64) -> !llvm.ptr
%544 = arith.constant 1 : i32
%545 = arith.constant 4 : i32
%546 = arith.extsi %544 : i32 to i64
%547 = arith.extsi %545 : i32 to i64
%543 = func.call @calloc(%546, %547) : (i64, i64) -> !llvm.ptr
%548 = llvm.mlir.zero : !llvm.ptr
%549 = llvm.icmp "eq" %489, %548 : !llvm.ptr
%550 = scf.if %549 -> (i1) {
%551 = arith.constant true
scf.yield %551 : i1
} else {
%552 = llvm.mlir.zero : !llvm.ptr
%553 = llvm.icmp "eq" %492, %552 : !llvm.ptr
scf.yield %553 : i1
}
%554 = scf.if %550 -> (i1) {
%555 = arith.constant true
scf.yield %555 : i1
} else {
%556 = llvm.mlir.zero : !llvm.ptr
%557 = llvm.icmp "eq" %497, %556 : !llvm.ptr
scf.yield %557 : i1
}
%558 = scf.if %554 -> (i1) {
%559 = arith.constant true
scf.yield %559 : i1
} else {
%560 = llvm.mlir.zero : !llvm.ptr
%561 = llvm.icmp "eq" %500, %560 : !llvm.ptr
scf.yield %561 : i1
}
%562 = scf.if %558 -> (i1) {
%563 = arith.constant true
scf.yield %563 : i1
} else {
%564 = llvm.mlir.zero : !llvm.ptr
%565 = llvm.icmp "eq" %505, %564 : !llvm.ptr
scf.yield %565 : i1
}
%566 = scf.if %562 -> (i1) {
%567 = arith.constant true
scf.yield %567 : i1
} else {
%568 = llvm.mlir.zero : !llvm.ptr
%569 = llvm.icmp "eq" %508, %568 : !llvm.ptr
scf.yield %569 : i1
}
%570 = scf.if %566 -> (i1) {
%571 = arith.constant true
scf.yield %571 : i1
} else {
%572 = llvm.mlir.zero : !llvm.ptr
%573 = llvm.icmp "eq" %513, %572 : !llvm.ptr
scf.yield %573 : i1
}
%574 = scf.if %570 -> (i1) {
%575 = arith.constant true
scf.yield %575 : i1
} else {
%576 = llvm.mlir.zero : !llvm.ptr
%577 = llvm.icmp "eq" %516, %576 : !llvm.ptr
scf.yield %577 : i1
}
%578 = scf.if %574 -> (i1) {
%579 = arith.constant true
scf.yield %579 : i1
} else {
%580 = llvm.mlir.zero : !llvm.ptr
%581 = llvm.icmp "eq" %521, %580 : !llvm.ptr
scf.yield %581 : i1
}
%582 = scf.if %578 -> (i1) {
%583 = arith.constant true
scf.yield %583 : i1
} else {
%584 = llvm.mlir.zero : !llvm.ptr
%585 = llvm.icmp "eq" %524, %584 : !llvm.ptr
scf.yield %585 : i1
}
%586 = scf.if %582 -> (i1) {
%587 = arith.constant true
scf.yield %587 : i1
} else {
%588 = llvm.mlir.zero : !llvm.ptr
%589 = llvm.icmp "eq" %529, %588 : !llvm.ptr
scf.yield %589 : i1
}
%590 = scf.if %586 -> (i1) {
%591 = arith.constant true
scf.yield %591 : i1
} else {
%592 = llvm.mlir.zero : !llvm.ptr
%593 = llvm.icmp "eq" %532, %592 : !llvm.ptr
scf.yield %593 : i1
}
%594 = scf.if %590 -> (i1) {
%595 = arith.constant true
scf.yield %595 : i1
} else {
%596 = llvm.mlir.zero : !llvm.ptr
%597 = llvm.icmp "eq" %537, %596 : !llvm.ptr
scf.yield %597 : i1
}
%598 = scf.if %594 -> (i1) {
%599 = arith.constant true
scf.yield %599 : i1
} else {
%600 = llvm.mlir.zero : !llvm.ptr
%601 = llvm.icmp "eq" %543, %600 : !llvm.ptr
scf.yield %601 : i1
}
cf.cond_br %598, ^bb72, ^bb73
^bb72:
%602 = arith.constant 1 : i32
func.return %602 : i32
^bb73:
cf.br ^bb74
^bb74:
%604 = arith.constant 0 : i32
%605 = arith.constant 1 : i32
func.call @coeff_set_int(%489, %492, %604, %605) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%607 = arith.constant 1 : i32
%608 = arith.constant 3 : i32
func.call @coeff_set_int(%489, %492, %607, %608) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%610 = arith.constant 2 : i32
%611 = arith.constant 5 : i32
func.call @coeff_set_int(%489, %492, %610, %611) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%613 = arith.constant 3 : i32
%614 = arith.constant 5 : i32
func.call @coeff_set_int(%489, %492, %613, %614) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%616 = arith.constant 4 : i32
%617 = arith.constant 3 : i32
func.call @coeff_set_int(%489, %492, %616, %617) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%619 = arith.constant 5 : i32
%620 = arith.constant 1 : i32
func.call @coeff_set_int(%489, %492, %619, %620) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%622 = arith.constant 0 : i32
%623 = arith.constant 1 : i32
func.call @coeff_set_int(%497, %500, %622, %623) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%625 = arith.constant 1 : i32
%626 = arith.constant 5 : i32
func.call @coeff_set_int(%497, %500, %625, %626) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%628 = arith.constant 2 : i32
%629 = arith.constant 10 : i32
func.call @coeff_set_int(%497, %500, %628, %629) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%631 = arith.constant 3 : i32
%632 = arith.constant 10 : i32
func.call @coeff_set_int(%497, %500, %631, %632) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%634 = arith.constant 4 : i32
%635 = arith.constant 5 : i32
func.call @coeff_set_int(%497, %500, %634, %635) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
%637 = arith.constant 5 : i32
%638 = arith.constant 1 : i32
func.call @coeff_set_int(%497, %500, %637, %638) : (!llvm.ptr, !llvm.ptr, i32, i32) -> ()
func.call @poly_pow(%505, %508, %489, %492, %483, %521, %524, %529, %532, %537, %543) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @poly_mul(%513, %516, %497, %500, %505, %508, %537, %543) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%642 = llvm.mlir.addressof @CAP : !llvm.ptr
%643 = llvm.load %642 : !llvm.ptr -> i32
%644 = arith.extsi %643 : i32 to i64
%645 = arith.constant 4 : i32
%646 = arith.extsi %645 : i32 to i64
%641 = func.call @calloc(%644, %646) : (i64, i64) -> !llvm.ptr
%648 = arith.constant 1 : i32
%649 = arith.constant 4 : i32
%650 = arith.extsi %648 : i32 to i64
%651 = arith.extsi %649 : i32 to i64
%647 = func.call @calloc(%650, %651) : (i64, i64) -> !llvm.ptr
%652 = llvm.mlir.zero : !llvm.ptr
%653 = llvm.icmp "eq" %641, %652 : !llvm.ptr
%654 = scf.if %653 -> (i1) {
%655 = arith.constant true
scf.yield %655 : i1
} else {
%656 = llvm.mlir.zero : !llvm.ptr
%657 = llvm.icmp "eq" %647, %656 : !llvm.ptr
scf.yield %657 : i1
}
cf.cond_br %654, ^bb75, ^bb76
^bb75:
%658 = arith.constant 1 : i32
func.return %658 : i32
^bb76:
cf.br ^bb77
^bb77:
%660 = arith.constant 0 : i32
%661 = arith.constant 5 : i32
func.call @coeff_copy(%641, %647, %660, %513, %516, %661) : (!llvm.ptr, !llvm.ptr, i32, !llvm.ptr, !llvm.ptr, i32) -> ()
%663 = arith.constant 0 : i32
%662 = func.call @coeff_nonzero(%641, %647, %663) : (!llvm.ptr, !llvm.ptr, i32) -> i1
%664 = arith.constant 0 : i1
%665 = arith.cmpi eq, %662, %664 : i1
cf.cond_br %665, ^bb78, ^bb79
^bb78:
%666 = llvm.mlir.addressof @str_0 : !llvm.ptr
%667 = llvm.call @printf(%666) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
func.call @free(%489) : (!llvm.ptr) -> ()
func.call @free(%492) : (!llvm.ptr) -> ()
func.call @free(%497) : (!llvm.ptr) -> ()
func.call @free(%500) : (!llvm.ptr) -> ()
func.call @free(%505) : (!llvm.ptr) -> ()
func.call @free(%508) : (!llvm.ptr) -> ()
func.call @free(%513) : (!llvm.ptr) -> ()
func.call @free(%516) : (!llvm.ptr) -> ()
func.call @free(%521) : (!llvm.ptr) -> ()
func.call @free(%524) : (!llvm.ptr) -> ()
func.call @free(%529) : (!llvm.ptr) -> ()
func.call @free(%532) : (!llvm.ptr) -> ()
func.call @free(%537) : (!llvm.ptr) -> ()
func.call @free(%543) : (!llvm.ptr) -> ()
func.call @free(%641) : (!llvm.ptr) -> ()
func.call @free(%647) : (!llvm.ptr) -> ()
%684 = arith.constant 0 : i32
func.return %684 : i32
^bb79:
cf.br ^bb80
^bb80:
%686 = arith.constant 250000 : i32
%687 = arith.constant 4 : i32
%688 = arith.extsi %686 : i32 to i64
%689 = arith.extsi %687 : i32 to i64
%685 = func.call @calloc(%688, %689) : (i64, i64) -> !llvm.ptr
%690 = llvm.mlir.zero : !llvm.ptr
%691 = llvm.icmp "eq" %685, %690 : !llvm.ptr
cf.cond_br %691, ^bb81, ^bb82
^bb81:
%692 = arith.constant 1 : i32
func.return %692 : i32
^bb82:
cf.br ^bb83
^bb83:
%693 = arith.constant 0 : i32
%694 = llvm.mlir.constant(1 : i64) : i64
%695 = llvm.alloca %694 x i32 : (i64) -> !llvm.ptr
llvm.store %693, %695 : i32, !llvm.ptr
cf.br ^bb84
^bb84:
%697 = arith.constant 0 : i32
%696 = func.call @coeff_nonzero(%641, %647, %697) : (!llvm.ptr, !llvm.ptr, i32) -> i1
cf.cond_br %696, ^bb85, ^bb86
^bb85:
%699 = arith.constant 0 : i32
%700 = arith.constant 7 : i32
%698 = func.call @coeff_divmod_small(%641, %647, %699, %700) : (!llvm.ptr, !llvm.ptr, i32, i32) -> i32
%701 = llvm.load %695 : !llvm.ptr -> i32
%702 = arith.extsi %701 : i32 to i64
%703 = llvm.getelementptr %685[%702] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %698, %703 : i32, !llvm.ptr
%704 = llvm.load %695 : !llvm.ptr -> i32
%705 = arith.constant 1 : i32
%706 = arith.addi %704, %705 : i32
llvm.store %706, %695 : i32, !llvm.ptr
cf.br ^bb84
^bb86:
%707 = arith.constant 0 : i32
%708 = llvm.mlir.constant(1 : i64) : i64
%709 = llvm.alloca %708 x i32 : (i64) -> !llvm.ptr
llvm.store %707, %709 : i32, !llvm.ptr
%710 = llvm.load %695 : !llvm.ptr -> i32
%711 = arith.constant 1 : i32
%712 = arith.subi %710, %711 : i32
%713 = llvm.mlir.constant(1 : i64) : i64
%714 = llvm.alloca %713 x i32 : (i64) -> !llvm.ptr
llvm.store %712, %714 : i32, !llvm.ptr
cf.br ^bb87
^bb87:
%715 = llvm.load %714 : !llvm.ptr -> i32
%716 = arith.constant 0 : i32
%717 = arith.cmpi sge, %715, %716 : i32
%718 = scf.if %717 -> (i1) {
%719 = llvm.load %709 : !llvm.ptr -> i32
%720 = arith.constant 10 : i32
%721 = arith.cmpi slt, %719, %720 : i32
scf.yield %721 : i1
} else {
%722 = arith.constant false
scf.yield %722 : i1
}
cf.cond_br %718, ^bb88, ^bb89
^bb88:
%723 = llvm.mlir.addressof @str_1 : !llvm.ptr
%725 = llvm.load %714 : !llvm.ptr -> i32
%726 = arith.extsi %725 : i32 to i64
%727 = llvm.getelementptr %685[%726] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%724 = llvm.load %727 : !llvm.ptr -> i32
%728 = arith.extsi %724 : i32 to i64
%729 = llvm.call @printf(%723, %728) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%730 = llvm.load %709 : !llvm.ptr -> i32
%731 = arith.constant 1 : i32
%732 = arith.addi %730, %731 : i32
llvm.store %732, %709 : i32, !llvm.ptr
%733 = llvm.load %714 : !llvm.ptr -> i32
%734 = arith.constant 1 : i32
%735 = arith.subi %733, %734 : i32
llvm.store %735, %714 : i32, !llvm.ptr
cf.br ^bb87
^bb89:
cf.br ^bb90
^bb90:
%736 = llvm.load %709 : !llvm.ptr -> i32
%737 = arith.constant 10 : i32
%738 = arith.cmpi slt, %736, %737 : i32
cf.cond_br %738, ^bb91, ^bb92
^bb91:
%739 = llvm.mlir.addressof @str_2 : !llvm.ptr
%740 = llvm.call @printf(%739) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
%741 = llvm.load %709 : !llvm.ptr -> i32
%742 = arith.constant 1 : i32
%743 = arith.addi %741, %742 : i32
llvm.store %743, %709 : i32, !llvm.ptr
cf.br ^bb90
^bb92:
%744 = llvm.mlir.addressof @str_3 : !llvm.ptr
%745 = llvm.call @printf(%744) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
func.call @free(%489) : (!llvm.ptr) -> ()
func.call @free(%492) : (!llvm.ptr) -> ()
func.call @free(%497) : (!llvm.ptr) -> ()
func.call @free(%500) : (!llvm.ptr) -> ()
func.call @free(%505) : (!llvm.ptr) -> ()
func.call @free(%508) : (!llvm.ptr) -> ()
func.call @free(%513) : (!llvm.ptr) -> ()
func.call @free(%516) : (!llvm.ptr) -> ()
func.call @free(%521) : (!llvm.ptr) -> ()
func.call @free(%524) : (!llvm.ptr) -> ()
func.call @free(%529) : (!llvm.ptr) -> ()
func.call @free(%532) : (!llvm.ptr) -> ()
func.call @free(%537) : (!llvm.ptr) -> ()
func.call @free(%543) : (!llvm.ptr) -> ()
func.call @free(%641) : (!llvm.ptr) -> ()
func.call @free(%647) : (!llvm.ptr) -> ()
func.call @free(%685) : (!llvm.ptr) -> ()
%763 = arith.constant 0 : i32
func.return %763 : i32
}
}