An Improved Algorithm for Recovering Exact Value from its Approximation ∗ Jingzhong Zhang Yong Feng LaboratoryforAutomatedReasoningand LaboratoryforAutomatedReasoningand Programming Programming 7 ChengduInstituteofComputerApplications ChengduInstituteofComputerApplications 0 ChineseAcademyofSciences ChineseAcademyofSciences 0 610041Chengdu,P.R.China 610041Chengdu,P.R.China 2 [email protected] [email protected] n a J ABSTRACT factor obtained is an approximate one. After then, numer- 4 Numerical approximate computation can solve large and ical methods have been studied to get approximate factors 2 complex problems fast. It has the advantage of high effi- of a polynomial[4][11][15][16] [17][18]. In themeantime, nu- ciency. However it only gives approximate results, whereas merical methods are applied to get approximate greatest ] we need exact results in many fields. There is a gap be- commondivisorsofapproximatepolynomials[1][2][12][5],to G tweenapproximatecomputationandexactresults. Abridge compute functional decompositions[6], to test primality[10] A overriding the gap was built by Zhang, in which an ex- and to find zeroes of a polynomial[13]. In 2000, Corless act rational number is recovered from its approximation et al. applied numerical method in implicitization of para- . h by continued fraction method when the error is less than metric curves, surfaces and hypersurfaces[3]. The resulting t 1/((2N +2)(N −1)N), where N is a bound on absolute implicit equation is still an approximate one. a value of denominator of the rational number. In this pa- m per, an improved algorithm is presented by which a exact There is a gap between approximate computations and ex- [ rational number is recovered when the error is less than act results[19]. People usually use rational number compu- 1/(4(N −1)N). tationstooverridethegap[7]. Infact,thesearenotapproxi- 1 matecomputationsbutbignumbercomputations,whichare v also exact computations. In 2005, Zhang et al proposed an 2 Keywords 7 algorithm to get exact factors of a multivariate polynomial Numericalapproximatecomputation,Symbolic-numericalcom- 6 by approximate computation[20] but they did not discuss putation, Continued fraction. 1 howtooverridethegap. In[9],ChezeandGalligodiscussed 0 how to obtain an exact absolute polynomial factorization 7 1. INTRODUCTION fromitsapproximateone,whichonlyinvolvesrecoveringan 0 Numerical approximate computations have the advantage integer from its approximation. They did not discuss how / of being fast, flexible in accuracy and being applicable to toobtain anexactrational numberfrom itsapproximation. h large scale problems. They only give approximate results Command convert in maple can obtain an approximate ra- t a and are applied in many fields. However, some fields such tional number from a float if we set variable Digits to a m as theorem proving, need exact results and symbolic com- positive integer. When variable Digits is taken to different : putations are used to obtain the exact results. Symbolic positive integers, a different rational numbersare obtained. v computationsareprincipallyexactandstable. Theyhavea Whichoneistherationalnumberwewant? Wedonotknow. Xi high complexity. They are slow and in practice, are appli- Insomecases,what’smore,noneoftherationalnumbersis cable only to small systems. In recent two decades, numer- the one we want. For example, if we want to get 1/7, we ar ical methods are applied in the field of symbolic computa- take 0.1196013289 as its approximation. However, no mat- tions. In1985,Kaltofenpresentedanalgorithmforperform- terwhattakingvariableDigitsto,wecannotobtain1/7by ing the absolute irreducible factorization, and suggested to command convert. In [22], Zhang and Feng systematically perform his algorithm by floating-point numbers, then the discussed how to obtain the exact result from its approxi- mation. Theyprovedthattheexactrationalnumbercanbe ∗The work is partially supported by China 973 Project obtainedfromitsapproximationwhentheerrorislessthan NKBRPC-2004CB318003. 1/(2N(N−1)),butinpractice, thealgorithm requiresthat the approximate error is less than 1/((2K +2)N(N −1)), where N is an bound on absolute value of denominator of the exact rational number and K ≥ N. In this paper, we proposeanimprovedalgorithm whichcanrecovertheexact rational number from its approximation when the error is less than 1/(4N(N −1)). The remainder of the paper is organized as follows. Sec- tion 2 gives a review of some properties of continued frac- tion, which are used to prove our theorems later. Section Theorem 3. Each convergent is nearer to the nth con- 3 proves that the rational number we want is the only one vergent than any of the preceding convergents. In symbols, satisfying the error control ǫ ≤ 1/(2N(N −1)), and then if the nth convergent is taken to be [a0;a1,a2,··· ,an] = x, shows that a kind of rational numbers can not be obtained then from its approximation bycontinuedfraction method when the error 1/(4N(N −1))<ǫ≤1/(2N(N −1)); and finally, |[a0;,a1,a2,··· ,ar]−x|>|[a0;,a1,a2,···,as]−x| an improved algorithm is proposed. Section 4 gives some for all r<s<n. experimental results. The final section makes conclusions. 2. PROPERTIESOFCONTINUEDFRACTION Proof: Denote x=[a0;a1,a2,··· ,ar,xr+1], where xr+1 = A continuedfraction representation of a real numberis one [ar+1,··· ,an]. From theorem 1, it holds that of theforms: 1 x= xr+1hr+hr−1 a0+ a + 1 , (1) xr+1kr+kr−1 1 a2+a3+1··· Accordingly, we can deduceas follows: where a is an integer and a ,a ,a ,··· are positive inte- gers. On0e can abbreviate the1 ab2ove3 continued fraction as x(xr+1kr+kr−1)=xr+1hr+hr−1 [a0;a1,a2,···]. For finitecontinued fractions, note that ⇒xr+1(xkr−hr)=−(xkr−1−hr−1) [a0;a1,a2,··· ,an,1]=[a0;a1,a2,··· ,an+1]. Dividing aboveequation byxr+1kr yields So,foreveryfinitecontinuedfraction,thereisanotherfinite continued fraction that represents thesame number. Every x− hr =(− kr−1 )(x− hr−1) finite continued fraction is rational number and every ra- kr xr+1kr kr−1 tional number can be represented in precisely two different waysasafinitecontinuedfraction. Theotherrepresentation Since xr+1≥1 and kr >kr−1>0, we have is one element shorter, and the final term must be greater 0<( kr−1 )<1 than 1 unless there is only one element. However, every xr+1kr infinitecontinued fraction is irrational, and every irrational numbercanberepresentedinpreciselyonewayasaninfinite Therefore, it is provedthat continued fraction. An infinite continued fraction represen- tation for an irrational numberis mainly useful because its |x− hr|<|x− hr−1|. initialsegmentsprovideexcellentrationalapproximationsto kr kr−1 the number. These rational numbers are called the conver- The proof is finished gentsofthecontinuedfraction. Even-numberedconvergents are smaller than the original number, while odd-numbered onesarebigger. Ifsuccessiveconvergentsarefound,withnu- Theorem 4. Let x=[a0,a1,a2,···] and hn =anhn−1+ merators h1,h2,···, and denominators k1,k2,···, then the hn−2, kn =ankn−1+kn−2. Then it holds that relevant recursiverelation is: ˛ ˛ ˛˛hn − hn−1˛˛= 1 hn =anhn−1+hn−2, kn =ankn−1+kn−2. ˛kn kn−1˛ knkn−1 The successive convergentsare given by theformula and ˛ ˛ hknn = aannhknn−−11++hknn−−22, kn(kn+11+kn) <˛˛˛x− hknn˛˛˛< knk1n+1 where h−1 = 1, h−2 = 0, k−1 = 0 and k−2 = 1. Here are 3. AN IMPROVED ALGORITHM FOR RE- some useful theorems[8]: COVERINGTHEEXACTNUMBERFROM ITS APPROXIMATION Theorem 1. For any positive x∈R, it holds that Inthissection,wewillsolvesuchaproblem: Someonehasa [a0,a1,··· ,an−1,x]= xxhknn−−11++hknn−−12 (2) panosuitpivpeerrabtoiounnadlnNumofbderenmnomininhaitsomr oinfdt,haenrdatyioounaolnnlyumknboewr, andhecannottellyoutherationalnumberbutanapproxi- mationoftherationalnumberatanyaccuracy. Howdoyou Theorem 2. Theconvergentsof[a ,a ,a ,···]aregiven computetherational numberfrom oneof these approxima- 0 1 2 tions? Let’sattackthisproblem. Withoutlossofgenerality, by we always assume that m,n are positive numbers. At first, [a0,a1,··· ,an]= hknn we havea lemma as follows: and Lemma 1. m,n,p,qareinteger,andpn>0. If|m−q|< n p knhn−1−kn−1hn =(−1)n. 1 , then m = q. pn n p Proof. |m − q| = |pm−qn|. Noticing |pm−qn| is a non- So,wehaver=[0,1,n−2,2,n,n−1]. Itisobviousthatwe n p pn negative integer, and |m − q| < 1 , yields |pm−qn| < 1. cannotobtainn−1/nfrom[0,1,n−2,2,n,n−1]. Therefore, n p pn Hence|pm−qn|=0. Thatis m = q. Theproofisfinished. we need smaller neighborhood so as to recover the exact n p rational numberbycontinued fraction method. And now, we discuss how to obtain rational number from Corollary 1. m,n,p,q are integers and p > 0,n > 0. itsapproximationbycontinuedfractionmethod. Letn2/n1 Let N ≥max{p,n,2}. If |m − q|< 1 , then m = q. be a rational number and r0 its approximation. Their con- n p N(N−1) n p tinued fraction representations are n2/n1 =[a0,a1,··· ,aL] and r0 =[b0,b1,···,bM] respectively. Wewish that ai =bi Proof: When p 6= n, it holds that pn≤ N(N −1). Hence for i = 0,1,2,··· ,L−1 and for the last term of the con- |mn − pq| < N(N1−1) ≤ p1n. According to lemma 1, it is tinued fraction representations of n2/n1, either aL = bL or obtained that m = q. When p=n, we have aL−1=bL,sothatwecangetn2/n1from[b0,b1,··· ,bL+1]. n p This is thefollowing theorem: m q |m−q| 1 | − |= < n p n N(N −1) Theorem 6. Let n /n be a rational number and r its 2 1 0 n 1 approximation. Assumethatn ,n arecoprimepositivenum- ⇒|m−q|< ≤ ≤1 2 1 N(N −1) N−1 bers, where n < n ,and n > 1. The representations of 2 1 1 So, it holds that m = q. The proof of the corollary is fin- n2/n1 andr0 are[a0,a1,··· ,aL]and[b0,b1,··· ,bM]respec- tively. If |r −n /n | < 1/(4n (n −1)), then one of the ished. 0 2 1 1 1 following statements must hold. Theorem 5. Letx= mn beareducedproperfraction,and • ai=bi (i=0,1,··· ,L); N ≥max{n,2}. Assume that |x−w|<1/(2N(N −1)). If we get positive rational number p/q such that |p/q−w| < • ai=bi (i=0,1,··· ,L−1),aL−1=bL,and bL+1 = 1. 1/(2N(N −1)) , where q≤N , then it holds that x=q/p. According to assumption of n < n , we have that a = 2 1 0 Proof: From the assumption of the theorem, we have |x− 0, and b = 0. Hence a = b . In order to finish the 0 0 0 q/p|<1/(N(N−1)). Accordingtocorollary1,itholdsthat proof of theorem 6, we need two lemmas. Due to n /n = 2 1 q/p=m/n=x. The proof of the theorem is finished. [a0,a1,···,aL] and r0 = [b0,b1,··· ,bM], we have the fol- lowing expansions: Theorem 5 shows us as follows. Onehas a rational number n n n n mn in his mind, if he tells you an approximation w such n1 =a1+ n3, n2 =a2+ n4, ··· , that |m −w| < 1/(2N(N −1)), then there is an unique 2 2 3 3 nraetigiohnbanolrhnouomdb(ewr w−h1o/s(e2Nde(nNom−in1a)t)o,wr i+s l1e/s(s2Nth(aNn −N1i)n))t.he nnLL−1 =aL−1+ n1L, nL =aL (3) and The remaining question is as follows. How do we fetch out 1 1 the unique rational number in the neighborhood? We wish r =b1+r1, r =b2+r2, ··· , 0 1 get it by continued fraction. Unfortunately, we can not al- 1 1 ways fetch out the unique rational number in the neigh- =bL+rL, ··· , =bM (4) borhood (w−1/(2N(N −1)),w+1/(2N(N −1))) by con- rL−1 rM−1 tinued fraction method. One counterexample is the ratio- Denotingdi=ri−ni+2/ni+1,wehavealemmaasfollows: nal number such as (n − 1)/n for n > 1. Let us show this: set N = n, and its approximation r := (2n+2n3 − Lemma 2. Let n /n be a rational number and r its ap- 4n2 −1)/(2n2 −2n+1)/n. One can check its error d = 2 1 0 proximation. Assume that n ,n are coprime positive in- 1/(2n(n−1)+1)<1/(2N(N −1)). However, one can not 2 1 tegers, where n < n ,and n > 1. The representations recover rational number (n−1)/n from its approximation 2 1 1 by continued fraction method. In fact. First we can easily of n2/n1 and r0 are [a0,a1,··· ,aL] and [b0,b1,··· ,bM] re- compute (n−1)/n=[0,1,n−1], continued fraction repre- spectively. And assume that ai = bi for i ≤ k < L(k is a sentationofn−1)/n. Andthencomputecontinuedfraction positive integer). Then when |dk| < nk+1(n1k+1−1), it holds representation of r as follows. that ak+1 =bk+1 for k<L−1; when |dL−1|< nL(n1L+1), it holds that aL=bL or aL−1=bL. 2n+2n3−4n2−1 1 2n2−n+1 r= ⇒ =1+ (2n2−2n+1)n r 2n+2n3−4n2−1 Proof: At first, we show that under the assumption of the 2n2−n+1 1 1+n2−n r = ⇒ =n−2+ lemma if we have 1 21n++n22n−3−n4n2−11 r1 n−1 2n2−n+1 ˛˛˛ n2k+1dk ˛˛˛< 1 (5) r2= 2n2−n+1 ⇒ r =2+ 1+n2−n ˛nk+2(nk+2+nk+1dk)˛ nk+2 2 n−1 1 1 then, it holds that ak+1 = bk+1 for k < L−1, and ak+1 = r = ⇒ =n+ 3 1+n2−n r3 n−1 bk+1 orak+1−1=bk+1 fork=L−1. Wediscussit intwo cases: Lemma 3. Let n /n be a rational number and r its ap- 2 1 0 Case1(k<L−1): Fromdk =rk−nk+2/nk+1,itholdsthat proximation, where n2,n1 are coprime positive integers, and rk =nk+2/nk+1+dk. Hencewe havethat n2 <n1,andn1 >1. Thecontinuedfractionrepresentations 1 − nk+1 =− n2k+1dk sopfenct2i/vnel1y.anDdern0otaered[ia0=,ar1i,·−··n,ia+L2]/nain+d1[bfo0,rb1i,=···0,,b·M··],rLe-. rk nk+2 nk+2(nk+2+nk+1dk) Assumethat ai=bi fori≤k<L−1(k isapositiveinteger ⇒ 1 = nk+1 − n2k+1dk ). Then when |dk|< nk+1(n1k+1−1), it holds that ⇒ rr1kk =ankk++12+ nnnkkk+++322(−nkn+k2++2(nnknk++2k2+1d1+kd)knk+1dk) |dk+1|< nnkk++12((nnkk++12−−11))|dk| (11) =bk+1+rk+1 Proof: Undertheassumptionthatai =bifori=0,1,··· ,k, Hence, obviously,ak+1 =bk+1 if and only if fromequation(5),wegetdk+1 =−nk+2(nnk2k++21+dnkk+1dk). Hence 0≤ nk+3 − n2k+1dk <1. (6) we deducea relation as follows: Therefore, if innekq+u2alitynk(5+)2(hnokl+d2s,+thnekn+1adbko)ve inequality is |dk+1| = n2k+2+n2kn+k1+|d1kn|k+2dk = nk+2n(knn+kk1++|12dk+| dk) guaranteed. Case 2:(when k=L−1) Wehave = nk+1(nk+1−1)|dk| rL1−1 =aL− nL+1(nLn+2L1dL+−n1LdL−1) =bL+rL = nk+2(nk+2n(nk+kn+1k1+−11()n+k+(1n−k+11)−|dk1|)dk) From theabove equation, if nk+2(nk+2−1+ nk+n1k−+n1k+2 +(nk+1−1)dk) | n2LdL−1 |< 1 =1 When|dk|< nk+1(n1k+1−1),itholdsthat nk+n1k−+n1k+2+(nk+1− nL+1(nL+1+nLdL−1) nL+2 1)dk >0. Hencewe havea relation between dk+1 and dk: TthheenreafLore=, wbLefhoarvdeLs−h1ow<n0t,haantdifaiLne−qu1a=litybL(5f)orhdolLd−s1, t≥he0n. |dk+1|< nnkk++12((nnkk++12−−11))|dk| ak+1 = bk+1 for k < L−1, and either ak+1 = bk+1 or The proof of thelemma is finished. ak+1−1=bk+1 for k=L−1. Andnow,letusprovethetheorem. If|d |=|r −n /n |< On the otherhand, we have 0 0 2 1 1/(4n (n −1)), From lemma 3, we can get ˛˛˛˛nk+2(nkn+2k2+1+dknk+1dk)˛˛˛˛= |nk+2(nnk2k++21+|dkn|k+1dk)| 1 1 |di|<1/(4ni+1(ni+1−1)) = nk+1|dk| ≤ nk+1|dk| for i=0,··· ,L−1. Note that nL >nL+1 =1 and nk+2(|nnkk++12 +dk|) nk+2|(nnkk++21 −|dk|)| 1 < 1 < 1 4ni+1(ni+1−1) ni+1(ni+1+1) ni+1(ni+1−1) So, in order to ensure inequality (5), we only need it holds that when ni+1 >1. So, it holds that nk+2|n(nnkkk+++112|d−k||dk|)| < nk1+2 (7) |di|< 4ni+1(n1i+1−1) < ni+1(ni1+1+1) fori=0,··· ,L−1. Accordingtolemma2,theproofofthe Solving inequality (7) yields theorem is finished. |dk|< nk+2 (8) nk+1(nk+1+1) For an unknown rational number n2/n1 and its approxi- When k<L−1, we have that nk+2 >1. So, it holds that mn2a/tnio1n=r[0b,0,tbh1e,o·r·e·m,b6L,s1h]owwhsenth|art0−n2n/2n/1n=1|<[b01,/·(·4·n,1b(Ln]1o−r 1 ≤ nk+2 1)). However,forpractical purpose,wehopetherestriction nk+1(nk+1−1) nk+1(nk+1+1) on n1 >1 and n1 >n2 can be lifted. So we have following theorem: Accordingly, it is obtained that 1 |dk|< nk+1(nk+1−1) (9) Theorem 7. Letn0/n1 beareducedrationalnumberand ritsapproximation. Assumethatn ,n arepositiveintegers 0 1 When k = L−1, we have that nL+1 = 1, so it is obtained and N ≥ max{n1,2}. The continued fraction representa- that tionsofn0/n1 andr are[a0,a1,··· ,aL]and[b0,b1,··· ,bM] 1 respectively. If|d|=|r−n0/n1|<1/(4N(N−1)), then one |dL−1|< nL(nL+1) (10) of the following two statements must hold The proof of lemma 2 is finished. • ai=bi for i=0,··· ,L; • ai=bi fori=0,··· ,L−1, and bL =aL−1, bL+1= Algorithm 1. Input: a nonnegative floating-point num- 1. ber r and a positive number N; Output: a rational number b. Proof: Weprovethetheorem in threecases: Case1(n1 >1, n0 <n1): From1/(4N(N−1))≤1/(4n1(n1− Step 1: Set i = 0, tem = r, h−1 = 1, h−2 = 0, 1)) and theorem 6, thetheorem holds. k−1 =0, and k−2 =1; Case 2(n = 1): We have that a = n /n . If d = r − 1 0 0 1 Step 2: Get integral part of tem and assigning it n /n >0,thenb =a andr =r−a <1/(4×2(2−1)). 0 1 0 0 0 0 to a, assigning its remains to b. If d=r−n /n <0, then 0 1 Step 3: Compute hi = a∗hi−1 +hi−2 and ki = r=a0−|d|=a0−1+1−|d|=b0+1−|d| a∗ki−1+ki−1. If ki>N,then goto Step 6; ⇒r =r−b =1−|d| 0 0 Step 4: Set i:=i+1; |d| ⇒1/r =1+ 0 1−|d| Step 5: Set tem= 1 and goto Step 2; b On the otherhand, we have Step 6: Computing hi−1/ki−1 and assigning it to b. |d|<1/8⇒2|d|<1⇒|d|<1−|d| Step 7: return b. |d| ⇒0< <1⇒b =1 1−|d| 1 The correctness of algorithm 1 is obvious from theorem 7 and theorem 8. So, we havethat b =a −1, b =1. 0 0 1 Case 3(n > n > 1): From n /n = a +n /n , it holds 0 1 0 1 0 2 1 4. EXPERIMENTAL RESULTS that n /n −a =n /n . Ontheotherhand,we havethat 0 1 0 2 1 |n /n −r| < 1/(4N(N −1)) ≤ 1/n . So, we can deduce ThefollowingexamplesrunintheplatformofMaple10and 0 1 1 that a < r < a +1. Accordingly, it holds that b = a . PIV 3.0G, 512M RAM. They take little time for obtaining 0 0 0 0 Hence, we have exactrationalnumbersfromtheirapproximations,sowedo not show time. |d| = |r−n /n |=|b +r −a −n /n |=|r −n /n | 0 1 0 0 0 2 1 0 2 1 = d <1/(4N(N −1))<1/(4n (n −1)) Example 1. Let a be unknown rational number. We only 0 1 1 know a bound of its denominator N = 170. According to And now, we have n1 > 1 and n2 < n1, which is case 1. theorem 7, Computing rational number a as follows: Com- Therefore, theproof is finished. pute d = 1/(4∗N ∗(N −1)) = 1/114920. Assume that we use some numerical method to get an approximation Forsimplicity,sets=Lwhen[a0,a1,··· ,aL]=[b0,b1,··· ,bL] b=.8106421859 such that |a−b|<1/d. Calling algorithm and s = L+ 1 when [a0,a1,··· ,aL] = [b0,b1,··· ,bL,1]. 1 yields as follows. For an unknown rational number n /n and its approxi- 0 1 4 13 17 30 107 137 518 mation r, theorem 7 shows that n0/n1 = [b0,··· ,bs] when 0,1, , , , , , , 5 16 21 37 132 169 639 |r−n /n | < 1/(4N(N −1)). However, we do not know 0 1 what thenumbersis. Thefollowing theoremshowsushow Whenalgorithm1findsthatthedenominatorof 518 isgreater 639 to get [b0,··· ,bs]. than N, it outputs 113679. Example 2.Let a be unknown rational number. We only Theorem 8. Letn /n beareducedrationalnumberand know a bound of its denominator N = 1790. According to 0 1 r itsapproximation. Assumethatn ,n arepositiveintegers theorem 7, Computing rational number a as follows: Com- 0 1 andN ≥max{n1,2}. Wehaver=[b0,b1,··· ,bM]and|r− pute d = 1/(4∗N ∗(N −1)) = 1/12809241. Assume that n0/n1| < 1/(4N(N −1)). Denote n0/n1 = [b0,b1,··· ,bs]. we use some numerical method to get an approximation Then, for any positive integer s<t≤M, the denominator b = .178870799516605 such that |a − b| < 1/d. Calling of rational number g=[b0,b1,··· ,bt] is greater than N. algorithm 1 yields as follows: 1 1 2 5 17 22 149 171 320 1131 0, , , , , , , , , , 5 6 11 28 95 123 833 956 1789 6323 Proof: Proof is given by contradiction. Denote by m the Whenthealgorithmfindsthatthedenominatorof1131/6323 denominatorofg. Assumem≤N. Fromtheorem3,itholds is greater than N, it outputs320/1789. that |r−[b0,b1,···,bt]|<|r−[b0,b1,··· ,bs]|. Noting that |r−[b0,b1,··· ,bs]| = |r−n0/n1| < 1/(4N(N −1)) yields Example 3.Let a be unknown rational number. We only |r−[b0,b1,···,bt]|<1/(4N(N−1)). Accordingtotheorem knowaboundofitsdenominatorN =18. Accordingtothe- 5, it should hold that [b0,b1,··· ,bs] =[b0,b1,··· ,bt]. This orem 7, Computing rational numbera as follows: Compute contradict to that t>s. The proof is finished. d=1/(4∗N∗(N−1))=1/1225. Assumethatweusesome numericalmethodtogetanapproximationb=1.881536615 Basedontheorem7andtheorem5,analgorithmforobtain- suchthat|a−b|<1/d. Callingalgorithm1yieldsasfollows. ing the exact numberis as follows: 1,2,15/8,32/17,111/59 When the algorithm finds that the denominator of 111/59 [5] Robert M. Corless , Stephen M. Watt,and Lihong is greater than N, 32/17. Zhi,QR Factoring to ComputetheGCD of Univariate ApproximatePolynomials IEEE Transactions on Example 4. This example is an application in obtaining Signal Processing, 52(12) pp.3394-3402, 2004. exact factors from their approximations. Let p = −16− [6] Robert M. Corless, Mark W. Giesbrecht, et al, 56y−48z+64x2−32xy+48xz−45y2−96yz−27z2 bea Approximatepolynomialdecomposition.Inproceeding polynomial. Wewant touseapproximatemethodtoget its of ISSAC1999, S.S. Dooley, Ed., ACM pp 213-220. exactfactorsoverrationalnumberfield. First,wetransform [7] YongFeng, YaohuiLi, Checking RSCCriteria for p to a monic polynomial as follows: ExtendedDixon Resultant by Interpolation Method, Proceedings of 7-th International Symposium on 1 3 45 3 27 7 3 1 p=x2− xy+ xz− y2− yz− z2− y− z− Symbolic and NumericAlgorithms for Scientific 2 4 64 2 64 8 4 4 Computing, Timisoara, Romania, September25 - 29, theleastcommonmultipleofdenominatorsofcoefficientsof 2005, IEEE ComputerSociety press pp48-51 polynomial p(x,y,z) is 64, which is an upper bound[21] of [8] Continued fraction, In: http://www.answer.com. denominators of coefficients of themonic factors of polyno- [9] Gauillaume, AndreGalligo, From an approximate to mialp. TakingN =65yieldsd=1/(4∗65∗64)=1/16128. an exact absolute polynomial factorization. Weusenumericalmethodstogetitsapproximatefactorsas http://math1.unice.fr∼cheze/appexact 2.pdf follows[21]: [10] Galligo A., and Watt S. M. A numerical absolute primality test for bivariate polynomials In proceeding g¯ =1.0000x+.6250000000067y+1.124999999530z+.50000 1 of ISSAC1997. W. Ku¨chlin, Ed.ACM, pp 217-224 [11] Huang, Y.,Wu, W.,Stetter, H.,and Zhi, L. g¯ =1.0000x−1.125000000015y−.3749999995480z−.50000 2 Pseudofactors of multivariate polynomials. In Proc. the error of coefficients of g¯ and g¯ is less than d by the ISSAC’00(2000), ACM Press, pp.161-168. 1 2 numerical methods. According to theorem 7, taking N in [12] Karmarka N., and Lakshman Y. N., Approximate algorithm 1, we obtain two exact factors: polynomial greatest common divisors and nearest singular polynomials. In Proceeding of ISSAC1996, 5 9 1 g =x+ y+ z+ ACM, pp.35 -42. 1 8 8 2 [13] Greg Reid , and Lihong Zhi, Solving Nonlinear Polynomial System via Symbolic-NumericElimination 9 3 1 g =x− y− z− Method, In Proceedings of international conference on 2 8 8 2 polynomial system solving. pp. 50-53. 2004 [14] ZhiLIHONGand WU WENDA,Nearest Singular 5. CONCLUSION Polynomials Journal of Symbolic Computation, 26(6). In [22], a bridge overriding the gap between approximate pp.667-676, December 1998 computation and exact results was built. However, the al- [15] Mou-Yan,Z., and Unbehausen,R. Approximate gorithm in [22] requires the error between approximation factorization of multivariable polynomials. Signal and exactresult is lessthan 1/((2N+2)N(N−1)). Inthis Proces. 14(1988), 141-152. paper,weproposeanalgorithm thatonlyrequirestheerror [16] Sasaki, T., Suzuki,M., et al., Approximate islessthan1/(4N(N−1)),whichdecreasesthecostofcom- factorization of multivariate polynomials and absolute puting approximation. Just like the algorithm in [22], our irreducibility testing. Japan J. Indust.Appl.Math. 8 method can be applied in many aspect, such as proving in- (1991),357-375. equalitystatementsandequalitystatements,andcomputing [17] Sasaki, T., Saito T., and Hilano, T., Analysis of resultants,etc. Thuswecantakefullyadvantageofapprox- approximate factorization algorithm. Japan J. Indust. imate methods to solve larger scale symbolic computation Appl.Math.9 (1992),351-368. problems. [18] Tateaki Sasaki, Approximatemultivariate polynomial factorization based on zero-sum relations. In Proc. 6. REFERENCES ISSAC’2001, ACM Press, pp.284-291. [1] Beckermann, B., and Labahn, G., When are two [19] L. Yang,Jingzhong Zhang, and Xiaorong Hou, A polynomials relatively prime? Journal of Symbolic Criterion of Dependencybetween Algebraic equation Computation 26 (1998), pp 677-689. and its Application. Proceeding of IWMN’92, [2] Corless R.M., Gianni P.M., Trager B.M. and Watt, International Academic Publishers, pp 110-134, 1992. S.M. The singular valuedecomposition for polynomial [20] Jingzhong Zhang, YongFengand Xijing Tang: systems. In InternationalSymposium on Symbolicand Multivariate Polynomial factorization byInterpolation Algebraic Computation (Montreal, Canada, 1995), A methods (extendedabstract), Proc. the 7th Asian Levelt, Ed., ACM pp.195-207. Symposium on Computer Mathematics (ASCM2005), [3] Corless, R.M., Giesbrecht,M.W., et al, Numerical (Sung-ilPae, H.Park, eds.), Seoul, Dec.8-10, 2005. implicitization of parametric hypersurfaces with linear [21] Jingzhong Zhang, YongFengand Xijing Tang: algebra. In proceeding of AISC2000, LNAI 1930, Multivariate Polynomial factorization pp.174-183. byInterpolationmethods,submittedtoChinaSciences. [4] Robert M. Corless, Mark W. Giesbrecht, et al, http://arxiv.org/PS cache/math/pdf/0701/0701670.pdf Towards factoring bivariate approximate polynomials, [22] Jingzhong Zhang, YongFeng, Obtainingexact value In Proc. ISSAC2001, ACM press, pp.85-92 by approximate computations, submitted to China Sciences. http://arxiv.org/PS cache/math/pdf/0611/0611915.pdf