"""Exact rational enclosures for the heterogeneous half-step separation. Fraction endpoints, integer-root comparisons and outward interval elimination enclose the exact Hermite coefficients; coefficient error enters count margins. No floating-point sign decisions are used. """ from fractions import Fraction as F from rational_cox import add,sub,mul,scale,outward,enclose ZERO=(F(0),F(0));ONE=(F(1),F(1)) def point(x):return (F(x),F(x)) def root(x,n,digits=70): """Positive nth root enclosed by exact comparisons on a rational grid.""" if x<0:raise ValueError('nonnegative input required') den=10**digits;lo=0;hi=max(1,(x.numerator+x.denominator-1)//x.denominator)*den while hi-lo>1: mid=(lo+hi)//2 if mid**n*x.denominator<=x.numerator*den**n:lo=mid else:hi=mid return F(lo,den),F(hi,den) def powrat(x,p,q): return root(x[0]**p,q)[0],root(x[1]**p,q)[1] def div(a,b): if b[0]<=0<=b[1]:raise ValueError('interval denominator contains zero') return mul(a,(1/b[1],1/b[0])) def isum(items): out=ZERO for item in items:out=add(out,item) return out def solve(A,y): B=[row[:]+[rhs] for row,rhs in zip(A,y)] for i in range(4): candidates=[k for k in range(i,4) if not B[k][i][0]<=0<=B[k][i][1]] k=max(candidates,key=lambda k:abs(sum(B[k][i]))) B[k],B[i]=B[i],B[k] denom=B[i][i] B[i]=[div(x,denom) for x in B[i]] for k in range(4): if k==i:continue z=B[k][i] B[k]=[sub(x,mul(z,y)) for x,y in zip(B[k],B[i])] return [row[-1] for row in B] def row(t,deriv=False): return [ZERO,ONE,scale(t,2),scale(mul(t,t),3)] if deriv else [ONE,t,mul(t,t),mul(mul(t,t),t)] def coeffs(a,b): # p interpolates t^(17/10) at a,b, each twice. p=solve([row(a),row(a,True),row(b),row(b,True)], [powrat(a,17,10),scale(powrat(a,7,10),F(17,10)), powrat(b,17,10),scale(powrat(b,7,10),F(17,10))]) z=point(F(1,2)) q=solve([row(ZERO),row(z),row(z,True),row(ONE)], [ZERO,powrat(z,13,10),scale(powrat(z,3,10),F(13,10)),ONE]) return p,q def radius_upper(y,n): # t=6.58 > log(36/.05)=log(720); exact Taylor partial verifies this. t=F(329,50);term=F(1);partial=F(1) for k in range(1,40):term=term*t/k;partial+=term assert partial>720 z=t/n return min(F(1),5*z/3+root(2*y*z+7*z*z/3,2)[1]) def finite_lower(group,c,orientation): cells=group['outcomes'];n=sum(cells.values()) vb=F(sum(v for k,v in cells.items() if k[0]=='0'),n) baseline=sub(isum(c),ONE) coefficients={'2':ONE,'-':scale(c[0],-1),'+':scale(c[2],-1),'3':scale(c[3],-1)} estimate=scale(baseline,vb) rad=max(abs(x) for x in baseline)*radius_upper(vb,n) for (label,i) in [('2',1),('3',2),('-',3),('+',4)]: pp=F(sum(v for k,v in cells.items() if int(k[i])-int(k[0])==1),n) pm=F(sum(v for k,v in cells.items() if int(k[i])-int(k[0])==-1),n) cc=coefficients[label] estimate=add(estimate,scale(cc,pp-pm)) rad+=max(abs(x) for x in cc)*(radius_upper(pp,n)+radius_upper(pm,n)) estimate=scale(estimate,orientation) return outward((estimate[0]-rad,estimate[1]-rad)) def certificate(fixture): assert fixture['contract']=={'step':'.5','ratio_error':'.1'} and fixture['alpha']=='.05' v=[point(F(1,10)),point(F(1,2)),point(F(9,10))] w1=scale(isum(powrat(t,7,4) for t in v),F(1,3)) w2=scale(isum(powrat(t,5,4) for t in v),F(1,3)) rt=root(F(8,75),2);a=sub(point(F(1,2)),rt);b=add(point(F(1,2)),rt) G=scale(add(powrat(a,17,10),powrat(b,17,10)),F(1,2)) J=add(scale(powrat(point(F(1,2)),13,10),F(43,75)),point(F(16,75))) H1=scale(sub(G,w1),F(4,5));H2=scale(sub(w2,J),F(4,5)) p,q=coeffs(a,b) printed=[['-.006914452375','.162611267906','1.013345008781','-.170765293415'], ['0','.512648562186','.711063898866','-.223712461052']] cells=[[(F(x)-F(1,2*10**12),F(x)+F(1,2*10**12)) for x in row] for row in printed] cells[1][0]=ZERO assert all(cell[0]<=co[0]<=co[1]<=cell[1] for row,cs in zip([p,q],cells) for co,cell in zip(row,cs)) finite=[finite_lower(g,c,o) for g,c,o in zip(fixture['groups'],cells,[1,-1])] assertions=dict(population_H1_above_0_00393195=H1[0]>F(393195,10**8), population_H2_above_0_00393297=H2[0]>F(393297,10**8), old_variance_allowance_inconclusive=w2[1]F(39293,10**7), finite_H2_above_0_0039310=finite[1][0]>F(39310,10**7)) assert all(assertions.values()),assertions return dict(method='exact rational roots, interval elimination and outward propagation; t=6.58', assertions=assertions,H1=enclose(H1),H2=enclose(H2), finite_lower_endpoints=[enclose(x) for x in finite], coefficient_enclosures=[[enclose(x) for x in co] for co in [p,q]], printed_coefficient_enclosures=[[enclose(x) for x in co] for co in cells])