# Project Euler 255
# Average iterations for rounded square roots of 14-digit integers.
import euler.nt { isqrt }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function pow10(e: i64) -> i64 {
let mut r: i64 = 1
for i in 0..e {
r = r * 10
}
return r
}
function floordiv(a: i64, b: i64) -> i64 {
if b == 0 { return 0 }
let q: i64 = a / b
let r: i64 = a % b
if r != 0 {
if a < 0 && b > 0 { q = q - 1 }
elif a > 0 && b < 0 { q = q - 1 }
}
return q
}
function x0_for_digits(d: i64) -> i64 {
if d % 2 == 1 {
return 2 * pow10((d - 1) / 2)
}
return 7 * pow10((d - 2) / 2)
}
function iter_count(n: i64, x0: i64) -> i64 {
let mut x: i64 = x0
let mut it: i64 = 0
while true {
it = it + 1
let x1: i64 = floordiv(x + floordiv(n + x - 1, x), 2)
if x1 == x { return it }
x = x1
}
return 0
}
function print_average(total: i64, count: i64) -> void {
let scale: i64 = 10000000000
let mut ip: i64 = total / count
let mut rem: i64 = total % count
let mut fp: i64 = 0
for di in 0..10 {
rem = rem * 10
let digit: i64 = floordiv(rem, count)
fp = fp * 10 + digit
rem = rem % count
}
if 2 * rem >= count {
fp = fp + 1
if fp >= scale {
fp = fp - scale
ip = ip + 1
}
}
printf("%lld.%010lld\n", ip, fp)
}
function iters_sum_seg(mm: i64, a: i64, b: i64, x: i64, k: i64, total_p: ptr<i64>) -> void {
let q_lo: i64 = floordiv(mm + a + x - 1, x)
let q_hi: i64 = floordiv(mm + b + x - 1, x)
let nk: i64 = k + 1
let mut q: i64 = q_lo
while q <= q_hi {
let mut sa: i64 = (q - 1) * x - mm + 1
if sa < a { sa = a }
let mut sb: i64 = q * x - mm
if sb > b { sb = b }
if sa <= sb {
let cnt: i64 = sb - sa + 1
let x1: i64 = floordiv(x + q, 2)
if x1 == x {
total_p[0] = total_p[0] + nk * cnt
} else {
iters_sum_seg(mm, sa, sb, x1, nk, total_p)
}
}
q = q + 1
}
}
function iters_sum_interval(mm: i64, s_lo: i64, s_hi: i64, x0: i64) -> i64 {
if s_lo > s_hi { return 0 }
let total_p: ptr<i64> = calloc(1, 8)
total_p[0] = 0
iters_sum_seg(mm, s_lo, s_hi, x0, 0, total_p)
let ans: i64 = total_p[0]
free(total_p)
return ans
}
function average_interval(d: i64) -> void {
let L: i64 = pow10(d - 1)
let U: i64 = pow10(d) - 1
let x0: i64 = x0_for_digits(d)
let mut m_full_start: i64 = isqrt(L)
while m_full_start * m_full_start - m_full_start + 1 < L {
m_full_start = m_full_start + 1
}
let mut m_full_end: i64 = isqrt(U)
while m_full_end * m_full_end + m_full_end > U {
m_full_end = m_full_end - 1
}
let mut total: i64 = 0
let m_low: i64 = m_full_start - 1
if m_low > 0 {
let mm: i64 = m_low * m_low
let end: i64 = mm + m_low
if end >= L {
let mut s_lo: i64 = L - mm
let s_min: i64 = -m_low + 1
if s_lo < s_min { s_lo = s_min }
let s_hi: i64 = m_low
total = total + iters_sum_interval(mm, s_lo, s_hi, x0)
}
}
let m_high: i64 = m_full_end + 1
let mm_h: i64 = m_high * m_high
let start: i64 = mm_h - m_high + 1
if start <= U {
let s_lo2: i64 = -m_high + 1
let mut s_hi2: i64 = U - mm_h
if s_hi2 > m_high { s_hi2 = m_high }
total = total + iters_sum_interval(mm_h, s_lo2, s_hi2, x0)
}
let mut m: i64 = m_full_start
let mut mm: i64 = m * m
while m <= m_full_end {
total = total + iters_sum_interval(mm, -m + 1, m, x0)
mm = mm + 2 * m + 1
m = m + 1
}
let count: i64 = U - L + 1
print_average(total, count)
}
function main() -> i32 {
average_interval(14)
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_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t pow10_i64(int64_t e);
int64_t floordiv_i64_i64(int64_t a, int64_t b);
int64_t x0_for_digits_i64(int64_t d);
int64_t iter_count_i64_i64(int64_t n, int64_t x0);
void print_average_i64_i64(int64_t total, int64_t count);
void iters_sum_seg_i64_i64_i64_i64_i64_ptr_i64(int64_t mm, int64_t a, int64_t b, int64_t x, int64_t k, int64_t* total_p);
int64_t iters_sum_interval_i64_i64_i64_i64(int64_t mm, int64_t s_lo, int64_t s_hi, int64_t x0);
void average_interval_i64(int64_t d);
int32_t main(void);
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t pow10_i64(int64_t e) {
int64_t r = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= e) ? i < e : i > e; i += (0 <= e) ? 1 : -1) {
r = (r * 10);
}
return r;
}
int64_t floordiv_i64_i64(int64_t a, int64_t b) {
if (b == 0) {
return 0;
}
int64_t q = FLOW_CHECKED_DIV((a), (b));
int64_t r = FLOW_CHECKED_MOD((a), (b));
if (r != 0) {
if ((a < 0 && b > 0)) {
q = (q - 1);
} else if ((a > 0 && b < 0)) {
q = (q - 1);
}
}
return q;
}
int64_t x0_for_digits_i64(int64_t d) {
if (FLOW_CHECKED_MOD((d), (2)) == 1) {
return (2 * pow10_i64(FLOW_CHECKED_DIV(((d - 1)), (2))));
}
return (7 * pow10_i64(FLOW_CHECKED_DIV(((d - 2)), (2))));
}
int64_t iter_count_i64_i64(int64_t n, int64_t x0) {
int64_t x = x0;
int64_t it = 0;
while (1) {
it = (it + 1);
int64_t x1 = floordiv_i64_i64((x + floordiv_i64_i64(((n + x) - 1), x)), 2);
if (x1 == x) {
return it;
}
x = x1;
}
return 0;
}
void print_average_i64_i64(int64_t total, int64_t count) {
int64_t scale = 10000000000;
int64_t ip = FLOW_CHECKED_DIV((total), (count));
int64_t rem = FLOW_CHECKED_MOD((total), (count));
int64_t fp = 0;
int32_t __flow_step_2 = 1;
for (int32_t di = 0; (0 <= 10) ? di < 10 : di > 10; di += (0 <= 10) ? 1 : -1) {
rem = (rem * 10);
int64_t digit = floordiv_i64_i64(rem, count);
fp = ((fp * 10) + digit);
rem = FLOW_CHECKED_MOD((rem), (count));
}
if ((2 * rem) >= count) {
fp = (fp + 1);
if (fp >= scale) {
fp = (fp - scale);
ip = (ip + 1);
}
}
printf("%lld.%010lld\n", ip, fp);
}
void iters_sum_seg_i64_i64_i64_i64_i64_ptr_i64(int64_t mm, int64_t a, int64_t b, int64_t x, int64_t k, int64_t* total_p) {
int64_t q_lo = floordiv_i64_i64((((mm + a) + x) - 1), x);
int64_t q_hi = floordiv_i64_i64((((mm + b) + x) - 1), x);
int64_t nk = (k + 1);
int64_t q = q_lo;
while (q <= q_hi) {
int64_t sa = ((((q - 1) * x) - mm) + 1);
if (sa < a) {
sa = a;
}
int64_t sb = ((q * x) - mm);
if (sb > b) {
sb = b;
}
if (sa <= sb) {
int64_t cnt = ((sb - sa) + 1);
int64_t x1 = floordiv_i64_i64((x + q), 2);
if (x1 == x) {
total_p[0] = (total_p[0] + (nk * cnt));
} else {
iters_sum_seg_i64_i64_i64_i64_i64_ptr_i64(mm, sa, sb, x1, nk, total_p);
}
}
q = (q + 1);
}
}
int64_t iters_sum_interval_i64_i64_i64_i64(int64_t mm, int64_t s_lo, int64_t s_hi, int64_t x0) {
if (s_lo > s_hi) {
return 0;
}
int64_t* total_p = (int64_t*)(calloc(1, 8));
total_p[0] = 0;
iters_sum_seg_i64_i64_i64_i64_i64_ptr_i64(mm, s_lo, s_hi, x0, 0, total_p);
int64_t ans = total_p[0];
free(total_p);
return ans;
}
void average_interval_i64(int64_t d) {
int64_t L = pow10_i64((d - 1));
int64_t U = (pow10_i64(d) - 1);
int64_t x0 = x0_for_digits_i64(d);
int64_t m_full_start = isqrt_i64(L);
while ((((m_full_start * m_full_start) - m_full_start) + 1) < L) {
m_full_start = (m_full_start + 1);
}
int64_t m_full_end = isqrt_i64(U);
while (((m_full_end * m_full_end) + m_full_end) > U) {
m_full_end = (m_full_end - 1);
}
int64_t total = 0;
int64_t m_low = (m_full_start - 1);
if (m_low > 0) {
int64_t mm = (m_low * m_low);
int64_t end = (mm + m_low);
if (end >= L) {
int64_t s_lo = (L - mm);
int64_t s_min = ((-m_low) + 1);
if (s_lo < s_min) {
s_lo = s_min;
}
int64_t s_hi = m_low;
total = (total + iters_sum_interval_i64_i64_i64_i64(mm, s_lo, s_hi, x0));
}
}
int64_t m_high = (m_full_end + 1);
int64_t mm_h = (m_high * m_high);
int64_t start = ((mm_h - m_high) + 1);
if (start <= U) {
int64_t s_lo2 = ((-m_high) + 1);
int64_t s_hi2 = (U - mm_h);
if (s_hi2 > m_high) {
s_hi2 = m_high;
}
total = (total + iters_sum_interval_i64_i64_i64_i64(mm_h, s_lo2, s_hi2, x0));
}
int64_t m = m_full_start;
int64_t mm = (m * m);
while (m <= m_full_end) {
total = (total + iters_sum_interval_i64_i64_i64_i64(mm, ((-m) + 1), m, x0));
mm = ((mm + (2 * m)) + 1);
m = (m + 1);
}
int64_t count = ((U - L) + 1);
print_average_i64_i64(total, count);
}
int32_t main(void) {
average_interval_i64(14);
return 0;
}