"""Original exact finite bracket trace and a Newton two-cycle."""
from fractions import Fraction as F
import json
def value(f,x):
 y=f(x)
 if type(y) not in [int,F] or abs(y)>10**12:raise ValueError('finite bounded exact function output')
 return F(y)
def bisect(f,left,right,tol=F(1,512),cap=8):
 if type(left) not in [int,F] or type(right) not in [int,F] or abs(left)>100 or abs(right)>100 or left>=right or type(tol) not in [int,F] or tol<=0 or type(cap) is not int or not 1<=cap<=32:raise ValueError('bounded ordered exact bracket, positive tolerance/cap')
 a=F(left);b=F(right);fa=value(f,a);fb=value(f,b);trace=[]
 if fa==0:return a,a,trace,'endpoint_root'
 if fb==0:return b,b,trace,'endpoint_root'
 if fa*fb>=0:raise ValueError('opposite endpoint signs required')
 for k in range(cap):
  mid=(a+b)/2;fm=value(f,mid);before=[str(a),str(b)]
  if fm==0:return mid,mid,trace+[{'step':k+1,'before':before,'mid':str(mid),'f_mid':str(fm),'exact_root':True}],'exact_root'
  if fa*fm<0:b=mid;fb=fm
  else:a=mid;fa=fm
  assert fa*fb<0
  trace.append({'step':k+1,'before':before,'mid':str(mid),'f_mid':str(fm),'after':[str(a),str(b)],'width':str(b-a),'endpoint_sign_product':str(fa*fb)})
  if b-a<=tol:return a,b,trace,'width_tolerance'
 return a,b,trace,'budget_exhausted'
def cubic(x):return x**3-2*x+2
def newton_steps(f,derivative,start,cap):
 x=F(start);points=[str(x)]
 for i in range(cap):
  fx=value(f,x);df=value(derivative,x)
  if df==0:return points,'zero_derivative'
  x-=fx/df
  if abs(x)>100:raise ValueError('bounded iterate')
  points.append(str(x))
 return points,'budget_exhausted'
def demo():
 a,b,tr,status=bisect(cubic,-2,-1);assert (a,b)==(F(-453,256),F(-113,64)) and b-a==F(1,256)
 newton,ns=newton_steps(cubic,lambda x:3*x*x-2,0,6)
 assert newton==['0','1','0','1','0','1','0']
 e=bisect(lambda x:x-1,1,2);assert e[3]=='endpoint_root' and e[0]==1
 c=bisect(lambda x:x*x-2,1,2,F(1,1024),16);assert c[3]=='width_tolerance' and c[1]-c[0]<=F(1,1024)
 da,db,dt,ds=bisect(lambda x:1/x,-1,2);assert da<0<db and all(1/F(r['mid'])!=0 for r in dt)
 rejected=[]
 zero_derivative=newton_steps(lambda x:x*x-2,lambda x:2*x,0,3);assert zero_derivative[1]=='zero_derivative'
 for label,fn in [('no_bracket',lambda:bisect(lambda x:x*x+1,-1,1)),('reversed',lambda:bisect(cubic,1,-1)),('zero_tol',lambda:bisect(cubic,-2,-1,0)),('invalid_cap',lambda:bisect(cubic,-2,-1,cap=True)),('nonfinite_function',lambda:bisect(lambda x:float('inf'),-1,1))]:
  try:fn()
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'function':'x^3-2x+2','bisection_eight_steps':tr,'final_bracket':[str(a),str(b)],'width':str(b-a),'status':status,'Newton_from_zero_exact_cycle':newton,'Newton_status':ns,'separate_Newton_zero_derivative':{'points':zero_derivative[0],'status':zero_derivative[1]},'endpoint_root':{'value':str(e[0]),'status':e[3]},'separate_width_stop':{'bracket':[str(c[0]),str(c[1])],'status':c[3]},'discontinuous_one_over_x_counterexample':{'bracket':[str(da),str(db)],'last_midpoint_residual':str(1/F(dt[-1]['mid'])),'status':ds,'continuous_precondition_false':True,'root_claimed':False},'rejected':rejected,'scope':'no SciPy run, no universal Newton convergence, bracket sign alone requires continuity for root existence'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))