Problem 125

Sum of numbers below 10^8 that are palindromic and sum of consecutive squares.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 125
# Sum of numbers below 10^8 that are palindromic and sum of consecutive squares.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

function is_palindrome(n0: i64) -> bool {
    let mut n: i64 = n0
    let mut rev: i64 = 0
    let orig: i64 = n0
    while n > 0 {
        rev = rev * 10 + n % 10
        n = n / 10
    }
    return rev == orig
}

function main() -> i32 {
    let limit: i64 = 100000000
    # max square root: sqrt(limit) ~ 10000, but consecutive so start from 1
    let max_n: i64 = 10000
    # collect unique sums via boolean array — too big; use sorted unique list
    let capacity: i32 = 200000
    let vals: ptr<i64> = calloc(capacity as i64, 8)
    if vals == null { return 1 }
    let mut count: i32 = 0

    let mut i: i64 = 1
    while i <= max_n {
        let mut s: i64 = i * i
        let mut j: i64 = i + 1
        while j <= max_n {
            s = s + j * j
            if s >= limit { break }
            if is_palindrome(s) {
                # insert unique
                let mut found: bool = false
                let mut k: i32 = 0
                while k < count {
                    if vals[k] == s {
                        found = true
                        break
                    }
                    k = k + 1
                }
                if !found {
                    vals[count] = s
                    count = count + 1
                }
            }
            j = j + 1
        }
        i = i + 1
    }

    let mut total: i64 = 0
    let mut k: i32 = 0
    while k < count {
        total = total + vals[k]
        k = k + 1
    }
    printf("%lld\n", total)
    free(vals)
    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; }

bool is_palindrome_i64(int64_t n0);
int32_t main(void);



bool is_palindrome_i64(int64_t n0) {
    int64_t n = n0;
    int64_t rev = 0;
    int64_t orig = n0;
    while (n > 0) {
        rev = ((rev * 10) + FLOW_CHECKED_MOD((n), (10)));
        n = FLOW_CHECKED_DIV((n), (10));
    }
    return rev == orig;
}

