Problem 165
Distinct true intersections among 5000 BBS line segments.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n^2 log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Sweep line or pairwise check |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 165
# Distinct true intersections among 5000 BBS line segments.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function gcd_abs(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
if a < 0 { a = -a }
let mut b: i64 = b0
if b < 0 { b = -b }
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
return a
}
function main() -> i32 {
let nseg: i32 = 5000
let xs0: ptr<i32> = calloc(nseg as i64, 4)
let ys0: ptr<i32> = calloc(nseg as i64, 4)
let xs1: ptr<i32> = calloc(nseg as i64, 4)
let ys1: ptr<i32> = calloc(nseg as i64, 4)
if xs0 == null || ys0 == null || xs1 == null || ys1 == null { return 1 }
let mut state: i64 = 290797
let mut i: i32 = 0
while i < nseg {
state = (state * state) % 50515093
xs0[i] = (state % 500) as i32
state = (state * state) % 50515093
ys0[i] = (state % 500) as i32
state = (state * state) % 50515093
xs1[i] = (state % 500) as i32
state = (state * state) % 50515093
ys1[i] = (state % 500) as i32
i = i + 1
}
# Hash set of reduced rational points (nx,dx,ny,dy)
let cap: i64 = 8388608
let hx: ptr<i64> = calloc(cap, 8)
let hdx: ptr<i64> = calloc(cap, 8)
let hy: ptr<i64> = calloc(cap, 8)
let hdy: ptr<i64> = calloc(cap, 8)
let used: ptr<i8> = calloc(cap, 1)
if hx == null || hdx == null || hy == null || hdy == null || used == null { return 1 }
let mut count: i64 = 0
i = 0
while i < nseg {
let mut j: i32 = i + 1
while j < nseg {
let x0: i64 = xs0[i] as i64
let y0: i64 = ys0[i] as i64
let x1: i64 = xs1[i] as i64
let y1: i64 = ys1[i] as i64
let x2: i64 = xs0[j] as i64
let y2: i64 = ys0[j] as i64
let x3: i64 = xs1[j] as i64
let y3: i64 = ys1[j] as i64
let denom: i64 = (x0 - x1) * (y2 - y3) - (x2 - x3) * (y0 - y1)
if denom != 0 {
let numer0: i64 = (x0 - x2) * (y2 - y3) - (x2 - x3) * (y0 - y2)
let numer1: i64 = (x1 - x0) * (y0 - y2) - (x0 - x2) * (y1 - y0)
# 0 < t0 < 1 and 0 < t1 < 1 with t0=numer0/denom, t1=numer1/denom
let mut ok: bool = false
if denom > 0 {
if numer0 > 0 && numer0 < denom && numer1 > 0 && numer1 < denom {
ok = true
}
} else {
if numer0 < 0 && numer0 > denom && numer1 < 0 && numer1 > denom {
ok = true
}
}
if ok {
# point = (x0,y0) + t0 * ((x1,y1)-(x0,y0))
# px = (x0*denom + numer0*(x1-x0)) / denom
let mut pxn: i64 = x0 * denom + numer0 * (x1 - x0)
let mut pyn: i64 = y0 * denom + numer0 * (y1 - y0)
let mut pxd: i64 = denom
let mut pyd: i64 = denom
let gx: i64 = gcd_abs(pxn, pxd)
pxn = pxn / gx
pxd = pxd / gx
let gy: i64 = gcd_abs(pyn, pyd)
pyn = pyn / gy
pyd = pyd / gy
if pxd < 0 { pxn = -pxn; pxd = -pxd }
if pyd < 0 { pyn = -pyn; pyd = -pyd }
let mut slot: i64 = pxn * 1315423911 + pxd * 2654435761 + pyn * 97531 + pyd
if slot < 0 { slot = -slot }
slot = slot & (cap - 1)
let mut found: bool = false
while used[slot] != 0 {
if hx[slot] == pxn && hdx[slot] == pxd && hy[slot] == pyn && hdy[slot] == pyd {
found = true
break
}
slot = (slot + 1) & (cap - 1)
}
if found == false {
used[slot] = 1
hx[slot] = pxn
hdx[slot] = pxd
hy[slot] = pyn
hdy[slot] = pyd
count = count + 1
}
}
}
j = j + 1
}
i = i + 1
}
printf("%lld\n", count)
free(xs0)
free(ys0)
free(xs1)
free(ys1)
free(hx)
free(hdx)
free(hy)
free(hdy)
free(used)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t gcd_abs_i64_i64(int64_t a0, int64_t b0);
int32_t main(void);
int64_t gcd_abs_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
if (a < 0) {
a = (-a);
}
int64_t b = b0;
if (b < 0) {
b = (-b);
}
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int32_t main(void) {
int32_t nseg = 5000;
int32_t* xs0 = (int32_t*)(calloc(((int64_t)(nseg)), 4));
int32_t* ys0 = (int32_t*)(calloc(((int64_t)(nseg)), 4));
int32_t* xs1 = (int32_t*)(calloc(((int64_t)(nseg)), 4));
int32_t* ys1 = (int32_t*)(calloc(((int64_t)(nseg)), 4));
if ((((xs0 == NULL || ys0 == NULL) || xs1 == NULL) || ys1 == NULL)) {
return 1;
}
int64_t state = 290797;
int32_t i = 0;
while (i < nseg) {
state = FLOW_CHECKED_MOD(((state * state)), (50515093));
xs0[i] = ((int32_t)(FLOW_CHECKED_MOD((state), (500))));
state = FLOW_CHECKED_MOD(((state * state)), (50515093));
ys0[i] = ((int32_t)(FLOW_CHECKED_MOD((state), (500))));
state = FLOW_CHECKED_MOD(((state * state)), (50515093));
xs1[i] = ((int32_t)(FLOW_CHECKED_MOD((state), (500))));
state = FLOW_CHECKED_MOD(((state * state)), (50515093));
ys1[i] = ((int32_t)(FLOW_CHECKED_MOD((state), (500))));
i = (i + 1);
}
int64_t cap = 8388608;
int64_t* hx = (int64_t*)(calloc(cap, 8));
int64_t* hdx = (int64_t*)(calloc(cap, 8));
int64_t* hy = (int64_t*)(calloc(cap, 8));
int64_t* hdy = (int64_t*)(calloc(cap, 8));
int8_t* used = (int8_t*)(calloc(cap, 1));
if (((((hx == NULL || hdx == NULL) || hy == NULL) || hdy == NULL) || used == NULL)) {
return 1;
}
int64_t count = 0;
i = 0;
while (i < nseg) {
int32_t j = (i + 1);
while (j < nseg) {
int64_t x0 = ((int64_t)(xs0[i]));
int64_t y0 = ((int64_t)(ys0[i]));
int64_t x1 = ((int64_t)(xs1[i]));
int64_t y1 = ((int64_t)(ys1[i]));
int64_t x2 = ((int64_t)(xs0[j]));
int64_t y2 = ((int64_t)(ys0[j]));
int64_t x3 = ((int64_t)(xs1[j]));
int64_t y3 = ((int64_t)(ys1[j]));
int64_t denom = (((x0 - x1) * (y2 - y3)) - ((x2 - x3) * (y0 - y1)));
if (denom != 0) {
int64_t numer0 = (((x0 - x2) * (y2 - y3)) - ((x2 - x3) * (y0 - y2)));
int64_t numer1 = (((x1 - x0) * (y0 - y2)) - ((x0 - x2) * (y1 - y0)));
bool ok = 0;
if (denom > 0) {
if ((((numer0 > 0 && numer0 < denom) && numer1 > 0) && numer1 < denom)) {
ok = 1;
}
} else {
if ((((numer0 < 0 && numer0 > denom) && numer1 < 0) && numer1 > denom)) {
ok = 1;
}
}
if (ok) {
int64_t pxn = ((x0 * denom) + (numer0 * (x1 - x0)));
int64_t pyn = ((y0 * denom) + (numer0 * (y1 - y0)));
int64_t pxd = denom;
int64_t pyd = denom;
int64_t gx = gcd_abs_i64_i64(pxn, pxd);
pxn = FLOW_CHECKED_DIV((pxn), (gx));
pxd = FLOW_CHECKED_DIV((pxd), (gx));
int64_t gy = gcd_abs_i64_i64(pyn, pyd);
pyn = FLOW_CHECKED_DIV((pyn), (gy));
pyd = FLOW_CHECKED_DIV((pyd), (gy));
if (pxd < 0) {
pxn = (-pxn);
pxd = (-pxd);
}
if (pyd < 0) {
pyn = (-pyn);
pyd = (-pyd);
}
int64_t slot = ((((pxn * 1315423911) + (pxd * 2654435761)) + (pyn * 97531)) + pyd);
if (slot < 0) {
slot = (-slot);
}
slot = (slot & (cap - 1));
bool found = 0;
while (used[slot] != 0) {
if ((((hx[slot] == pxn && hdx[slot] == pxd) && hy[slot] == pyn) && hdy[slot] == pyd)) {
found = 1;
break;
}
slot = ((slot + 1) & (cap - 1));
}
if (found == 0) {
used[slot] = 1;
hx[slot] = pxn;
hdx[slot] = pxd;
hy[slot] = pyn;
hdy[slot] = pyd;
count = (count + 1);
}
}
}
j = (j + 1);
}
i = (i + 1);
}
printf("%lld\n", count);
free(xs0);
free(ys0);
free(xs1);
free(ys1);
free(hx);
free(hdx);
free(hy);
free(hdy);
free(used);
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 @gcd_abs(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.load %1 : !llvm.ptr -> i64
%3 = arith.constant 0 : i32
%5 = arith.extsi %3 : i32 to i64
%4 = arith.cmpi slt, %2, %5 : i64
cf.cond_br %4, ^bb0, ^bb1
^bb0:
%6 = llvm.load %1 : !llvm.ptr -> i64
%8 = arith.constant 0 : i64
%7 = arith.subi %8, %6 : i64
llvm.store %7, %1 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %10 : i64, !llvm.ptr
%11 = llvm.load %10 : !llvm.ptr -> i64
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi slt, %11, %14 : i64
cf.cond_br %13, ^bb3, ^bb4
^bb3:
%15 = llvm.load %10 : !llvm.ptr -> i64
%17 = arith.constant 0 : i64
%16 = arith.subi %17, %15 : i64
llvm.store %16, %10 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%18 = llvm.load %10 : !llvm.ptr -> i64
%19 = arith.constant 0 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi ne, %18, %21 : i64
cf.cond_br %20, ^bb7, ^bb8
^bb7:
%22 = llvm.load %1 : !llvm.ptr -> i64
%23 = llvm.load %10 : !llvm.ptr -> i64
%24 = arith.remsi %22, %23 : i64
%25 = llvm.load %10 : !llvm.ptr -> i64
llvm.store %25, %1 : i64, !llvm.ptr
llvm.store %24, %10 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%26 = llvm.load %1 : !llvm.ptr -> i64
func.return %26 : i64
}
func.func @main() -> i32 {
%27 = arith.constant 5000 : i32
%29 = arith.extsi %27 : i32 to i64
%30 = arith.constant 4 : i32
%31 = arith.extsi %30 : i32 to i64
%28 = func.call @calloc(%29, %31) : (i64, i64) -> !llvm.ptr
%33 = arith.extsi %27 : i32 to i64
%34 = arith.constant 4 : i32
%35 = arith.extsi %34 : i32 to i64
%32 = func.call @calloc(%33, %35) : (i64, i64) -> !llvm.ptr
%37 = arith.extsi %27 : i32 to i64
%38 = arith.constant 4 : i32
%39 = arith.extsi %38 : i32 to i64
%36 = func.call @calloc(%37, %39) : (i64, i64) -> !llvm.ptr
%41 = arith.extsi %27 : i32 to i64
%42 = arith.constant 4 : i32
%43 = arith.extsi %42 : i32 to i64
%40 = func.call @calloc(%41, %43) : (i64, i64) -> !llvm.ptr
%44 = llvm.mlir.zero : !llvm.ptr
%45 = llvm.icmp "eq" %28, %44 : !llvm.ptr
%46 = scf.if %45 -> (i1) {
%47 = arith.constant true
scf.yield %47 : i1
} else {
%48 = llvm.mlir.zero : !llvm.ptr
%49 = llvm.icmp "eq" %32, %48 : !llvm.ptr
scf.yield %49 : i1
}
%50 = scf.if %46 -> (i1) {
%51 = arith.constant true
scf.yield %51 : i1
} else {
%52 = llvm.mlir.zero : !llvm.ptr
%53 = llvm.icmp "eq" %36, %52 : !llvm.ptr
scf.yield %53 : i1
}
%54 = scf.if %50 -> (i1) {
%55 = arith.constant true
scf.yield %55 : i1
} else {
%56 = llvm.mlir.zero : !llvm.ptr
%57 = llvm.icmp "eq" %40, %56 : !llvm.ptr
scf.yield %57 : i1
}
cf.cond_br %54, ^bb9, ^bb10
^bb9:
%58 = arith.constant 1 : i32
func.return %58 : i32
^bb10:
cf.br ^bb11
^bb11:
%59 = arith.constant 290797 : i32
%60 = arith.extsi %59 : i32 to i64
%61 = llvm.mlir.constant(1 : i64) : i64
%62 = llvm.alloca %61 x i64 : (i64) -> !llvm.ptr
llvm.store %60, %62 : i64, !llvm.ptr
%63 = arith.constant 0 : i32
%64 = llvm.mlir.constant(1 : i64) : i64
%65 = llvm.alloca %64 x i32 : (i64) -> !llvm.ptr
llvm.store %63, %65 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%66 = llvm.load %65 : !llvm.ptr -> i32
%67 = arith.cmpi slt, %66, %27 : i32
cf.cond_br %67, ^bb13, ^bb14
^bb13:
%68 = llvm.load %62 : !llvm.ptr -> i64
%69 = llvm.load %62 : !llvm.ptr -> i64
%70 = arith.muli %68, %69 : i64
%71 = arith.constant 50515093 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.remsi %70, %73 : i64
llvm.store %72, %62 : i64, !llvm.ptr
%74 = llvm.load %62 : !llvm.ptr -> i64
%75 = arith.constant 500 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.remsi %74, %77 : i64
%78 = arith.trunci %76 : i64 to i32
%79 = llvm.load %65 : !llvm.ptr -> i32
%80 = arith.extsi %79 : i32 to i64
%81 = llvm.getelementptr %28[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %78, %81 : i32, !llvm.ptr
%82 = llvm.load %62 : !llvm.ptr -> i64
%83 = llvm.load %62 : !llvm.ptr -> i64
%84 = arith.muli %82, %83 : i64
%85 = arith.constant 50515093 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.remsi %84, %87 : i64
llvm.store %86, %62 : i64, !llvm.ptr
%88 = llvm.load %62 : !llvm.ptr -> i64
%89 = arith.constant 500 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.remsi %88, %91 : i64
%92 = arith.trunci %90 : i64 to i32
%93 = llvm.load %65 : !llvm.ptr -> i32
%94 = arith.extsi %93 : i32 to i64
%95 = llvm.getelementptr %32[%94] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %92, %95 : i32, !llvm.ptr
%96 = llvm.load %62 : !llvm.ptr -> i64
%97 = llvm.load %62 : !llvm.ptr -> i64
%98 = arith.muli %96, %97 : i64
%99 = arith.constant 50515093 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.remsi %98, %101 : i64
llvm.store %100, %62 : i64, !llvm.ptr
%102 = llvm.load %62 : !llvm.ptr -> i64
%103 = arith.constant 500 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.remsi %102, %105 : i64
%106 = arith.trunci %104 : i64 to i32
%107 = llvm.load %65 : !llvm.ptr -> i32
%108 = arith.extsi %107 : i32 to i64
%109 = llvm.getelementptr %36[%108] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %106, %109 : i32, !llvm.ptr
%110 = llvm.load %62 : !llvm.ptr -> i64
%111 = llvm.load %62 : !llvm.ptr -> i64
%112 = arith.muli %110, %111 : i64
%113 = arith.constant 50515093 : i32
%115 = arith.extsi %113 : i32 to i64
%114 = arith.remsi %112, %115 : i64
llvm.store %114, %62 : i64, !llvm.ptr
%116 = llvm.load %62 : !llvm.ptr -> i64
%117 = arith.constant 500 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.remsi %116, %119 : i64
%120 = arith.trunci %118 : i64 to i32
%121 = llvm.load %65 : !llvm.ptr -> i32
%122 = arith.extsi %121 : i32 to i64
%123 = llvm.getelementptr %40[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %120, %123 : i32, !llvm.ptr
%124 = llvm.load %65 : !llvm.ptr -> i32
%125 = arith.constant 1 : i32
%126 = arith.addi %124, %125 : i32
llvm.store %126, %65 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%127 = arith.constant 8388608 : i32
%128 = arith.extsi %127 : i32 to i64
%130 = arith.constant 8 : i32
%131 = arith.extsi %130 : i32 to i64
%129 = func.call @calloc(%128, %131) : (i64, i64) -> !llvm.ptr
%133 = arith.constant 8 : i32
%134 = arith.extsi %133 : i32 to i64
%132 = func.call @calloc(%128, %134) : (i64, i64) -> !llvm.ptr
%136 = arith.constant 8 : i32
%137 = arith.extsi %136 : i32 to i64
%135 = func.call @calloc(%128, %137) : (i64, i64) -> !llvm.ptr
%139 = arith.constant 8 : i32
%140 = arith.extsi %139 : i32 to i64
%138 = func.call @calloc(%128, %140) : (i64, i64) -> !llvm.ptr
%142 = arith.constant 1 : i32
%143 = arith.extsi %142 : i32 to i64
%141 = func.call @calloc(%128, %143) : (i64, i64) -> !llvm.ptr
%144 = llvm.mlir.zero : !llvm.ptr
%145 = llvm.icmp "eq" %129, %144 : !llvm.ptr
%146 = scf.if %145 -> (i1) {
%147 = arith.constant true
scf.yield %147 : i1
} else {
%148 = llvm.mlir.zero : !llvm.ptr
%149 = llvm.icmp "eq" %132, %148 : !llvm.ptr
scf.yield %149 : i1
}
%150 = scf.if %146 -> (i1) {
%151 = arith.constant true
scf.yield %151 : i1
} else {
%152 = llvm.mlir.zero : !llvm.ptr
%153 = llvm.icmp "eq" %135, %152 : !llvm.ptr
scf.yield %153 : i1
}
%154 = scf.if %150 -> (i1) {
%155 = arith.constant true
scf.yield %155 : i1
} else {
%156 = llvm.mlir.zero : !llvm.ptr
%157 = llvm.icmp "eq" %138, %156 : !llvm.ptr
scf.yield %157 : i1
}
%158 = scf.if %154 -> (i1) {
%159 = arith.constant true
scf.yield %159 : i1
} else {
%160 = llvm.mlir.zero : !llvm.ptr
%161 = llvm.icmp "eq" %141, %160 : !llvm.ptr
scf.yield %161 : i1
}
cf.cond_br %158, ^bb15, ^bb16
^bb15:
%162 = arith.constant 1 : i32
func.return %162 : i32
^bb16:
cf.br ^bb17
^bb17:
%163 = arith.constant 0 : i32
%164 = arith.extsi %163 : i32 to i64
%165 = llvm.mlir.constant(1 : i64) : i64
%166 = llvm.alloca %165 x i64 : (i64) -> !llvm.ptr
llvm.store %164, %166 : i64, !llvm.ptr
%167 = arith.constant 0 : i32
llvm.store %167, %65 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%168 = llvm.load %65 : !llvm.ptr -> i32
%169 = arith.cmpi slt, %168, %27 : i32
cf.cond_br %169, ^bb19, ^bb20
^bb19:
%170 = llvm.load %65 : !llvm.ptr -> i32
%171 = arith.constant 1 : i32
%172 = arith.addi %170, %171 : i32
%173 = llvm.mlir.constant(1 : i64) : i64
%174 = llvm.alloca %173 x i32 : (i64) -> !llvm.ptr
llvm.store %172, %174 : i32, !llvm.ptr
cf.br ^bb21
^bb21:
%175 = llvm.load %174 : !llvm.ptr -> i32
%176 = arith.cmpi slt, %175, %27 : i32
cf.cond_br %176, ^bb22, ^bb23
^bb22:
%178 = llvm.load %65 : !llvm.ptr -> i32
%179 = arith.extsi %178 : i32 to i64
%180 = llvm.getelementptr %28[%179] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%177 = llvm.load %180 : !llvm.ptr -> i32
%181 = arith.extsi %177 : i32 to i64
%183 = llvm.load %65 : !llvm.ptr -> i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.getelementptr %32[%184] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%182 = llvm.load %185 : !llvm.ptr -> i32
%186 = arith.extsi %182 : i32 to i64
%188 = llvm.load %65 : !llvm.ptr -> i32
%189 = arith.extsi %188 : i32 to i64
%190 = llvm.getelementptr %36[%189] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%187 = llvm.load %190 : !llvm.ptr -> i32
%191 = arith.extsi %187 : i32 to i64
%193 = llvm.load %65 : !llvm.ptr -> i32
%194 = arith.extsi %193 : i32 to i64
%195 = llvm.getelementptr %40[%194] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%192 = llvm.load %195 : !llvm.ptr -> i32
%196 = arith.extsi %192 : i32 to i64
%198 = llvm.load %174 : !llvm.ptr -> i32
%199 = arith.extsi %198 : i32 to i64
%200 = llvm.getelementptr %28[%199] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%197 = llvm.load %200 : !llvm.ptr -> i32
%201 = arith.extsi %197 : i32 to i64
%203 = llvm.load %174 : !llvm.ptr -> i32
%204 = arith.extsi %203 : i32 to i64
%205 = llvm.getelementptr %32[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%202 = llvm.load %205 : !llvm.ptr -> i32
%206 = arith.extsi %202 : i32 to i64
%208 = llvm.load %174 : !llvm.ptr -> i32
%209 = arith.extsi %208 : i32 to i64
%210 = llvm.getelementptr %36[%209] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%207 = llvm.load %210 : !llvm.ptr -> i32
%211 = arith.extsi %207 : i32 to i64
%213 = llvm.load %174 : !llvm.ptr -> i32
%214 = arith.extsi %213 : i32 to i64
%215 = llvm.getelementptr %40[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%212 = llvm.load %215 : !llvm.ptr -> i32
%216 = arith.extsi %212 : i32 to i64
%217 = arith.subi %181, %191 : i64
%218 = arith.subi %206, %216 : i64
%219 = arith.muli %217, %218 : i64
%220 = arith.subi %201, %211 : i64
%221 = arith.subi %186, %196 : i64
%222 = arith.muli %220, %221 : i64
%223 = arith.subi %219, %222 : i64
%224 = arith.constant 0 : i32
%226 = arith.extsi %224 : i32 to i64
%225 = arith.cmpi ne, %223, %226 : i64
cf.cond_br %225, ^bb24, ^bb25
^bb24:
%227 = arith.subi %181, %201 : i64
%228 = arith.subi %206, %216 : i64
%229 = arith.muli %227, %228 : i64
%230 = arith.subi %201, %211 : i64
%231 = arith.subi %186, %206 : i64
%232 = arith.muli %230, %231 : i64
%233 = arith.subi %229, %232 : i64
%234 = arith.subi %191, %181 : i64
%235 = arith.subi %186, %206 : i64
%236 = arith.muli %234, %235 : i64
%237 = arith.subi %181, %201 : i64
%238 = arith.subi %196, %186 : i64
%239 = arith.muli %237, %238 : i64
%240 = arith.subi %236, %239 : i64
%241 = arith.constant 0 : i1
%242 = llvm.mlir.constant(1 : i64) : i64
%243 = llvm.alloca %242 x i1 : (i64) -> !llvm.ptr
llvm.store %241, %243 : i1, !llvm.ptr
%244 = arith.constant 0 : i32
%246 = arith.extsi %244 : i32 to i64
%245 = arith.cmpi sgt, %223, %246 : i64
cf.cond_br %245, ^bb27, ^bb28
^bb27:
%247 = arith.constant 0 : i32
%249 = arith.extsi %247 : i32 to i64
%248 = arith.cmpi sgt, %233, %249 : i64
%250 = scf.if %248 -> (i1) {
%251 = arith.cmpi slt, %233, %223 : i64
scf.yield %251 : i1
} else {
%252 = arith.constant false
scf.yield %252 : i1
}
%253 = scf.if %250 -> (i1) {
%254 = arith.constant 0 : i32
%256 = arith.extsi %254 : i32 to i64
%255 = arith.cmpi sgt, %240, %256 : i64
scf.yield %255 : i1
} else {
%257 = arith.constant false
scf.yield %257 : i1
}
%258 = scf.if %253 -> (i1) {
%259 = arith.cmpi slt, %240, %223 : i64
scf.yield %259 : i1
} else {
%260 = arith.constant false
scf.yield %260 : i1
}
cf.cond_br %258, ^bb30, ^bb31
^bb30:
%261 = arith.constant 1 : i1
llvm.store %261, %243 : i1, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
cf.br ^bb29
^bb28:
%262 = arith.constant 0 : i32
%264 = arith.extsi %262 : i32 to i64
%263 = arith.cmpi slt, %233, %264 : i64
%265 = scf.if %263 -> (i1) {
%266 = arith.cmpi sgt, %233, %223 : i64
scf.yield %266 : i1
} else {
%267 = arith.constant false
scf.yield %267 : i1
}
%268 = scf.if %265 -> (i1) {
%269 = arith.constant 0 : i32
%271 = arith.extsi %269 : i32 to i64
%270 = arith.cmpi slt, %240, %271 : i64
scf.yield %270 : i1
} else {
%272 = arith.constant false
scf.yield %272 : i1
}
%273 = scf.if %268 -> (i1) {
%274 = arith.cmpi sgt, %240, %223 : i64
scf.yield %274 : i1
} else {
%275 = arith.constant false
scf.yield %275 : i1
}
cf.cond_br %273, ^bb33, ^bb34
^bb33:
%276 = arith.constant 1 : i1
llvm.store %276, %243 : i1, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
cf.br ^bb29
^bb29:
%277 = llvm.load %243 : !llvm.ptr -> i1
cf.cond_br %277, ^bb36, ^bb37
^bb36:
%278 = arith.muli %181, %223 : i64
%279 = arith.subi %191, %181 : i64
%280 = arith.muli %233, %279 : i64
%281 = arith.addi %278, %280 : i64
%282 = llvm.mlir.constant(1 : i64) : i64
%283 = llvm.alloca %282 x i64 : (i64) -> !llvm.ptr
llvm.store %281, %283 : i64, !llvm.ptr
%284 = arith.muli %186, %223 : i64
%285 = arith.subi %196, %186 : i64
%286 = arith.muli %233, %285 : i64
%287 = arith.addi %284, %286 : i64
%288 = llvm.mlir.constant(1 : i64) : i64
%289 = llvm.alloca %288 x i64 : (i64) -> !llvm.ptr
llvm.store %287, %289 : i64, !llvm.ptr
%290 = llvm.mlir.constant(1 : i64) : i64
%291 = llvm.alloca %290 x i64 : (i64) -> !llvm.ptr
llvm.store %223, %291 : i64, !llvm.ptr
%292 = llvm.mlir.constant(1 : i64) : i64
%293 = llvm.alloca %292 x i64 : (i64) -> !llvm.ptr
llvm.store %223, %293 : i64, !llvm.ptr
%295 = llvm.load %283 : !llvm.ptr -> i64
%296 = llvm.load %291 : !llvm.ptr -> i64
%294 = func.call @gcd_abs(%295, %296) : (i64, i64) -> i64
%297 = llvm.load %283 : !llvm.ptr -> i64
%298 = arith.divsi %297, %294 : i64
llvm.store %298, %283 : i64, !llvm.ptr
%299 = llvm.load %291 : !llvm.ptr -> i64
%300 = arith.divsi %299, %294 : i64
llvm.store %300, %291 : i64, !llvm.ptr
%302 = llvm.load %289 : !llvm.ptr -> i64
%303 = llvm.load %293 : !llvm.ptr -> i64
%301 = func.call @gcd_abs(%302, %303) : (i64, i64) -> i64
%304 = llvm.load %289 : !llvm.ptr -> i64
%305 = arith.divsi %304, %301 : i64
llvm.store %305, %289 : i64, !llvm.ptr
%306 = llvm.load %293 : !llvm.ptr -> i64
%307 = arith.divsi %306, %301 : i64
llvm.store %307, %293 : i64, !llvm.ptr
%308 = llvm.load %291 : !llvm.ptr -> i64
%309 = arith.constant 0 : i32
%311 = arith.extsi %309 : i32 to i64
%310 = arith.cmpi slt, %308, %311 : i64
cf.cond_br %310, ^bb39, ^bb40
^bb39:
%312 = llvm.load %283 : !llvm.ptr -> i64
%314 = arith.constant 0 : i64
%313 = arith.subi %314, %312 : i64
llvm.store %313, %283 : i64, !llvm.ptr
%315 = llvm.load %291 : !llvm.ptr -> i64
%317 = arith.constant 0 : i64
%316 = arith.subi %317, %315 : i64
llvm.store %316, %291 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%318 = llvm.load %293 : !llvm.ptr -> i64
%319 = arith.constant 0 : i32
%321 = arith.extsi %319 : i32 to i64
%320 = arith.cmpi slt, %318, %321 : i64
cf.cond_br %320, ^bb42, ^bb43
^bb42:
%322 = llvm.load %289 : !llvm.ptr -> i64
%324 = arith.constant 0 : i64
%323 = arith.subi %324, %322 : i64
llvm.store %323, %289 : i64, !llvm.ptr
%325 = llvm.load %293 : !llvm.ptr -> i64
%327 = arith.constant 0 : i64
%326 = arith.subi %327, %325 : i64
llvm.store %326, %293 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%328 = llvm.load %283 : !llvm.ptr -> i64
%329 = arith.constant 1315423911 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.muli %328, %331 : i64
%332 = llvm.load %291 : !llvm.ptr -> i64
%333 = arith.constant -1640531535 : i32
%335 = arith.extsi %333 : i32 to i64
%334 = arith.muli %332, %335 : i64
%336 = arith.addi %330, %334 : i64
%337 = llvm.load %289 : !llvm.ptr -> i64
%338 = arith.constant 97531 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.muli %337, %340 : i64
%341 = arith.addi %336, %339 : i64
%342 = llvm.load %293 : !llvm.ptr -> i64
%343 = arith.addi %341, %342 : i64
%344 = llvm.mlir.constant(1 : i64) : i64
%345 = llvm.alloca %344 x i64 : (i64) -> !llvm.ptr
llvm.store %343, %345 : i64, !llvm.ptr
%346 = llvm.load %345 : !llvm.ptr -> i64
%347 = arith.constant 0 : i32
%349 = arith.extsi %347 : i32 to i64
%348 = arith.cmpi slt, %346, %349 : i64
cf.cond_br %348, ^bb45, ^bb46
^bb45:
%350 = llvm.load %345 : !llvm.ptr -> i64
%352 = arith.constant 0 : i64
%351 = arith.subi %352, %350 : i64
llvm.store %351, %345 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%353 = llvm.load %345 : !llvm.ptr -> i64
%354 = arith.constant 1 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.subi %128, %356 : i64
%357 = arith.andi %353, %355 : i64
llvm.store %357, %345 : i64, !llvm.ptr
%358 = arith.constant 0 : i1
%359 = llvm.mlir.constant(1 : i64) : i64
%360 = llvm.alloca %359 x i1 : (i64) -> !llvm.ptr
llvm.store %358, %360 : i1, !llvm.ptr
cf.br ^bb48
^bb48:
%362 = llvm.load %345 : !llvm.ptr -> i64
%363 = llvm.getelementptr %141[%362] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%361 = llvm.load %363 : !llvm.ptr -> i8
%364 = arith.constant 0 : i32
%366 = arith.extsi %361 : i8 to i32
%365 = arith.cmpi ne, %366, %364 : i32
cf.cond_br %365, ^bb49, ^bb50
^bb49:
%368 = llvm.load %345 : !llvm.ptr -> i64
%369 = llvm.getelementptr %129[%368] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%367 = llvm.load %369 : !llvm.ptr -> i64
%370 = llvm.load %283 : !llvm.ptr -> i64
%371 = arith.cmpi eq, %367, %370 : i64
%372 = scf.if %371 -> (i1) {
%374 = llvm.load %345 : !llvm.ptr -> i64
%375 = llvm.getelementptr %132[%374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%373 = llvm.load %375 : !llvm.ptr -> i64
%376 = llvm.load %291 : !llvm.ptr -> i64
%377 = arith.cmpi eq, %373, %376 : i64
scf.yield %377 : i1
} else {
%378 = arith.constant false
scf.yield %378 : i1
}
%379 = scf.if %372 -> (i1) {
%381 = llvm.load %345 : !llvm.ptr -> i64
%382 = llvm.getelementptr %135[%381] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%380 = llvm.load %382 : !llvm.ptr -> i64
%383 = llvm.load %289 : !llvm.ptr -> i64
%384 = arith.cmpi eq, %380, %383 : i64
scf.yield %384 : i1
} else {
%385 = arith.constant false
scf.yield %385 : i1
}
%386 = scf.if %379 -> (i1) {
%388 = llvm.load %345 : !llvm.ptr -> i64
%389 = llvm.getelementptr %138[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%387 = llvm.load %389 : !llvm.ptr -> i64
%390 = llvm.load %293 : !llvm.ptr -> i64
%391 = arith.cmpi eq, %387, %390 : i64
scf.yield %391 : i1
} else {
%392 = arith.constant false
scf.yield %392 : i1
}
cf.cond_br %386, ^bb51, ^bb52
^bb51:
%393 = arith.constant 1 : i1
llvm.store %393, %360 : i1, !llvm.ptr
cf.br ^bb50
^bb52:
cf.br ^bb53
^bb53:
%394 = llvm.load %345 : !llvm.ptr -> i64
%395 = arith.constant 1 : i32
%397 = arith.extsi %395 : i32 to i64
%396 = arith.addi %394, %397 : i64
%398 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%399 = arith.subi %128, %400 : i64
%401 = arith.andi %396, %399 : i64
llvm.store %401, %345 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%402 = llvm.load %360 : !llvm.ptr -> i1
%403 = arith.constant 0 : i1
%404 = arith.cmpi eq, %402, %403 : i1
cf.cond_br %404, ^bb54, ^bb55
^bb54:
%405 = arith.constant 1 : i32
%406 = llvm.load %345 : !llvm.ptr -> i64
%407 = arith.trunci %405 : i32 to i8
%408 = llvm.getelementptr %141[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %407, %408 : i8, !llvm.ptr
%409 = llvm.load %283 : !llvm.ptr -> i64
%410 = llvm.load %345 : !llvm.ptr -> i64
%411 = llvm.getelementptr %129[%410] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %409, %411 : i64, !llvm.ptr
%412 = llvm.load %291 : !llvm.ptr -> i64
%413 = llvm.load %345 : !llvm.ptr -> i64
%414 = llvm.getelementptr %132[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %412, %414 : i64, !llvm.ptr
%415 = llvm.load %289 : !llvm.ptr -> i64
%416 = llvm.load %345 : !llvm.ptr -> i64
%417 = llvm.getelementptr %135[%416] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %415, %417 : i64, !llvm.ptr
%418 = llvm.load %293 : !llvm.ptr -> i64
%419 = llvm.load %345 : !llvm.ptr -> i64
%420 = llvm.getelementptr %138[%419] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %418, %420 : i64, !llvm.ptr
%421 = llvm.load %166 : !llvm.ptr -> i64
%422 = arith.constant 1 : i32
%424 = arith.extsi %422 : i32 to i64
%423 = arith.addi %421, %424 : i64
llvm.store %423, %166 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%425 = llvm.load %174 : !llvm.ptr -> i32
%426 = arith.constant 1 : i32
%427 = arith.addi %425, %426 : i32
llvm.store %427, %174 : i32, !llvm.ptr
cf.br ^bb21
^bb23:
%428 = llvm.load %65 : !llvm.ptr -> i32
%429 = arith.constant 1 : i32
%430 = arith.addi %428, %429 : i32
llvm.store %430, %65 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%431 = llvm.mlir.addressof @str_0 : !llvm.ptr
%432 = llvm.load %166 : !llvm.ptr -> i64
%433 = llvm.call @printf(%431, %432) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%28) : (!llvm.ptr) -> ()
func.call @free(%32) : (!llvm.ptr) -> ()
func.call @free(%36) : (!llvm.ptr) -> ()
func.call @free(%40) : (!llvm.ptr) -> ()
func.call @free(%129) : (!llvm.ptr) -> ()
func.call @free(%132) : (!llvm.ptr) -> ()
func.call @free(%135) : (!llvm.ptr) -> ()
func.call @free(%138) : (!llvm.ptr) -> ()
func.call @free(%141) : (!llvm.ptr) -> ()
%443 = arith.constant 0 : i32
func.return %443 : i32
}
}