"""Interval bounds on the first variations in the third and fourth vertex Fourier directions.""" from fractions import Fraction as F from functools import cache from itertools import product from kernel_poly import add, avg, mode, mul, scale, sqrt_bounds class I: """Outward dyadic interval arithmetic for the quadrature and sector matrices.""" scale = 1 << 100 def __init__(self, x=0, hi=None): if isinstance(x, I) and hi is None: self.l, self.h = x.l, x.h return a,b=F(x),F(x if hi is None else hi) self.l=(a.numerator*self.scale)//a.denominator self.h=-((-b.numerator*self.scale)//b.denominator) @classmethod def raw(cls,l,h): v=object.__new__(cls); v.l=l; v.h=h return v def __add__(self,other): y=other if isinstance(other,I) else I(other) return I.raw(self.l+y.l,self.h+y.h) __radd__=__add__ def __neg__(self): return I.raw(-self.h,-self.l) def __sub__(self,other): return self+-I(other) def __rsub__(self,other): return I(other)+-self def __mul__(self,other): y=other if isinstance(other,I) else I(other) vals=(self.l*y.l,self.l*y.h,self.h*y.l,self.h*y.h) return I.raw(min(vals)//self.scale,-((-max(vals))//self.scale)) __rmul__=__mul__ def __truediv__(self,other): d=I(other) assert d.l>0 or d.h<0 vals=[F(x*self.scale,y) for x,y in product((self.l,self.h),(d.l,d.h))] a,b=min(vals),max(vals) return I.raw(a.numerator//a.denominator,-((-b.numerator)//b.denominator)) def lo(self):return F(self.l,self.scale) def hi(self):return F(self.h,self.scale) def mag(self):return max(abs(self.lo()),abs(self.hi())) def ctimes(u,v): a,b=u;c,d=v return a*c-b*d,a*d+b*c @cache def vertices(): root=I(*sqrt_bounds(F(5))) c=(root-1)/4 ss=(5+root)/8 s=I(sqrt_bounds(ss.lo())[0],sqrt_bounds(ss.hi())[1]) a=[(I(1),I(0))] for _ in range(4):a.append(ctimes(a[-1],(c,s))) return a def quadrature(d): nodes=[F(i,d) for i in range(d+1)] weights=[] for i in range(d+1): coeff=[F(1)] for j in range(d+1): if i==j:continue div=nodes[i]-nodes[j] res=[F(0)]*(len(coeff)+1) for k,v in enumerate(coeff): res[k]-=v*nodes[j]/div res[k+1]+=v/div coeff=res weights.append(sum(v/F(k+1) for k,v in enumerate(coeff))) for k in range(d+1): assert sum(w*x**k for x,w in zip(nodes,weights))==F(1,k+1) return [(I(x),I((1-x)*y),I(2*(1-x)*a*b)) for x,a in zip(nodes,weights) for y,b in zip(nodes,weights) if x!=1] def samples(): mod=[(1,0,1000),(1,1,-537),(1,2,83),(4,0,89),(4,1,-10),(6,0,-17)] poly=add(*(scale(w,mode(m,k)) for m,k,w in mod)) mlo,mhi=avg(mul(poly,poly)) norm=I(sqrt_bounds(mlo)[0],sqrt_bounds(mhi)[1]) invnorm=I(1)/norm qrule=quadrature(13) av=vertices() out=[] for j in range(5): v,w=av[j],av[(j+1)%5] cell=[[I(0) for _ in range(11)] for _ in range(2)] for a,b,wt in qrule: x=a*v[0]+b*w[0]; y=a*v[1]+b*w[1]; rr=x*x+y*y powers=[(I(1),I(0))] for _ in range(6): powers.append(ctimes(powers[-1],(x,y))) radii=[I(1),rr,rr*rr] def value(m,k,odd): z=powers[m];t=powers[m-1] val=z[odd]*radii[k] dx=m*t[odd]*radii[k] dy=m*(t[0] if odd else -t[1])*radii[k] if k: d=2*k*z[odd]*radii[k-1] dx=dx+d*x;dy=dy+d*y return val,dx,dy for odd in (0,1): test=[I(0)]*3;cor=[I(0)]*3 for m,k,coef in mod: f=value(m,k,odd) for i in range(3): test[i]=test[i]+coef*(-1 if odd and m%5==4 else 1)*f[i] for m,k,coef in [(2,0,7),(3,0,1),(2,1,-5)]: f=value(m,k,odd) for i in range(3): cor[i]=cor[i]+coef*(-1 if odd and m==2 else 1)*f[i] f,gx,gy=(v*invnorm for v in test) t,hx,hy=cor vals=(f*f,f*t,t*t,gx*gx,gx*gy,gy*gy,hx*gx,hx*gy,hy*gx,hy*gy,hx*hx+hy*hy) for i,z in enumerate(vals):cell[odd][i]=cell[odd][i]+wt*z out.append(cell) return out def mat(j,m): v=vertices(); a,b=v[j],v[(j+1)%5]; c,d=v[(m*j)%5],v[(m*(j+1))%5] det=a[0]*b[1]-a[1]*b[0] return [[(c[i]*b[1]-d[i]*a[1])/det,(d[i]*a[0]-c[i]*b[0])/det] for i in range(2)] def fields(alpha,only4=False): out=[] for j in range(5): p,q=mat(j,3),mat(j,4) if only4: G=q else:G=[[p[i][k]+alpha*q[i][k] for k in range(2)] for i in range(2)] a,b=G[0];c,d=G[1] tr=a+d;det=a*d-b*c K1=(d-a,-b-c,a-d);K2=(a*a+b*b-det,a*c+b*d,c*c+d*d-det) out.append((tr,det,K1,K2)) return out def bvalue(cs,field,lam): z=I(0) for cell,(d,_,k,_) in zip(cs,field): a=cell[0] z=z+k[0]*a[3]+2*k[1]*a[4]+k[2]*a[5]-lam*d*a[0] return z/5 def op(k):return max(k[0].mag()+k[1].mag(),k[1].mag()+k[2].mag()) def check(): cs=samples() L,r=F('4.352639'),F('4.354790') d0,d1=F('0.017906'),F('0.059544') sqrt_r=sqrt_bounds(r)[1] lam=I(L,r) # The preceding certificate gives LF(1,100): assert -F('2.075')