← All problems Problem 776
For n >= 1, let d(n) be the sum of decimal digits of n. F(N) = sum_{n=1..N} n / d(n). A digit DP over the decimal representation of N groups every integer in [0, N] by its digit sum s. For each s we track the count of integers and their sum. F(N) = sum_{s>=1} (sum of integers with digit sum s) / s.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n)Space complexity O(1)O(n)Approach Flow solution Big-integer arithmetic Verdict Suboptimal
Flow source
# Project Euler 776: Digit Sum Division
#
# For n >= 1, let d(n) be the sum of decimal digits of n.
# F(N) = sum_{n=1..N} n / d(n).
#
# A digit DP over the decimal representation of N groups every integer in
# [0, N] by its digit sum s. For each s we track the count of integers and
# their sum. F(N) = sum_{s>=1} (sum of integers with digit sum s) / s.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function floor(x: f64) -> f64
function log(x: f64) -> f64
function exp(x: f64) -> f64
}
function zero_arr(a: ptr<f64>, n: i32) {
for i in 0..n {
a[i] = 0.0
}
}
function main() -> i32 {
# N = 1234567890123456789
let digits: ptr<i32> = calloc(19, 4)
digits[0] = 1
digits[1] = 2
digits[2] = 3
digits[3] = 4
digits[4] = 5
digits[5] = 6
digits[6] = 7
digits[7] = 8
digits[8] = 9
digits[9] = 0
digits[10] = 1
digits[11] = 2
digits[12] = 3
digits[13] = 4
digits[14] = 5
digits[15] = 6
digits[16] = 7
digits[17] = 8
digits[18] = 9
let L: i32 = 19
let max_sum: i32 = 9 * L
let cnt_tight: ptr<f64> = calloc(172, 8)
let sum_tight: ptr<f64> = calloc(172, 8)
let cnt_loose: ptr<f64> = calloc(172, 8)
let sum_loose: ptr<f64> = calloc(172, 8)
let ncnt_tight: ptr<f64> = calloc(172, 8)
let nsum_tight: ptr<f64> = calloc(172, 8)
let ncnt_loose: ptr<f64> = calloc(172, 8)
let nsum_loose: ptr<f64> = calloc(172, 8)
zero_arr(cnt_tight, 172)
zero_arr(sum_tight, 172)
zero_arr(cnt_loose, 172)
zero_arr(sum_loose, 172)
cnt_tight[0] = 1.0
for i in 0..L {
let lim: i32 = digits[i]
zero_arr(ncnt_tight, 172)
zero_arr(nsum_tight, 172)
zero_arr(ncnt_loose, 172)
zero_arr(nsum_loose, 172)
# Loose -> loose: next digit free (0..9).
for s in 0..(max_sum + 1) {
let c: f64 = cnt_loose[s]
if c == 0.0 {
continue
}
let v10: f64 = sum_loose[s] * 10.0
for d in 0..10 {
let ns: i32 = s + d
if ns > max_sum {
break
}
ncnt_loose[ns] = ncnt_loose[ns] + c
nsum_loose[ns] = nsum_loose[ns] + v10 + c * (d as f64)
}
}
# Tight -> tight/loose: next digit restricted by lim.
for s in 0..(max_sum + 1) {
let c: f64 = cnt_tight[s]
if c == 0.0 {
continue
}
let v10: f64 = sum_tight[s] * 10.0
for d in 0..(lim + 1) {
let ns: i32 = s + d
if ns > max_sum {
break
}
if d == lim {
ncnt_tight[ns] = ncnt_tight[ns] + c
nsum_tight[ns] = nsum_tight[ns] + v10 + c * (d as f64)
} else {
ncnt_loose[ns] = ncnt_loose[ns] + c
nsum_loose[ns] = nsum_loose[ns] + v10 + c * (d as f64)
}
}
}
for s in 0..172 {
cnt_tight[s] = ncnt_tight[s]
sum_tight[s] = nsum_tight[s]
cnt_loose[s] = ncnt_loose[s]
sum_loose[s] = nsum_loose[s]
}
}
# F(N) = sum_{s>=1} (sum_tight[s] + sum_loose[s]) / s.
let mut total: f64 = 0.0
for s in 1..(max_sum + 1) {
let sums: f64 = sum_tight[s] + sum_loose[s]
if sums != 0.0 {
total = total + sums / (s as f64)
}
}
# Format as %.12e without '+' in exponent.
let mut mant: f64 = total
let mut ex: i64 = 0
while mant >= 10.0 {
mant = mant / 10.0
ex = ex + 1
}
while mant < 1.0 && mant > 0.0 {
mant = mant * 10.0
ex = ex - 1
}
printf("%.12fe%lld\n", mant, ex)
free(nsum_loose)
free(ncnt_loose)
free(nsum_tight)
free(ncnt_tight)
free(sum_loose)
free(cnt_loose)
free(sum_tight)
free(cnt_tight)
free(digits)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
void zero_arr_ptr_f64_i32(double* a, int32_t n);
int32_t main(void);
void zero_arr_ptr_f64_i32(double* a, int32_t n) {
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= n) ? i < n : i > n; i += (0 <= n) ? 1 : -1) {
a[i] = 0.0;
}
}
int32_t main(void) {
int32_t* digits = (int32_t*)(calloc(19, 4));
digits[0] = 1;
digits[1] = 2;
digits[2] = 3;
digits[3] = 4;
digits[4] = 5;
digits[5] = 6;
digits[6] = 7;
digits[7] = 8;
digits[8] = 9;
digits[9] = 0;
digits[10] = 1;
digits[11] = 2;
digits[12] = 3;
digits[13] = 4;
digits[14] = 5;
digits[15] = 6;
digits[16] = 7;
digits[17] = 8;
digits[18] = 9;
int32_t L = 19;
int32_t max_sum = (9 * L);
double* cnt_tight = (double*)(calloc(172, 8));
double* sum_tight = (double*)(calloc(172, 8));
double* cnt_loose = (double*)(calloc(172, 8));
double* sum_loose = (double*)(calloc(172, 8));
double* ncnt_tight = (double*)(calloc(172, 8));
double* nsum_tight = (double*)(calloc(172, 8));
double* ncnt_loose = (double*)(calloc(172, 8));
double* nsum_loose = (double*)(calloc(172, 8));
zero_arr_ptr_f64_i32(cnt_tight, 172);
zero_arr_ptr_f64_i32(sum_tight, 172);
zero_arr_ptr_f64_i32(cnt_loose, 172);
zero_arr_ptr_f64_i32(sum_loose, 172);
cnt_tight[0] = 1.0;
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= L) ? i < L : i > L; i += (0 <= L) ? 1 : -1) {
int32_t lim = digits[i];
zero_arr_ptr_f64_i32(ncnt_tight, 172);
zero_arr_ptr_f64_i32(nsum_tight, 172);
zero_arr_ptr_f64_i32(ncnt_loose, 172);
zero_arr_ptr_f64_i32(nsum_loose, 172);
int32_t __flow_step_3 = 1;
for (int32_t s = 0; (0 <= (max_sum + 1)) ? s < (max_sum + 1) : s > (max_sum + 1); s += (0 <= (max_sum + 1)) ? 1 : -1) {
double c = cnt_loose[s];
if (c == 0.0) {
continue;
}
double v10 = (sum_loose[s] * 10.0);
int32_t __flow_step_4 = 1;
for (int32_t d = 0; (0 <= 10) ? d < 10 : d > 10; d += (0 <= 10) ? 1 : -1) {
int32_t ns = (s + d);
if (ns > max_sum) {
break;
}
ncnt_loose[ns] = (ncnt_loose[ns] + c);
nsum_loose[ns] = ((nsum_loose[ns] + v10) + (c * ((double)(d))));
}
}
int32_t __flow_step_5 = 1;
for (int32_t s = 0; (0 <= (max_sum + 1)) ? s < (max_sum + 1) : s > (max_sum + 1); s += (0 <= (max_sum + 1)) ? 1 : -1) {
double c = cnt_tight[s];
if (c == 0.0) {
continue;
}
double v10 = (sum_tight[s] * 10.0);
int32_t __flow_step_6 = 1;
for (int32_t d = 0; (0 <= (lim + 1)) ? d < (lim + 1) : d > (lim + 1); d += (0 <= (lim + 1)) ? 1 : -1) {
int32_t ns = (s + d);
if (ns > max_sum) {
break;
}
if (d == lim) {
ncnt_tight[ns] = (ncnt_tight[ns] + c);
nsum_tight[ns] = ((nsum_tight[ns] + v10) + (c * ((double)(d))));
} else {
ncnt_loose[ns] = (ncnt_loose[ns] + c);
nsum_loose[ns] = ((nsum_loose[ns] + v10) + (c * ((double)(d))));
}
}
}
int32_t __flow_step_7 = 1;
for (int32_t s = 0; (0 <= 172) ? s < 172 : s > 172; s += (0 <= 172) ? 1 : -1) {
cnt_tight[s] = ncnt_tight[s];
sum_tight[s] = nsum_tight[s];
cnt_loose[s] = ncnt_loose[s];
sum_loose[s] = nsum_loose[s];
}
}
double total = 0.0;
int32_t __flow_step_8 = 1;
for (int32_t s = 1; (1 <= (max_sum + 1)) ? s < (max_sum + 1) : s > (max_sum + 1); s += (1 <= (max_sum + 1)) ? 1 : -1) {
double sums = (sum_tight[s] + sum_loose[s]);
if (sums != 0.0) {
total = (total + (sums / ((double)(s))));
}
}
double mant = total;
int64_t ex = 0;
while (mant >= 10.0) {
mant = (mant / 10.0);
ex = (ex + 1);
}
while ((mant < 1.0 && mant > 0.0)) {
mant = (mant * 10.0);
ex = (ex - 1);
}
printf("%.12fe%lld\n", mant, ex);
free(nsum_loose);
free(ncnt_loose);
free(nsum_tight);
free(ncnt_tight);
free(sum_loose);
free(cnt_loose);
free(sum_tight);
free(cnt_tight);
free(digits);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.12fe%lld\n\00") {addr_space = 0 : i32} : !llvm.array<12 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @floor(f64) -> f64
func.func private @log(f64) -> f64
func.func private @exp(f64) -> f64
func.func @zero_arr(%arg0: !llvm.ptr, %arg1: i32) -> () {
%0 = arith.constant 0 : i32
%1 = arith.index_cast %0 : i32 to index
%2 = arith.index_cast %arg1 : i32 to index
%4 = arith.constant 1 : index
%5 = arith.constant -1 : index
%6 = arith.cmpi sle, %1, %2 : index
%3 = arith.select %6, %4, %5 : index
cf.br ^bb0(%1 : index)
^bb0(%7: index):
%8 = arith.cmpi slt, %7, %2 : index
%9 = arith.cmpi sgt, %7, %2 : index
%10 = arith.select %6, %8, %9 : i1
cf.cond_br %10, ^bb1(%7 : index), ^bb2(%7 : index)
^bb1(%11: index):
%12 = arith.constant 0.0 : f32
%13 = arith.extf %12 : f32 to f64
%14 = arith.index_cast %11 : index to i64
%15 = llvm.getelementptr %arg0[%14] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %13, %15 : f64, !llvm.ptr
%16 = arith.addi %11, %3 : index
cf.br ^bb0(%16 : index)
^bb2(%17: index):
func.return
}
func.func @main() -> i32 {
%19 = arith.constant 19 : i32
%20 = arith.constant 4 : i32
%21 = arith.extsi %19 : i32 to i64
%22 = arith.extsi %20 : i32 to i64
%18 = func.call @calloc(%21, %22) : (i64, i64) -> !llvm.ptr
%23 = arith.constant 1 : i32
%24 = arith.constant 0 : i32
%25 = arith.extsi %24 : i32 to i64
%26 = llvm.getelementptr %18[%25] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %23, %26 : i32, !llvm.ptr
%27 = arith.constant 2 : i32
%28 = arith.constant 1 : i32
%29 = arith.extsi %28 : i32 to i64
%30 = llvm.getelementptr %18[%29] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %27, %30 : i32, !llvm.ptr
%31 = arith.constant 3 : i32
%32 = arith.constant 2 : i32
%33 = arith.extsi %32 : i32 to i64
%34 = llvm.getelementptr %18[%33] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %31, %34 : i32, !llvm.ptr
%35 = arith.constant 4 : i32
%36 = arith.constant 3 : i32
%37 = arith.extsi %36 : i32 to i64
%38 = llvm.getelementptr %18[%37] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %35, %38 : i32, !llvm.ptr
%39 = arith.constant 5 : i32
%40 = arith.constant 4 : i32
%41 = arith.extsi %40 : i32 to i64
%42 = llvm.getelementptr %18[%41] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %39, %42 : i32, !llvm.ptr
%43 = arith.constant 6 : i32
%44 = arith.constant 5 : i32
%45 = arith.extsi %44 : i32 to i64
%46 = llvm.getelementptr %18[%45] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %43, %46 : i32, !llvm.ptr
%47 = arith.constant 7 : i32
%48 = arith.constant 6 : i32
%49 = arith.extsi %48 : i32 to i64
%50 = llvm.getelementptr %18[%49] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %47, %50 : i32, !llvm.ptr
%51 = arith.constant 8 : i32
%52 = arith.constant 7 : i32
%53 = arith.extsi %52 : i32 to i64
%54 = llvm.getelementptr %18[%53] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %51, %54 : i32, !llvm.ptr
%55 = arith.constant 9 : i32
%56 = arith.constant 8 : i32
%57 = arith.extsi %56 : i32 to i64
%58 = llvm.getelementptr %18[%57] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %55, %58 : i32, !llvm.ptr
%59 = arith.constant 0 : i32
%60 = arith.constant 9 : i32
%61 = arith.extsi %60 : i32 to i64
%62 = llvm.getelementptr %18[%61] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %59, %62 : i32, !llvm.ptr
%63 = arith.constant 1 : i32
%64 = arith.constant 10 : i32
%65 = arith.extsi %64 : i32 to i64
%66 = llvm.getelementptr %18[%65] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %63, %66 : i32, !llvm.ptr
%67 = arith.constant 2 : i32
%68 = arith.constant 11 : i32
%69 = arith.extsi %68 : i32 to i64
%70 = llvm.getelementptr %18[%69] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %67, %70 : i32, !llvm.ptr
%71 = arith.constant 3 : i32
%72 = arith.constant 12 : i32
%73 = arith.extsi %72 : i32 to i64
%74 = llvm.getelementptr %18[%73] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %71, %74 : i32, !llvm.ptr
%75 = arith.constant 4 : i32
%76 = arith.constant 13 : i32
%77 = arith.extsi %76 : i32 to i64
%78 = llvm.getelementptr %18[%77] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %75, %78 : i32, !llvm.ptr
%79 = arith.constant 5 : i32
%80 = arith.constant 14 : i32
%81 = arith.extsi %80 : i32 to i64
%82 = llvm.getelementptr %18[%81] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %79, %82 : i32, !llvm.ptr
%83 = arith.constant 6 : i32
%84 = arith.constant 15 : i32
%85 = arith.extsi %84 : i32 to i64
%86 = llvm.getelementptr %18[%85] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %83, %86 : i32, !llvm.ptr
%87 = arith.constant 7 : i32
%88 = arith.constant 16 : i32
%89 = arith.extsi %88 : i32 to i64
%90 = llvm.getelementptr %18[%89] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %87, %90 : i32, !llvm.ptr
%91 = arith.constant 8 : i32
%92 = arith.constant 17 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.getelementptr %18[%93] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %91, %94 : i32, !llvm.ptr
%95 = arith.constant 9 : i32
%96 = arith.constant 18 : i32
%97 = arith.extsi %96 : i32 to i64
%98 = llvm.getelementptr %18[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %95, %98 : i32, !llvm.ptr
%99 = arith.constant 19 : i32
%100 = arith.constant 9 : i32
%101 = arith.muli %100, %99 : i32
%103 = arith.constant 172 : i32
%104 = arith.constant 8 : i32
%105 = arith.extsi %103 : i32 to i64
%106 = arith.extsi %104 : i32 to i64
%102 = func.call @calloc(%105, %106) : (i64, i64) -> !llvm.ptr
%108 = arith.constant 172 : i32
%109 = arith.constant 8 : i32
%110 = arith.extsi %108 : i32 to i64
%111 = arith.extsi %109 : i32 to i64
%107 = func.call @calloc(%110, %111) : (i64, i64) -> !llvm.ptr
%113 = arith.constant 172 : i32
%114 = arith.constant 8 : i32
%115 = arith.extsi %113 : i32 to i64
%116 = arith.extsi %114 : i32 to i64
%112 = func.call @calloc(%115, %116) : (i64, i64) -> !llvm.ptr
%118 = arith.constant 172 : i32
%119 = arith.constant 8 : i32
%120 = arith.extsi %118 : i32 to i64
%121 = arith.extsi %119 : i32 to i64
%117 = func.call @calloc(%120, %121) : (i64, i64) -> !llvm.ptr
%123 = arith.constant 172 : i32
%124 = arith.constant 8 : i32
%125 = arith.extsi %123 : i32 to i64
%126 = arith.extsi %124 : i32 to i64
%122 = func.call @calloc(%125, %126) : (i64, i64) -> !llvm.ptr
%128 = arith.constant 172 : i32
%129 = arith.constant 8 : i32
%130 = arith.extsi %128 : i32 to i64
%131 = arith.extsi %129 : i32 to i64
%127 = func.call @calloc(%130, %131) : (i64, i64) -> !llvm.ptr
%133 = arith.constant 172 : i32
%134 = arith.constant 8 : i32
%135 = arith.extsi %133 : i32 to i64
%136 = arith.extsi %134 : i32 to i64
%132 = func.call @calloc(%135, %136) : (i64, i64) -> !llvm.ptr
%138 = arith.constant 172 : i32
%139 = arith.constant 8 : i32
%140 = arith.extsi %138 : i32 to i64
%141 = arith.extsi %139 : i32 to i64
%137 = func.call @calloc(%140, %141) : (i64, i64) -> !llvm.ptr
%143 = arith.constant 172 : i32
func.call @zero_arr(%102, %143) : (!llvm.ptr, i32) -> ()
%145 = arith.constant 172 : i32
func.call @zero_arr(%107, %145) : (!llvm.ptr, i32) -> ()
%147 = arith.constant 172 : i32
func.call @zero_arr(%112, %147) : (!llvm.ptr, i32) -> ()
%149 = arith.constant 172 : i32
func.call @zero_arr(%117, %149) : (!llvm.ptr, i32) -> ()
%150 = arith.constant 1.0 : f32
%151 = arith.constant 0 : i32
%152 = arith.extf %150 : f32 to f64
%153 = arith.extsi %151 : i32 to i64
%154 = llvm.getelementptr %102[%153] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %152, %154 : f64, !llvm.ptr
%155 = arith.constant 0 : i32
%156 = arith.index_cast %155 : i32 to index
%157 = arith.index_cast %99 : i32 to index
%159 = arith.constant 1 : index
%160 = arith.constant -1 : index
%161 = arith.cmpi sle, %156, %157 : index
%158 = arith.select %161, %159, %160 : index
cf.br ^bb3(%156 : index)
^bb3(%162: index):
%163 = arith.cmpi slt, %162, %157 : index
%164 = arith.cmpi sgt, %162, %157 : index
%165 = arith.select %161, %163, %164 : i1
cf.cond_br %165, ^bb4(%162 : index), ^bb5(%162 : index)
^bb4(%166: index):
%168 = arith.index_cast %166 : index to i64
%169 = llvm.getelementptr %18[%168] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%167 = llvm.load %169 : !llvm.ptr -> i32
%171 = arith.constant 172 : i32
func.call @zero_arr(%122, %171) : (!llvm.ptr, i32) -> ()
%173 = arith.constant 172 : i32
func.call @zero_arr(%127, %173) : (!llvm.ptr, i32) -> ()
%175 = arith.constant 172 : i32
func.call @zero_arr(%132, %175) : (!llvm.ptr, i32) -> ()
%177 = arith.constant 172 : i32
func.call @zero_arr(%137, %177) : (!llvm.ptr, i32) -> ()
%178 = arith.constant 0 : i32
%179 = arith.constant 1 : i32
%180 = arith.addi %101, %179 : i32
%181 = arith.index_cast %178 : i32 to index
%182 = arith.index_cast %180 : i32 to index
%184 = arith.constant 1 : index
%185 = arith.constant -1 : index
%186 = arith.cmpi sle, %181, %182 : index
%183 = arith.select %186, %184, %185 : index
cf.br ^bb6(%181 : index)
^bb6(%187: index):
%188 = arith.cmpi slt, %187, %182 : index
%189 = arith.cmpi sgt, %187, %182 : index
%190 = arith.select %186, %188, %189 : i1
cf.cond_br %190, ^bb7(%187 : index), ^bb8(%187 : index)
^bb7(%191: index):
%193 = arith.index_cast %191 : index to i64
%194 = llvm.getelementptr %112[%193] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%192 = llvm.load %194 : !llvm.ptr -> f64
%195 = arith.constant 0.0 : f32
%197 = arith.extf %195 : f32 to f64
%196 = arith.cmpf oeq, %192, %197 : f64
cf.cond_br %196, ^bb9, ^bb10
^bb9:
%198 = arith.addi %191, %183 : index
cf.br ^bb6(%198 : index)
^bb10:
cf.br ^bb11
^bb11:
%200 = arith.index_cast %191 : index to i64
%201 = llvm.getelementptr %117[%200] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%199 = llvm.load %201 : !llvm.ptr -> f64
%202 = arith.constant 10.0 : f32
%204 = arith.extf %202 : f32 to f64
%203 = arith.mulf %199, %204 : f64
%205 = arith.constant 0 : i32
%206 = arith.constant 10 : i32
%207 = arith.index_cast %205 : i32 to index
%208 = arith.index_cast %206 : i32 to index
%210 = arith.constant 1 : index
%211 = arith.constant -1 : index
%212 = arith.cmpi sle, %207, %208 : index
%209 = arith.select %212, %210, %211 : index
cf.br ^bb12(%207 : index)
^bb12(%213: index):
%214 = arith.cmpi slt, %213, %208 : index
%215 = arith.cmpi sgt, %213, %208 : index
%216 = arith.select %212, %214, %215 : i1
cf.cond_br %216, ^bb13(%213 : index), ^bb14(%213 : index)
^bb13(%217: index):
%218 = arith.addi %191, %217 : index
%219 = arith.index_cast %218 : index to i32
%220 = arith.cmpi sgt, %219, %101 : i32
cf.cond_br %220, ^bb15, ^bb16
^bb15:
cf.br ^bb14(%217 : index)
^bb16:
cf.br ^bb17
^bb17:
%222 = arith.extsi %219 : i32 to i64
%223 = llvm.getelementptr %132[%222] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%221 = llvm.load %223 : !llvm.ptr -> f64
%224 = arith.addf %221, %192 : f64
%225 = arith.extsi %219 : i32 to i64
%226 = llvm.getelementptr %132[%225] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %224, %226 : f64, !llvm.ptr
%228 = arith.extsi %219 : i32 to i64
%229 = llvm.getelementptr %137[%228] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%227 = llvm.load %229 : !llvm.ptr -> f64
%230 = arith.addf %227, %203 : f64
%232 = arith.index_cast %217 : index to i64
%231 = arith.sitofp %232 : i64 to f64
%233 = arith.mulf %192, %231 : f64
%234 = arith.addf %230, %233 : f64
%235 = arith.extsi %219 : i32 to i64
%236 = llvm.getelementptr %137[%235] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %234, %236 : f64, !llvm.ptr
%237 = arith.addi %217, %209 : index
cf.br ^bb12(%237 : index)
^bb14(%238: index):
%239 = arith.addi %191, %183 : index
cf.br ^bb6(%239 : index)
^bb8(%240: index):
%241 = arith.constant 0 : i32
%242 = arith.constant 1 : i32
%243 = arith.addi %101, %242 : i32
%244 = arith.index_cast %241 : i32 to index
%245 = arith.index_cast %243 : i32 to index
%247 = arith.constant 1 : index
%248 = arith.constant -1 : index
%249 = arith.cmpi sle, %244, %245 : index
%246 = arith.select %249, %247, %248 : index
cf.br ^bb18(%244 : index)
^bb18(%250: index):
%251 = arith.cmpi slt, %250, %245 : index
%252 = arith.cmpi sgt, %250, %245 : index
%253 = arith.select %249, %251, %252 : i1
cf.cond_br %253, ^bb19(%250 : index), ^bb20(%250 : index)
^bb19(%254: index):
%256 = arith.index_cast %254 : index to i64
%257 = llvm.getelementptr %102[%256] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%255 = llvm.load %257 : !llvm.ptr -> f64
%258 = arith.constant 0.0 : f32
%260 = arith.extf %258 : f32 to f64
%259 = arith.cmpf oeq, %255, %260 : f64
cf.cond_br %259, ^bb21, ^bb22
^bb21:
%261 = arith.addi %254, %246 : index
cf.br ^bb18(%261 : index)
^bb22:
cf.br ^bb23
^bb23:
%263 = arith.index_cast %254 : index to i64
%264 = llvm.getelementptr %107[%263] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%262 = llvm.load %264 : !llvm.ptr -> f64
%265 = arith.constant 10.0 : f32
%267 = arith.extf %265 : f32 to f64
%266 = arith.mulf %262, %267 : f64
%268 = arith.constant 0 : i32
%269 = arith.constant 1 : i32
%270 = arith.addi %167, %269 : i32
%271 = arith.index_cast %268 : i32 to index
%272 = arith.index_cast %270 : i32 to index
%274 = arith.constant 1 : index
%275 = arith.constant -1 : index
%276 = arith.cmpi sle, %271, %272 : index
%273 = arith.select %276, %274, %275 : index
cf.br ^bb24(%271 : index)
^bb24(%277: index):
%278 = arith.cmpi slt, %277, %272 : index
%279 = arith.cmpi sgt, %277, %272 : index
%280 = arith.select %276, %278, %279 : i1
cf.cond_br %280, ^bb25(%277 : index), ^bb26(%277 : index)
^bb25(%281: index):
%282 = arith.addi %254, %281 : index
%283 = arith.index_cast %282 : index to i32
%284 = arith.cmpi sgt, %283, %101 : i32
cf.cond_br %284, ^bb27, ^bb28
^bb27:
cf.br ^bb26(%281 : index)
^bb28:
cf.br ^bb29
^bb29:
%286 = arith.index_cast %281 : index to i32
%285 = arith.cmpi eq, %286, %167 : i32
cf.cond_br %285, ^bb30, ^bb31
^bb30:
%288 = arith.extsi %283 : i32 to i64
%289 = llvm.getelementptr %122[%288] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%287 = llvm.load %289 : !llvm.ptr -> f64
%290 = arith.addf %287, %255 : f64
%291 = arith.extsi %283 : i32 to i64
%292 = llvm.getelementptr %122[%291] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %290, %292 : f64, !llvm.ptr
%294 = arith.extsi %283 : i32 to i64
%295 = llvm.getelementptr %127[%294] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%293 = llvm.load %295 : !llvm.ptr -> f64
%296 = arith.addf %293, %266 : f64
%298 = arith.index_cast %281 : index to i64
%297 = arith.sitofp %298 : i64 to f64
%299 = arith.mulf %255, %297 : f64
%300 = arith.addf %296, %299 : f64
%301 = arith.extsi %283 : i32 to i64
%302 = llvm.getelementptr %127[%301] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %300, %302 : f64, !llvm.ptr
cf.br ^bb32
^bb31:
%304 = arith.extsi %283 : i32 to i64
%305 = llvm.getelementptr %132[%304] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%303 = llvm.load %305 : !llvm.ptr -> f64
%306 = arith.addf %303, %255 : f64
%307 = arith.extsi %283 : i32 to i64
%308 = llvm.getelementptr %132[%307] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %306, %308 : f64, !llvm.ptr
%310 = arith.extsi %283 : i32 to i64
%311 = llvm.getelementptr %137[%310] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%309 = llvm.load %311 : !llvm.ptr -> f64
%312 = arith.addf %309, %266 : f64
%314 = arith.index_cast %281 : index to i64
%313 = arith.sitofp %314 : i64 to f64
%315 = arith.mulf %255, %313 : f64
%316 = arith.addf %312, %315 : f64
%317 = arith.extsi %283 : i32 to i64
%318 = llvm.getelementptr %137[%317] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %316, %318 : f64, !llvm.ptr
cf.br ^bb32
^bb32:
%319 = arith.addi %281, %273 : index
cf.br ^bb24(%319 : index)
^bb26(%320: index):
%321 = arith.addi %254, %246 : index
cf.br ^bb18(%321 : index)
^bb20(%322: index):
%323 = arith.constant 0 : i32
%324 = arith.constant 172 : i32
%325 = arith.index_cast %323 : i32 to index
%326 = arith.index_cast %324 : i32 to index
%328 = arith.constant 1 : index
%329 = arith.constant -1 : index
%330 = arith.cmpi sle, %325, %326 : index
%327 = arith.select %330, %328, %329 : index
cf.br ^bb33(%325 : index)
^bb33(%331: index):
%332 = arith.cmpi slt, %331, %326 : index
%333 = arith.cmpi sgt, %331, %326 : index
%334 = arith.select %330, %332, %333 : i1
cf.cond_br %334, ^bb34(%331 : index), ^bb35(%331 : index)
^bb34(%335: index):
%337 = arith.index_cast %335 : index to i64
%338 = llvm.getelementptr %122[%337] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%336 = llvm.load %338 : !llvm.ptr -> f64
%339 = arith.index_cast %335 : index to i64
%340 = llvm.getelementptr %102[%339] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %336, %340 : f64, !llvm.ptr
%342 = arith.index_cast %335 : index to i64
%343 = llvm.getelementptr %127[%342] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%341 = llvm.load %343 : !llvm.ptr -> f64
%344 = arith.index_cast %335 : index to i64
%345 = llvm.getelementptr %107[%344] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %341, %345 : f64, !llvm.ptr
%347 = arith.index_cast %335 : index to i64
%348 = llvm.getelementptr %132[%347] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%346 = llvm.load %348 : !llvm.ptr -> f64
%349 = arith.index_cast %335 : index to i64
%350 = llvm.getelementptr %112[%349] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %346, %350 : f64, !llvm.ptr
%352 = arith.index_cast %335 : index to i64
%353 = llvm.getelementptr %137[%352] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%351 = llvm.load %353 : !llvm.ptr -> f64
%354 = arith.index_cast %335 : index to i64
%355 = llvm.getelementptr %117[%354] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %351, %355 : f64, !llvm.ptr
%356 = arith.addi %335, %327 : index
cf.br ^bb33(%356 : index)
^bb35(%357: index):
%358 = arith.addi %166, %158 : index
cf.br ^bb3(%358 : index)
^bb5(%359: index):
%360 = arith.constant 0.0 : f32
%361 = arith.extf %360 : f32 to f64
%362 = llvm.mlir.constant(1 : i64) : i64
%363 = llvm.alloca %362 x f64 : (i64) -> !llvm.ptr
llvm.store %361, %363 : f64, !llvm.ptr
%364 = arith.constant 1 : i32
%365 = arith.constant 1 : i32
%366 = arith.addi %101, %365 : i32
%367 = arith.index_cast %364 : i32 to index
%368 = arith.index_cast %366 : i32 to index
%370 = arith.constant 1 : index
%371 = arith.constant -1 : index
%372 = arith.cmpi sle, %367, %368 : index
%369 = arith.select %372, %370, %371 : index
cf.br ^bb36(%367 : index)
^bb36(%373: index):
%374 = arith.cmpi slt, %373, %368 : index
%375 = arith.cmpi sgt, %373, %368 : index
%376 = arith.select %372, %374, %375 : i1
cf.cond_br %376, ^bb37(%373 : index), ^bb38(%373 : index)
^bb37(%377: index):
%379 = arith.index_cast %377 : index to i64
%380 = llvm.getelementptr %107[%379] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%378 = llvm.load %380 : !llvm.ptr -> f64
%382 = arith.index_cast %377 : index to i64
%383 = llvm.getelementptr %117[%382] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%381 = llvm.load %383 : !llvm.ptr -> f64
%384 = arith.addf %378, %381 : f64
%385 = arith.constant 0.0 : f32
%387 = arith.extf %385 : f32 to f64
%386 = arith.cmpf one, %384, %387 : f64
cf.cond_br %386, ^bb39, ^bb40
^bb39:
%388 = llvm.load %363 : !llvm.ptr -> f64
%390 = arith.index_cast %377 : index to i64
%389 = arith.sitofp %390 : i64 to f64
%391 = arith.divf %384, %389 : f64
%392 = arith.addf %388, %391 : f64
llvm.store %392, %363 : f64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%393 = arith.addi %377, %369 : index
cf.br ^bb36(%393 : index)
^bb38(%394: index):
%395 = llvm.load %363 : !llvm.ptr -> f64
%396 = llvm.mlir.constant(1 : i64) : i64
%397 = llvm.alloca %396 x f64 : (i64) -> !llvm.ptr
llvm.store %395, %397 : f64, !llvm.ptr
%398 = arith.constant 0 : i32
%399 = arith.extsi %398 : i32 to i64
%400 = llvm.mlir.constant(1 : i64) : i64
%401 = llvm.alloca %400 x i64 : (i64) -> !llvm.ptr
llvm.store %399, %401 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%402 = llvm.load %397 : !llvm.ptr -> f64
%403 = arith.constant 10.0 : f32
%405 = arith.extf %403 : f32 to f64
%404 = arith.cmpf oge, %402, %405 : f64
cf.cond_br %404, ^bb43, ^bb44
^bb43:
%406 = llvm.load %397 : !llvm.ptr -> f64
%407 = arith.constant 10.0 : f32
%409 = arith.extf %407 : f32 to f64
%408 = arith.divf %406, %409 : f64
llvm.store %408, %397 : f64, !llvm.ptr
%410 = llvm.load %401 : !llvm.ptr -> i64
%411 = arith.constant 1 : i32
%413 = arith.extsi %411 : i32 to i64
%412 = arith.addi %410, %413 : i64
llvm.store %412, %401 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
cf.br ^bb45
^bb45:
%414 = llvm.load %397 : !llvm.ptr -> f64
%415 = arith.constant 1.0 : f32
%417 = arith.extf %415 : f32 to f64
%416 = arith.cmpf olt, %414, %417 : f64
%418 = scf.if %416 -> (i1) {
%419 = llvm.load %397 : !llvm.ptr -> f64
%420 = arith.constant 0.0 : f32
%422 = arith.extf %420 : f32 to f64
%421 = arith.cmpf ogt, %419, %422 : f64
scf.yield %421 : i1
} else {
%423 = arith.constant false
scf.yield %423 : i1
}
cf.cond_br %418, ^bb46, ^bb47
^bb46:
%424 = llvm.load %397 : !llvm.ptr -> f64
%425 = arith.constant 10.0 : f32
%427 = arith.extf %425 : f32 to f64
%426 = arith.mulf %424, %427 : f64
llvm.store %426, %397 : f64, !llvm.ptr
%428 = llvm.load %401 : !llvm.ptr -> i64
%429 = arith.constant 1 : i32
%431 = arith.extsi %429 : i32 to i64
%430 = arith.subi %428, %431 : i64
llvm.store %430, %401 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%432 = llvm.mlir.addressof @str_0 : !llvm.ptr
%433 = llvm.load %397 : !llvm.ptr -> f64
%434 = llvm.load %401 : !llvm.ptr -> i64
%435 = llvm.call @printf(%432, %433, %434) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64, i64) -> i32
func.call @free(%137) : (!llvm.ptr) -> ()
func.call @free(%132) : (!llvm.ptr) -> ()
func.call @free(%127) : (!llvm.ptr) -> ()
func.call @free(%122) : (!llvm.ptr) -> ()
func.call @free(%117) : (!llvm.ptr) -> ()
func.call @free(%112) : (!llvm.ptr) -> ()
func.call @free(%107) : (!llvm.ptr) -> ()
func.call @free(%102) : (!llvm.ptr) -> ()
func.call @free(%18) : (!llvm.ptr) -> ()
%445 = arith.constant 0 : i32
func.return %445 : i32
}
}