"""Exact dihedral integration of real-coefficient polynomials in z and zbar.""" from functools import cache from fractions import Fraction as F from math import comb, factorial, isqrt from collections import defaultdict @cache def moment(a,b): if (a-b)%5: return (F(0),F(0)) # cos(2*pi*j/5)=(A+B*sqrt(5))/4 cos=((4,0),(-1,1),(-1,-1),(-1,-1),(-1,1)) v,w=0,0 for j in range(a+1): for k in range(b+1): h=(comb(a,j)*comb(b,k)*factorial(a+b-j-k)*factorial(j+k)) c,d=cos[(j-k)%5] v+=h*c w+=h*d q=2*factorial(a+b+2) return (F(v,q),F(w,q)) def add(*ps): o=defaultdict(int) for p in ps: for ab,c in p.items(): o[ab]+=c return {ij:c for ij,c in o.items() if c} def scale(c,p): return {ab:c*v for ab,v in p.items()} def mul(*ps): o={(0,0):1} for p in ps: t=defaultdict(int) for (i,j),v in o.items(): for (k,l),w in p.items(): t[i+k,j+l]+=v*w o=t return {ij:c for ij,c in o.items() if c} def derivative(p,sign): o=defaultdict(int) for (a,b),c in p.items(): if a: o[a-1,b]+=a*c if b: o[a,b-1]+=sign*b*c return dict(o) def energy(v,w): return add(mul(derivative(v,1),derivative(w,1)), scale(-1,mul(derivative(v,-1),derivative(w,-1)))) def sqrt_bounds(x,precision=60): assert x>=0 scale_=10**precision n=isqrt(x.numerator*scale_**2//x.denominator) return F(n,scale_), F(n+1,scale_) SQRT5=sqrt_bounds(F(5)) def avg(p): s,t=0,0 for ab,c in p.items(): a,b=moment(*ab) s+=c*a t+=c*b a,b=(t*e for e in SQRT5) return min(s+a,s+b),max(s+a,s+b) def mode(m,k): return {(m+k,k):F(1,2),(k,m+k):F(1,2)}