module main

import benchmark
import math
import math.big
import os
import strconv

// Regression benchmark for issue #21319.
// It mirrors the external edigits workload without printing every line,
// so the timing stays focused on `math.big`.
const default_n = 250_001
const one = big.one_int
const ten = big.c10

fn main() {
	mut n := default_n
	if os.args.len > 1 {
		n = strconv.atoi(os.args[1]) or { default_n }
	}
	mut clock := benchmark.start()
	k := binary_search(n)
	clock.measure('k=${k}')
	mut p, q := sum_terms(0, k - 1)
	clock.measure('sum_terms p.bit_len=${p.bit_len()} q.bit_len=${q.bit_len()}')
	p += q
	a := ten.pow(u32(n - 1))
	clock.measure('pow 10^${n - 1}')
	answer := p * a / q
	clock.measure('division answer.bit_len=${answer.bit_len()}')
	s := answer.str()
	clock.measure('str digits=${s.len}')
	if s.len != n {
		eprintln('unexpected digit count: got ${s.len}, want ${n}')
		return
	}
	println(last_line(s, n))
}

fn sum_terms(a int, b int) (big.Integer, big.Integer) {
	if b == a + 1 {
		return one, big.integer_from_int(b)
	}
	mid := (a + b) / 2
	p_left, q_left := sum_terms(a, mid)
	p_right, q_right := sum_terms(mid, b)
	return p_left * q_right + p_right, q_left * q_right
}

fn binary_search(n int) int {
	mut a := 0
	mut b := 1
	for !test_k(n, b) {
		a = b
		b *= 2
	}
	for b - a > 1 {
		m := (a + b) / 2
		if test_k(n, m) {
			b = m
		} else {
			a = m
		}
	}
	return b
}

fn test_k(n int, k int) bool {
	if k < 0 {
		return false
	}
	ln_k_factorial := k * (math.log(k) - 1) + 0.5 * math.log(math.tau)
	log_10_k_factorial := ln_k_factorial / math.ln10
	return log_10_k_factorial >= n + 50
}

fn last_line(s string, n int) string {
	chunk_len := if n % 10 == 0 { 10 } else { n % 10 }
	start := n - chunk_len
	mut line := s[start..n]
	for line.len < 10 {
		line += ' '
	}
	return '${line}\t:${n}'
}