"""Exact interpolation of the four shape variables in the single-ear chart.""" from fractions import Fraction as Q from itertools import product from math import comb,factorial,lcm import numpy as np from affine_cut_data import EXPONENTS,DEGREE,TARGET def inverse_evaluation(n): a=[[Q(comb(n,k)*r**k*(n-r)**(n-k),n**n) for k in range(n+1)] +[Q(int(j==r)) for j in range(n+1)] for r in range(n+1)] for k in range(n+1): pivot=next(i for i in range(k,n+1) if a[i][k]) a[k],a[pivot]=a[pivot],a[k];p=a[k][k];a[k]=[v/p for v in a[k]] for i in range(n+1): if i==k:continue c=a[i][k];a[i]=[v-c*w for v,w in zip(a[i],a[k])] inv=[row[n+1:] for row in a];den=lcm(*(v.denominator for row in inv for v in row)) return den,np.array([[int(v*den) for v in row] for row in inv],dtype=object) def interpolate(array,op): result=array for i in range(4): front=np.moveaxis(result,i,0); shape=front.shape result=np.moveaxis((op@front.reshape(9,-1)).reshape(shape),0,i) return result def table_moments(verts,F,D,terms): xp=[[1] for p in verts];yp=[[1] for p in verts] for a,(x,y) in enumerate(verts): for k in range(6): xp[a].append(xp[a][-1]*x);yp[a].append(yp[a][-1]*y) det=[x*v-y*u for (x,y),(u,v) in zip(verts,verts[1:])] out={} for i,j,c,coef in terms: val=0 for e,d in enumerate(det): if d: inner=sum(f*xp[e][i-k]*yp[e][j-l]*xp[e+1][k]*yp[e+1][l] for k,l,f in coef) val+=d*inner out[i,j]=val*c return out def exact_data(): n=DEGREE;F=n**3; D=factorial(8)*F**8 nodes=np.empty((9,9,9,9,4,45),dtype=object) linear=np.empty((9,9,9,9,2),dtype=object) terms=[] for d in range(7): for i in range(d+1): j=d-i coeffs=[(k,l,comb(i,k)*comb(j,l)*factorial(d-k-l)*factorial(k+l)) for k in range(i+1) for l in range(j+1)] terms.append((i,j,D//(factorial(d+2)*F**(d+2)),coeffs)) desc=[] for p,(i,j) in enumerate(EXPONENTS): for k,l in EXPONENTS[:p+1]: desc.append((i,j,k,l,i*k,j*l,i*l+j*k)) for key in product(range(n+1),repeat=4): u,r,a,g=key # Coordinates in the square after the unimodular shear (x,y)->(x,x+y). ux=u*n*n;uy=ux-u*a*n vx=(u*n+(n-u)*r)*n;vy=vx-a*(u*(n-r)+g*r) I=table_moments([(ux,uy),(vx,vy),(F,F),(0,F)],F,D,terms) area=I[0,0];a2=area*area for ix,(i,j,k,l,dx,dy,dxy) in enumerate(desc): nodes[key+(0,ix)]=103*D*(area*I[i+k,j+l]-I[i,j]*I[k,l]) nodes[key+(1,ix)]=10*a2*dx*I[i+k-2,j+l] if dx else 0 nodes[key+(2,ix)]=10*a2*dy*I[i+k,j+l-2] if dy else 0 nodes[key+(3,ix)]=10*a2*dxy*I[i+k-1,j+l-1] if dxy else 0 sx=24*D*(area*I[2,0]-I[1,0]**2)-area**3 sy=24*D*(area*I[0,2]-I[0,1]**2)-area**3 cross=24*D*(area*I[1,1]-I[1,0]*I[0,1]) linear[key+(0,)]=sx;linear[key+(1,)]=sx*sy-cross*cross den,op=inverse_evaluation(n) lin=interpolate(linear,op) mins=[Q(int(lin[...,0].min()),24*D**3*den**4),Q(int(lin[...,1].min()),24**2*D**6*den**4)] assert min(mins)>0,mins root=interpolate(nodes,op) return 10*D**3*den**4,root,mins if __name__=='__main__': from time import monotonic t=monotonic();d,v,mins=exact_data();print(d.bit_length(),mins,round(monotonic()-t,2),flush=True)