Problem 380
Spanning trees of 100×500 grid in scientific notation (5 sig digits).
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(1) | ? |
|---|
| Space complexity | O(n) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 380
# Spanning trees of 100×500 grid in scientific notation (5 sig digits).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function cos(x: f64) -> f64
function log(x: f64) -> f64
function pow(x: f64, y: f64) -> f64
function floor(x: f64) -> f64
}
function flog10(x: f64) -> f64 {
return log(x) / log(10.0)
}
function spanning_log(m: i64, n: i64) -> f64 {
if m * n == 1 { return 0.0 }
let pi: f64 = 3.14159265358979323846
let a: ptr<f64> = calloc(m, 8)
let b: ptr<f64> = calloc(n, 8)
let mut i: i64 = 0
while i < m {
a[i] = 2.0 * cos(pi * (i as f64) / (m as f64))
i = i + 1
}
let mut j: i64 = 0
while j < n {
b[j] = 2.0 * cos(pi * (j as f64) / (n as f64))
j = j + 1
}
let mut total: f64 = 0.0 - flog10((m * n) as f64)
let mut c: f64 = 0.0
i = 0
while i < m {
let ai: f64 = a[i]
j = 0
while j < n {
if !(i == 0 && j == 0) {
let lam: f64 = 4.0 - ai - b[j]
let y: f64 = flog10(lam) - c
let t: f64 = total + y
c = (t - total) - y
total = t
}
j = j + 1
}
i = i + 1
}
free(b)
free(a)
return total
}
function main() -> i32 {
let log10x: f64 = spanning_log(100, 500)
let expv: i64 = floor(log10x) as i64
let frac: f64 = log10x - (expv as f64)
let mut mant: f64 = pow(10.0, frac)
# round to 4 decimal places (5 significant digits)
let mut mant_r: f64 = floor(mant * 10000.0 + 0.5) / 10000.0
let mut exp_out: i64 = expv
if mant_r >= 10.0 {
mant_r = mant_r / 10.0
exp_out = exp_out + 1
}
printf("%.4fe%lld\n", mant_r, exp_out)
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; }
double flog10_f64(double x);
double spanning_log_i64_i64(int64_t m, int64_t n);
int32_t main(void);
double flog10_f64(double x) {
return (log(x) / log(10.0));
}
double spanning_log_i64_i64(int64_t m, int64_t n) {
if ((m * n) == 1) {
return 0.0;
}
double pi = 3.14159265358979323846;
double* a = (double*)(calloc(m, 8));
double* b = (double*)(calloc(n, 8));
int64_t i = 0;
while (i < m) {
a[i] = (2.0 * cos(((pi * ((double)(i))) / ((double)(m)))));
i = (i + 1);
}
int64_t j = 0;
while (j < n) {
b[j] = (2.0 * cos(((pi * ((double)(j))) / ((double)(n)))));
j = (j + 1);
}
double total = (0.0 - flog10_f64(((double)((m * n)))));
double c = 0.0;
i = 0;
while (i < m) {
double ai = a[i];
j = 0;
while (j < n) {
if ((!((i == 0 && j == 0)))) {
double lam = ((4.0 - ai) - b[j]);
double y = (flog10_f64(lam) - c);
double t = (total + y);
c = ((t - total) - y);
total = t;
}
j = (j + 1);
}
i = (i + 1);
}
free(b);
free(a);
return total;
}
int32_t main(void) {
double log10x = spanning_log_i64_i64(100, 500);
int64_t expv = ((int64_t)(floor(log10x)));
double frac = (log10x - ((double)(expv)));
double mant = pow(10.0, frac);
double mant_r = (floor(((mant * 10000.0) + 0.5)) / 10000.0);
int64_t exp_out = expv;
if (mant_r >= 10.0) {
mant_r = (mant_r / 10.0);
exp_out = (exp_out + 1);
}
printf("%.4fe%lld\n", mant_r, exp_out);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%.4fe%lld\n\00") {addr_space = 0 : i32} : !llvm.array<11 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @cos(f64) -> f64
func.func private @log(f64) -> f64
func.func private @pow(f64, f64) -> f64
func.func private @floor(f64) -> f64
func.func @flog10(%arg0: f64) -> f64 {
%0 = math.log %arg0 : f64
%1 = arith.constant 10.0 : f32
%2 = math.log %1 : f32
%3 = arith.divf %0, %2 : f64
func.return %3 : f64
}
func.func @spanning_log(%arg0: i64, %arg1: i64) -> f64 {
%4 = arith.muli %arg0, %arg1 : i64
%5 = arith.constant 1 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi eq, %4, %7 : i64
cf.cond_br %6, ^bb0, ^bb1
^bb0:
%8 = arith.constant 0.0 : f32
%9 = arith.extf %8 : f32 to f64
func.return %9 : f64
^bb1:
cf.br ^bb2
^bb2:
%10 = arith.constant 3.14159265358979323846 : f32
%11 = arith.extf %10 : f32 to f64
%13 = arith.constant 8 : i32
%14 = arith.extsi %13 : i32 to i64
%12 = func.call @calloc(%arg0, %14) : (i64, i64) -> !llvm.ptr
%16 = arith.constant 8 : i32
%17 = arith.extsi %16 : i32 to i64
%15 = func.call @calloc(%arg1, %17) : (i64, i64) -> !llvm.ptr
%18 = arith.constant 0 : i32
%19 = arith.extsi %18 : i32 to i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%22 = llvm.load %21 : !llvm.ptr -> i64
%23 = arith.cmpi slt, %22, %arg0 : i64
cf.cond_br %23, ^bb4, ^bb5
^bb4:
%24 = arith.constant 2.0 : f32
%25 = llvm.load %21 : !llvm.ptr -> i64
%26 = arith.sitofp %25 : i64 to f64
%27 = arith.mulf %11, %26 : f64
%28 = arith.sitofp %arg0 : i64 to f64
%29 = arith.divf %27, %28 : f64
%30 = math.cos %29 : f64
%32 = arith.extf %24 : f32 to f64
%31 = arith.mulf %32, %30 : f64
%33 = llvm.load %21 : !llvm.ptr -> i64
%34 = llvm.getelementptr %12[%33] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %31, %34 : f64, !llvm.ptr
%35 = llvm.load %21 : !llvm.ptr -> i64
%36 = arith.constant 1 : i32
%38 = arith.extsi %36 : i32 to i64
%37 = arith.addi %35, %38 : i64
llvm.store %37, %21 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%39 = arith.constant 0 : i32
%40 = arith.extsi %39 : i32 to i64
%41 = llvm.mlir.constant(1 : i64) : i64
%42 = llvm.alloca %41 x i64 : (i64) -> !llvm.ptr
llvm.store %40, %42 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%43 = llvm.load %42 : !llvm.ptr -> i64
%44 = arith.cmpi slt, %43, %arg1 : i64
cf.cond_br %44, ^bb7, ^bb8
^bb7:
%45 = arith.constant 2.0 : f32
%46 = llvm.load %42 : !llvm.ptr -> i64
%47 = arith.sitofp %46 : i64 to f64
%48 = arith.mulf %11, %47 : f64
%49 = arith.sitofp %arg1 : i64 to f64
%50 = arith.divf %48, %49 : f64
%51 = math.cos %50 : f64
%53 = arith.extf %45 : f32 to f64
%52 = arith.mulf %53, %51 : f64
%54 = llvm.load %42 : !llvm.ptr -> i64
%55 = llvm.getelementptr %15[%54] : (!llvm.ptr, i64) -> !llvm.ptr, f64
llvm.store %52, %55 : f64, !llvm.ptr
%56 = llvm.load %42 : !llvm.ptr -> i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.addi %56, %59 : i64
llvm.store %58, %42 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%60 = arith.constant 0.0 : f32
%62 = arith.muli %arg0, %arg1 : i64
%63 = arith.sitofp %62 : i64 to f64
%61 = func.call @flog10(%63) : (f64) -> f64
%65 = arith.extf %60 : f32 to f64
%64 = arith.subf %65, %61 : f64
%66 = llvm.mlir.constant(1 : i64) : i64
%67 = llvm.alloca %66 x f64 : (i64) -> !llvm.ptr
llvm.store %64, %67 : f64, !llvm.ptr
%68 = arith.constant 0.0 : f32
%69 = arith.extf %68 : f32 to f64
%70 = llvm.mlir.constant(1 : i64) : i64
%71 = llvm.alloca %70 x f64 : (i64) -> !llvm.ptr
llvm.store %69, %71 : f64, !llvm.ptr
%72 = arith.constant 0 : i32
%73 = arith.extsi %72 : i32 to i64
llvm.store %73, %21 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%74 = llvm.load %21 : !llvm.ptr -> i64
%75 = arith.cmpi slt, %74, %arg0 : i64
cf.cond_br %75, ^bb10, ^bb11
^bb10:
%77 = llvm.load %21 : !llvm.ptr -> i64
%78 = llvm.getelementptr %12[%77] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%76 = llvm.load %78 : !llvm.ptr -> f64
%79 = arith.constant 0 : i32
%80 = arith.extsi %79 : i32 to i64
llvm.store %80, %42 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%81 = llvm.load %42 : !llvm.ptr -> i64
%82 = arith.cmpi slt, %81, %arg1 : i64
cf.cond_br %82, ^bb13, ^bb14
^bb13:
%83 = llvm.load %21 : !llvm.ptr -> i64
%84 = arith.constant 0 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.cmpi eq, %83, %86 : i64
%87 = scf.if %85 -> (i1) {
%88 = llvm.load %42 : !llvm.ptr -> i64
%89 = arith.constant 0 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.cmpi eq, %88, %91 : i64
scf.yield %90 : i1
} else {
%92 = arith.constant false
scf.yield %92 : i1
}
%94 = arith.constant 1 : i1
%93 = arith.xori %87, %94 : i1
cf.cond_br %93, ^bb15, ^bb16
^bb15:
%96 = arith.constant 4.0 : f32
%98 = arith.extf %96 : f32 to f64
%97 = arith.subf %98, %76 : f64
%100 = llvm.load %42 : !llvm.ptr -> i64
%101 = llvm.getelementptr %15[%100] : (!llvm.ptr, i64) -> !llvm.ptr, f64
%99 = llvm.load %101 : !llvm.ptr -> f64
%102 = arith.subf %97, %99 : f64
%103 = func.call @flog10(%102) : (f64) -> f64
%104 = llvm.load %71 : !llvm.ptr -> f64
%105 = arith.subf %103, %104 : f64
%106 = llvm.load %67 : !llvm.ptr -> f64
%107 = arith.addf %106, %105 : f64
%108 = llvm.load %67 : !llvm.ptr -> f64
%109 = arith.subf %107, %108 : f64
%110 = arith.subf %109, %105 : f64
llvm.store %110, %71 : f64, !llvm.ptr
llvm.store %107, %67 : f64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%111 = llvm.load %42 : !llvm.ptr -> i64
%112 = arith.constant 1 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.addi %111, %114 : i64
llvm.store %113, %42 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%115 = llvm.load %21 : !llvm.ptr -> i64
%116 = arith.constant 1 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.addi %115, %118 : i64
llvm.store %117, %21 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
func.call @free(%15) : (!llvm.ptr) -> ()
func.call @free(%12) : (!llvm.ptr) -> ()
%121 = llvm.load %67 : !llvm.ptr -> f64
func.return %121 : f64
}
func.func @main() -> i32 {
%123 = arith.constant 100 : i32
%124 = arith.constant 500 : i32
%125 = arith.extsi %123 : i32 to i64
%126 = arith.extsi %124 : i32 to i64
%122 = func.call @spanning_log(%125, %126) : (i64, i64) -> f64
%127 = func.call @floor(%122) : (f64) -> f64
%128 = arith.fptosi %127 : f64 to i64
%129 = arith.sitofp %128 : i64 to f64
%130 = arith.subf %122, %129 : f64
%132 = arith.constant 10.0 : f32
%133 = arith.extf %132 : f32 to f64
%131 = func.call @pow(%133, %130) : (f64, f64) -> f64
%134 = llvm.mlir.constant(1 : i64) : i64
%135 = llvm.alloca %134 x f64 : (i64) -> !llvm.ptr
llvm.store %131, %135 : f64, !llvm.ptr
%137 = llvm.load %135 : !llvm.ptr -> f64
%138 = arith.constant 10000.0 : f32
%140 = arith.extf %138 : f32 to f64
%139 = arith.mulf %137, %140 : f64
%141 = arith.constant 0.5 : f32
%143 = arith.extf %141 : f32 to f64
%142 = arith.addf %139, %143 : f64
%136 = func.call @floor(%142) : (f64) -> f64
%144 = arith.constant 10000.0 : f32
%146 = arith.extf %144 : f32 to f64
%145 = arith.divf %136, %146 : f64
%147 = llvm.mlir.constant(1 : i64) : i64
%148 = llvm.alloca %147 x f64 : (i64) -> !llvm.ptr
llvm.store %145, %148 : f64, !llvm.ptr
%149 = llvm.mlir.constant(1 : i64) : i64
%150 = llvm.alloca %149 x i64 : (i64) -> !llvm.ptr
llvm.store %128, %150 : i64, !llvm.ptr
%151 = llvm.load %148 : !llvm.ptr -> f64
%152 = arith.constant 10.0 : f32
%154 = arith.extf %152 : f32 to f64
%153 = arith.cmpf oge, %151, %154 : f64
cf.cond_br %153, ^bb18, ^bb19
^bb18:
%155 = llvm.load %148 : !llvm.ptr -> f64
%156 = arith.constant 10.0 : f32
%158 = arith.extf %156 : f32 to f64
%157 = arith.divf %155, %158 : f64
llvm.store %157, %148 : f64, !llvm.ptr
%159 = llvm.load %150 : !llvm.ptr -> i64
%160 = arith.constant 1 : i32
%162 = arith.extsi %160 : i32 to i64
%161 = arith.addi %159, %162 : i64
llvm.store %161, %150 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%163 = llvm.mlir.addressof @str_0 : !llvm.ptr
%164 = llvm.load %148 : !llvm.ptr -> f64
%165 = llvm.load %150 : !llvm.ptr -> i64
%166 = llvm.call @printf(%163, %164, %165) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, f64, i64) -> i32
%167 = arith.constant 0 : i32
func.return %167 : i32
}
}