Problem 500
Smallest n with 2^500500 divisors, mod 500500507. Min-heap keyed by log(value); residues track the modular multiplier.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Smallest number with 2^500500 divisors |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 500
# Smallest n with 2^500500 divisors, mod 500500507.
# Min-heap keyed by log(value); residues track the modular multiplier.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function log(x: f64) -> f64
}
function main() -> i32 {
let TARGET: i64 = 500500
let MOD: i64 = 500500507
let SIEVE_N: i64 = 7376508
let half: i64 = (SIEVE_N >> 1) + 1
let sieve: ptr<i8> = calloc(half, 1)
if sieve == null { return 1 }
sieve[0] = 1
let mut i: i64 = 1
while 2 * i * i < half {
if sieve[i] == 0 {
let mut current: i64 = 3 * i + 1
let step: i64 = 2 * i + 1
while current < half {
sieve[current] = 1
current = current + step
}
}
i = i + 1
}
let heap_log: ptr<f64> = calloc(TARGET + 64, 8)
let heap_res: ptr<i64> = calloc(TARGET + 64, 8)
let heap_fresh: ptr<i8> = calloc(TARGET + 64, 1)
if heap_log == null || heap_res == null || heap_fresh == null { return 1 }
let mut hs: i64 = 0
let mut nextprime: i64 = 2
heap_log[0] = log(2.0)
heap_res[0] = 2
heap_fresh[0] = 1
hs = 1
let mut ans: i64 = 1
let mut step: i64 = 0
while step < TARGET {
let lg: f64 = heap_log[0]
let item: i64 = heap_res[0]
let fresh: i8 = heap_fresh[0]
hs = hs - 1
if hs > 0 {
heap_log[0] = heap_log[hs]
heap_res[0] = heap_res[hs]
heap_fresh[0] = heap_fresh[hs]
let mut idx: i64 = 0
while true {
let l: i64 = 2 * idx + 1
let r: i64 = l + 1
let mut smallest: i64 = idx
if l < hs && heap_log[l] < heap_log[smallest] { smallest = l }
if r < hs && heap_log[r] < heap_log[smallest] { smallest = r }
if smallest == idx { break }
let tl: f64 = heap_log[idx]
let tr: i64 = heap_res[idx]
let tf: i8 = heap_fresh[idx]
heap_log[idx] = heap_log[smallest]
heap_res[idx] = heap_res[smallest]
heap_fresh[idx] = heap_fresh[smallest]
heap_log[smallest] = tl
heap_res[smallest] = tr
heap_fresh[smallest] = tf
idx = smallest
}
}
let tmul: i128 = (ans as i128) * (item as i128) % (MOD as i128)
ans = tmul as i64
# push square of this contribution
let mut idx2: i64 = hs
heap_log[idx2] = lg + lg
let tsq: i128 = (item as i128) * (item as i128) % (MOD as i128)
heap_res[idx2] = tsq as i64
heap_fresh[idx2] = 0
hs = hs + 1
while idx2 > 0 {
let parent: i64 = (idx2 - 1) / 2
if heap_log[parent] <= heap_log[idx2] { break }
let tl: f64 = heap_log[idx2]
let tr: i64 = heap_res[idx2]
let tf: i8 = heap_fresh[idx2]
heap_log[idx2] = heap_log[parent]
heap_res[idx2] = heap_res[parent]
heap_fresh[idx2] = heap_fresh[parent]
heap_log[parent] = tl
heap_res[parent] = tr
heap_fresh[parent] = tf
idx2 = parent
}
if fresh != 0 {
nextprime = nextprime + 1
while true {
let mut is_p: bool = false
if nextprime == 2 {
is_p = true
} else {
if (nextprime & 1) != 0 {
if sieve[nextprime >> 1] == 0 {
is_p = true
}
}
}
if is_p { break }
nextprime = nextprime + 1
}
let mut idx3: i64 = hs
heap_log[idx3] = log(nextprime as f64)
heap_res[idx3] = nextprime % MOD
heap_fresh[idx3] = 1
hs = hs + 1
while idx3 > 0 {
let parent: i64 = (idx3 - 1) / 2
if heap_log[parent] <= heap_log[idx3] { break }
let tl: f64 = heap_log[idx3]
let tr: i64 = heap_res[idx3]
let tf: i8 = heap_fresh[idx3]
heap_log[idx3] = heap_log[parent]
heap_res[idx3] = heap_res[parent]
heap_fresh[idx3] = heap_fresh[parent]
heap_log[parent] = tl
heap_res[parent] = tr
heap_fresh[parent] = tf
idx3 = parent
}
}
step = step + 1
}
printf("%lld\n", ans)
free(heap_fresh)
free(heap_res)
free(heap_log)
free(sieve)
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; }
int32_t main(void);
int32_t main(void) {
int64_t TARGET = 500500;
int64_t MOD = 500500507;
int64_t SIEVE_N = 7376508;
int64_t half = (FLOW_CHECKED_SHR((SIEVE_N), (1)) + 1);
int8_t* sieve = (int8_t*)(calloc(half, 1));
if (sieve == NULL) {
return 1;
}
sieve[0] = 1;
int64_t i = 1;
while (((2 * i) * i) < half) {
if (sieve[i] == 0) {
int64_t current = ((3 * i) + 1);
int64_t step = ((2 * i) + 1);
while (current < half) {
sieve[current] = 1;
current = (current + step);
}
}
i = (i + 1);
}
double* heap_log = (double*)(calloc((TARGET + 64), 8));
int64_t* heap_res = (int64_t*)(calloc((TARGET + 64), 8));
int8_t* heap_fresh = (int8_t*)(calloc((TARGET + 64), 1));
if (((heap_log == NULL || heap_res == NULL) || heap_fresh == NULL)) {
return 1;
}
int64_t hs = 0;
int64_t nextprime = 2;
heap_log[0] = log(2.0);
heap_res[0] = 2;
heap_fresh[0] = 1;
hs = 1;
int64_t ans = 1;
int64_t step = 0;
while (step < TARGET) {
double lg = heap_log[0];
int64_t item = heap_res[0];
int8_t fresh = heap_fresh[0];
hs = (hs - 1);
if (hs > 0) {
heap_log[0] = heap_log[hs];
heap_res[0] = heap_res[hs];
heap_fresh[0] = heap_fresh[hs];
int64_t idx = 0;
while (1) {
int64_t l = ((2 * idx) + 1);
int64_t r = (l + 1);
int64_t smallest = idx;
if ((l < hs && heap_log[l] < heap_log[smallest])) {
smallest = l;
}
if ((r < hs && heap_log[r] < heap_log[smallest])) {
smallest = r;
}
if (smallest == idx) {
break;
}
double tl = heap_log[idx];
int64_t tr = heap_res[idx];
int8_t tf = heap_fresh[idx];
heap_log[idx] = heap_log[smallest];
heap_res[idx] = heap_res[smallest];
heap_fresh[idx] = heap_fresh[smallest];
heap_log[smallest] = tl;
heap_res[smallest] = tr;
heap_fresh[smallest] = tf;
idx = smallest;
}
}
__int128 tmul = FLOW_CHECKED_MOD(((((__int128)(ans)) * ((__int128)(item)))), (((__int128)(MOD))));
ans = ((int64_t)(tmul));
int64_t idx2 = hs;
heap_log[idx2] = (lg + lg);
__int128 tsq = FLOW_CHECKED_MOD(((((__int128)(item)) * ((__int128)(item)))), (((__int128)(MOD))));
heap_res[idx2] = ((int64_t)(tsq));
heap_fresh[idx2] = 0;
hs = (hs + 1);
while (idx2 > 0) {
int64_t parent = FLOW_CHECKED_DIV(((idx2 - 1)), (2));
if (heap_log[parent] <= heap_log[idx2]) {
break;
}
double tl = heap_log[idx2];
int64_t tr = heap_res[idx2];
int8_t tf = heap_fresh[idx2];
heap_log[idx2] = heap_log[parent];
heap_res[idx2] = heap_res[parent];
heap_fresh[idx2] = heap_fresh[parent];
heap_log[parent] = tl;
heap_res[parent] = tr;
heap_fresh[parent] = tf;
idx2 = parent;
}
if (fresh != 0) {
nextprime = (nextprime + 1);
while (1) {
bool is_p = 0;
if (nextprime == 2) {
is_p = 1;
} else {
if ((nextprime & 1) != 0) {
if (sieve[FLOW_CHECKED_SHR((nextprime), (1))] == 0) {
is_p = 1;
}
}
}
if (is_p) {
break;
}
nextprime = (nextprime + 1);
}
int64_t idx3 = hs;
heap_log[idx3] = log(((double)(nextprime)));
heap_res[idx3] = FLOW_CHECKED_MOD((nextprime), (MOD));
heap_fresh[idx3] = 1;
hs = (hs + 1);
while (idx3 > 0) {
int64_t parent = FLOW_CHECKED_DIV(((idx3 - 1)), (2));
if (heap_log[parent] <= heap_log[idx3]) {
break;
}
double tl = heap_log[idx3];
int64_t tr = heap_res[idx3];
int8_t tf = heap_fresh[idx3];
heap_log[idx3] = heap_log[parent];
heap_res[idx3] = heap_res[parent];
heap_fresh[idx3] = heap_fresh[parent];
heap_log[parent] = tl;
heap_res[parent] = tr;
heap_fresh[parent] = tf;
idx3 = parent;
}
}
step = (step + 1);
}
printf("%lld\n", ans);
free(heap_fresh);
free(heap_res);
free(heap_log);
free(sieve);
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 @log(f64) -> f64
func.func @main() -> i32 {
%0 = arith.constant 500500 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 500500507 : i32
%3 = arith.extsi %2 : i32 to i64
%4 = arith.constant 7376508 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = arith.constant 1 : i32
%8 = arith.extsi %6 : i32 to i64
%7 = arith.shrsi %5, %8 : i64
%9 = arith.constant 1 : i32
%11 = arith.extsi %9 : i32 to i64
%10 = arith.addi %7, %11 : i64
%13 = arith.constant 1 : i32
%14 = arith.extsi %13 : i32 to i64
%12 = func.call @calloc(%10, %14) : (i64, i64) -> !llvm.ptr
%15 = llvm.mlir.zero : !llvm.ptr
%16 = llvm.icmp "eq" %12, %15 : !llvm.ptr
cf.cond_br %16, ^bb0, ^bb1
^bb0:
%17 = arith.constant 1 : i32
func.return %17 : i32
^bb1:
cf.br ^bb2
^bb2:
%18 = arith.constant 1 : i32
%19 = arith.constant 0 : i32
%20 = arith.trunci %18 : i32 to i8
%21 = arith.extsi %19 : i32 to i64
%22 = llvm.getelementptr %12[%21] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %20, %22 : i8, !llvm.ptr
%23 = arith.constant 1 : i32
%24 = arith.extsi %23 : i32 to i64
%25 = llvm.mlir.constant(1 : i64) : i64
%26 = llvm.alloca %25 x i64 : (i64) -> !llvm.ptr
llvm.store %24, %26 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%27 = arith.constant 2 : i32
%28 = llvm.load %26 : !llvm.ptr -> i64
%30 = arith.extsi %27 : i32 to i64
%29 = arith.muli %30, %28 : i64
%31 = llvm.load %26 : !llvm.ptr -> i64
%32 = arith.muli %29, %31 : i64
%33 = arith.cmpi slt, %32, %10 : i64
cf.cond_br %33, ^bb4, ^bb5
^bb4:
%35 = llvm.load %26 : !llvm.ptr -> i64
%36 = llvm.getelementptr %12[%35] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%34 = llvm.load %36 : !llvm.ptr -> i8
%37 = arith.constant 0 : i32
%39 = arith.extsi %34 : i8 to i32
%38 = arith.cmpi eq, %39, %37 : i32
cf.cond_br %38, ^bb6, ^bb7
^bb6:
%40 = arith.constant 3 : i32
%41 = llvm.load %26 : !llvm.ptr -> i64
%43 = arith.extsi %40 : i32 to i64
%42 = arith.muli %43, %41 : i64
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.addi %42, %46 : i64
%47 = llvm.mlir.constant(1 : i64) : i64
%48 = llvm.alloca %47 x i64 : (i64) -> !llvm.ptr
llvm.store %45, %48 : i64, !llvm.ptr
%49 = arith.constant 2 : i32
%50 = llvm.load %26 : !llvm.ptr -> i64
%52 = arith.extsi %49 : i32 to i64
%51 = arith.muli %52, %50 : i64
%53 = arith.constant 1 : i32
%55 = arith.extsi %53 : i32 to i64
%54 = arith.addi %51, %55 : i64
cf.br ^bb9
^bb9:
%56 = llvm.load %48 : !llvm.ptr -> i64
%57 = arith.cmpi slt, %56, %10 : i64
cf.cond_br %57, ^bb10, ^bb11
^bb10:
%58 = arith.constant 1 : i32
%59 = llvm.load %48 : !llvm.ptr -> i64
%60 = arith.trunci %58 : i32 to i8
%61 = llvm.getelementptr %12[%59] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %60, %61 : i8, !llvm.ptr
%62 = llvm.load %48 : !llvm.ptr -> i64
%63 = arith.addi %62, %54 : i64
llvm.store %63, %48 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%64 = llvm.load %26 : !llvm.ptr -> i64
%65 = arith.constant 1 : i32
%67 = arith.extsi %65 : i32 to i64
%66 = arith.addi %64, %67 : i64
llvm.store %66, %26 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%69 = arith.constant 64 : i32
%71 = arith.extsi %69 : i32 to i64
%70 = arith.addi %1, %71 : i64
%72 = arith.constant 8 : i32
%73 = arith.extsi %72 : i32 to i64
%68 = func.call @calloc(%70, %73) : (i64, i64) -> !llvm.ptr
%75 = arith.constant 64 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.addi %1, %77 : i64
%78 = arith.constant 8 : i32
%79 = arith.extsi %78 : i32 to i64
%74 = func.call @calloc(%76, %79) : (i64, i64) -> !llvm.ptr
%81 = arith.constant 64 : i32
%83 = arith.extsi %81 : i32 to i64
%82 = arith.addi %1, %83 : i64
%84 = arith.constant 1 : i32
%85 = arith.extsi %84 : i32 to i64
%80 = func.call @calloc(%82, %85) : (i64, i64) -> !llvm.ptr
%86 = llvm.mlir.zero : !llvm.ptr
%87 = llvm.icmp "eq" %68, %86 : !llvm.ptr
%88 = scf.if %87 -> (i1) {
%89 = arith.constant true
scf.yield %89 : i1
} else {
%90 = llvm.mlir.zero : !llvm.ptr
%91 = llvm.icmp "eq" %74, %90 : !llvm.ptr
scf.yield %91 : i1
}
%92 = scf.if %88 -> (i1) {
%93 = arith.constant true
scf.yield %93 : i1
} else {
%94 = llvm.mlir.zero : !llvm.ptr
%95 = llvm.icmp "eq" %80, %94 : !llvm.ptr
scf.yield %95 : i1
}
cf.cond_br %92, ^bb12, ^bb13
^bb12:
%96 = arith.constant 1 : i32
func.return %96 : i32
^bb13:
cf.br ^bb14
^bb14:
%97 = arith.constant 0 : i32
%98 = arith.extsi %97 : i32 to i64
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %98, %100 : i64, !llvm.ptr
%101 = arith.constant 2 : i32
%102 = arith.extsi %101 : i32 to i64
%103 = llvm.mlir.constant(1 : i64) : i64
%104 = llvm.alloca %103 x i64 : (i64) -> !llvm.ptr
llvm.store %102, %104 : i64, !llvm.ptr
%105 = arith.constant 2.0 : f32
%106 = math.log %105 : f32
%107 = arith.constant 0 : i32
%108 = arith.extf %106 : f32 to f64
%109 = arith.extsi %107 : i32 to i64
%110 = llvm.getelementptr %68[%109] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %108, %110 : f64, !llvm.ptr
%111 = arith.constant 2 : i32
%112 = arith.constant 0 : i32
%113 = arith.extsi %111 : i32 to i64
%114 = arith.extsi %112 : i32 to i64
%115 = llvm.getelementptr %74[%114] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %113, %115 : i64, !llvm.ptr
%116 = arith.constant 1 : i32
%117 = arith.constant 0 : i32
%118 = arith.trunci %116 : i32 to i8
%119 = arith.extsi %117 : i32 to i64
%120 = llvm.getelementptr %80[%119] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %118, %120 : i8, !llvm.ptr
%121 = arith.constant 1 : i32
%122 = arith.extsi %121 : i32 to i64
llvm.store %122, %100 : i64, !llvm.ptr
%123 = arith.constant 1 : i32
%124 = arith.extsi %123 : i32 to i64
%125 = llvm.mlir.constant(1 : i64) : i64
%126 = llvm.alloca %125 x i64 : (i64) -> !llvm.ptr
llvm.store %124, %126 : i64, !llvm.ptr
%127 = arith.constant 0 : i32
%128 = arith.extsi %127 : i32 to i64
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i64 : (i64) -> !llvm.ptr
llvm.store %128, %130 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%131 = llvm.load %130 : !llvm.ptr -> i64
%132 = arith.cmpi slt, %131, %1 : i64
cf.cond_br %132, ^bb16, ^bb17
^bb16:
%134 = arith.constant 0 : i32
%135 = arith.extsi %134 : i32 to i64
%136 = llvm.getelementptr %68[%135] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%133 = llvm.load %136 : !llvm.ptr -> f64
%138 = arith.constant 0 : i32
%139 = arith.extsi %138 : i32 to i64
%140 = llvm.getelementptr %74[%139] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%137 = llvm.load %140 : !llvm.ptr -> i64
%142 = arith.constant 0 : i32
%143 = arith.extsi %142 : i32 to i64
%144 = llvm.getelementptr %80[%143] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%141 = llvm.load %144 : !llvm.ptr -> i8
%145 = llvm.load %100 : !llvm.ptr -> i64
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.subi %145, %148 : i64
llvm.store %147, %100 : i64, !llvm.ptr
%149 = llvm.load %100 : !llvm.ptr -> i64
%150 = arith.constant 0 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.cmpi sgt, %149, %152 : i64
cf.cond_br %151, ^bb18, ^bb19
^bb18:
%154 = llvm.load %100 : !llvm.ptr -> i64
%155 = llvm.getelementptr %68[%154] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%153 = llvm.load %155 : !llvm.ptr -> f64
%156 = arith.constant 0 : i32
%157 = arith.extsi %156 : i32 to i64
%158 = llvm.getelementptr %68[%157] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %153, %158 : f64, !llvm.ptr
%160 = llvm.load %100 : !llvm.ptr -> i64
%161 = llvm.getelementptr %74[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%159 = llvm.load %161 : !llvm.ptr -> i64
%162 = arith.constant 0 : i32
%163 = arith.extsi %162 : i32 to i64
%164 = llvm.getelementptr %74[%163] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %159, %164 : i64, !llvm.ptr
%166 = llvm.load %100 : !llvm.ptr -> i64
%167 = llvm.getelementptr %80[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%165 = llvm.load %167 : !llvm.ptr -> i8
%168 = arith.constant 0 : i32
%169 = arith.extsi %168 : i32 to i64
%170 = llvm.getelementptr %80[%169] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %165, %170 : i8, !llvm.ptr
%171 = arith.constant 0 : i32
%172 = arith.extsi %171 : i32 to i64
%173 = llvm.mlir.constant(1 : i64) : i64
%174 = llvm.alloca %173 x i64 : (i64) -> !llvm.ptr
llvm.store %172, %174 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%175 = arith.constant 1 : i1
cf.cond_br %175, ^bb22, ^bb23
^bb22:
%176 = arith.constant 2 : i32
%177 = llvm.load %174 : !llvm.ptr -> i64
%179 = arith.extsi %176 : i32 to i64
%178 = arith.muli %179, %177 : i64
%180 = arith.constant 1 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.addi %178, %182 : i64
%183 = arith.constant 1 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.addi %181, %185 : i64
%186 = llvm.load %174 : !llvm.ptr -> i64
%187 = llvm.mlir.constant(1 : i64) : i64
%188 = llvm.alloca %187 x i64 : (i64) -> !llvm.ptr
llvm.store %186, %188 : i64, !llvm.ptr
%189 = llvm.load %100 : !llvm.ptr -> i64
%190 = arith.cmpi slt, %181, %189 : i64
%191 = scf.if %190 -> (i1) {
%193 = llvm.getelementptr %68[%181] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%192 = llvm.load %193 : !llvm.ptr -> f64
%195 = llvm.load %188 : !llvm.ptr -> i64
%196 = llvm.getelementptr %68[%195] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%194 = llvm.load %196 : !llvm.ptr -> f64
%197 = arith.cmpf olt, %192, %194 : f64
scf.yield %197 : i1
} else {
%198 = arith.constant false
scf.yield %198 : i1
}
cf.cond_br %191, ^bb24, ^bb25
^bb24:
llvm.store %181, %188 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%199 = llvm.load %100 : !llvm.ptr -> i64
%200 = arith.cmpi slt, %184, %199 : i64
%201 = scf.if %200 -> (i1) {
%203 = llvm.getelementptr %68[%184] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%202 = llvm.load %203 : !llvm.ptr -> f64
%205 = llvm.load %188 : !llvm.ptr -> i64
%206 = llvm.getelementptr %68[%205] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%204 = llvm.load %206 : !llvm.ptr -> f64
%207 = arith.cmpf olt, %202, %204 : f64
scf.yield %207 : i1
} else {
%208 = arith.constant false
scf.yield %208 : i1
}
cf.cond_br %201, ^bb27, ^bb28
^bb27:
llvm.store %184, %188 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%209 = llvm.load %188 : !llvm.ptr -> i64
%210 = llvm.load %174 : !llvm.ptr -> i64
%211 = arith.cmpi eq, %209, %210 : i64
cf.cond_br %211, ^bb30, ^bb31
^bb30:
cf.br ^bb23
^bb31:
cf.br ^bb32
^bb32:
%213 = llvm.load %174 : !llvm.ptr -> i64
%214 = llvm.getelementptr %68[%213] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%212 = llvm.load %214 : !llvm.ptr -> f64
%216 = llvm.load %174 : !llvm.ptr -> i64
%217 = llvm.getelementptr %74[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%215 = llvm.load %217 : !llvm.ptr -> i64
%219 = llvm.load %174 : !llvm.ptr -> i64
%220 = llvm.getelementptr %80[%219] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%218 = llvm.load %220 : !llvm.ptr -> i8
%222 = llvm.load %188 : !llvm.ptr -> i64
%223 = llvm.getelementptr %68[%222] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%221 = llvm.load %223 : !llvm.ptr -> f64
%224 = llvm.load %174 : !llvm.ptr -> i64
%225 = llvm.getelementptr %68[%224] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %221, %225 : f64, !llvm.ptr
%227 = llvm.load %188 : !llvm.ptr -> i64
%228 = llvm.getelementptr %74[%227] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%226 = llvm.load %228 : !llvm.ptr -> i64
%229 = llvm.load %174 : !llvm.ptr -> i64
%230 = llvm.getelementptr %74[%229] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %226, %230 : i64, !llvm.ptr
%232 = llvm.load %188 : !llvm.ptr -> i64
%233 = llvm.getelementptr %80[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%231 = llvm.load %233 : !llvm.ptr -> i8
%234 = llvm.load %174 : !llvm.ptr -> i64
%235 = llvm.getelementptr %80[%234] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %231, %235 : i8, !llvm.ptr
%236 = llvm.load %188 : !llvm.ptr -> i64
%237 = llvm.getelementptr %68[%236] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %212, %237 : f64, !llvm.ptr
%238 = llvm.load %188 : !llvm.ptr -> i64
%239 = llvm.getelementptr %74[%238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %215, %239 : i64, !llvm.ptr
%240 = llvm.load %188 : !llvm.ptr -> i64
%241 = llvm.getelementptr %80[%240] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %218, %241 : i8, !llvm.ptr
%242 = llvm.load %188 : !llvm.ptr -> i64
llvm.store %242, %174 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%243 = llvm.load %126 : !llvm.ptr -> i64
%244 = arith.extsi %243 : i64 to i128
%245 = arith.extsi %137 : i64 to i128
%247 = arith.trunci %244 : i128 to i64
%248 = arith.trunci %245 : i128 to i64
%246 = arith.muli %247, %248 : i64
%249 = arith.extsi %3 : i64 to i128
%251 = arith.trunci %249 : i128 to i64
%250 = arith.remsi %246, %251 : i64
%252 = arith.extsi %250 : i64 to i128
%253 = arith.trunci %252 : i128 to i64
llvm.store %253, %126 : i64, !llvm.ptr
%254 = llvm.load %100 : !llvm.ptr -> i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %254, %256 : i64, !llvm.ptr
%257 = arith.addf %133, %133 : f64
%258 = llvm.load %256 : !llvm.ptr -> i64
%259 = llvm.getelementptr %68[%258] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %257, %259 : f64, !llvm.ptr
%260 = arith.extsi %137 : i64 to i128
%261 = arith.extsi %137 : i64 to i128
%263 = arith.trunci %260 : i128 to i64
%264 = arith.trunci %261 : i128 to i64
%262 = arith.muli %263, %264 : i64
%265 = arith.extsi %3 : i64 to i128
%267 = arith.trunci %265 : i128 to i64
%266 = arith.remsi %262, %267 : i64
%268 = arith.extsi %266 : i64 to i128
%269 = arith.trunci %268 : i128 to i64
%270 = llvm.load %256 : !llvm.ptr -> i64
%271 = llvm.getelementptr %74[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %269, %271 : i64, !llvm.ptr
%272 = arith.constant 0 : i32
%273 = llvm.load %256 : !llvm.ptr -> i64
%274 = arith.trunci %272 : i32 to i8
%275 = llvm.getelementptr %80[%273] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %274, %275 : i8, !llvm.ptr
%276 = llvm.load %100 : !llvm.ptr -> i64
%277 = arith.constant 1 : i32
%279 = arith.extsi %277 : i32 to i64
%278 = arith.addi %276, %279 : i64
llvm.store %278, %100 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%280 = llvm.load %256 : !llvm.ptr -> i64
%281 = arith.constant 0 : i32
%283 = arith.extsi %281 : i32 to i64
%282 = arith.cmpi sgt, %280, %283 : i64
cf.cond_br %282, ^bb34, ^bb35
^bb34:
%284 = llvm.load %256 : !llvm.ptr -> i64
%285 = arith.constant 1 : i32
%287 = arith.extsi %285 : i32 to i64
%286 = arith.subi %284, %287 : i64
%288 = arith.constant 2 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.divsi %286, %290 : i64
%292 = llvm.getelementptr %68[%289] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%291 = llvm.load %292 : !llvm.ptr -> f64
%294 = llvm.load %256 : !llvm.ptr -> i64
%295 = llvm.getelementptr %68[%294] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%293 = llvm.load %295 : !llvm.ptr -> f64
%296 = arith.cmpf ole, %291, %293 : f64
cf.cond_br %296, ^bb36, ^bb37
^bb36:
cf.br ^bb35
^bb37:
cf.br ^bb38
^bb38:
%298 = llvm.load %256 : !llvm.ptr -> i64
%299 = llvm.getelementptr %68[%298] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%297 = llvm.load %299 : !llvm.ptr -> f64
%301 = llvm.load %256 : !llvm.ptr -> i64
%302 = llvm.getelementptr %74[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%300 = llvm.load %302 : !llvm.ptr -> i64
%304 = llvm.load %256 : !llvm.ptr -> i64
%305 = llvm.getelementptr %80[%304] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%303 = llvm.load %305 : !llvm.ptr -> i8
%307 = llvm.getelementptr %68[%289] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%306 = llvm.load %307 : !llvm.ptr -> f64
%308 = llvm.load %256 : !llvm.ptr -> i64
%309 = llvm.getelementptr %68[%308] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %306, %309 : f64, !llvm.ptr
%311 = llvm.getelementptr %74[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%310 = llvm.load %311 : !llvm.ptr -> i64
%312 = llvm.load %256 : !llvm.ptr -> i64
%313 = llvm.getelementptr %74[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %310, %313 : i64, !llvm.ptr
%315 = llvm.getelementptr %80[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%314 = llvm.load %315 : !llvm.ptr -> i8
%316 = llvm.load %256 : !llvm.ptr -> i64
%317 = llvm.getelementptr %80[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %314, %317 : i8, !llvm.ptr
%318 = llvm.getelementptr %68[%289] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %297, %318 : f64, !llvm.ptr
%319 = llvm.getelementptr %74[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %300, %319 : i64, !llvm.ptr
%320 = llvm.getelementptr %80[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %303, %320 : i8, !llvm.ptr
llvm.store %289, %256 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%321 = arith.constant 0 : i32
%323 = arith.extsi %141 : i8 to i32
%322 = arith.cmpi ne, %323, %321 : i32
cf.cond_br %322, ^bb39, ^bb40
^bb39:
%324 = llvm.load %104 : !llvm.ptr -> i64
%325 = arith.constant 1 : i32
%327 = arith.extsi %325 : i32 to i64
%326 = arith.addi %324, %327 : i64
llvm.store %326, %104 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%328 = arith.constant 1 : i1
cf.cond_br %328, ^bb43, ^bb44
^bb43:
%329 = arith.constant 0 : i1
%330 = llvm.mlir.constant(1 : i64) : i64
%331 = llvm.alloca %330 x i1 : (i64) -> !llvm.ptr
llvm.store %329, %331 : i1, !llvm.ptr
%332 = llvm.load %104 : !llvm.ptr -> i64
%333 = arith.constant 2 : i32
%335 = arith.extsi %333 : i32 to i64
%334 = arith.cmpi eq, %332, %335 : i64
cf.cond_br %334, ^bb45, ^bb46
^bb45:
%336 = arith.constant 1 : i1
llvm.store %336, %331 : i1, !llvm.ptr
cf.br ^bb47
^bb46:
%337 = llvm.load %104 : !llvm.ptr -> i64
%338 = arith.constant 1 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.andi %337, %340 : i64
%341 = arith.constant 0 : i32
%343 = arith.extsi %341 : i32 to i64
%342 = arith.cmpi ne, %339, %343 : i64
cf.cond_br %342, ^bb48, ^bb49
^bb48:
%345 = llvm.load %104 : !llvm.ptr -> i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.shrsi %345, %348 : i64
%349 = llvm.getelementptr %12[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%344 = llvm.load %349 : !llvm.ptr -> i8
%350 = arith.constant 0 : i32
%352 = arith.extsi %344 : i8 to i32
%351 = arith.cmpi eq, %352, %350 : i32
cf.cond_br %351, ^bb51, ^bb52
^bb51:
%353 = arith.constant 1 : i1
llvm.store %353, %331 : i1, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
cf.br ^bb47
^bb47:
%354 = llvm.load %331 : !llvm.ptr -> i1
cf.cond_br %354, ^bb54, ^bb55
^bb54:
cf.br ^bb44
^bb55:
cf.br ^bb56
^bb56:
%355 = llvm.load %104 : !llvm.ptr -> i64
%356 = arith.constant 1 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.addi %355, %358 : i64
llvm.store %357, %104 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%359 = llvm.load %100 : !llvm.ptr -> i64
%360 = llvm.mlir.constant(1 : i64) : i64
%361 = llvm.alloca %360 x i64 : (i64) -> !llvm.ptr
llvm.store %359, %361 : i64, !llvm.ptr
%362 = llvm.load %104 : !llvm.ptr -> i64
%363 = arith.sitofp %362 : i64 to f64
%364 = math.log %363 : f64
%365 = llvm.load %361 : !llvm.ptr -> i64
%366 = llvm.getelementptr %68[%365] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %364, %366 : f64, !llvm.ptr
%367 = llvm.load %104 : !llvm.ptr -> i64
%368 = arith.remsi %367, %3 : i64
%369 = llvm.load %361 : !llvm.ptr -> i64
%370 = llvm.getelementptr %74[%369] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %368, %370 : i64, !llvm.ptr
%371 = arith.constant 1 : i32
%372 = llvm.load %361 : !llvm.ptr -> i64
%373 = arith.trunci %371 : i32 to i8
%374 = llvm.getelementptr %80[%372] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %373, %374 : i8, !llvm.ptr
%375 = llvm.load %100 : !llvm.ptr -> i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %375, %378 : i64
llvm.store %377, %100 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%379 = llvm.load %361 : !llvm.ptr -> i64
%380 = arith.constant 0 : i32
%382 = arith.extsi %380 : i32 to i64
%381 = arith.cmpi sgt, %379, %382 : i64
cf.cond_br %381, ^bb58, ^bb59
^bb58:
%383 = llvm.load %361 : !llvm.ptr -> i64
%384 = arith.constant 1 : i32
%386 = arith.extsi %384 : i32 to i64
%385 = arith.subi %383, %386 : i64
%387 = arith.constant 2 : i32
%389 = arith.extsi %387 : i32 to i64
%388 = arith.divsi %385, %389 : i64
%391 = llvm.getelementptr %68[%388] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%390 = llvm.load %391 : !llvm.ptr -> f64
%393 = llvm.load %361 : !llvm.ptr -> i64
%394 = llvm.getelementptr %68[%393] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%392 = llvm.load %394 : !llvm.ptr -> f64
%395 = arith.cmpf ole, %390, %392 : f64
cf.cond_br %395, ^bb60, ^bb61
^bb60:
cf.br ^bb59
^bb61:
cf.br ^bb62
^bb62:
%397 = llvm.load %361 : !llvm.ptr -> i64
%398 = llvm.getelementptr %68[%397] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%396 = llvm.load %398 : !llvm.ptr -> f64
%400 = llvm.load %361 : !llvm.ptr -> i64
%401 = llvm.getelementptr %74[%400] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%399 = llvm.load %401 : !llvm.ptr -> i64
%403 = llvm.load %361 : !llvm.ptr -> i64
%404 = llvm.getelementptr %80[%403] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%402 = llvm.load %404 : !llvm.ptr -> i8
%406 = llvm.getelementptr %68[%388] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%405 = llvm.load %406 : !llvm.ptr -> f64
%407 = llvm.load %361 : !llvm.ptr -> i64
%408 = llvm.getelementptr %68[%407] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %405, %408 : f64, !llvm.ptr
%410 = llvm.getelementptr %74[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%409 = llvm.load %410 : !llvm.ptr -> i64
%411 = llvm.load %361 : !llvm.ptr -> i64
%412 = llvm.getelementptr %74[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %409, %412 : i64, !llvm.ptr
%414 = llvm.getelementptr %80[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%413 = llvm.load %414 : !llvm.ptr -> i8
%415 = llvm.load %361 : !llvm.ptr -> i64
%416 = llvm.getelementptr %80[%415] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %413, %416 : i8, !llvm.ptr
%417 = llvm.getelementptr %68[%388] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %396, %417 : f64, !llvm.ptr
%418 = llvm.getelementptr %74[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %399, %418 : i64, !llvm.ptr
%419 = llvm.getelementptr %80[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %402, %419 : i8, !llvm.ptr
llvm.store %388, %361 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%420 = llvm.load %130 : !llvm.ptr -> i64
%421 = arith.constant 1 : i32
%423 = arith.extsi %421 : i32 to i64
%422 = arith.addi %420, %423 : i64
llvm.store %422, %130 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%424 = llvm.mlir.addressof @str_0 : !llvm.ptr
%425 = llvm.load %126 : !llvm.ptr -> i64
%426 = llvm.call @printf(%424, %425) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%80) : (!llvm.ptr) -> ()
func.call @free(%74) : (!llvm.ptr) -> ()
func.call @free(%68) : (!llvm.ptr) -> ()
func.call @free(%12) : (!llvm.ptr) -> ()
%431 = arith.constant 0 : i32
func.return %431 : i32
}
}