Problem 006

Difference between the square of the sum and the sum of the squares of the first one hundred natural numbers.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 006
# Difference between the square of the sum and the sum of the squares
# of the first one hundred natural numbers.

function solve(n: i64) -> i64 {
    let sum: i64 = n * (n + 1) / 2
    let sum_sq: i64 = n * (n + 1) * (2 * n + 1) / 6
    return sum * sum - sum_sq
}

function main() -> i32 {
    printf("%lld\n", solve(100))
    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 solve_i64(int64_t n);
int32_t main(void);

int64_t solve_i64(int64_t n) {
    int64_t sum = FLOW_CHECKED_DIV(((n * (n + 1))), (2));
    int64_t sum_sq = FLOW_CHECKED_DIV((((n * (n + 1)) * ((2 * n) + 1))), (6));
    return ((sum * sum) - sum_sq);
}

int32_t main(void) {
    printf("%lld\n", solve_i64(100));
    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 @solve(%arg0: i64) -> i64 {
    %0 = arith.constant 1 : i32
    %2 = arith.extsi %0 : i32 to i64
    %1 = arith.addi %arg0, %2 : i64
    %3 = arith.muli %arg0, %1 : i64
    %4 = arith.constant 2 : i32
    %6 = arith.extsi %4 : i32 to i64
    %5 = arith.divsi %3, %6 : i64
    %7 = arith.constant 1 : i32
    %9 = arith.extsi %7 : i32 to i64
    %8 = arith.addi %arg0, %9 : i64
    %10 = arith.muli %arg0, %8 : i64
    %11 = arith.constant 2 : i32
    %13 = arith.extsi %11 : i32 to i64
    %12 = arith.muli %13, %arg0 : i64
    %14 = arith.constant 1 : i32
    %16 = arith.extsi %14 : i32 to i64
    %15 = arith.addi %12, %16 : i64
    %17 = arith.muli %10, %15 : i64
    %18 = arith.constant 6 : i32
    %20 = arith.extsi %18 : i32 to i64
    %19 = arith.divsi %17, %20 : i64
    %21 = arith.muli %5, %5 : i64
    %22 = arith.subi %21, %19 : i64
    func.return %22 : i64
  }
  func.func @main() -> i32 {
    %23 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %25 = arith.constant 100 : i32
    %26 = arith.extsi %25 : i32 to i64
    %24 = func.call @solve(%26) : (i64) -> i64
    %27 = llvm.call @printf(%23, %24) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %28 = arith.constant 0 : i32
    func.return %28 : i32
  }
}