← All problems Problem 783
Urns: E(10^6, 10) nearest integer. Iterative expectation with Kahan summation.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 783
# Urns: E(10^6, 10) nearest integer.
# Iterative expectation with Kahan summation.
function main() -> i32 {
let n: i64 = 1000000
let k: i64 = 10
let m: f64 = 2.0 * (k as f64)
let mut mu: f64 = 0.0
let mut s2: f64 = 0.0
let mut M: f64 = (k as f64) * ((n + 1) as f64)
let mut total: f64 = 0.0
let mut comp: f64 = 0.0
let kf: f64 = k as f64
let mut i: i64 = 0
while i < n {
let Ey: f64 = mu + kf
let Ey2: f64 = s2 + 2.0 * kf * mu + kf * kf
let denom: f64 = M * (M - 1.0)
let c1: f64 = m * (M - m) / denom
let c2: f64 = m * (m - 1.0) / denom
let Eb2: f64 = c1 * Ey + c2 * Ey2
let y: f64 = Eb2 - comp
let t: f64 = total + y
comp = (t - total) - y
total = t
let alpha: f64 = (M - m) / M
let mu_next: f64 = alpha * Ey
let coeff_y2: f64 = 1.0 - 2.0 * m / M + c2
let s2_next: f64 = coeff_y2 * Ey2 + c1 * Ey
mu = mu_next
s2 = s2_next
M = M - kf
i = i + 1
}
printf("%lld\n", (total + 0.5) as i64)
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 n = 1000000;
int64_t k = 10;
double m = (2.0 * ((double)(k)));
double mu = 0.0;
double s2 = 0.0;
double M = (((double)(k)) * ((double)((n + 1))));
double total = 0.0;
double comp = 0.0;
double kf = ((double)(k));
int64_t i = 0;
while (i < n) {
double Ey = (mu + kf);
double Ey2 = ((s2 + ((2.0 * kf) * mu)) + (kf * kf));
double denom = (M * (M - 1.0));
double c1 = ((m * (M - m)) / denom);
double c2 = ((m * (m - 1.0)) / denom);
double Eb2 = ((c1 * Ey) + (c2 * Ey2));
double y = (Eb2 - comp);
double t = (total + y);
comp = ((t - total) - y);
total = t;
double alpha = ((M - m) / M);
double mu_next = (alpha * Ey);
double coeff_y2 = ((1.0 - ((2.0 * m) / M)) + c2);
double s2_next = ((coeff_y2 * Ey2) + (c1 * Ey));
mu = mu_next;
s2 = s2_next;
M = (M - kf);
i = (i + 1);
}
printf("%lld\n", ((int64_t)((total + 0.5))));
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 @main() -> i32 {
%0 = arith.constant 1000000 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 10 : i32
%3 = arith.extsi %2 : i32 to i64
%4 = arith.constant 2.0 : f32
%5 = arith.sitofp %3 : i64 to f64
%7 = arith.extf %4 : f32 to f64
%6 = arith.mulf %7, %5 : f64
%8 = arith.constant 0.0 : f32
%9 = arith.extf %8 : f32 to f64
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x f64 : (i64) -> !llvm.ptr
llvm.store %9, %11 : f64, !llvm.ptr
%12 = arith.constant 0.0 : f32
%13 = arith.extf %12 : f32 to f64
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x f64 : (i64) -> !llvm.ptr
llvm.store %13, %15 : f64, !llvm.ptr
%16 = arith.sitofp %3 : i64 to f64
%17 = arith.constant 1 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.addi %1, %19 : i64
%20 = arith.sitofp %18 : i64 to f64
%21 = arith.mulf %16, %20 : f64
%22 = llvm.mlir.constant(1 : i64) : i64
%23 = llvm.alloca %22 x f64 : (i64) -> !llvm.ptr
llvm.store %21, %23 : f64, !llvm.ptr
%24 = arith.constant 0.0 : f32
%25 = arith.extf %24 : f32 to f64
%26 = llvm.mlir.constant(1 : i64) : i64
%27 = llvm.alloca %26 x f64 : (i64) -> !llvm.ptr
llvm.store %25, %27 : f64, !llvm.ptr
%28 = arith.constant 0.0 : f32
%29 = arith.extf %28 : f32 to f64
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x f64 : (i64) -> !llvm.ptr
llvm.store %29, %31 : f64, !llvm.ptr
%32 = arith.sitofp %3 : i64 to f64
%33 = arith.constant 0 : i32
%34 = arith.extsi %33 : i32 to i64
%35 = llvm.mlir.constant(1 : i64) : i64
%36 = llvm.alloca %35 x i64 : (i64) -> !llvm.ptr
llvm.store %34, %36 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%37 = llvm.load %36 : !llvm.ptr -> i64
%38 = arith.cmpi slt, %37, %1 : i64
cf.cond_br %38, ^bb1, ^bb2
^bb1:
%39 = llvm.load %11 : !llvm.ptr -> f64
%40 = arith.addf %39, %32 : f64
%41 = llvm.load %15 : !llvm.ptr -> f64
%42 = arith.constant 2.0 : f32
%44 = arith.extf %42 : f32 to f64
%43 = arith.mulf %44, %32 : f64
%45 = llvm.load %11 : !llvm.ptr -> f64
%46 = arith.mulf %43, %45 : f64
%47 = arith.addf %41, %46 : f64
%48 = arith.mulf %32, %32 : f64
%49 = arith.addf %47, %48 : f64
%50 = llvm.load %23 : !llvm.ptr -> f64
%51 = llvm.load %23 : !llvm.ptr -> f64
%52 = arith.constant 1.0 : f32
%54 = arith.extf %52 : f32 to f64
%53 = arith.subf %51, %54 : f64
%55 = arith.mulf %50, %53 : f64
%56 = llvm.load %23 : !llvm.ptr -> f64
%57 = arith.subf %56, %6 : f64
%58 = arith.mulf %6, %57 : f64
%59 = arith.divf %58, %55 : f64
%60 = arith.constant 1.0 : f32
%62 = arith.extf %60 : f32 to f64
%61 = arith.subf %6, %62 : f64
%63 = arith.mulf %6, %61 : f64
%64 = arith.divf %63, %55 : f64
%65 = arith.mulf %59, %40 : f64
%66 = arith.mulf %64, %49 : f64
%67 = arith.addf %65, %66 : f64
%68 = llvm.load %31 : !llvm.ptr -> f64
%69 = arith.subf %67, %68 : f64
%70 = llvm.load %27 : !llvm.ptr -> f64
%71 = arith.addf %70, %69 : f64
%72 = llvm.load %27 : !llvm.ptr -> f64
%73 = arith.subf %71, %72 : f64
%74 = arith.subf %73, %69 : f64
llvm.store %74, %31 : f64, !llvm.ptr
llvm.store %71, %27 : f64, !llvm.ptr
%75 = llvm.load %23 : !llvm.ptr -> f64
%76 = arith.subf %75, %6 : f64
%77 = llvm.load %23 : !llvm.ptr -> f64
%78 = arith.divf %76, %77 : f64
%79 = arith.mulf %78, %40 : f64
%80 = arith.constant 1.0 : f32
%81 = arith.constant 2.0 : f32
%83 = arith.extf %81 : f32 to f64
%82 = arith.mulf %83, %6 : f64
%84 = llvm.load %23 : !llvm.ptr -> f64
%85 = arith.divf %82, %84 : f64
%87 = arith.extf %80 : f32 to f64
%86 = arith.subf %87, %85 : f64
%88 = arith.addf %86, %64 : f64
%89 = arith.mulf %88, %49 : f64
%90 = arith.mulf %59, %40 : f64
%91 = arith.addf %89, %90 : f64
llvm.store %79, %11 : f64, !llvm.ptr
llvm.store %91, %15 : f64, !llvm.ptr
%92 = llvm.load %23 : !llvm.ptr -> f64
%93 = arith.subf %92, %32 : f64
llvm.store %93, %23 : f64, !llvm.ptr
%94 = llvm.load %36 : !llvm.ptr -> i64
%95 = arith.constant 1 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.addi %94, %97 : i64
llvm.store %96, %36 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%98 = llvm.mlir.addressof @str_0 : !llvm.ptr
%99 = llvm.load %27 : !llvm.ptr -> f64
%100 = arith.constant 0.5 : f32
%102 = arith.extf %100 : f32 to f64
%101 = arith.addf %99, %102 : f64
%103 = arith.fptosi %101 : f64 to i64
%104 = llvm.call @printf(%98, %103) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%105 = arith.constant 0 : i32
func.return %105 : i32
}
}