# Project Euler 066
# Minimal solution of x² − D y² = 1; find D ≤ 1000 with largest x.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
}
function is_square(n: i64) -> bool {
let mut r: i64 = 1
while r * r < n { r = r + 1 }
return r * r == n
}
function max2i(a: i32, b: i32) -> i32 {
if a > b { return a }
return b
}
function set_small(d: ptr<i32>, v: i64) -> i32 {
if v == 0 {
d[0] = 0
return 1
}
let mut x: i64 = v
let mut len: i32 = 0
while x > 0 {
d[len] = (x % 10) as i32
x = x / 10
len = len + 1
}
return len
}
function add_big(a: ptr<i32>, alen: i32, b: ptr<i32>, blen: i32, out: ptr<i32>) -> i32 {
let mut carry: i32 = 0
let mut i: i32 = 0
let maxlen: i32 = max2i(alen, blen)
while i < maxlen || carry > 0 {
let mut v: i32 = carry
if i < alen { v = v + a[i] }
if i < blen { v = v + b[i] }
out[i] = v % 10
carry = v / 10
i = i + 1
}
return i
}
function mul_small(a: ptr<i32>, alen: i32, m: i64, out: ptr<i32>) -> i32 {
let mut carry: i64 = 0
let mut i: i32 = 0
while i < alen {
let v: i64 = (a[i] as i64) * m + carry
out[i] = (v % 10) as i32
carry = v / 10
i = i + 1
}
while carry > 0 {
out[i] = (carry % 10) as i32
carry = carry / 10
i = i + 1
}
return i
}
function mul_big(a: ptr<i32>, alen: i32, b: ptr<i32>, blen: i32, out: ptr<i32>, outmax: i32) -> i32 {
let mut i: i32 = 0
while i < outmax {
out[i] = 0
i = i + 1
}
i = 0
while i < alen {
let mut carry: i64 = 0
let mut j: i32 = 0
while j < blen {
let idx: i32 = i + j
let v: i64 = (out[idx] as i64) + (a[i] as i64) * (b[j] as i64) + carry
out[idx] = (v % 10) as i32
carry = v / 10
j = j + 1
}
let mut idx: i32 = i + blen
while carry > 0 {
let v: i64 = (out[idx] as i64) + carry
out[idx] = (v % 10) as i32
carry = v / 10
idx = idx + 1
}
i = i + 1
}
let mut len: i32 = alen + blen
while len > 1 && out[len - 1] == 0 {
len = len - 1
}
return len
}
function cmp_big(a: ptr<i32>, alen: i32, b: ptr<i32>, blen: i32) -> i32 {
if alen != blen {
if alen > blen { return 1 }
return -1
}
let mut i: i32 = alen - 1
while i >= 0 {
if a[i] != b[i] {
if a[i] > b[i] { return 1 }
return -1
}
i = i - 1
}
return 0
}
# returns true if a - b == 1 (a >= b)
function diff_is_one(a: ptr<i32>, alen: i32, b: ptr<i32>, blen: i32) -> bool {
let mut borrow: i32 = 0
let mut i: i32 = 0
let maxlen: i32 = max2i(alen, blen)
while i < maxlen {
let mut av: i32 = 0
let mut bv: i32 = 0
if i < alen { av = a[i] }
if i < blen { bv = b[i] }
let mut v: i32 = av - bv - borrow
if v < 0 {
v = v + 10
borrow = 1
} else {
borrow = 0
}
if i == 0 {
if v != 1 { return false }
} else {
if v != 0 { return false }
}
i = i + 1
}
return borrow == 0
}
function main() -> i32 {
let width: i32 = 80
let wide: i32 = 160
let best_x: ptr<i32> = calloc(width as i64, 4)
let tmp: ptr<i32> = calloc(width as i64, 4)
let hh: ptr<i32> = calloc(wide as i64, 4)
let kk: ptr<i32> = calloc(wide as i64, 4)
let dkk: ptr<i32> = calloc(wide as i64, 4)
if best_x == null || tmp == null || hh == null || kk == null || dkk == null { return 1 }
let mut best_len: i32 = 0
let mut best_d: i64 = 0
let mut d: i64 = 2
while d <= 1000 {
if !is_square(d) {
let mut r: i64 = 1
while r * r <= d { r = r + 1 }
r = r - 1
let h0: ptr<i32> = calloc(width as i64, 4)
let h1: ptr<i32> = calloc(width as i64, 4)
let h2: ptr<i32> = calloc(width as i64, 4)
let k0: ptr<i32> = calloc(width as i64, 4)
let k1: ptr<i32> = calloc(width as i64, 4)
let k2: ptr<i32> = calloc(width as i64, 4)
if h0 == null || h1 == null || h2 == null || k0 == null || k1 == null || k2 == null {
return 1
}
# h-2=0, h-1=1; k-2=1, k-1=0
let mut hlen0: i32 = set_small(h0, 0)
let mut hlen1: i32 = set_small(h1, 1)
let mut klen0: i32 = set_small(k0, 1)
let mut klen1: i32 = set_small(k1, 0)
let mut m: i64 = 0
let mut dd: i64 = 1
let mut a: i64 = r
let mut step: i32 = 0
while step < 500 {
let ml: i32 = mul_small(h1, hlen1, a, tmp)
let hlen2: i32 = add_big(tmp, ml, h0, hlen0, h2)
let mlk: i32 = mul_small(k1, klen1, a, tmp)
let klen2: i32 = add_big(tmp, mlk, k0, klen0, k2)
let hhlen: i32 = mul_big(h2, hlen2, h2, hlen2, hh, wide)
let kklen: i32 = mul_big(k2, klen2, k2, klen2, kk, wide)
# dkk = d * kk
let mut i: i32 = 0
while i < wide {
dkk[i] = 0
i = i + 1
}
let dkklen: i32 = mul_small(kk, kklen, d, dkk)
if diff_is_one(hh, hhlen, dkk, dkklen) {
if best_len == 0 || cmp_big(h2, hlen2, best_x, best_len) > 0 {
memcpy(best_x, h2, (hlen2 as i64) * 4)
best_len = hlen2
best_d = d
}
break
}
memcpy(h0, h1, (hlen1 as i64) * 4)
hlen0 = hlen1
memcpy(h1, h2, (hlen2 as i64) * 4)
hlen1 = hlen2
memcpy(k0, k1, (klen1 as i64) * 4)
klen0 = klen1
memcpy(k1, k2, (klen2 as i64) * 4)
klen1 = klen2
m = dd * a - m
dd = (d - m * m) / dd
a = (r + m) / dd
step = step + 1
}
free(h0)
free(h1)
free(h2)
free(k0)
free(k1)
free(k2)
}
d = d + 1
}
printf("%lld\n", best_d)
free(dkk)
free(kk)
free(hh)
free(tmp)
free(best_x)
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_square_i64(int64_t n);
int32_t max2i_i32_i32(int32_t a, int32_t b);
int32_t set_small_ptr_i32_i64(int32_t* d, int64_t v);
int32_t add_big_ptr_i32_i32_ptr_i32_i32_ptr_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen, int32_t* out);
int32_t mul_small_ptr_i32_i32_i64_ptr_i32(int32_t* a, int32_t alen, int64_t m, int32_t* out);
int32_t mul_big_ptr_i32_i32_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen, int32_t* out, int32_t outmax);
int32_t cmp_big_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen);
bool diff_is_one_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen);
int32_t main(void);
bool is_square_i64(int64_t n) {
int64_t r = 1;
while ((r * r) < n) {
r = (r + 1);
}
return (r * r) == n;
}
int32_t max2i_i32_i32(int32_t a, int32_t b) {
if (a > b) {
return a;
}
return b;
}
int32_t set_small_ptr_i32_i64(int32_t* d, int64_t v) {
if (v == 0) {
d[0] = 0;
return 1;
}
int64_t x = v;
int32_t len = 0;
while (x > 0) {
d[len] = ((int32_t)(FLOW_CHECKED_MOD((x), (10))));
x = FLOW_CHECKED_DIV((x), (10));
len = (len + 1);
}
return len;
}
int32_t add_big_ptr_i32_i32_ptr_i32_i32_ptr_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen, int32_t* out) {
int32_t carry = 0;
int32_t i = 0;
int32_t maxlen = max2i_i32_i32(alen, blen);
while ((i < maxlen || carry > 0)) {
int32_t v = carry;
if (i < alen) {
v = (v + a[i]);
}
if (i < blen) {
v = (v + b[i]);
}
out[i] = FLOW_CHECKED_MOD((v), (10));
carry = FLOW_CHECKED_DIV((v), (10));
i = (i + 1);
}
return i;
}
int32_t mul_small_ptr_i32_i32_i64_ptr_i32(int32_t* a, int32_t alen, int64_t m, int32_t* out) {
int64_t carry = 0;
int32_t i = 0;
while (i < alen) {
int64_t v = ((((int64_t)(a[i])) * m) + carry);
out[i] = ((int32_t)(FLOW_CHECKED_MOD((v), (10))));
carry = FLOW_CHECKED_DIV((v), (10));
i = (i + 1);
}
while (carry > 0) {
out[i] = ((int32_t)(FLOW_CHECKED_MOD((carry), (10))));
carry = FLOW_CHECKED_DIV((carry), (10));
i = (i + 1);
}
return i;
}
int32_t mul_big_ptr_i32_i32_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen, int32_t* out, int32_t outmax) {
int32_t i = 0;
while (i < outmax) {
out[i] = 0;
i = (i + 1);
}
i = 0;
while (i < alen) {
int64_t carry = 0;
int32_t j = 0;
while (j < blen) {
int32_t idx = (i + j);
int64_t v = ((((int64_t)(out[idx])) + (((int64_t)(a[i])) * ((int64_t)(b[j])))) + carry);
out[idx] = ((int32_t)(FLOW_CHECKED_MOD((v), (10))));
carry = FLOW_CHECKED_DIV((v), (10));
j = (j + 1);
}
int32_t idx = (i + blen);
while (carry > 0) {
int64_t v = (((int64_t)(out[idx])) + carry);
out[idx] = ((int32_t)(FLOW_CHECKED_MOD((v), (10))));
carry = FLOW_CHECKED_DIV((v), (10));
idx = (idx + 1);
}
i = (i + 1);
}
int32_t len = (alen + blen);
while ((len > 1 && out[(len - 1)] == 0)) {
len = (len - 1);
}
return len;
}
int32_t cmp_big_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen) {
if (alen != blen) {
if (alen > blen) {
return 1;
}
return (-1);
}
int32_t i = (alen - 1);
while (i >= 0) {
if (a[i] != b[i]) {
if (a[i] > b[i]) {
return 1;
}
return (-1);
}
i = (i - 1);
}
return 0;
}
bool diff_is_one_ptr_i32_i32_ptr_i32_i32(int32_t* a, int32_t alen, int32_t* b, int32_t blen) {
int32_t borrow = 0;
int32_t i = 0;
int32_t maxlen = max2i_i32_i32(alen, blen);
while (i < maxlen) {
int32_t av = 0;
int32_t bv = 0;
if (i < alen) {
av = a[i];
}
if (i < blen) {
bv = b[i];
}
int32_t v = ((av - bv) - borrow);
if (v < 0) {
v = (v + 10);
borrow = 1;
} else {
borrow = 0;
}
if (i == 0) {
if (v != 1) {
return 0;
}
} else {
if (v != 0) {
return 0;
}
}
i = (i + 1);
}
return borrow == 0;
}
int32_t main(void) {
int32_t width = 80;
int32_t wide = 160;
int32_t* best_x = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* tmp = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* hh = (int32_t*)(calloc(((int64_t)(wide)), 4));
int32_t* kk = (int32_t*)(calloc(((int64_t)(wide)), 4));
int32_t* dkk = (int32_t*)(calloc(((int64_t)(wide)), 4));
if (((((best_x == NULL || tmp == NULL) || hh == NULL) || kk == NULL) || dkk == NULL)) {
return 1;
}
int32_t best_len = 0;
int64_t best_d = 0;
int64_t d = 2;
while (d <= 1000) {
if ((!(is_square_i64(d)))) {
int64_t r = 1;
while ((r * r) <= d) {
r = (r + 1);
}
r = (r - 1);
int32_t* h0 = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* h1 = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* h2 = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* k0 = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* k1 = (int32_t*)(calloc(((int64_t)(width)), 4));
int32_t* k2 = (int32_t*)(calloc(((int64_t)(width)), 4));
if ((((((h0 == NULL || h1 == NULL) || h2 == NULL) || k0 == NULL) || k1 == NULL) || k2 == NULL)) {
return 1;
}
int32_t hlen0 = set_small_ptr_i32_i64(h0, 0);
int32_t hlen1 = set_small_ptr_i32_i64(h1, 1);
int32_t klen0 = set_small_ptr_i32_i64(k0, 1);
int32_t klen1 = set_small_ptr_i32_i64(k1, 0);
int64_t m = 0;
int64_t dd = 1;
int64_t a = r;
int32_t step = 0;
while (step < 500) {
int32_t ml = mul_small_ptr_i32_i32_i64_ptr_i32(h1, hlen1, a, tmp);
int32_t hlen2 = add_big_ptr_i32_i32_ptr_i32_i32_ptr_i32(tmp, ml, h0, hlen0, h2);
int32_t mlk = mul_small_ptr_i32_i32_i64_ptr_i32(k1, klen1, a, tmp);
int32_t klen2 = add_big_ptr_i32_i32_ptr_i32_i32_ptr_i32(tmp, mlk, k0, klen0, k2);
int32_t hhlen = mul_big_ptr_i32_i32_ptr_i32_i32_ptr_i32_i32(h2, hlen2, h2, hlen2, hh, wide);
int32_t kklen = mul_big_ptr_i32_i32_ptr_i32_i32_ptr_i32_i32(k2, klen2, k2, klen2, kk, wide);
int32_t i = 0;
while (i < wide) {
dkk[i] = 0;
i = (i + 1);
}
int32_t dkklen = mul_small_ptr_i32_i32_i64_ptr_i32(kk, kklen, d, dkk);
if (diff_is_one_ptr_i32_i32_ptr_i32_i32(hh, hhlen, dkk, dkklen)) {
if ((best_len == 0 || cmp_big_ptr_i32_i32_ptr_i32_i32(h2, hlen2, best_x, best_len) > 0)) {
memcpy(best_x, h2, (((int64_t)(hlen2)) * 4));
best_len = hlen2;
best_d = d;
}
break;
}
memcpy(h0, h1, (((int64_t)(hlen1)) * 4));
hlen0 = hlen1;
memcpy(h1, h2, (((int64_t)(hlen2)) * 4));
hlen1 = hlen2;
memcpy(k0, k1, (((int64_t)(klen1)) * 4));
klen0 = klen1;
memcpy(k1, k2, (((int64_t)(klen2)) * 4));
klen1 = klen2;
m = ((dd * a) - m);
dd = FLOW_CHECKED_DIV(((d - (m * m))), (dd));
a = FLOW_CHECKED_DIV(((r + m)), (dd));
step = (step + 1);
}
free(h0);
free(h1);
free(h2);
free(k0);
free(k1);
free(k2);
}
d = (d + 1);
}
printf("%lld\n", best_d);
free(dkk);
free(kk);
free(hh);
free(tmp);
free(best_x);
return 0;
}