#------------------------------------------------------------------------------- # module: HybridInterp.mpl # # author: Wen-shin Lee # date: # # (c) Copyright 1999 Wen-shin Lee and Eirch Kaltofen, All Rights Reserved # This code is provided WITHOUT WARRANTY either expressed or implied. #------------------------------------------------------------------------------- protobox['HybridInterp'] := proc( # required arguments: bb_i # blackbox procedure evaluates a polynomial ,basis_i # the variable list in the blackbox polynomial ,degbound_i # the degree upper bound of the input blackbox polynomial ,modulus_i # the modulus # optional arguments: # ,'BM_thresh'= early termination threshold in Berlekamp/Massay algorithm # ,'N_thresh'= early termination threshold in Newton interpolation # ,'rndrep_thresh'= number of times a repeated random number allows being # being generated # ,'rndrange'= range of the random number generator # ,'mapmon_thresh'= the number of times before to re-generate a new random # number when different monomials map to a same value # ,'posttest_thresh'= the number of post tests # ,'Homogen'= boolean value indicate whether the homogenizing variable # interpolatin is "on" or "off" # ,'print_bbcnt' = the name assigned to the number of black box probes which # is to be returned (the default without such optional # argument will not return bbcnt) ) local rndrange_i # size of the random number generator ,print_bbcnt_i # a boolean value indicate whehter to print out the black box # probes ,print_name # store the name assigned to bbcnt if bbcnt is to be returned ,N_thresh_i # early termination threshold in Newton interpolation ,bbcnt # blackbox calls, number of blackbox calls ,dim # dimension of input basis ,homodim # dimension of input basis plus the homogenizing variable ,valuepnt # list of variable values at which the polynomial evaluates ,workinglist # list of terms whose coefficient polynomials are currently being # interpolated ,prunelist # permanent pruned list ,tmpprunelist # temporary pruned list ,pruneterm # a list keeps track of the elements that have been pruned ,rnd # random number generator ,i # loop variable ,fst # a table for interpolating the blackbox polynonomial with # respect to the "first" variable. It is homogenizing variable if # Homogen=true, and the first variable in the basis list if # Homogen=false ,degbound # the upper bound of degree ,monlist # the list represents the monomials in predix variables ,j # loop variable ,k # loop variable ,k_bound # the loop bound for k variable loop ,x_i # solution of vandermonde system ,kk # loop variable ,kk_bound # the loop bound for kk variable loop ,a_i # the right hand side of a vandermont system ,eval_v # list describe vandermont system, evaluate monomials at valuepnt ,raisedpnts # the power raised point list ,anchor # anchor point ,genpoly # a univariate polynomial that is a generating polynomial of a # sequence of values ,result_poly # the result of polynomial interpolation ,bound # an upper bound ,evalpnt # the point at which the blackbox is evaluated ,Termin # boolean value which indicate whether the current interpolatng # process is terminated ,num_monlist # number of elements in the monomial list ,mlist # monomial list ,clist # coeffcient list ,rlist # root list ,cplist # a list represent a coefficient polynomial ,dlist # degree list ,rec_result # the result of a recover procedure ,cpdeg # coefficient polynomial degree ,num_root # number of roots ,bbval # blackbox value ,num_element # number of elements ,test # a list of variable values for post test (blackbox) ,testpnt # a list of variable values for the post test (polynomial) ,degboundlist # the list of all the coefficent polynomial degree bounds ,testpolyval # the value of the polynomial in the post test ,New_race # a boolean value indicate whether to start a new Newton vs # Ben-Or/Tiwari race ,New_race_list# a boolean value list indicate whether each term is ready for a # new Newton vs Ben-Or/Tiwari race ,BM_thresh_i # the thresh used for the Berlekamp/Massey algorithm ,Same # a boolean value indicates whether two same value elements appear # in a list ,rndrep_thresh_i # the times a least a repeated random number can appear ,posttest_thresh_i # the threshold for post test ,mapmon_thresh_i # the times at least two monomials map to the same value # before we break the procedure ,Homogen_i # boolean value indicate whether the homogenizing variable # interpolation is "on" or "off" ,var1 # indicate the location of the "first variable" to start with. # 1 if Homogen=true, 2 if Homogen=false ,tmpplist # the polynomial list derives from the tmpprunelist after # interpolating all the variables in the basis list ,num_oparg # store the number of input arguments in this procedure ,Understood # boolean value indicate whether a optional argument is # understood and updated in the procedure ; # assign all the optional arguments with default values rndrange_i := modulus_i - 2; # -2 because 0 and 1 are not helpful rndrep_thresh_i := 0; # the times at least a repeated randome number can # appear is 0 posttest_thresh_i := 0; # no post test after interpolation mapmon_thresh_i := 1; # two monomials map to the same value will happen # at least once before the program abort N_thresh_i := 1; # an early termination threshold is at least 1 BM_thresh_i := 1; # an early termination threshold is at least 1 Homogen_i := true; # homogenizing interpolation is "on" by default print_bbcnt_i := false; # as default, number of black box probes is not # returned num_oparg := nargs; # the number of arguments # if there are more than 4 arguments, then there are optional arguments if num_oparg > 4 then # check and read the values of those oprional arguments (starting from 5-th # argument) for i from 5 to num_oparg do # Understood is false by default, it will only be true once an argument is # read Understood := false; if 'rndrange'=op(1,args[i]) then rndrange_i := op(2,args[i]); Understood := true; else if 'posttest_thresh'=op(1,args[i]) then posttest_thresh_i := op(2,args[i]); Understood := true; else if 'mapmon_thresh'=op(1,args[i]) then mapmon_thresh_i := op(2,args[i]); Understood := true; else if 'N_thresh'=op(1,args[i]) then N_thresh_i := op(2,args[i]); Understood := true; else if 'BM_thresh'=op(1,args[i]) then BM_thresh_i := op(2,args[i]); Understood := true; else if 'Homogen'=op(1,args[i]) and type( op(2,args[i]), boolean ) then Homogen_i := op(2,args[i]); Understood := true; else if 'rndrep_thresh'=op(1,args[i]) then rndrep_thresh_i := op(2,args[i]); Understood := true; else if 'print_bbcnt'=op(1,args[i]) then print_bbcnt_i := true; print_name := op(2,args[i]); Understood := true; fi; # end of: if print_bbcnt=op(1,args[i]) then fi; # end of: if rndrep_thresh=op(1,args[i]) fi; # end of: if Homogen=op(1,args[i]) fi; # end of: if BM_thresh=op(1,args[i]) fi; # end of: if N_thresh=op(1,args[i]) fi; # end of: if mapmon_thresh=op(1,args[i]) fi; # end of: if posttest_thresh=op(1,args[i]) fi; # end of: if rndrange=op(1,args[i]) # if certain optional argument cannot be read, then print warning and keep # those unchanged one as default if Understood=false then print(`Warning: cannot comprehend`, op(1,args[i])); fi; od; fi; # end od: if num_oparg > 4 (the end of checking and updating the optional # arguments # if according to the degree bound and thesholds, the range of the random # number generator is not enough, then print put a warning if N_thresh_i + degbound_i + 1 > min( rndrange_i, modulus_i ) or BM_thresh_i + degbound_i + 1 > min( rndrange_i, modulus_i ) then print(`Warning: range of random number generator or the modulus might not be enough`); userinfo(1 , suggestion, `increase:modulus, rndrang `); fi; # check if both N_thresh and BM_thresh are infinity to prevend an infinite loop if type( N_thresh_i, infinity ) and type( BM_thresh_i, infinity ) then ERROR(`Invalid input: both N_thresh and BM_thresh infinity will cause infinite loop`); fi; dim := nops( basis_i ); # the dimension of the input basis homodim := dim + 1; # dimension of the homoginized basis bbcnt := 0; # initialize the black box count as 0 prunelist := []; # the preminant pruned list monlist := []; # initialize the monomial list tmpprunelist := []; # initialize the temporary pruned list fst := table([ ]); # initialize the fst table rnd := rand( 2..rndrange_i + 1 ); # random number generator Termin := false; # initialize Termin as false #-- randomly pick the anchor point --------------------------------------- anchor := []; # anchor is a list of values # if Homogen_i=ture then we need to pick up a random number for the # homogenizing variable, and make var1=1 ( the location of homogenizing # variable in the value list) in order to start interpolating from the # homogenizing variable if ( Homogen_i ) then anchor := [op(anchor), rnd()]; var1 := 1; # if homogenizing interpolation is off, then make homogenizing variable become # one and var1=2 (the location of the first variable in the basis list) so that # start interpolating from the first variable in the basis list else anchor := [op(anchor), 1 ]; var1 := 2; fi; # randomly pick a number for all the variables in the basis list for i from 2 to homodim do anchor := [op(anchor), rnd()]; od; # initialize valuepnt as anchor, we will evaluate at valuepnt valuepnt := anchor; #------- initiate the first step -------------------- evalpnt := protobox['heval_pnt_mod']( valuepnt, modulus_i ); bbval := bb_i( evalpnt, modulus_i ); bbcnt := bbcnt + 1; # start the BM-table in fst from the first blackbox evaluation fst['BM'] := copy( protobox['BM_step_mod'] ( [], 1, 0, 0, 1, bbval, BM_thresh_i, BM_thresh_i, modulus_i ) ); # start the N-table in fst from the first blackbox evaluation fst['N'] := copy( protobox['NewtonInterp_step'] ( bbval, 0, 1, valuepnt[var1], N_thresh_i, N_thresh_i, modulus_i) ); # initialize new_race as false fst['new_race'] := copy( false ); #------- interpolating ------------------------------------------------- # decide the loop bound ( we cannot recover a power larger than modulus_i - 1 ) if degbound_i > modulus_i - 1 then degbound := modulus_i - 1; else degbound := degbound_i; fi; # if N_thresh is infinity, then set up a bound according to BM_thresh, else # Newton interpolation will decide the upper bound of the interpolatino loop if N_thresh_i=infinity then bound := 2*degbound + BM_thresh_i + 2 + rndrep_thresh_i; #?? else bound := degbound + N_thresh_i + rndrep_thresh_i; fi; # interpolate until the loop bound for i from 1 to bound do # check whether a new race on the power of a new point should start # if new_race is true then start to work on the powers of a new point if fst['new_race']=true then userinfo_homo_interp(`restart race`); anchor[var1] := rnd(); valuepnt[var1] := anchor[var1]; evalpnt := protobox['heval_pnt_mod']( valuepnt, modulus_i ); bbval := bb_i( evalpnt, modulus_i ); bbcnt := bbcnt + 1; # Newton interpolation update still continues from all the previous result fst['N'] := copy( protobox['NewtonInterp_step'] ( bbval, fst['N']['poly'], fst['N']['term'], valuepnt[var1], fst['N']['remt'], N_thresh_i, modulus_i ) ); # Berlekamp-Massey Algorithm restart on a new sequence of powers of this # new point fst['BM'] := copy( protobox['BM_step_mod'] ( [], 1, 0, 0, 1, bbval, BM_thresh_i, BM_thresh_i, modulus_i ) ); # set new_race false because now we will continue powering o_valuepnt[1] fst['new_race'] := copy( false ); # if not a new race is started, we keep working on the next power on # anchor[var1] else valuepnt[var1] := modp( valuepnt[var1] * anchor[var1], modulus_i ); evalpnt := protobox['heval_pnt_mod']( valuepnt, modulus_i ); bbval := bb_i( evalpnt, modulus_i ); bbcnt := bbcnt + 1; # Newton interpolation update fst['N'] := copy( protobox['NewtonInterp_step'] ( bbval, fst['N']['poly'], fst['N']['term'], valuepnt[var1], fst['N']['remt'], N_thresh_i, modulus_i ) ); # Berlekamp-Massey update fst['BM'] := copy( protobox['BM_step_mod'] ( fst['BM']['s'], fst['BM']['revpoly'], fst['BM']['B'], fst['BM']['L'], fst['BM']['D'], bbval, fst['BM']['remt'], BM_thresh_i, modulus_i ) ); fi; # the end of updating on fst['N'] and fst['BM'] # if Newton interpolation succeed then stop and return the result if fst['N']['remt']=0 then fst['N']['poly'] := copy( modp( expand( fst['N']['poly'] ), modulus_i ) ); fst['plist'] := copy( protobox['spoly_to_slist'] ( fst['N']['poly'], x, modulus_i ) ); num_element := nops( fst['plist'] ); Termin := true; userinfo_homo_interp('Newton'); userinfo_bbcnt(0,bbcnt); break; # if Newton interpolation is yet finished, then check the parelle # interpolaiton on Ben-Or and Tiwari, if we fail at any stage of # Ben-Or/Tiwari, then abort and start a new race on the powers of a new # point else # if Berlekamp-Massey succeed then continue with Ben-Or/Tiwari if fst['BM']['remt']=0 then # form the generating polynomial and find all its roots and the number # of roots genpoly := protobox['rev']( fst['BM']['revpoly'], modulus_i ); mlist := []; rlist := Roots( genpoly ) mod modulus_i; num_root := nops( rlist ); # if generating polynomial can be factorized as linear factors then # continue see wether there is any multiple root if not( num_root=degree( genpoly ) ) or ( num_root=0 ) then fst['new_race'] := true; else for j from 1 to num_root do # if there is a multiple root then abort and start a new race, else # the roots form a list of values of monomials if rlist[j][2] > 1 then fst['new_race'] := true; break; else # form the monomial list mlist := [ op(mlist), rlist[j][1] ]; fi; od; if fst['new_race']=false then # recover the monomials in the monomial list; if can't recover, abort # the Ben-Or/Tiwari procedure and restart at a new point rec_result := protobox['recover'] ( mlist, anchor[var1], degbound, modulus_i); # if can not recover then start a new race if not( rec_result[1] ) then fst['new_race'] := true; # if can recover, then dlist=rec_result[2] else dlist := rec_result[2]; # find all the coefficients and locate them to the corresponding # monomials clist := protobox['vansolve_kl_mod'] ( mlist, fst['BM']['s'], num_root, modulus_i ); fst['plist'] := copy( protobox['relocate_c'] ( clist, dlist, modulus_i ) ); # check the degree bound on the result of Ben-Or/Tiwari num_element := nops( fst['plist'] ); if num_element > bound then fst['new_race']:=true; else userinfo_homo_interp(`early termination Ben-Or/Tiwari`); userinfo_bbcnt(0,bbcnt); Termin := true; break; fi; # end of ( if num_element > bound then ) fi; # end of ( if not( rec_result[1] ) then ) fi; # end of ( if fst['new_race']=false then ) fi; # end of ( if not( num_root=degree(genpoly) ) or ( num_root=0 ) then ) fi; # end of ( if fst['BM']['remt']=0 then ) fi; # end of check fst['N']['remt']=0 and fst['BM']['remt']=0 # if reach the loop bound but non of the interpoaltion is finished, the # either an invalid degree upper bound was input or fail to interpolate the # first variable if ( i = bound ) and not( Termin ) then userinfo(1 , suggestion, `increase: modulus, degree upper, thresholds`); ERROR(`different terms map to the same value when interpolating the first variable or invalid input: wrong degree upperbound`); fi; od; # initialize the workinglist workinglist := []; # if homogenizing interpolation is on then initiate the workinglist as follows if ( Homogen_i ) then # prune the nonzero constant term to the prunelist if not( fst['plist'][1] = 0 ) then prunelist := [ [fst['plist'][1]] ]; fi; # term by term constructing workinglist for all nozero terms in the # homogenizing variable if num_element > 1 then for i from 2 to num_element do if not( fst['plist'][i]=0 ) then workinglist := [ op(workinglist), table(['degbd'=i-1, 'hvardlist'=[i-1], 'tmpc'=fst['plist'][i], 'new_race'=false, 'Restart'=false, 'plist'=[], 'BM'=table([ 'remt'=BM_thresh_i, 's'=[], 'revpoly'=0, 'B'=0, 'L'=0, 'D'=0, 'r'=0 ]), 'N'=table(['poly'=0, 'term'=1, 'remt'=N_thresh_i ]) ]) ]; fi; od; fi; # end of (if num_element > 1 then) # if homogeninzing interpolation is off, then initiate workinglist as such else for i from 1 to num_element do # creat a term in workinglist for every nonzero term in fst['plist'] if not( fst['plist'][i]=0 ) then degbound := min( degbound_i, degbound*(dim-1) ); workinglist := [ op(workinglist), table(['degbd'=degbound-(i-1), 'hvardlist'=[0,i-1], 'tmpc'=fst['plist'][i], 'new_race'=false, 'Restart'=false, 'plist'=[], 'BM'=table([ 'remt'=BM_thresh_i, 's'=[], 'revpoly'=0, 'B'=0, 'L'=0, 'D'=0, 'r'=0 ]), 'N'=table(['poly'=0, 'term'=1, 'remt'=N_thresh_i ]) ]) ]; fi; od; fi; #- interpolate the polynomial # initialize the value point as anchor point valuepnt := copy( anchor ); # no term has been pruned in the workinglist before the interpolation pruneterm := []; #------ interpolate one more variable ------------------------------------------ # now continue to interpolate the rest variables for i from var1 to dim do tmpprunelist:=[]; # stop early if all the terms have been pruned if nops( workinglist )=0 then break; fi; # find the degbound degboundlist := protobox['slice']( workinglist, 'degbd' ); degbound := protobox['find_max']( degboundlist ); # monomial list inherite from the all the monomials in prefix variables monlist := protobox['slice']( workinglist, 'hvardlist' ); # -- initiate the interpolation for the i-th variable ------------- # if different monomials map to the same value, we will try mapmon_thresh # many times for k from 1 to mapmon_thresh_i do # randomly pick p_i anchor[i] := rnd(); # evaluate monomials at anchor eval_v := protobox['eval_mon_mod']( anchor, monlist, modulus_i ); # check whether the vandermonde matrix is singular Same := protobox['check_same']( eval_v ); if not( Same ) then # if no two monomials map to a same value then proceed with iterpolating # its coefficient polynomial valuepnt := copy( anchor ); break; fi; od; if Same then userinfo(1 , suggestion, `increase: modulus, BM_thresh, N_thresh, mapmon_thresh, rndrange`); ERROR(`In Zippel algorithm: different terms map to the same value`, mapmon_thresh_i, `times`); fi; # construct the a_i num_monlist := nops( monlist ); a_i := []; k_bound := num_monlist - 1; for k from 0 to k_bound do raisedpnts := protobox['raising_pnts_mod']( k, i, valuepnt, modulus_i ); evalpnt := protobox['heval_pnt_mod']( raisedpnts, modulus_i ); a_i := [ op(a_i), bb_i( evalpnt, modulus_i ) - protobox['heval_plist_mod'](raisedpnts, prunelist, modulus_i) ]; bbcnt := bbcnt + 1; od; # solve for x_i x_i := protobox['vansolve_kl_mod']( eval_v, a_i, num_monlist, modulus_i); # initiate the interpolation for the coefficient of each term in wrokinglist for k from 1 to num_monlist do workinglist[k]['N'] := copy( protobox['NewtonInterp_step'] ( x_i[k], 0, 1, valuepnt[i+1], N_thresh_i, N_thresh_i, modulus_i )); workinglist[k]['BM'] := copy( protobox['BM_step_mod'] ( [], 1, 0, 0, 1, x_i[k], BM_thresh_i, BM_thresh_i, modulus_i) ); od; # initiate New_race as false New_race := false; # determine k_bound if N_thresh_i=infinity then k_bound := 2*degbound + BM_thresh_i + 2 + rndrep_thresh_i; else k_bound := degbound + N_thresh_i + 1 + rndrep_thresh_i; fi; # interpolate all coefficient polynomials update k_bound many times for k from 2 to k_bound do # decide whether restart the race New_race_list := protobox['slice'](workinglist, 'new_race'); New_race := protobox['find_true']( New_race_list ); # monomial list inherite from the all the monomials remaining in the # workinglist monlist := protobox['slice'](workinglist, 'hvardlist'): # if continue poweing a random value, not start at a new value if New_race=false then valuepnt[i+1] := modp( valuepnt[i+1] * anchor[i+1], modulus_i ); eval_v := protobox['eval_mon_mod']( valuepnt, monlist, modulus_i ); Same := protobox['check_same']( eval_v ); if Same then userinfo(1 , suggestion, `increase: modulus, BM_thresh, N_thresh`); ERROR(`In Zippel algorithm: differrnt terms map to the same value`); fi; # if need to find a new random number, then try to test whether it will # make two monomials map to a same value. retry when it is still under # the mapmon_thresh else for kk from 1 to mapmon_thresh_i do # randomly pick a new valuepnt[i+1] anchor[i+1] := rnd(); eval_v := protobox['eval_mon_mod'](anchor, monlist, modulus_i); # check whether the vandermonde matrix is singular Same := protobox['check_same']( eval_v ); # if pass the "same-mapping" test, then proceed if not( Same ) then valuepnt[i+1] := copy( anchor[i+1] ); break; fi; od; if Same then userinfo(1 , suggestion, `increase: modulus, BM_thresh, N_thresh, mapmon_thresh`); ERROR(`In Zippel algorithm: differrnt terms map to the same value`,mapmon_thresh_i, 'times' ); fi; fi; num_monlist := nops( monlist ); # construct the a_i a_i := []; kk_bound := num_monlist - 1; for kk from 0 to kk_bound do raisedpnts := protobox['raising_pnts_mod']( kk, i, valuepnt, modulus_i ); evalpnt := protobox['heval_pnt_mod']( raisedpnts, modulus_i ); a_i := [ op(a_i), bb_i( evalpnt, modulus_i ) - protobox['heval_plist_mod'] ( raisedpnts, prunelist, modulus_i ) - protobox['eval_tmpprunelist_mod'] (raisedpnts, tmpprunelist, modulus_i)]; bbcnt := bbcnt + 1; od; # solve for x_i x_i := protobox['vansolve_kl_mod']( eval_v, a_i, num_monlist, modulus_i ); #-- interpolating each coefficient polynomial one more in degree for kk from 1 to num_monlist do Termin := false; # update Newton interpolation workinglist[kk]['N'] := copy( protobox['NewtonInterp_step'] ( x_i[kk], workinglist[kk]['N']['poly'], workinglist[kk]['N']['term'], valuepnt[i+1], workinglist[kk]['N']['remt'], N_thresh_i, modulus_i) ); # if New_race=false, the keep updating the BM table if New_race=false then workinglist[kk]['BM'] := copy( protobox['BM_step_mod'] ( workinglist[kk]['BM']['s'], workinglist[kk]['BM']['revpoly'], workinglist[kk]['BM']['B'], workinglist[kk]['BM']['L'], workinglist[kk]['BM']['D'], x_i[kk], workinglist[kk]['BM']['remt'], BM_thresh_i, modulus_i ) ); # if a new race just started, then initiate a new BM table else workinglist[kk]['BM'] := copy( protobox['BM_step_mod'] ( [], 1, 0, 0, 1, x_i[kk], BM_thresh_i,BM_thresh_i,modulus_i) ); workinglist[kk]['new_race'] := copy( false ); fi; # end of (if New_race=true then) # check if Newton interpolation is early terminated if workinglist[kk]['N']['remt']=0 then Termin := true; userinfo_interp(i,k,'Newton'); userinfo_bbcnt(i,bbcnt); cplist := protobox['spoly_to_slist'] ( workinglist[kk]['N']['poly'], x, modulus_i ); else # else see if Berlekemp/Massey algorithm is early terminated if workinglist[kk]['new_race']=false and workinglist[kk]['BM']['remt']=0 then userinfo_bbcnt(i,bbcnt); genpoly := protobox['rev'] ( workinglist[kk]['BM']['revpoly'], modulus_i ); mlist := []; rlist := Roots( genpoly ) mod modulus_i; num_root := nops( rlist ); # number of roots # if genpoly can not be factorized then restart the race if not( num_root=degree( genpoly ) ) or ( num_root=0 ) then workinglist[kk]['new_race'] := copy( true ); else for j from 1 to num_root do # see if there are multiple roots in genpoly if rlist[j][2] > 1 then workinglist[kk]['new_race'] := copy( true ); break; else mlist := [ op(mlist), rlist[j][1] ]; fi; # end of (if rlist[j][2] > 1 then) od; # end of (j from 1 to num_root do) fi; if workinglist[kk]['new_race']=false then rec_result:=protobox['recover'] ( mlist, anchor[i+1], degbound, modulus_i ); # if we can recover all the monomials if rec_result[1] then dlist := rec_result[2]; clist := protobox['vansolve_kl_mod'] ( mlist, workinglist[kk]['BM']['s'], num_root, modulus_i ); cplist:=protobox['relocate_shift_c'] ( clist, dlist, mlist, modulus_i) mod modulus_i; userinfo_interp(i,k,`early termination Ben-Or/Tiwari`); Termin := true; else workinglist[kk]['new_race'] := copy( true ); fi; # end of ( if rec_result[1] then ) fi; # end of ( if workinglist[kk]['new_race']=false then ) fi; # end of ( if workinglist[kk]['new_race']=false and # workinglist[kk]['BM']['remt']=0 then ) fi; # end of ( if workinglist[kk]['N']['remt']=0 then ) # if early termination occurs if Termin=true then cpdeg := nops( cplist ) - 1; workinglist[kk]['plist'] := copy( cplist ); # if workinglist[kk]['degbd'] > cpdeg then temporarily prune if workinglist[kk]['degbd'] > cpdeg then tmpprunelist := copy( protobox['tmpprune'] ( kk, workinglist, tmpprunelist, BM_thresh_i, N_thresh_i, modulus_i) ); pruneterm := [op(pruneterm), kk]; fi; # if workinglist[kk]['degbd'] = cpdeg then permanently prune if workinglist[kk]['degbd']=cpdeg then prunelist := protobox['prune'](kk, workinglist, prunelist); workinglist[kk]['plist'] := copy( protobox['rm_element']( [nops(cplist)], cplist) ); tmpprunelist := protobox['tmpprune'] ( kk, workinglist, tmpprunelist, BM_thresh_i, N_thresh_i, modulus_i); pruneterm := [op(pruneterm), kk]; fi; fi; # end of ( if Termin=true then ) od; # end of kk loop workinglist := protobox['rm_element']( pruneterm, workinglist); x_i := protobox['rm_element']( pruneterm, x_i); #reset pruneterm after those terms have been pruned pruneterm := []; if k = k_bound and workinglist <> [] then userinfo(1 , suggestion, `increase: modulus, BM_thresh, N_thresh`); ERROR(`Interpolation Failure: dropped a non-zero term`); fi; if workinglist=[] then break; fi; od; # end of k loop # reset the workinglist for next variable workinglist:= copy( tmpprunelist ); od; # end of i loop result_poly := protobox['list_to_poly'](prunelist, basis_i, modulus_i); if not( Homogen_i ) then tmpplist := protobox['tmpprunelist_to_plist']( tmpprunelist ); result_poly := result_poly + protobox['list_to_poly']( tmpplist, basis_i, modulus_i); fi; for j from 1 to posttest_thresh_i do test:= []; testpnt:=[]; for i from 1 to dim do test := [op(test), rnd()]; testpnt := [ op(testpnt), basis_i[i]=test[i] ]; od; userinfo(100, userinfo_test, "Final test: rand points", testpnt); bbval:= bb_i( test, modulus_i ); bbcnt := bbcnt + 1; testpolyval := modp( eval(result_poly, testpnt), modulus_i); if not(bbval=testpolyval mod modulus_i) then ERROR(`Fail to pass the post test`); break; fi; od; if print_bbcnt_i then assign(`print_name`, bbcnt); fi; RETURN(result_poly); end: userinfo_homo_interp := proc ( alg ) userinfo( 2, userinfo_homo_interp, `homogenizing variable:`, alg); end: userinfo_interp := proc ( i ,j ,alg ) userinfo( 2, userinfo_interp, i,`-th variable`, j,`-th interpolation`, alg); end: userinfo_bbcnt := proc ( i ,bbcnt ) userinfo( 2, `after interpolating`, i,`-th variable, number of black box probes:`, bbcnt); end: