Problem 451

Modular Inverses — sum I(n) for 3..2e7 via SPF + CRT root expansion.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 451
# Modular Inverses — sum I(n) for 3..2e7 via SPF + CRT root expansion.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

function modinv(a0: i64, m: i64) -> i64 {
    let mut a: i64 = a0 % m
    let mut b: i64 = m
    let mut x0: i64 = 1
    let mut x1: i64 = 0
    while b != 0 {
        let q: i64 = a / b
        let t: i64 = a - q * b
        a = b
        b = t
        let tx: i64 = x0 - q * x1
        x0 = x1
        x1 = tx
    }
    if x0 < 0 { x0 = x0 + m }
    return x0
}

function I_n(n: i64, spf: ptr<i32>, roots: ptr<i64>) -> i64 {
    let mut rc: i32 = 1
    roots[0] = n - 1
    let mut best: i64 = 1
    let mut remaining: i64 = n
    while remaining > 1 {
        let p: i64 = spf[remaining] as i64
        let mut prime_power: i64 = 1
        while remaining % p == 0 {
            remaining = remaining / p
            prime_power = prime_power * p
        }
        if prime_power == 2 {
            continue
        }
        let cofactor: i64 = n / prime_power
        let projector: i64 = cofactor * modinv(cofactor % prime_power, prime_power) % n
        let delta_two: i64 = (2 * projector) % n
        let mut has_extra: bool = false
        let mut delta_half: i64 = 0
        let mut delta_half_plus_two: i64 = 0
        if prime_power % 2 == 0 && prime_power >= 8 {
            has_extra = true
            let half: i64 = prime_power / 2
            delta_half = (half * projector) % n
            delta_half_plus_two = ((half + 2) * projector) % n
        }
        let prev_rc: i32 = rc
        let mut i: i32 = 0
        while i < prev_rc {
            let root: i64 = roots[i]
            let candidate: i64 = (root + delta_two) % n
            roots[rc] = candidate
            rc = rc + 1
            if best < candidate && candidate < n - 1 {
                best = candidate
            }
            if has_extra {
                let c2: i64 = (root + delta_half) % n
                roots[rc] = c2
                rc = rc + 1
                if best < c2 && c2 < n - 1 { best = c2 }
                let c3: i64 = (root + delta_half_plus_two) % n
                roots[rc] = c3
                rc = rc + 1
                if best < c3 && c3 < n - 1 { best = c3 }
            }
            i = i + 1
        }
    }
    return best
}

function main() -> i32 {
    let LIMIT: i64 = 20000000
    let spf: ptr<i32> = calloc(LIMIT + 1, 4)
    let roots: ptr<i64> = calloc(256, 8)
    if spf == null || roots == null { return 1 }
    let mut i: i64 = 0
    while i <= LIMIT {
        spf[i] = i as i32
        i = i + 1
    }
    i = 2
    while i * i <= LIMIT {
        if (spf[i] as i64) == i {
            let mut j: i64 = i * i
            while j <= LIMIT {
                if (spf[j] as i64) == j {
                    spf[j] = i as i32
                }
                j = j + i
            }
        }
        i = i + 1
    }
    let mut total: i64 = 0
    let mut n: i64 = 3
    while n <= LIMIT {
        total = total + I_n(n, spf, roots)
        n = n + 1
    }
    printf("%lld\n", total)
    free(roots)
    free(spf)
    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 modinv_i64_i64(int64_t a0, int64_t m);
int64_t I_n_i64_ptr_i32_ptr_i64(int64_t n, int32_t* spf, int64_t* roots);
int32_t main(void);



int64_t modinv_i64_i64(int64_t a0, int64_t m) {
    int64_t a = FLOW_CHECKED_MOD((a0), (m));
    int64_t b = m;
    int64_t x0 = 1;
    int64_t x1 = 0;
    while (b != 0) {
        int64_t q = FLOW_CHECKED_DIV((a), (b));
        int64_t t = (a - (q * b));
        a = b;
        b = t;
        int64_t tx = (x0 - (q * x1));
        x0 = x1;
        x1 = tx;
    }
    if (x0 < 0) {
        x0 = (x0 + m);
    }
    return x0;
}

int64_t I_n_i64_ptr_i32_ptr_i64(int64_t n, int32_t* spf, int64_t* roots) {
    int32_t rc = 1;
    roots[0] = (n - 1);
    int64_t best = 1;
    int64_t remaining = n;
    while (remaining > 1) {
        int64_t p = ((int64_t)(spf[remaining]));
        int64_t prime_power = 1;
        while (FLOW_CHECKED_MOD((remaining), (p)) == 0) {
            remaining = FLOW_CHECKED_DIV((remaining), (p));
            prime_power = (prime_power * p);
        }
        if (prime_power == 2) {
            continue;
        }
        int64_t cofactor = FLOW_CHECKED_DIV((n), (prime_power));
        int64_t projector = FLOW_CHECKED_MOD(((cofactor * modinv_i64_i64(FLOW_CHECKED_MOD((cofactor), (prime_power)), prime_power))), (n));
        int64_t delta_two = FLOW_CHECKED_MOD(((2 * projector)), (n));
        bool has_extra = 0;
        int64_t delta_half = 0;
        int64_t delta_half_plus_two = 0;
        if ((FLOW_CHECKED_MOD((prime_power), (2)) == 0 && prime_power >= 8)) {
            has_extra = 1;
            int64_t half = FLOW_CHECKED_DIV((prime_power), (2));
            delta_half = FLOW_CHECKED_MOD(((half * projector)), (n));
            delta_half_plus_two = FLOW_CHECKED_MOD((((half + 2) * projector)), (n));
        }
        int32_t prev_rc = rc;
        int32_t i = 0;
        while (i < prev_rc) {
            int64_t root = roots[i];
            int64_t candidate = FLOW_CHECKED_MOD(((root + delta_two)), (n));
            roots[rc] = candidate;
            rc = (rc + 1);
            if ((best < candidate && candidate < (n - 1))) {
                best = candidate;
            }
            if (has_extra) {
                int64_t c2 = FLOW_CHECKED_MOD(((root + delta_half)), (n));
                roots[rc] = c2;
                rc = (rc + 1);
                if ((best < c2 && c2 < (n - 1))) {
                    best = c2;
                }
                int64_t c3 = FLOW_CHECKED_MOD(((root + delta_half_plus_two)), (n));
                roots[rc] = c3;
                rc = (rc + 1);
                if ((best < c3 && c3 < (n - 1))) {
                    best = c3;
                }
            }
            i = (i + 1);
        }
    }
    return best;
}

int32_t main(void) {
    int64_t LIMIT = 20000000;
    int32_t* spf = (int32_t*)(calloc((LIMIT + 1), 4));
    int64_t* roots = (int64_t*)(calloc(256, 8));
    if ((spf == NULL || roots == NULL)) {
        return 1;
    }
    int64_t i = 0;
    while (i <= LIMIT) {
        spf[i] = ((int32_t)(i));
        i = (i + 1);
    }
    i = 2;
    while ((i * i) <= LIMIT) {
        if (((int64_t)(spf[i])) == i) {
            int64_t j = (i * i);
            while (j <= LIMIT) {
                if (((int64_t)(spf[j])) == j) {
                    spf[j] = ((int32_t)(i));
                }
                j = (j + i);
            }
        }
        i = (i + 1);
    }
    int64_t total = 0;
    int64_t n = 3;
    while (n <= LIMIT) {
        total = (total + I_n_i64_ptr_i32_ptr_i64(n, spf, roots));
        n = (n + 1);
    }
    printf("%lld\n", total);
    free(roots);
    free(spf);
    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 @modinv(%arg0: i64, %arg1: i64) -> i64 {
    %0 = arith.remsi %arg0, %arg1 : i64
    %1 = llvm.mlir.constant(1 : i64) : i64
    %2 = llvm.alloca %1 x i64 : (i64) -> !llvm.ptr
    llvm.store %0, %2 : i64, !llvm.ptr
    %3 = llvm.mlir.constant(1 : i64) : i64
    %4 = llvm.alloca %3 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %4 : i64, !llvm.ptr
    %5 = arith.constant 1 : i32
    %6 = arith.extsi %5 : i32 to i64
    %7 = llvm.mlir.constant(1 : i64) : i64
    %8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
    llvm.store %6, %8 : i64, !llvm.ptr
    %9 = arith.constant 0 : i32
    %10 = arith.extsi %9 : i32 to i64
    %11 = llvm.mlir.constant(1 : i64) : i64
    %12 = llvm.alloca %11 x i64 : (i64) -> !llvm.ptr
    llvm.store %10, %12 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %13 = llvm.load %4 : !llvm.ptr -> i64
    %14 = arith.constant 0 : i32
    %16 = arith.extsi %14 : i32 to i64
    %15 = arith.cmpi ne, %13, %16 : i64
    cf.cond_br %15, ^bb1, ^bb2
    ^bb1:
      %17 = llvm.load %2 : !llvm.ptr -> i64
      %18 = llvm.load %4 : !llvm.ptr -> i64
      %19 = arith.divsi %17, %18 : i64
      %20 = llvm.load %2 : !llvm.ptr -> i64
      %21 = llvm.load %4 : !llvm.ptr -> i64
      %22 = arith.muli %19, %21 : i64
      %23 = arith.subi %20, %22 : i64
      %24 = llvm.load %4 : !llvm.ptr -> i64
      llvm.store %24, %2 : i64, !llvm.ptr
      llvm.store %23, %4 : i64, !llvm.ptr
      %25 = llvm.load %8 : !llvm.ptr -> i64
      %26 = llvm.load %12 : !llvm.ptr -> i64
      %27 = arith.muli %19, %26 : i64
      %28 = arith.subi %25, %27 : i64
      %29 = llvm.load %12 : !llvm.ptr -> i64
      llvm.store %29, %8 : i64, !llvm.ptr
      llvm.store %28, %12 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %30 = llvm.load %8 : !llvm.ptr -> i64
    %31 = arith.constant 0 : i32
    %33 = arith.extsi %31 : i32 to i64
    %32 = arith.cmpi slt, %30, %33 : i64
    cf.cond_br %32, ^bb3, ^bb4
    ^bb3:
      %34 = llvm.load %8 : !llvm.ptr -> i64
      %35 = arith.addi %34, %arg1 : i64
      llvm.store %35, %8 : i64, !llvm.ptr
      cf.br ^bb5
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %36 = llvm.load %8 : !llvm.ptr -> i64
    func.return %36 : i64
  }
  func.func @I_n(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
    %37 = arith.constant 1 : i32
    %38 = llvm.mlir.constant(1 : i64) : i64
    %39 = llvm.alloca %38 x i32 : (i64) -> !llvm.ptr
    llvm.store %37, %39 : i32, !llvm.ptr
    %40 = arith.constant 1 : i32
    %42 = arith.extsi %40 : i32 to i64
    %41 = arith.subi %arg0, %42 : i64
    %43 = arith.constant 0 : i32
    %44 = arith.extsi %43 : i32 to i64
    %45 = llvm.getelementptr %arg2[%44] : (!llvm.ptr, i64) -> !llvm.ptr, i64
    llvm.store %41, %45 : i64, !llvm.ptr
    %46 = arith.constant 1 : i32
    %47 = arith.extsi %46 : i32 to i64
    %48 = llvm.mlir.constant(1 : i64) : i64
    %49 = llvm.alloca %48 x i64 : (i64) -> !llvm.ptr
    llvm.store %47, %49 : i64, !llvm.ptr
    %50 = llvm.mlir.constant(1 : i64) : i64
    %51 = llvm.alloca %50 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %51 : i64, !llvm.ptr
    cf.br ^bb6
    ^bb6:
    %52 = llvm.load %51 : !llvm.ptr -> i64
    %53 = arith.constant 1 : i32
    %55 = arith.extsi %53 : i32 to i64
    %54 = arith.cmpi sgt, %52, %55 : i64
    cf.cond_br %54, ^bb7, ^bb8
    ^bb7:
      %57 = llvm.load %51 : !llvm.ptr -> i64
      %58 = llvm.getelementptr %arg1[%57] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %56 = llvm.load %58 : !llvm.ptr -> i32
      %59 = arith.extsi %56 : i32 to i64
      %60 = arith.constant 1 : i32
      %61 = arith.extsi %60 : i32 to i64
      %62 = llvm.mlir.constant(1 : i64) : i64
      %63 = llvm.alloca %62 x i64 : (i64) -> !llvm.ptr
      llvm.store %61, %63 : i64, !llvm.ptr
      cf.br ^bb9
      ^bb9:
      %64 = llvm.load %51 : !llvm.ptr -> i64
      %65 = arith.remsi %64, %59 : i64
      %66 = arith.constant 0 : i32
      %68 = arith.extsi %66 : i32 to i64
      %67 = arith.cmpi eq, %65, %68 : i64
      cf.cond_br %67, ^bb10, ^bb11
      ^bb10:
        %69 = llvm.load %51 : !llvm.ptr -> i64
        %70 = arith.divsi %69, %59 : i64
        llvm.store %70, %51 : i64, !llvm.ptr
        %71 = llvm.load %63 : !llvm.ptr -> i64
        %72 = arith.muli %71, %59 : i64
        llvm.store %72, %63 : i64, !llvm.ptr
        cf.br ^bb9
      ^bb11:
      %73 = llvm.load %63 : !llvm.ptr -> i64
      %74 = arith.constant 2 : i32
      %76 = arith.extsi %74 : i32 to i64
      %75 = arith.cmpi eq, %73, %76 : i64
      cf.cond_br %75, ^bb12, ^bb13
      ^bb12:
        cf.br ^bb6
      ^bb13:
        cf.br ^bb14
      ^bb14:
      %77 = llvm.load %63 : !llvm.ptr -> i64
      %78 = arith.divsi %arg0, %77 : i64
      %80 = llvm.load %63 : !llvm.ptr -> i64
      %81 = arith.remsi %78, %80 : i64
      %82 = llvm.load %63 : !llvm.ptr -> i64
      %79 = func.call @modinv(%81, %82) : (i64, i64) -> i64
      %83 = arith.muli %78, %79 : i64
      %84 = arith.remsi %83, %arg0 : i64
      %85 = arith.constant 2 : i32
      %87 = arith.extsi %85 : i32 to i64
      %86 = arith.muli %87, %84 : i64
      %88 = arith.remsi %86, %arg0 : i64
      %89 = arith.constant 0 : i1
      %90 = llvm.mlir.constant(1 : i64) : i64
      %91 = llvm.alloca %90 x i1 : (i64) -> !llvm.ptr
      llvm.store %89, %91 : i1, !llvm.ptr
      %92 = arith.constant 0 : i32
      %93 = arith.extsi %92 : i32 to i64
      %94 = llvm.mlir.constant(1 : i64) : i64
      %95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
      llvm.store %93, %95 : i64, !llvm.ptr
      %96 = arith.constant 0 : i32
      %97 = arith.extsi %96 : i32 to i64
      %98 = llvm.mlir.constant(1 : i64) : i64
      %99 = llvm.alloca %98 x i64 : (i64) -> !llvm.ptr
      llvm.store %97, %99 : i64, !llvm.ptr
      %100 = llvm.load %63 : !llvm.ptr -> i64
      %101 = arith.constant 2 : i32
      %103 = arith.extsi %101 : i32 to i64
      %102 = arith.remsi %100, %103 : i64
      %104 = arith.constant 0 : i32
      %106 = arith.extsi %104 : i32 to i64
      %105 = arith.cmpi eq, %102, %106 : i64
      %107 = scf.if %105 -> (i1) {
        %108 = llvm.load %63 : !llvm.ptr -> i64
        %109 = arith.constant 8 : i32
        %111 = arith.extsi %109 : i32 to i64
        %110 = arith.cmpi sge, %108, %111 : i64
        scf.yield %110 : i1
      } else {
        %112 = arith.constant false
        scf.yield %112 : i1
      }
      cf.cond_br %107, ^bb15, ^bb16
      ^bb15:
        %113 = arith.constant 1 : i1
        llvm.store %113, %91 : i1, !llvm.ptr
        %114 = llvm.load %63 : !llvm.ptr -> i64
        %115 = arith.constant 2 : i32
        %117 = arith.extsi %115 : i32 to i64
        %116 = arith.divsi %114, %117 : i64
        %118 = arith.muli %116, %84 : i64
        %119 = arith.remsi %118, %arg0 : i64
        llvm.store %119, %95 : i64, !llvm.ptr
        %120 = arith.constant 2 : i32
        %122 = arith.extsi %120 : i32 to i64
        %121 = arith.addi %116, %122 : i64
        %123 = arith.muli %121, %84 : i64
        %124 = arith.remsi %123, %arg0 : i64
        llvm.store %124, %99 : i64, !llvm.ptr
        cf.br ^bb17
      ^bb16:
        cf.br ^bb17
      ^bb17:
      %125 = llvm.load %39 : !llvm.ptr -> i32
      %126 = arith.constant 0 : i32
      %127 = llvm.mlir.constant(1 : i64) : i64
      %128 = llvm.alloca %127 x i32 : (i64) -> !llvm.ptr
      llvm.store %126, %128 : i32, !llvm.ptr
      cf.br ^bb18
      ^bb18:
      %129 = llvm.load %128 : !llvm.ptr -> i32
      %130 = arith.cmpi slt, %129, %125 : i32
      cf.cond_br %130, ^bb19, ^bb20
      ^bb19:
        %132 = llvm.load %128 : !llvm.ptr -> i32
        %133 = arith.extsi %132 : i32 to i64
        %134 = llvm.getelementptr %arg2[%133] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %131 = llvm.load %134 : !llvm.ptr -> i64
        %135 = arith.addi %131, %88 : i64
        %136 = arith.remsi %135, %arg0 : i64
        %137 = llvm.load %39 : !llvm.ptr -> i32
        %138 = arith.extsi %137 : i32 to i64
        %139 = llvm.getelementptr %arg2[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %136, %139 : i64, !llvm.ptr
        %140 = llvm.load %39 : !llvm.ptr -> i32
        %141 = arith.constant 1 : i32
        %142 = arith.addi %140, %141 : i32
        llvm.store %142, %39 : i32, !llvm.ptr
        %143 = llvm.load %49 : !llvm.ptr -> i64
        %144 = arith.cmpi slt, %143, %136 : i64
        %145 = scf.if %144 -> (i1) {
          %146 = arith.constant 1 : i32
          %148 = arith.extsi %146 : i32 to i64
          %147 = arith.subi %arg0, %148 : i64
          %149 = arith.cmpi slt, %136, %147 : i64
          scf.yield %149 : i1
        } else {
          %150 = arith.constant false
          scf.yield %150 : i1
        }
        cf.cond_br %145, ^bb21, ^bb22
        ^bb21:
          llvm.store %136, %49 : i64, !llvm.ptr
          cf.br ^bb23
        ^bb22:
          cf.br ^bb23
        ^bb23:
        %151 = llvm.load %91 : !llvm.ptr -> i1
        cf.cond_br %151, ^bb24, ^bb25
        ^bb24:
          %152 = llvm.load %95 : !llvm.ptr -> i64
          %153 = arith.addi %131, %152 : i64
          %154 = arith.remsi %153, %arg0 : i64
          %155 = llvm.load %39 : !llvm.ptr -> i32
          %156 = arith.extsi %155 : i32 to i64
          %157 = llvm.getelementptr %arg2[%156] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %154, %157 : i64, !llvm.ptr
          %158 = llvm.load %39 : !llvm.ptr -> i32
          %159 = arith.constant 1 : i32
          %160 = arith.addi %158, %159 : i32
          llvm.store %160, %39 : i32, !llvm.ptr
          %161 = llvm.load %49 : !llvm.ptr -> i64
          %162 = arith.cmpi slt, %161, %154 : i64
          %163 = scf.if %162 -> (i1) {
            %164 = arith.constant 1 : i32
            %166 = arith.extsi %164 : i32 to i64
            %165 = arith.subi %arg0, %166 : i64
            %167 = arith.cmpi slt, %154, %165 : i64
            scf.yield %167 : i1
          } else {
            %168 = arith.constant false
            scf.yield %168 : i1
          }
          cf.cond_br %163, ^bb27, ^bb28
          ^bb27:
            llvm.store %154, %49 : i64, !llvm.ptr
            cf.br ^bb29
          ^bb28:
            cf.br ^bb29
          ^bb29:
          %169 = llvm.load %99 : !llvm.ptr -> i64
          %170 = arith.addi %131, %169 : i64
          %171 = arith.remsi %170, %arg0 : i64
          %172 = llvm.load %39 : !llvm.ptr -> i32
          %173 = arith.extsi %172 : i32 to i64
          %174 = llvm.getelementptr %arg2[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %171, %174 : i64, !llvm.ptr
          %175 = llvm.load %39 : !llvm.ptr -> i32
          %176 = arith.constant 1 : i32
          %177 = arith.addi %175, %176 : i32
          llvm.store %177, %39 : i32, !llvm.ptr
          %178 = llvm.load %49 : !llvm.ptr -> i64
          %179 = arith.cmpi slt, %178, %171 : i64
          %180 = scf.if %179 -> (i1) {
            %181 = arith.constant 1 : i32
            %183 = arith.extsi %181 : i32 to i64
            %182 = arith.subi %arg0, %183 : i64
            %184 = arith.cmpi slt, %171, %182 : i64
            scf.yield %184 : i1
          } else {
            %185 = arith.constant false
            scf.yield %185 : i1
          }
          cf.cond_br %180, ^bb30, ^bb31
          ^bb30:
            llvm.store %171, %49 : i64, !llvm.ptr
            cf.br ^bb32
          ^bb31:
            cf.br ^bb32
          ^bb32:
          cf.br ^bb26
        ^bb25:
          cf.br ^bb26
        ^bb26:
        %186 = llvm.load %128 : !llvm.ptr -> i32
        %187 = arith.constant 1 : i32
        %188 = arith.addi %186, %187 : i32
        llvm.store %188, %128 : i32, !llvm.ptr
        cf.br ^bb18
      ^bb20:
      cf.br ^bb6
    ^bb8:
    %189 = llvm.load %49 : !llvm.ptr -> i64
    func.return %189 : i64
  }
  func.func @main() -> i32 {
    %190 = arith.constant 20000000 : i32
    %191 = arith.extsi %190 : i32 to i64
    %193 = arith.constant 1 : i32
    %195 = arith.extsi %193 : i32 to i64
    %194 = arith.addi %191, %195 : i64
    %196 = arith.constant 4 : i32
    %197 = arith.extsi %196 : i32 to i64
    %192 = func.call @calloc(%194, %197) : (i64, i64) -> !llvm.ptr
    %199 = arith.constant 256 : i32
    %200 = arith.constant 8 : i32
    %201 = arith.extsi %199 : i32 to i64
    %202 = arith.extsi %200 : i32 to i64
    %198 = func.call @calloc(%201, %202) : (i64, i64) -> !llvm.ptr
    %203 = llvm.mlir.zero : !llvm.ptr
    %204 = llvm.icmp "eq" %192, %203 : !llvm.ptr
    %205 = scf.if %204 -> (i1) {
      %206 = arith.constant true
      scf.yield %206 : i1
    } else {
      %207 = llvm.mlir.zero : !llvm.ptr
      %208 = llvm.icmp "eq" %198, %207 : !llvm.ptr
      scf.yield %208 : i1
    }
    cf.cond_br %205, ^bb33, ^bb34
    ^bb33:
      %209 = arith.constant 1 : i32
      func.return %209 : i32
    ^bb34:
      cf.br ^bb35
    ^bb35:
    %210 = arith.constant 0 : i32
    %211 = arith.extsi %210 : i32 to i64
    %212 = llvm.mlir.constant(1 : i64) : i64
    %213 = llvm.alloca %212 x i64 : (i64) -> !llvm.ptr
    llvm.store %211, %213 : i64, !llvm.ptr
    cf.br ^bb36
    ^bb36:
    %214 = llvm.load %213 : !llvm.ptr -> i64
    %215 = arith.cmpi sle, %214, %191 : i64
    cf.cond_br %215, ^bb37, ^bb38
    ^bb37:
      %216 = llvm.load %213 : !llvm.ptr -> i64
      %217 = arith.trunci %216 : i64 to i32
      %218 = llvm.load %213 : !llvm.ptr -> i64
      %219 = llvm.getelementptr %192[%218] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %217, %219 : i32, !llvm.ptr
      %220 = llvm.load %213 : !llvm.ptr -> i64
      %221 = arith.constant 1 : i32
      %223 = arith.extsi %221 : i32 to i64
      %222 = arith.addi %220, %223 : i64
      llvm.store %222, %213 : i64, !llvm.ptr
      cf.br ^bb36
    ^bb38:
    %224 = arith.constant 2 : i32
    %225 = arith.extsi %224 : i32 to i64
    llvm.store %225, %213 : i64, !llvm.ptr
    cf.br ^bb39
    ^bb39:
    %226 = llvm.load %213 : !llvm.ptr -> i64
    %227 = llvm.load %213 : !llvm.ptr -> i64
    %228 = arith.muli %226, %227 : i64
    %229 = arith.cmpi sle, %228, %191 : i64
    cf.cond_br %229, ^bb40, ^bb41
    ^bb40:
      %231 = llvm.load %213 : !llvm.ptr -> i64
      %232 = llvm.getelementptr %192[%231] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %230 = llvm.load %232 : !llvm.ptr -> i32
      %233 = arith.extsi %230 : i32 to i64
      %234 = llvm.load %213 : !llvm.ptr -> i64
      %235 = arith.cmpi eq, %233, %234 : i64
      cf.cond_br %235, ^bb42, ^bb43
      ^bb42:
        %236 = llvm.load %213 : !llvm.ptr -> i64
        %237 = llvm.load %213 : !llvm.ptr -> i64
        %238 = arith.muli %236, %237 : i64
        %239 = llvm.mlir.constant(1 : i64) : i64
        %240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
        llvm.store %238, %240 : i64, !llvm.ptr
        cf.br ^bb45
        ^bb45:
        %241 = llvm.load %240 : !llvm.ptr -> i64
        %242 = arith.cmpi sle, %241, %191 : i64
        cf.cond_br %242, ^bb46, ^bb47
        ^bb46:
          %244 = llvm.load %240 : !llvm.ptr -> i64
          %245 = llvm.getelementptr %192[%244] : (!llvm.ptr, i64) -> !llvm.ptr, i32
          %243 = llvm.load %245 : !llvm.ptr -> i32
          %246 = arith.extsi %243 : i32 to i64
          %247 = llvm.load %240 : !llvm.ptr -> i64
          %248 = arith.cmpi eq, %246, %247 : i64
          cf.cond_br %248, ^bb48, ^bb49
          ^bb48:
            %249 = llvm.load %213 : !llvm.ptr -> i64
            %250 = arith.trunci %249 : i64 to i32
            %251 = llvm.load %240 : !llvm.ptr -> i64
            %252 = llvm.getelementptr %192[%251] : (!llvm.ptr, i64) -> !llvm.ptr, i32
            llvm.store %250, %252 : i32, !llvm.ptr
            cf.br ^bb50
          ^bb49:
            cf.br ^bb50
          ^bb50:
          %253 = llvm.load %240 : !llvm.ptr -> i64
          %254 = llvm.load %213 : !llvm.ptr -> i64
          %255 = arith.addi %253, %254 : i64
          llvm.store %255, %240 : i64, !llvm.ptr
          cf.br ^bb45
        ^bb47:
        cf.br ^bb44
      ^bb43:
        cf.br ^bb44
      ^bb44:
      %256 = llvm.load %213 : !llvm.ptr -> i64
      %257 = arith.constant 1 : i32
      %259 = arith.extsi %257 : i32 to i64
      %258 = arith.addi %256, %259 : i64
      llvm.store %258, %213 : i64, !llvm.ptr
      cf.br ^bb39
    ^bb41:
    %260 = arith.constant 0 : i32
    %261 = arith.extsi %260 : i32 to i64
    %262 = llvm.mlir.constant(1 : i64) : i64
    %263 = llvm.alloca %262 x i64 : (i64) -> !llvm.ptr
    llvm.store %261, %263 : i64, !llvm.ptr
    %264 = arith.constant 3 : i32
    %265 = arith.extsi %264 : i32 to i64
    %266 = llvm.mlir.constant(1 : i64) : i64
    %267 = llvm.alloca %266 x i64 : (i64) -> !llvm.ptr
    llvm.store %265, %267 : i64, !llvm.ptr
    cf.br ^bb51
    ^bb51:
    %268 = llvm.load %267 : !llvm.ptr -> i64
    %269 = arith.cmpi sle, %268, %191 : i64
    cf.cond_br %269, ^bb52, ^bb53
    ^bb52:
      %270 = llvm.load %263 : !llvm.ptr -> i64
      %272 = llvm.load %267 : !llvm.ptr -> i64
      %271 = func.call @I_n(%272, %192, %198) : (i64, !llvm.ptr, !llvm.ptr) -> i64
      %273 = arith.addi %270, %271 : i64
      llvm.store %273, %263 : i64, !llvm.ptr
      %274 = llvm.load %267 : !llvm.ptr -> i64
      %275 = arith.constant 1 : i32
      %277 = arith.extsi %275 : i32 to i64
      %276 = arith.addi %274, %277 : i64
      llvm.store %276, %267 : i64, !llvm.ptr
      cf.br ^bb51
    ^bb53:
    %278 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %279 = llvm.load %263 : !llvm.ptr -> i64
    %280 = llvm.call @printf(%278, %279) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%198) : (!llvm.ptr) -> ()
    func.call @free(%192) : (!llvm.ptr) -> ()
    %283 = arith.constant 0 : i32
    func.return %283 : i32
  }
}