int32_t main(void) {
    int64_t limit = 100000000;
    int64_t max_n = 10000;
    int32_t capacity = 200000;
    int64_t* vals = (int64_t*)(calloc(((int64_t)(capacity)), 8));
    if (vals == NULL) {
        return 1;
    }
    int32_t count = 0;
    int64_t i = 1;
    while (i <= max_n) {
        int64_t s = (i * i);
        int64_t j = (i + 1);
        while (j <= max_n) {
            s = (s + (j * j));
            if (s >= limit) {
                break;
            }
            if (is_palindrome_i64(s)) {
                bool found = 0;
                int32_t k = 0;
                while (k < count) {
                    if (vals[k] == s) {
                        found = 1;
                        break;
                    }
                    k = (k + 1);
                }
                if ((!(found))) {
                    vals[count] = s;
                    count = (count + 1);
                }
            }
            j = (j + 1);
        }
        i = (i + 1);
    }
    int64_t total = 0;
    int32_t k = 0;
    while (k < count) {
        total = (total + vals[k]);
        k = (k + 1);
    }
    printf("%lld\n", total);
    free(vals);
    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 private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  func.func @is_palindrome(%arg0: i64) -> i1 {
    %0 = llvm.mlir.constant(1 : i64) : i64
    %1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %1 : i64, !llvm.ptr
    %2 = arith.constant 0 : i32
    %3 = arith.extsi %2 : i32 to i64
    %4 = llvm.mlir.constant(1 : i64) : i64
    %5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
    llvm.store %3, %5 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %6 = llvm.load %1 : !llvm.ptr -> i64
    %7 = arith.constant 0 : i32
    %9 = arith.extsi %7 : i32 to i64
    %8 = arith.cmpi sgt, %6, %9 : i64
    cf.cond_br %8, ^bb1, ^bb2
    ^bb1:
      %10 = llvm.load %5 : !llvm.ptr -> i64
      %11 = arith.constant 10 : i32
      %13 = arith.extsi %11 : i32 to i64
      %12 = arith.muli %10, %13 : i64
      %14 = llvm.load %1 : !llvm.ptr -> i64
      %15 = arith.constant 10 : i32
      %17 = arith.extsi %15 : i32 to i64
      %16 = arith.remsi %14, %17 : i64
      %18 = arith.addi %12, %16 : i64
      llvm.store %18, %5 : i64, !llvm.ptr
      %19 = llvm.load %1 : !llvm.ptr -> i64
      %20 = arith.constant 10 : i32
      %22 = arith.extsi %20 : i32 to i64
      %21 = arith.divsi %19, %22 : i64
      llvm.store %21, %1 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %23 = llvm.load %5 : !llvm.ptr -> i64
    %24 = arith.cmpi eq, %23, %arg0 : i64
    func.return %24 : i1
  }
  func.func @main() -> i32 {
    %25 = arith.constant 100000000 : i32
    %26 = arith.extsi %25 : i32 to i64
    %27 = arith.constant 10000 : i32
    %28 = arith.extsi %27 : i32 to i64
    %29 = arith.constant 200000 : i32
    %31 = arith.extsi %29 : i32 to i64
    %32 = arith.constant 8 : i32
    %33 = arith.extsi %32 : i32 to i64
    %30 = func.call @calloc(%31, %33) : (i64, i64) -> !llvm.ptr
    %34 = llvm.mlir.zero : !llvm.ptr
    %35 = llvm.icmp "eq" %30, %34 : !llvm.ptr
    cf.cond_br %35, ^bb3, ^bb4
    ^bb3:
      %36 = arith.constant 1 : i32
      func.return %36 : i32
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %37 = arith.constant 0 : i32
    %38 = llvm.mlir.constant(1 : i64) : i64
    %39 = llvm.alloca %38 x i32 : (i64) -> !llvm.ptr
    llvm.store %37, %39 : i32, !llvm.ptr
    %40 = arith.constant 1 : i32
    %41 = arith.extsi %40 : i32 to i64
    %42 = llvm.mlir.constant(1 : i64) : i64
    %43 = llvm.alloca %42 x i64 : (i64) -> !llvm.ptr
    llvm.store %41, %43 : i64, !llvm.ptr
    cf.br ^bb6
    ^bb6:
    %44 = llvm.load %43 : !llvm.ptr -> i64
    %45 = arith.cmpi sle, %44, %28 : i64
    cf.cond_br %45, ^bb7, ^bb8
    ^bb7:
      %46 = llvm.load %43 : !llvm.ptr -> i64
      %47 = llvm.load %43 : !llvm.ptr -> i64
      %48 = arith.muli %46, %47 : i64
      %49 = llvm.mlir.constant(1 : i64) : i64
      %50 = llvm.alloca %49 x i64 : (i64) -> !llvm.ptr
      llvm.store %48, %50 : i64, !llvm.ptr
      %51 = llvm.load %43 : !llvm.ptr -> i64
      %52 = arith.constant 1 : i32
      %54 = arith.extsi %52 : i32 to i64
      %53 = arith.addi %51, %54 : i64
      %55 = llvm.mlir.constant(1 : i64) : i64
      %56 = llvm.alloca %55 x i64 : (i64) -> !llvm.ptr
      llvm.store %53, %56 : i64, !llvm.ptr
      cf.br ^bb9
      ^bb9:
      %57 = llvm.load %56 : !llvm.ptr -> i64
      %58 = arith.cmpi sle, %57, %28 : i64
      cf.cond_br %58, ^bb10, ^bb11
      ^bb10:
        %59 = llvm.load %50 : !llvm.ptr -> i64
        %60 = llvm.load %56 : !llvm.ptr -> i64
        %61 = llvm.load %56 : !llvm.ptr -> i64
        %62 = arith.muli %60, %61 : i64
        %63 = arith.addi %59, %62 : i64
        llvm.store %63, %50 : i64, !llvm.ptr
        %64 = llvm.load %50 : !llvm.ptr -> i64
        %65 = arith.cmpi sge, %64, %26 : i64
        cf.cond_br %65, ^bb12, ^bb13
        ^bb12:
          cf.br ^bb11
        ^bb13:
          cf.br ^bb14
        ^bb14:
        %67 = llvm.load %50 : !llvm.ptr -> i64
        %66 = func.call @is_palindrome(%67) : (i64) -> i1
        cf.cond_br %66, ^bb15, ^bb16
        ^bb15:
          %68 = arith.constant 0 : i1
          %69 = llvm.mlir.constant(1 : i64) : i64
          %70 = llvm.alloca %69 x i1 : (i64) -> !llvm.ptr
          llvm.store %68, %70 : i1, !llvm.ptr
          %71 = arith.constant 0 : i32
          %72 = llvm.mlir.constant(1 : i64) : i64
          %73 = llvm.alloca %72 x i32 : (i64) -> !llvm.ptr
          llvm.store %71, %73 : i32, !llvm.ptr
          cf.br ^bb18
          ^bb18:
          %74 = llvm.load %73 : !llvm.ptr -> i32
          %75 = llvm.load %39 : !llvm.ptr -> i32
          %76 = arith.cmpi slt, %74, %75 : i32
          cf.cond_br %76, ^bb19, ^bb20
          ^bb19:
            %78 = llvm.load %73 : !llvm.ptr -> i32
            %79 = arith.extsi %78 : i32 to i64
            %80 = llvm.getelementptr %30[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i64
            %77 = llvm.load %80 : !llvm.ptr -> i64
            %81 = llvm.load %50 : !llvm.ptr -> i64
            %82 = arith.cmpi eq, %77, %81 : i64
            cf.cond_br %82, ^bb21, ^bb22
            ^bb21:
              %83 = arith.constant 1 : i1
              llvm.store %83, %70 : i1, !llvm.ptr
              cf.br ^bb20
            ^bb22:
              cf.br ^bb23
            ^bb23:
            %84 = llvm.load %73 : !llvm.ptr -> i32
            %85 = arith.constant 1 : i32
            %86 = arith.addi %84, %85 : i32
            llvm.store %86, %73 : i32, !llvm.ptr
            cf.br ^bb18
          ^bb20:
          %87 = llvm.load %70 : !llvm.ptr -> i1
          %89 = arith.constant 1 : i1
          %88 = arith.xori %87, %89 : i1
          cf.cond_br %88, ^bb24, ^bb25
          ^bb24:
            %91 = llvm.load %50 : !llvm.ptr -> i64
            %92 = llvm.load %39 : !llvm.ptr -> i32
            %93 = arith.extsi %92 : i32 to i64
            %94 = llvm.getelementptr %30[%93] : (!llvm.ptr, i64) -> !llvm.ptr, i64
            llvm.store %91, %94 : i64, !llvm.ptr
            %95 = llvm.load %39 : !llvm.ptr -> i32
            %96 = arith.constant 1 : i32
            %97 = arith.addi %95, %96 : i32
            llvm.store %97, %39 : i32, !llvm.ptr
            cf.br ^bb26
          ^bb25:
            cf.br ^bb26
          ^bb26:
          cf.br ^bb17
        ^bb16:
          cf.br ^bb17
        ^bb17:
        %98 = llvm.load %56 : !llvm.ptr -> i64
        %99 = arith.constant 1 : i32
        %101 = arith.extsi %99 : i32 to i64
        %100 = arith.addi %98, %101 : i64
        llvm.store %100, %56 : i64, !llvm.ptr
        cf.br ^bb9
      ^bb11:
      %102 = llvm.load %43 : !llvm.ptr -> i64
      %103 = arith.constant 1 : i32
      %105 = arith.extsi %103 : i32 to i64
      %104 = arith.addi %102, %105 : i64
      llvm.store %104, %43 : i64, !llvm.ptr
      cf.br ^bb6
    ^bb8:
    %106 = arith.constant 0 : i32
    %107 = arith.extsi %106 : i32 to i64
    %108 = llvm.mlir.constant(1 : i64) : i64
    %109 = llvm.alloca %108 x i64 : (i64) -> !llvm.ptr
    llvm.store %107, %109 : i64, !llvm.ptr
    %110 = arith.constant 0 : i32
    %111 = llvm.mlir.constant(1 : i64) : i64
    %112 = llvm.alloca %111 x i32 : (i64) -> !llvm.ptr
    llvm.store %110, %112 : i32, !llvm.ptr
    cf.br ^bb27
    ^bb27:
    %113 = llvm.load %112 : !llvm.ptr -> i32
    %114 = llvm.load %39 : !llvm.ptr -> i32
    %115 = arith.cmpi slt, %113, %114 : i32
    cf.cond_br %115, ^bb28, ^bb29
    ^bb28:
      %116 = llvm.load %109 : !llvm.ptr -> i64
      %118 = llvm.load %112 : !llvm.ptr -> i32
      %119 = arith.extsi %118 : i32 to i64
      %120 = llvm.getelementptr %30[%119] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %117 = llvm.load %120 : !llvm.ptr -> i64
      %121 = arith.addi %116, %117 : i64
      llvm.store %121, %109 : i64, !llvm.ptr
      %122 = llvm.load %112 : !llvm.ptr -> i32
      %123 = arith.constant 1 : i32
      %124 = arith.addi %122, %123 : i32
      llvm.store %124, %112 : i32, !llvm.ptr
      cf.br ^bb27
    ^bb29:
    %125 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %126 = llvm.load %109 : !llvm.ptr -> i64
    %127 = llvm.call @printf(%125, %126) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%30) : (!llvm.ptr) -> ()
    %129 = arith.constant 0 : i32
    func.return %129 : i32
  }
}