Rewritten heuristic and PRS GCD for univariate polynomials, added benchmark.
authorAlexei Sheplyakov <varg@theor.jinr.ru>
Sun, 19 Oct 2008 17:27:14 +0000 (21:27 +0400)
committerAlexei Sheplyakov <varg@theor.jinr.ru>
Sun, 19 Oct 2008 17:27:14 +0000 (21:27 +0400)
Using a better data structure for univariate polynomials makes GCD 10 -- 300
times faster (and less memory hungry).

check/Makefile.am
check/test_runner.h [new file with mode: 0644]
check/time_uvar_gcd.cpp [new file with mode: 0644]
ginac/Makefile.am
ginac/polynomial/eval_uvar.h [new file with mode: 0644]
ginac/polynomial/gcd_uvar.cpp [new file with mode: 0644]
ginac/polynomial/heur_gcd_uvar.h [new file with mode: 0644]
ginac/polynomial/interpolate_padic_uvar.h [new file with mode: 0644]
ginac/polynomial/prem_uvar.h [new file with mode: 0644]
ginac/polynomial/sr_gcd_uvar.h [new file with mode: 0644]

index 5c24aee..b601756 100644 (file)
@@ -55,6 +55,7 @@ TIMES = time_dennyfliegner \
        time_lw_Qprime \
        time_antipode \
        time_fateman_expand \
+       time_uvar_gcd \
        time_parser
 
 TESTS = $(CHECKS) $(EXAMS) $(TIMES)
@@ -243,6 +244,9 @@ time_fateman_expand_SOURCES = time_fateman_expand.cpp \
                              randomize_serials.cpp timer.cpp timer.h
 time_fateman_expand_LDADD = ../ginac/libginac.la
 
+time_uvar_gcd_SOURCES = time_uvar_gcd.cpp test_runner.h timer.cpp timer.h
+time_uvar_gcd_LDADD = ../ginac/libginac.la
+
 time_parser_SOURCES = time_parser.cpp \
                      randomize_serials.cpp timer.cpp timer.h
 time_parser_LDADD = ../ginac/libginac.la
diff --git a/check/test_runner.h b/check/test_runner.h
new file mode 100644 (file)
index 0000000..3f668a7
--- /dev/null
@@ -0,0 +1,67 @@
+#ifndef GINAC_CHECK_TEST_RUNNER_H
+#define GINAC_CHECK_TEST_RUNNER_H
+#include <iostream>
+#include <cstdlib>
+#include <string>
+#include <ctime>
+#include "timer.h"
+
+template<typename T> static void 
+run_benchmark(T& benchmark,
+             const unsigned ntests = 10,
+             const std::clock_t t_annoying = 15*CLOCKS_PER_SEC,
+             const std::clock_t t_min = CLOCKS_PER_SEC/100)
+{
+       const std::clock_t start(std::clock());
+       std::clock_t elapsed(start);
+
+       timer P36;
+       unsigned n = 0;
+       double t = 0;
+       bool go_on = true;
+       do {
+               ++n;
+               P36.start();
+               benchmark.run();
+               t += P36.read();
+               go_on = benchmark.check();
+               if (!go_on)
+                       break;
+               elapsed = std::clock() - start;
+               if (elapsed > t_annoying)
+                       break;
+       } while (n <= ntests || elapsed < t_min);
+       t /= n;
+       benchmark.print_result(t);
+}
+
+// By default long-running timings are disabled (to not annoy the user).
+// If the GINAC_RUN_EXPENSIVE_TIMINGS environment variable is set to "1",
+// some of them (which are supposed to be relatively fast) will be enabled.
+// If GINAC_RUN_EXPENSIVE_TIMINGS is set to "2", all timings are enabled.
+static int run_expensive_timings_p()
+{
+       static int value = 0;
+       static int cc = 0;
+       static const std::string env_name("GINAC_RUN_EXPENSIVE_TIMINGS");
+       if (cc++ == 0) {
+               char* envvar = std::getenv(env_name.c_str());
+               if (envvar != NULL) {
+                       value = std::atoi(envvar);
+                       if (value < 0 || value > 2)
+                               value = 0;
+               }
+               if (value) {
+                       std::cerr << "WARNING: "
+                               << "long-running timings are ENABLED."
+                               << std::endl
+                               << "Unset the \"" << env_name << "\" "
+                               << "environment variable skip them."
+                               << std::endl;
+               }
+       }
+       return value;
+}
+
+#endif // GINAC_CHECK_TEST_RUNNER_H
+
diff --git a/check/time_uvar_gcd.cpp b/check/time_uvar_gcd.cpp
new file mode 100644 (file)
index 0000000..1a073ea
--- /dev/null
@@ -0,0 +1,1877 @@
+#include <string>
+#include <cassert>
+#include <iostream>
+#include "timer.h"
+#include "ginac.h"
+#include "error_report.hpp"
+#include "test_runner.h"
+#include "polynomial/remainder.tcc"
+#include "polynomial/upoly.hpp"
+#include "polynomial/mod_gcd.hpp"
+using namespace GiNaC;
+
+static const std::string p1_srep("\
+-936639990+26248623452*x^47-30174373832*x^46-19627087954*x^45 \
++23532819511*x^24-15331409214*x^23-5892518210*x^22-2954269379*x^28 \
+-35110566664*x^27-4846605217*x^26-31276301429*x^25-19509035058*x^44 \
++18467021749*x^43+18517327396*x^42-3435911855*x^50-272899085*x^49 \
++1530941050*x^48+4507833875*x+10918084347*x^21+7814495607*x^20 \
++23471621465*x^19-11157075535*x^18-11580405260*x^41-12162845828*x^39 \
++12293848678*x^10-14679334842*x^9+17276957972*x^8+6436149609*x^7 \
+-8608995580*x^3-178435747*x^2+21474090980*x^17-3966988360*x^16 \
+-1330154020*x^15-13410537172*x^14-31038290506*x^51+17469329915*x^52 \
+-15282350857*x^53-11990574398*x^54+4255578378*x^55+2134905268*x^56 \
++38375274669*x^57+9183261708*x^58+23467669465*x^59-5872201799*x^60 \
++44704228721*x^61+27682281779*x^62-17204774085*x^63-7544450778*x^64 \
+-319408644*x^65+36034512058*x^66-6744628155*x^67+1363904895*x^68 \
++22219362387*x^69+4275663006*x^70+14038262112*x^71+25591410149*x^72 \
++9385606040*x^73-4745283802*x^74+11598735101*x^75-2508504600*x^76 \
++11912265375*x^77+6624766926*x^78-4828562936*x^79+16636451249*x^80 \
+-9654281719*x^81+1913801599*x^82+2030662033*x^83-5474416933*x^84 \
++11196778577*x^85+512268187*x^86-1029159530*x^87+1890708440*x^88 \
++142491112*x^89-1261023993*x^90+3580061526*x^91-967823912*x^92 \
++2292551912*x^93-3890383043*x^94-7104898913*x^95+3692350529*x^96 \
+-933592128*x^97+1199649580*x^98-227816977*x^99-12217636980*x^40 \
++26794929142*x^38-41046742100*x^37+8432066353*x^36-6214147095*x^35 \
++741141010*x^100-6270990007*x^34-6863205889*x^33-38388107386*x^32 \
+-561107347*x^13-6663332709*x^12+5507703343*x^11+11614165303*x^31 \
+-4503859503*x^30+26050790733*x^29+1788729074*x^6+2123912816*x^5- \
+2542140060*x^4\
+");
+
+static const std::string p2_srep("\
+1882371920-30937311949*x^47+6616907060*x^46-7420079075*x^45-28689993421*x^24 \
++5544486596*x^23+7149046134*x^22+29115114125*x^28-7204610489*x^27 \
+-214559874*x^26+3363043648*x^25-6061422988*x^44-85814533599*x^43 \
+-5548876327*x^42+20531692560*x^50-23673866858*x^49+1553111326*x^48 \
+-7521320830*x-19801882818*x^21+7056872613*x^20-8039690791*x^19 \
++11049483001*x^18+21957440404*x^41+18566882873*x^39-1088265300*x^10 \
++29943249139*x^9+3160532878*x^8+110919258*x^7+1584505491*x^3-2133682609*x^2 \
++11700952246*x^17-12424469513*x^16-426278523*x^15+7561875663*x^14 \
++19494168654*x^51-8174921854*x^52+18073788685*x^53-48441925739*x^54 \
+-3850452489*x^55-17753230977*x^56-44973929094*x^57+7332053562*x^58 \
+-18246235652*x^59+9980611956*x^60+6961020716*x^61-3323333429*x^62 \
+-20693764726*x^63+2577247520*x^64-22463329638*x^65-13528331424*x^66 \
++440594870*x^67+778770195*x^68+24497174109*x^69-11578701274*x^70 \
+-217623403*x^71+16461882236*x^72-6001481047*x^73-5750277357*x^74 \
+-16262001424*x^75+13760397067*x^76+12678193001*x^77+29675566382*x^78 \
++1889202286*x^79+12672890141*x^80+26252749471*x^81+25061328813*x^82 \
++20393397488*x^83-6344703601*x^84-12986831645*x^85+10287410396*x^86 \
++18964048763*x^87+9141433582*x^88+9742202475*x^89+1800283356*x^90 \
++9411879011*x^91+13562767020*x^92-3883570155*x^93+1190623161*x^94 \
++4638169279*x^95+10385086102*x^96+10263027507*x^97+5186524611*x^98 \
++1309311388*x^99+2485463829*x^40-14414308862*x^38-2750892631*x^37 \
+-34230002076*x^36-21558061051*x^35+2789684836*x^100-9973372012*x^34 \
++12038293769*x^33-2280622009*x^32-14841292646*x^13+4463462090*x^12 \
++11039962159*x^11+20714527103*x^31+29530802947*x^30+4813620791*x^29 \
++8841198971*x^6-4237029618*x^5-1135211878*x^4");
+
+static const std::string q1_srep("\
+-96986421453*x^426-75230349764*x^425+128202397899*x^424+67687797741*x^423 \
++3024931260*x^422+43589211963*x^421+17028560437*x^420+9502389896*x^419 \
++4613252773*x^418+12194328527*x^417-57222260166*x^416+40667752907*x^415 \
++93728947357*x^414+35662883623*x^47-14000072723*x^46-9724148606*x^45 \
+-368500426*x^174-66112223350*x^173-44075800265*x^172+7490450738*x^171 \
++51779005621*x^170-64020260063*x^169-35711451392*x^192-13811036693*x^191 \
++38422996693*x^190+78178593950*x^189-26765678624*x^188-36201354868*x^187 \
++2322225247*x^24-4088975893*x^23-5491427592*x^22+66441957259*x^333 \
++132975753131*x^332-25949991451*x^331-18528608186*x^330+34867243557*x^329 \
+-86291867505*x^328-23705975211*x^327+28864997607*x^326-29169139957*x^325 \
+-72081734233*x^324+16339897368*x^323-36285833017*x^322+38448532777*x^321 \
++5689122392*x^320-11755215572*x^113+27585680289*x^112+42744050328*x^111 \
+-19842208161*x^110-15319380323*x^109-9901465464*x^108-5117699979*x^107 \
+-46666019657*x^106-9394133585*x^105-6971615995*x^104+6471181832*x^114 \
+-93545055409*x^347-52862770931*x^346-17176975268*x^345+102286955731*x^344 \
+-108335379176*x^343-49965250837*x^342+70929683596*x^341+43502762174*x^340 \
+-21623476978*x^339-48184795307*x^338+147075382031*x^337+2375821388*x^336 \
++73656068270*x^335-36587627572*x^334-46411968297*x^477+117867456111*x^476 \
++21597655248*x^475-96794140788*x^474+39647492898*x^473+34037992542*x^472 \
++46480360486*x^471-83731284596*x^470-95857281423*x^469+6999736667*x^468 \
+-38822852477*x^467-130028027968*x^466-14942819105*x^465-44491532079*x^464 \
+-136904650366*x^450+127351380760*x^449-127679332542*x^448-43163228644*x^447 \
++130723680563*x^446+20671214531*x^445+28594103126*x^444-20976472951*x^443 \
++51300798407*x^442-136736402258*x^441-70334716366*x^440-15000956055*x^439 \
+-62750491292*x^438+80489844722*x^451-72300799704*x^373+85385725929*x^372 \
+-36185314264*x^371+40354846070*x^370+100343908392*x^369-64625422713*x^368 \
++64635098245*x^367+148519100093*x^366-2548271547*x^365+81466612776*x^364 \
++4505982224*x^363-27138600773*x^362+33493048106*x^361-24851820772*x^28 \
+-10244897195*x^27-4624820516*x^26-7148687043*x^25-31464114015*x^44 \
++4702632945*x^43+7767686263*x^42+42336900887*x^399+3102221349*x^398 \
+-70334528471*x^397+64364012828*x^396+2888804578*x^395+128564212488*x^394 \
++46187560735*x^393-22449464022*x^392-10778814882*x^391-12324659485*x^390 \
+-29896766926*x^389-81652748187*x^388+83789647837*x^387+117499172*x^50 \
++12296030709*x^49-19192082610*x^48-75325243338*x^202-23708473101*x^201 \
+-26628963155*x^200+8750880100*x^199+51496310059*x^198-825543354*x^197 \
+-55510698265*x^196+360107673*x^195+63114288079*x^194+47841450181*x^193 \
+-64231677271*x^203-33846557625*x^500+32003634503*x^499-58125049485*x^498 \
+-201024576939*x^497-16961069022*x^496-6460857023*x^495+17540403418*x^494 \
++110942113017*x^493+31743184966*x^492-25555053476*x^491+4508005212*x \
++54592680578*x^437-76412796528*x^436+1877940561*x^435-103704559046*x^434 \
++67584435952*x^433-92743779936*x^432+16830509289*x^431+90333755240*x^430 \
++7491824203*x^429-39217091446*x^428+9937722888*x^427-19900810770*x^281 \
++99196779*x^280-16832864815*x^279+12499571427*x^278+45347289311*x^277 \
++71352470823*x^276+43741436118*x^275+37615792835*x^274+46658948580*x^273 \
++33324303635*x^272+73592650369*x^271-67395425230*x^270-9849537996*x^269 \
++66141877639*x^268+123533283703*x^360+23749744933*x^359-158320760707*x^358 \
+-96354447711*x^357+74192188378*x^356-12722639577*x^355-5277964622*x^354 \
++27541514016*x^353-15290636975*x^352-56026626672*x^351-83627404427*x^350 \
++134971538669*x^349-70927614564*x^348-30866959351*x^21+23196788827*x^20 \
++14806487974*x^19+7202161677*x^18-77560240113*x^168-97097519755*x^167 \
+-7146671571*x^166+74640588234*x^165+44466905554*x^164+54305760741*x^163 \
+-42912777561*x^162-53367072318*x^161-53826227844*x^160+58601558389*x^159 \
++46328377750*x^158+50761112626*x^157+45872218888*x^156-2281730398*x^155 \
++17638972322*x^41-18461568113*x^39+138681011610*x^186+37241543347*x^185 \
++6568392823*x^184+51513027685*x^183-7992856706*x^182+76890726092*x^181 \
++42349995803*x^180+56514811799*x^179+39745228095*x^178-5406867587*x^177 \
+-1951053982*x^176-5802216424*x^175-50792201214*x^463+6116297*x^462 \
++6556570017*x^461+108055362490*x^460-12691470210*x^459+4182889988*x^458 \
+-43791168823*x^457+34631974035*x^456-19719579134*x^455+25960754189*x^454 \
++98225606953*x^453+91031125129*x^452-24988409414*x^10-743558160*x^9 \
+-1699950291*x^8+2808610975*x^7-48769244040*x^154-96704849123*x^153 \
++111227374137*x^152-14353055349*x^151-3530455648*x^150+67627044718*x^149 \
++48938383630*x^148-36284076468*x^147-36888035781*x^146+21119495829*x^145 \
+-7910849264*x^144-12955332083*x^143-45900441635*x^142-13504842602*x^3 \
++6990226732*x^2-104066823246*x^294-33495506282*x^293+14075627371*x^292 \
++98874306790*x^291-60578180611*x^290+4520025730*x^289+11037329991*x^288 \
+-61725490177*x^287-81799020830*x^286-7490987671*x^285-53034900008*x^284 \
+-18832528068*x^283-41894083315*x^282+37239574099*x^217-19338020660*x^216 \
+-12240694841*x^215+43055454509*x^214+40264787273*x^213-5627707745*x^212 \
++65168034480*x^211+60502488359*x^210-43821281361*x^209-66454240411*x^208 \
+-2909056156*x^207+28786587304*x^206-30816172728*x^205+33777871529*x^204 \
+-190549103953*x^490+76694110369*x^489-2193972225*x^488-15694566522*x^487 \
+-5687638790*x^486+108859908155*x^485-10632768957*x^484+59932596621*x^483 \
+-128319694751*x^482+9747184412*x^481-46212670973*x^480-241524000*x^479 \
+-109350192806*x^478-19351431004*x^17-10992374349*x^16+4266182503*x^15 \
++1491492502*x^14-26936243598*x^51+9140784640*x^52-17235611114*x^53 \
++51043001177*x^54+17375254851*x^55+29087076273*x^56+41034433851*x^57 \
+-3776695101*x^58+15602920815*x^59-33931973560*x^60-5394467773*x^61 \
+-33356572049*x^62+26987634076*x^63-13728305358*x^64-9103761879*x^65 \
+-7718466644*x^66-36314004427*x^67-5838889357*x^68-34997974374*x^69 \
++18394398361*x^70+2693349321*x^71+26120420097*x^72+17127750642*x^73 \
+-13997783088*x^74-20592275154*x^75-32678406375*x^76-37626204617*x^77 \
+-48378652006*x^78+21054785420*x^79-29131926756*x^80+8395471553*x^81 \
++7784927438*x^82+13009002197*x^83-6234144809*x^84-37572100716*x^85 \
+-6593230199*x^86+66776088000*x^87+78828918914*x^88+11091149924*x^89 \
++10549817427*x^90+6921991220*x^91-10162442680*x^92-31105862688*x^93 \
++29905246284*x^94+56641649019*x^95+2729368709*x^96-29516060802*x^97 \
+-60463907529*x^98-20589437573*x^99-76023724773*x^386-66294717897*x^385 \
++127893777713*x^384-33654971374*x^383+67124743823*x^382-31169670568*x^381 \
+-62445748947*x^380-88066123018*x^379-38626212646*x^378-16479040877*x^377 \
+-38277841666*x^376-22265169452*x^375-94473640391*x^374-16848867764*x^40 \
++97436811*x^38-11456803668*x^37+29134819428*x^36+19443677064*x^35 \
++115142334273*x^308+56747688015*x^307+25168740472*x^306+13152212288*x^305 \
+-44950776707*x^304+76665344711*x^303+29576368959*x^302+32075973218*x^301 \
+-9029375348*x^300+6642245020*x^299+91687715671*x^298-51412655310*x^297 \
++83980703440*x^296+46894388060*x^295-5884703744*x^141+2949366186*x^140 \
+-94344563203*x^139-49160316545*x^138-32150373572*x^137+12194208956*x^136 \
++6964141193*x^135-33897455084*x^134+10261728181*x^133-55302581972*x^132 \
++21255450769*x^131-36152255205*x^130-15653019958*x^129+35552230340*x^128 \
++19003739378*x^244+108435248514*x^243+56090919989*x^242+69228227868*x^241 \
++91831598024*x^240-17331067829*x^239+85583813531*x^238+23101424573*x^237 \
+-81857540502*x^236-36120008211*x^235+5734833290*x^234-18668026178*x^233 \
+-49074512287*x^232+17073277846*x^413+30247783286*x^412-165671844164*x^411 \
+-155653969476*x^410-187279578486*x^409+39531046142*x^408-27411804632*x^407 \
++29944561569*x^406-111402223051*x^405-154854505413*x^404-40754859947*x^403 \
+-42933459998*x^402-49470282393*x^401+47851831012*x^400+14974328774*x^100 \
++35782130492*x^267-46375317876*x^266+35773383758*x^265+20027063447*x^264 \
++21061029248*x^263+39184671316*x^262-90547480531*x^261-66296134219*x^260 \
+-17351793087*x^259+32060807026*x^258+94792744023*x^257+49960952178*x^256 \
+-56558329066*x^255+24220170558*x^34+13174400153*x^33-32599593323*x^32 \
++68703378390*x^127+7209203154*x^126+53371357578*x^125+29055746831*x^124 \
++7953940336*x^123+58282173183*x^122+9572688731*x^121+18717721630*x^120 \
+-73554904502*x^119+3118816831*x^118+14413362310*x^117+5342856589*x^116 \
++19553114613*x^115+21062039154*x^102-554311514*x^101-22619708092*x^103 \
++61239109029*x^254-3920281128*x^253-78250174682*x^252-54555413490*x^251 \
++115877792898*x^250+43662559749*x^249-120143669223*x^248+50903904162*x^247 \
++11038501743*x^246-77319776228*x^245+32754289554*x^13+9140139237*x^12 \
+-5050784936*x^11-28608214851*x^319-115868216966*x^318+21037102483*x^317 \
+-40760242975*x^316-97849927912*x^315+97524668075*x^314+15492130497*x^313 \
+-109577284825*x^312-15523330582*x^311+53171617167*x^310+2760321123*x^309 \
++11953881518*x^31-4644794034*x^30+8900679779*x^29+3038154286*x^6 \
+-1713528498*x^5-1682288772*x^4-48992402174*x^231-74205154963*x^230 \
+-12320683295*x^229+2580030624*x^228+64073843802*x^227+98985527674*x^226 \
++27217405490*x^225-4798940390*x^224-40677318547*x^223+22320424589*x^222 \
+-40460537540*x^221-2484720173*x^220+91568547773*x^219-30440775257*x^218 \
+-20925478361*x^501-55379150825*x^502+41318859160*x^503-201803259151*x^504 \
++24491832146*x^505+11945310232*x^506+16801030141*x^507-85919705432*x^508 \
+-204400811240*x^509+108827759662*x^510-7434778800*x^511+11930243788*x^512 \
++52620104622*x^513+2896973876*x^514-62777820856*x^515-58602826569*x^516 \
++133850541568*x^517-141993258526*x^518+23529758012*x^519-49454155126*x^520 \
++48873695726*x^521-4147628780*x^522+37394108608*x^523+47603927637*x^524 \
+-24791421698*x^525+227326835801*x^526-14216866536*x^527+18576010707*x^528 \
+-21047691775*x^529+41343039994*x^530+54576723923*x^531-93293864449*x^532 \
+-33311213168*x^533-121363092547*x^534+33716301298*x^535-141040357184*x^536 \
++51729666523*x^537+47937306583*x^538+59972281522*x^539-118977051593*x^540 \
++67621432194*x^541+49510957189*x^542-18373445363*x^543+77268324211*x^544 \
+-133652596329*x^545-33419335873*x^546-427835316*x^547-53735861227*x^548 \
+-18820033537*x^549+39133250886*x^550-56649816582*x^551+39906553346*x^552 \
+-38346679560*x^553-21315694546*x^554-5783912402*x^555+27780723169*x^556 \
+-38733479148*x^557-105931482172*x^558-96741538387*x^559-49387589876*x^560 \
++8867816401*x^561+49087289355*x^562+1454848177*x^563+33306828689*x^564 \
+-99246716946*x^565+37769469573*x^566+32186219432*x^567-11308309096*x^568 \
++18668048060*x^569+49786290189*x^570+18415965909*x^571+3684081565*x^572 \
+-4772411978*x^573+29967501107*x^574+88125664232*x^575-45402703990*x^576 \
+-17923494443*x^577-66856091994*x^578+52497931423*x^579-38961224535*x^580 \
+-37418352186*x^581+49679845815*x^582-57132928134*x^583+59226638697*x^584 \
+-154438376054*x^585-33182700061*x^586-29726913945*x^587-69912710958*x^588 \
+-35066505635*x^589+12117333556*x^590+90618649713*x^591+25641508805*x^592 \
+-14360015792*x^593-2388909185*x^594-66943383926*x^595+74263398539*x^596 \
++143519268530*x^597+69955222853*x^598+93655324812*x^599+95865179464*x^600 \
++26117219984*x^601+125957153927*x^602+85643852758*x^603+42892120680*x^604 \
+-21713462866*x^605+14954939220*x^606+10043903038*x^607+75469410317*x^608 \
+-51837119306*x^609+15040917218*x^610+20377338352*x^611+31441679566*x^612 \
+-83915039746*x^613+26252571519*x^614-503634581*x^615+26287902963*x^616 \
+-93906462389*x^617-31633190464*x^618+89968162928*x^619-170991982775*x^620 \
++83899910708*x^621+106560970300*x^622-44686742795*x^623+15837336057*x^624 \
++40628901174*x^625+45734331636*x^626+33015259104*x^627+98460164072*x^628 \
+-42946149377*x^629-7628175548*x^630+19113794084*x^631-41069464410*x^632 \
++14600883385*x^633-39765610904*x^634+15187751854*x^635-64373116881*x^636 \
++57427180760*x^637-54359632537*x^638-64614552532*x^639+33179178357*x^640 \
++48320365071*x^641-11056685372*x^642+38160121363*x^643-103617462479*x^644 \
+-2932820983*x^645+55149815103*x^646+2425431294*x^647-56577206559*x^648 \
++16057758155*x^649+35778946395*x^650-48176618659*x^651-64696379262*x^652 \
+-22620871596*x^653+58425156881*x^654+44785934533*x^655+80551487292*x^656 \
++54031151324*x^657-5670209695*x^658+17381996998*x^659-19820657597*x^660 \
++21974450271*x^661-82269840114*x^662-37921867307*x^663+36456465218*x^664 \
+-83294486767*x^665-15913209110*x^666-41870399203*x^667+75486284992*x^668 \
+-69200721639*x^669+71593232147*x^670-24896238679*x^671+12917620475*x^672 \
++83950160209*x^673-49426619038*x^674-75127058039*x^675+54011881154*x^676 \
++37241246401*x^677-57745731856*x^678+139894949202*x^679+81749104336*x^680 \
++19047569663*x^681-3263108647*x^682+27211133766*x^683-122451257494*x^684 \
+-8555594792*x^685+33253239722*x^686-107349740514*x^687+51092807913*x^688 \
++4057189648*x^689-93256950011*x^690+55162355472*x^691-61816339842*x^692 \
++16885083096*x^693-121751819826*x^694+50639115264*x^695+77247288431*x^696 \
++22943813602*x^697+33215869090*x^698-58975325286*x^699-157199542515*x^700 \
++87871148892*x^701-28766482795*x^702-29747811055*x^703-68956086160*x^704 \
++65220950625*x^705-21662209987*x^706+37272639173*x^707+96801516469*x^708 \
+-71318240058*x^709+51218503786*x^710+89676365367*x^711-74236109343*x^712 \
++73239144110*x^713+74363608320*x^714+9145207269*x^715-43125847627*x^716 \
++45624962357*x^717-87121922253*x^718-16301512498*x^719-74699639223*x^720 \
++10858510024*x^721-49718828989*x^722+69188784202*x^723-57283163802*x^724 \
+-25240946842*x^725-18848125183*x^726+30824101946*x^727+28131925069*x^728 \
+-4523237314*x^729-21708406770*x^730+16572200087*x^731+33901545283*x^732 \
++36570946377*x^733-85342952665*x^734-11024354222*x^735-52996875075*x^736 \
++2850866301*x^737+584390938*x^738-15576643293*x^739-19952462826*x^740 \
++118150124588*x^741-30970777574*x^742-65402936216*x^743+59841029763*x^744 \
+-45851459883*x^745-27905618565*x^746+9407727592*x^747+74081843028*x^748 \
+-36908923676*x^749+33404180933*x^750-12010832118*x^751-27598133503*x^752 \
+-18631604127*x^753+110706117529*x^754-58260993047*x^755+92000371551*x^756 \
+-3544997753*x^757-24026345516*x^758-5326405854*x^759+78096319892*x^760 \
+-597358210*x^761-35334977036*x^762+27768304059*x^763-27110809247*x^764 \
+-73612582334*x^765+107609364617*x^766-59301141886*x^767+23970324440*x^768 \
+-29060060082*x^769+68777102577*x^770-132377413827*x^771+22754238015*x^772 \
+-32129043594*x^773-64999432548*x^774-19372762078*x^775+31184492389*x^776 \
+-10477627638*x^777+50023457084*x^778+47413007239*x^779-26371384083*x^780 \
++60690219120*x^781+19239801238*x^782-83296732353*x^783+1369782155*x^784 \
++39528998233*x^785+89322610585*x^786-14469114718*x^787+61444882143*x^788 \
+-27268007305*x^789-66782025565*x^790+72559382333*x^791-58375896558*x^792 \
+-59019888869*x^793+59537001845*x^794-7672146710*x^795+46071362979*x^796 \
++43864876841*x^797-38389399338*x^798+12445498240*x^799+22445421945*x^800 \
+-19867191482*x^801+29695639763*x^802-439060343*x^803-14548926177*x^804 \
++6493137958*x^805-26475885652*x^806+17199673294*x^807-14472466294*x^808 \
+-3972443858*x^809-6694412444*x^810-27845179245*x^811+69564423337*x^812 \
+-1242944956*x^813+71753847110*x^814-110162491247*x^815+28760590961*x^816 \
+-45033514586*x^817+20432605842*x^818-2254902164*x^819-18122426841*x^820 \
++39792310652*x^821-16010785979*x^822-29809849055*x^823+9525854977*x^824 \
++17249950273*x^825-10134672379*x^826+20583429199*x^827+24105975389*x^828 \
++7878147881*x^829+7805909361*x^830+24860098133*x^831-5072168506*x^832 \
++40045803265*x^833+42779485436*x^834-13432875572*x^835+88161293341*x^836 \
++91355873384*x^837-1467257349*x^838+11158963816*x^839+9583583914*x^840 \
++31122429769*x^841-40482720803*x^842-4081869019*x^843-57902352430*x^844 \
++16964780747*x^845-29060953772*x^846-69504616419*x^847-61121483464*x^848 \
+-46713891301*x^849+44904999298*x^850-69604536083*x^851-11337020865*x^852 \
++294505024*x^853-47318977509*x^854+3027572134*x^855+21339618482*x^856 \
+-15853149005*x^857+16285335552*x^858+40110182790*x^859-18341657161*x^860 \
++49887789936*x^861-33552701768*x^862+46385081780*x^863-981469808*x^864 \
++41200826158*x^865+10777507154*x^866-14950519144*x^867+40419646263*x^868 \
+-53741450130*x^869-22868517477*x^870+45151817598*x^871-19543438862*x^872 \
++3955972510*x^873+54752188479*x^874+21656278056*x^875-37418558367*x^876 \
++46148554703*x^877-47291859633*x^878-60826337453*x^879-95667516424*x^880 \
+-25153078038*x^881-110893670927*x^882+36745227210*x^883+24891033298*x^884 \
++13329786568*x^885+1662662627*x^886+11971271338*x^887+17144987144*x^888 \
+-2615988799*x^889-28070812835*x^890+37844104025*x^891+4209715470*x^892 \
++20489525484*x^893-34750326173*x^894-26930924040*x^895+28807856566*x^896 \
+-67232744129*x^897+21557992547*x^898-7466474096*x^899-29460379882*x^900 \
++11599719084*x^901+67152781205*x^902+8214925141*x^903-36941792660*x^904 \
++53285909119*x^905+25945946437*x^906-50737201760*x^907-3797518282*x^908 \
+-14516581381*x^909+17052064867*x^910+49668098832*x^911-25564508274*x^912 \
+-27386697676*x^913-11774383518*x^914-493156372*x^915+13331359952*x^916 \
++18215828822*x^917-1703765835*x^918-25637155270*x^919+16201914729*x^920 \
++58046441105*x^921-63259400427*x^922+67373094341*x^923-10917543441*x^924 \
++12944714407*x^925-330113187*x^926+16734740522*x^927+2893980284*x^928 \
+-32842296951*x^929+36608286601*x^930-15595841*x^931+16778173120*x^932 \
+-19939580967*x^933-9051600178*x^934-35290902058*x^935+13004524714*x^936 \
+-41266776816*x^937+12920294247*x^938+1269376803*x^939-5513768295*x^940 \
++12475046328*x^941+31918641624*x^942+66368453249*x^943-897770392*x^944 \
++40506291484*x^945+6825383600*x^946-210725476*x^947+23275280063*x^948 \
+-5947164362*x^949-28808686423*x^950+4353896571*x^951+10244426548*x^952 \
+-7839372567*x^953+30532389165*x^954-3403582670*x^955+45380086128*x^956 \
+-13074314129*x^957+28545325753*x^958-5842784212*x^959-26959506281*x^960 \
++6604365268*x^961-32138117276*x^962-15682414365*x^963-4133390557*x^964 \
+-12416495535*x^965-2929737653*x^966-19993300065*x^967+11247744076*x^968 \
++3841401771*x^969+25671473626*x^970-7838123767*x^971+3182563094*x^972 \
+-23190705393*x^973+25687775853*x^974+4991068675*x^975+9883795932*x^976 \
+-9640729721*x^977-9525700462*x^978+18936689098*x^979-1080031439*x^980 \
++21713668278*x^981-16017536235*x^982+10320999730*x^983-6460201416*x^984 \
+-1480416714*x^985+1153896503*x^986-9970475903*x^987-1255301536*x^988 \
++7891254981*x^989+6703945740*x^990+6810250661*x^991+1856482568*x^992 \
++8149237774*x^993+7008509831*x^994+6006570629*x^995+6726792746*x^996 \
++4503145470*x^997+91649222*x^998+3092691860*x^999+2111130448*x^1000 \
++7931022064");
+
+static const std::string q2_srep("\
+13695560229*x^426 \
++16181971852*x^425-90237548124*x^424-71238644589*x^423-54046636289*x^422 \
+-56977010004*x^421+24652773038*x^420+20598565048*x^419+91475303480*x^418 \
+-84971121323*x^417-113672677125*x^416+175104489886*x^415+24909134379*x^414 \
++6097498021*x^47-184800727*x^46-20666602129*x^45-11384394640*x^174 \
+-39167969192*x^173+32831872664*x^172-414425301*x^171+26088535929*x^170 \
++35596493049*x^169+30563227841*x^192+11577650926*x^191-43191322527*x^190 \
++12086295210*x^189+23955571873*x^188-25298685458*x^187-28444834807*x^24 \
++7010388904*x^23-29006384328*x^22-84330871264*x^333+9836257003*x^332 \
++37640357302*x^331+17905116770*x^330-130251115515*x^329-95978501346*x^328 \
++19514981244*x^327-106652197296*x^326+35941298261*x^325+57388442425*x^324 \
++44763228998*x^323+51086800775*x^322-87113853021*x^321+63617860368*x^320 \
+-65881485345*x^113-14717773249*x^112-30051082488*x^111-16699273079*x^110 \
++52386582094*x^109-51477006365*x^108+86299667628*x^107+33339117727*x^106 \
+-11189599026*x^105+15726918*x^104-21825360566*x^114-31322461593*x^347 \
++65284435509*x^346-17301191144*x^345+15734564143*x^344+23681004128*x^343 \
++134055240076*x^342-63495561637*x^341+69119399187*x^340+15761017924*x^339 \
++62192334766*x^338+76140614307*x^337+48592812810*x^336-78591910551*x^335 \
++5387039994*x^334-20627179048*x^477+30863999178*x^476-81087236312*x^475 \
+-75933164205*x^474-33082131999*x^473+45384435920*x^472+116792836581*x^471 \
++116973440762*x^470-58617873216*x^469+16707117530*x^468+70585482190*x^467 \
+-25245695981*x^466+21964655001*x^465+156326246149*x^464+50572629272*x^450 \
++15562656594*x^449-31384475178*x^448+28806488822*x^447+98379780384*x^446 \
+-8577150468*x^445-241997040784*x^444+44292557638*x^443-41043057929*x^442 \
++43426121636*x^441+73421002043*x^440-122245378325*x^439+666183816*x^438 \
+-140210723957*x^451+33590048221*x^373+175101192821*x^372+70736972554*x^371 \
+-92048656022*x^370-3495793191*x^369-86224980665*x^368-67443623327*x^367 \
++32314536775*x^366-28883186212*x^365+5111742127*x^364+121792145390*x^363 \
++37030667675*x^362-4097118072*x^361+22857776248*x^28-12136573216*x^27 \
++20442780080*x^26+25846700052*x^25+13425491987*x^44-51594114984*x^43 \
+-4377477922*x^42-43041382453*x^399-57661186745*x^398-22359325055*x^397 \
++20325429303*x^396+69035457782*x^395+87685373045*x^394+24365492495*x^393 \
++29684393262*x^392+48430131525*x^391-695625227*x^390+20950623212*x^389 \
+-11707096914*x^388+27698204708*x^387-17709284679*x^50-23800618055*x^49 \
++58495527083*x^48+14753967994*x^202-7917376913*x^201-7656165582*x^200 \
++44410996825*x^199+27191475903*x^198-65422047389*x^197-14819333083*x^196 \
+-1269092109*x^195-23263288526*x^194+23503451557*x^193-45722872111*x^203 \
++18051733352*x^500-125499139260*x^499-36395631156*x^498-59637301917*x^497 \
++105481548989*x^496+75797493110*x^495+32239299835*x^494+11835972529*x^493 \
++116574982204*x^492-51868336172*x^491-9265203432*x-39597713836*x^437 \
++113015935234*x^436-153556796338*x^435-4853604252*x^434+97729740048*x^433 \
+-33063566031*x^432+126719186003*x^431-74175775603*x^430-42715005191*x^429 \
++32714632165*x^428+76253488404*x^427-22147870587*x^281-17004010435*x^280 \
+-17534946529*x^279+39828373720*x^278+52099668150*x^277+55016917354*x^276 \
+-27029028714*x^275+1832097078*x^274-60942810739*x^273+47857879747*x^272 \
+-51278864730*x^271-5222780191*x^270-5898650096*x^269-21678273747*x^268 \
+-21425566464*x^360+39916245264*x^359-48631849103*x^358-15434842369*x^357 \
+-11776709827*x^356+21409992004*x^355+60368342836*x^354-70458747506*x^353 \
++18437371892*x^352-51315223539*x^351-105763188874*x^350-41326464493*x^349 \
++26384980460*x^348-6783761138*x^21+21334689185*x^20-12549566198*x^19 \
++27317791211*x^18-21543723029*x^168-39565879160*x^167-85203918111*x^166 \
+-6431356158*x^165+7131456890*x^164+56067799364*x^163-65758483287*x^162 \
++14185002785*x^161+4476126737*x^160+58098059740*x^159-15413944760*x^158 \
+-21400285509*x^157+39120970417*x^156+41014228126*x^155+13550191011*x^41 \
++1778606821*x^39-41861155597*x^186-87150315050*x^185+60380468445*x^184 \
++11245803100*x^183-107391972561*x^182-15954816780*x^181-55185898305*x^180 \
+-51517237471*x^179+1349603646*x^178+39890682017*x^177+73058970151*x^176 \
+-88252631077*x^175+8225838344*x^463-52845822946*x^462-84438483052*x^461 \
+-17729797211*x^460-98562969717*x^459-82399019651*x^458+104524956499*x^457 \
+-126683869629*x^456+21367403421*x^455+36131797666*x^454-137807476393*x^453 \
+-94740863919*x^452+1868123354*x^10+6382151694*x^9-14641898053*x^8 \
++21502452426*x^7-4475582501*x^154+8381680030*x^153+1999803400*x^152 \
+-89024997066*x^151+38794061551*x^150-47355124077*x^149-43574475045*x^148 \
++981109162*x^147+13077105992*x^146-92234719034*x^145-22003948923*x^144 \
++65545791087*x^143-21673710856*x^142-3360829230*x^3-5213505618*x^2 \
++12467729502*x^294-5587793663*x^293+6216249569*x^292+1442921644*x^291 \
++37867507103*x^290-31492290101*x^289-14673167737*x^288+33015189422*x^287 \
+-2704565484*x^286+95174488990*x^285-54217068575*x^284+44084204773*x^283 \
+-36577262466*x^282+10376879211*x^217-20844169749*x^216-63109698641*x^215 \
++15376432884*x^214-21978305305*x^213+13899584470*x^212+139241561028*x^211 \
+-44664654159*x^210+2599647517*x^209+76562835916*x^208+18920601168*x^207 \
++45165432827*x^206-13822292860*x^205-25195536685*x^204+2953366208*x^490 \
++62275626307*x^489+44809710519*x^488+111073061078*x^487+76178250211*x^486 \
++4726676962*x^485-16307384*x^484+25134354985*x^483+35561572012*x^482 \
+-77940816336*x^481+14820209996*x^480-8713117577*x^479+138978861424*x^478 \
+-900952782*x^17-15341289507*x^16-12806716201*x^15+9443970355*x^14 \
+-5790259982*x^51-12187496620*x^52+14358577261*x^53+16962500513*x^54 \
++25955497814*x^55-18109191113*x^56-47942729935*x^57-25726536005*x^58 \
+-22107331394*x^59-26777218680*x^60+9526384172*x^61-2329994611*x^62 \
+-797667779*x^63+9992192122*x^64-10517453590*x^65+79225602882*x^66 \
++37973423762*x^67-14732143550*x^68-10707214185*x^69-20734263762*x^70 \
++32036697598*x^71-15304882544*x^72-8663047826*x^73+15796475487*x^74 \
+-15625754764*x^75-1806722698*x^76-13992042720*x^77+24071578801*x^78 \
+-1460871729*x^79-35556467385*x^80+6278675758*x^81+28441859025*x^82 \
+-21446356551*x^83-22846651633*x^84+10847836941*x^85+4499336468*x^86 \
++128532189*x^87+4158071015*x^88+5253407021*x^89+29777404725*x^90 \
+-26059465923*x^91-40927448548*x^92-25096489123*x^93+53387092350*x^94 \
+-3391739440*x^95+19640218031*x^96-55211392254*x^97-25873270895*x^98 \
+-9727303835*x^99+106230698908*x^386-15945119461*x^385-17935823635*x^384 \
+-53556374993*x^383-109640641868*x^382-59714904671*x^381-122191901431*x^380 \
++9957955506*x^379+149517895199*x^378+48813595534*x^377+54994058521*x^376 \
+-43911659492*x^375-40228007707*x^374+374490216*x^40+8496344002*x^38 \
++21128346388*x^37-492653491*x^36-26347609411*x^35+92580385617*x^308 \
++5753392383*x^307+72418711676*x^306-36955820476*x^305-2443808280*x^304 \
++51138244830*x^303+19081895493*x^302-777541237*x^301+42995124541*x^300 \
++43654667628*x^299-26268273836*x^298-61864683651*x^297+64621393027*x^296 \
+-51924046581*x^295-25603791079*x^141-23477310146*x^140+4635174703*x^139 \
+-2883430101*x^138+565462517*x^137+29217704662*x^136+40502985228*x^135 \
+-5190429488*x^134-815731986*x^133-18342727081*x^132+14168171180*x^131 \
++72498842324*x^130+19120698858*x^129+3448048300*x^128-42150729253*x^244 \
+-59646966806*x^243+25136726637*x^242-58312463169*x^241+13429294186*x^240 \
+-68028026326*x^239-1855231812*x^238+67042351401*x^237-24141943642*x^236 \
+-108693143246*x^235-42010041207*x^234+48918679823*x^233+72331711491*x^232 \
+-40303836579*x^413-8185236331*x^412-90945546891*x^411-105388424000*x^410 \
++37156268112*x^409-38869414179*x^408+87460111563*x^407+70482270872*x^406 \
+-73257224213*x^405-67165510452*x^404-45616617911*x^403+47409747378*x^402 \
+-10941088271*x^401-72305864589*x^400+18141927617*x^100-27919403621*x^267 \
+-75002469491*x^266-45875064276*x^265-18838130679*x^264+15478573827*x^263 \
++17341560325*x^262+54857986683*x^261+88131799297*x^260-76999127565*x^259 \
+-66198972699*x^258+48106377422*x^257-77285757762*x^256+1624330315*x^255 \
++3841588365*x^34+30013218950*x^33-5340125031*x^32-37334201612*x^127 \
+-59895558088*x^126-16505068767*x^125+33919294466*x^124+40944166758*x^123 \
++24536748508*x^122-51786214663*x^121+49057258571*x^120+5860208924*x^119 \
+-16197153571*x^118+20745014792*x^117+1859432439*x^116+1336798052*x^115 \
++25319297625*x^102+15443752161*x^101+15888204012*x^103+5268537528*x^254 \
++13437751905*x^253+55130661310*x^252-56945656856*x^251-53187848971*x^250 \
++36792199923*x^249+65889482847*x^248+54676062204*x^247+9373444102*x^246 \
++82778707527*x^245-1155729565*x^13+10818690967*x^12-3151299763*x^11 \
+-113435197911*x^319+36460320856*x^318+31533841659*x^317+59374192238*x^316 \
++36714124360*x^315-46466864464*x^314+57939540988*x^313-117051043786*x^312 \
++6908217352*x^311+119695096985*x^310-37288034834*x^309+32155729060*x^31 \
++10298011464*x^30-10817352548*x^29-4579078917*x^6+1775874428*x^5 \
++930697362*x^4-27139276488*x^231-12815380034*x^230+109060553835*x^229 \
+-3147654703*x^228-69338296876*x^227-2295143261*x^226+88918309431*x^225 \
+-52677961098*x^224-4339428106*x^223+39692513052*x^222+2368222659*x^221 \
+-12821485264*x^220+40810501984*x^219-3135618321*x^218-3478620156 \
++121642846747*x^501-30077710643*x^502+135206627500*x^503+80788885407*x^504 \
++4294142336*x^505+60113761961*x^506-52525711241*x^507-67661624614*x^508 \
+-19690589512*x^509+17662010567*x^510+46484264868*x^511-49055110297*x^512 \
++105429732598*x^513-159310387634*x^514-34712567266*x^515+17939009679*x^516 \
++10058720567*x^517+189648210622*x^518+178503051946*x^519+40612030324*x^520 \
++69140480072*x^521-19608267751*x^522-132451377221*x^523-101549814781*x^524 \
++50009385834*x^525-35218480373*x^526-108625790743*x^527+18136907263*x^528 \
+-179938816243*x^529-15427215352*x^530-67053449940*x^531+47014300252*x^532 \
+-119829185605*x^533-31934518648*x^534+44603663143*x^535-51498133528*x^536 \
+-3111728028*x^537+27910834213*x^538-26950819455*x^539-15441994785*x^540 \
+-109737641439*x^541+6588852171*x^542-38378954724*x^543+4250430490*x^544 \
++21653035413*x^545-90519813297*x^546+218486022762*x^547+15816240641*x^548 \
++27772488593*x^549-46868203601*x^550-692131251*x^551-21710665882*x^552 \
+-3789275125*x^553+35568459021*x^554-145437381161*x^555+104188652886*x^556 \
++11967964256*x^557+32234710722*x^558+51264850939*x^559+19578428472*x^560 \
+-6653459610*x^561+78776159254*x^562-90902552066*x^563+32028754344*x^564 \
+-16371374875*x^565+43915617220*x^566-40979866127*x^567-113279807002*x^568 \
++41056504620*x^569+87062936546*x^570+84540227360*x^571+176182414158*x^572 \
++126129784646*x^573-18113497064*x^574+95632973430*x^575-61835186044*x^576 \
+-1094266284*x^577-25548526606*x^578-16286188041*x^579+23652588125*x^580 \
++99748065654*x^581+89189400499*x^582-84281188422*x^583-24822510820*x^584 \
+-89019899561*x^585+17299853927*x^586+37447146519*x^587-52389168891*x^588 \
++60307425654*x^589+105423385125*x^590-16151503989*x^591+51669035353*x^592 \
++25896930669*x^593+68125207997*x^594-48076475979*x^595+49080185222*x^596 \
+-114085618440*x^597+62417918964*x^598-29972805919*x^599+102994192965*x^600 \
++9470661387*x^601-65249001543*x^602+101392509369*x^603+13718716428*x^604 \
++38937251889*x^605-65562594382*x^606+66443969710*x^607+18877176302*x^608 \
+-31358768559*x^609+82684433809*x^610-35507835802*x^611+123781293747*x^612 \
++31262151912*x^613-38249975546*x^614+3925377499*x^615-9663279445*x^616 \
++65505212623*x^617-38333318816*x^618-10947904682*x^619-33057241878*x^620 \
++137158617657*x^621+82280949071*x^622-144548051021*x^623+26049388729*x^624 \
++120972835647*x^625+22919074287*x^626+21809122232*x^627+38807820245*x^628 \
+-35626871745*x^629+61073211657*x^630+10263794194*x^631-87779372272*x^632 \
++122409165273*x^633-71973533044*x^634-16220803574*x^635+190684171230*x^636 \
++39466031010*x^637-28535534784*x^638-129018222849*x^639-83527842222*x^640 \
++12242673643*x^641-69609384363*x^642+110212358649*x^643+165584710235*x^644 \
++83720551042*x^645-46594433050*x^646-25255661563*x^647-32840172649*x^648 \
++38437706003*x^649+24359981454*x^650+103816698072*x^651+35342491654*x^652 \
++99935819866*x^653-76900534968*x^654+9187154790*x^655-21467901456*x^656 \
++11271802560*x^657+2793048339*x^658+156900676156*x^659-71757864537*x^660 \
++69068834560*x^661-21725605511*x^662+20565641172*x^663-17160005713*x^664 \
+-28846431158*x^665-63820679105*x^666+67344279329*x^667+17417509088*x^668 \
+-49749571514*x^669-149526619276*x^670+63726307333*x^671+47868397878*x^672 \
+-152430070*x^673-98024226774*x^674-5900709150*x^675+35049382555*x^676 \
++45151856490*x^677-74725155328*x^678+85550840075*x^679-28035942909*x^680 \
+-26105359645*x^681+8366135944*x^682-61065262686*x^683-11480596600*x^684 \
++66582786332*x^685+31934448191*x^686-4555392418*x^687+21122866405*x^688 \
++98576196894*x^689-67653329405*x^690+23891408534*x^691-97842890368*x^692 \
+-38880790121*x^693+31989951820*x^694-85233731747*x^695+81476023995*x^696 \
++13150343534*x^697+34515945612*x^698-28479873758*x^699+7200965291*x^700 \
++22962247818*x^701+31245755201*x^702-7231787902*x^703+20078549142*x^704 \
++112814365060*x^705-37906130331*x^706+119341166775*x^707-4419273787*x^708 \
+-136935403112*x^709-42320208584*x^710-76243411849*x^711-85094494474*x^712 \
++62345894287*x^713+123330307888*x^714-28416874429*x^715-8930496064*x^716 \
+-27860939118*x^717-67479134742*x^718+63217142335*x^719-104983862154*x^720 \
++63261675838*x^721+29568447967*x^722+5532882614*x^723+7122613368*x^724 \
+-75015246457*x^725+27623940192*x^726-71280327669*x^727+63881717913*x^728 \
+-64602087729*x^729+55116167817*x^730-37894641441*x^731+24570439656*x^732 \
++60506453909*x^733-56693236822*x^734+65202309407*x^735+48657462670*x^736 \
++7020063399*x^737-14972937697*x^738+14832651654*x^739+38685418056*x^740 \
+-120977459366*x^741+128129373977*x^742-93004438817*x^743+21708662393*x^744 \
+-42256337713*x^745-74943652142*x^746+13089216312*x^747-68161772735*x^748 \
+-9184732864*x^749-36881334485*x^750+12849929766*x^751-14616276010*x^752 \
+-117623139884*x^753+85738538127*x^754-39397879206*x^755-41203911145*x^756 \
++17752041163*x^757-28528185854*x^758-75782937817*x^759+58967984992*x^760 \
+-46501383932*x^761-30160463545*x^762+9264824504*x^763-61240651988*x^764 \
++46332296135*x^765-36374812215*x^766-33996335903*x^767+38748904012*x^768 \
++16692416615*x^769-24682633336*x^770-101120634096*x^771-16383524365*x^772 \
+-9803993525*x^773-41138860891*x^774+6438402836*x^775+15150248922*x^776 \
++37535375473*x^777+38243096134*x^778+42990687315*x^779+6806571489*x^780 \
+-98981551731*x^781+48378556460*x^782-20305038281*x^783-19970849999*x^784 \
+-32199627381*x^785-33726111417*x^786+26825654676*x^787+61472162609*x^788 \
+-52262572570*x^789+6245081045*x^790+37192923285*x^791-36188152777*x^792 \
+-37778625393*x^793+26152618527*x^794-18379411727*x^795-16240247039*x^796 \
++45087181394*x^797-124867049408*x^798-107527500523*x^799-24928581030*x^800 \
++19049432356*x^801-47425859030*x^802+94662514506*x^803-83733870803*x^804 \
++24856672813*x^805-94427622673*x^806+243768097*x^807+12589141374*x^808 \
++41959344927*x^809+18983184801*x^810+42147767843*x^811+69911314756*x^812 \
++41515466302*x^813-25611533183*x^814+20697173226*x^815-23226268622*x^816 \
+-3460976233*x^817+19330241623*x^818+53475160447*x^819-2631042112*x^820 \
+-9676147438*x^821-48282043682*x^822-90120418937*x^823+48976788717*x^824 \
+-7320635080*x^825-31580257870*x^826-40998967997*x^827-9980407645*x^828 \
++66749588012*x^829+7524200886*x^830+14940938828*x^831-28733285670*x^832 \
++61208670468*x^833-46627324765*x^834-324835109*x^835-104056679115*x^836 \
++29480632050*x^837-22586403838*x^838+40186158836*x^839+15807331652*x^840 \
+-32196192662*x^841+4141096053*x^842-23428399361*x^843-68414521546*x^844 \
+-39195126416*x^845+20150874189*x^846+70929847486*x^847+15213160735*x^848 \
+-209188024*x^849-55922045928*x^850+31518449658*x^851+9332299671*x^852 \
+-61000802604*x^853+42494294179*x^854+333778076*x^855+21847051495*x^856 \
+-53208254853*x^857+41428747135*x^858-13241351753*x^859-16608043286*x^860 \
++9621250261*x^861+25806175298*x^862-21297665820*x^863-14032790352*x^864 \
+-18013819490*x^865+15757760316*x^866+17003024240*x^867-30013032879*x^868 \
++30760011284*x^869-13804439291*x^870-51756563292*x^871+51909198130*x^872 \
+-29495505438*x^873+7110464993*x^874-36258305774*x^875-9149267274*x^876 \
+-30428902968*x^877-48039515073*x^878-34750047014*x^879+7876564124*x^880 \
+-45028260612*x^881+29426481275*x^882+36322178879*x^883+55350571320*x^884 \
+-72386726651*x^885+23215477084*x^886-95129391342*x^887-62068317572*x^888 \
+-5131982570*x^889+25120942005*x^890+47570343070*x^891-16931626769*x^892 \
++32866462223*x^893+75548504697*x^894-48026152317*x^895-33748968072*x^896 \
+-1682061382*x^897+8180943332*x^898+19356108993*x^899+7145333263*x^900 \
++22433305927*x^901+18401298176*x^902-46765206984*x^903-19742304183*x^904 \
+-48845002624*x^905-27099816961*x^906+23031415252*x^907-4460429941*x^908 \
+-14418681720*x^909-41227198785*x^910-10148524063*x^911+18686856429*x^912 \
+-97172567422*x^913-9574103314*x^914-18076030731*x^915-28358519392*x^916 \
+-16581350003*x^917+12090038057*x^918+44243258246*x^919-3986576854*x^920 \
++11411306779*x^921+17162852247*x^922+6351778392*x^923-15260387550*x^924 \
+-29138592351*x^925-14800636505*x^926+9885625539*x^927-36480762358*x^928 \
++844036464*x^929-7561956503*x^930-28235178974*x^931-15625555530*x^932 \
++2051786154*x^933-31812159700*x^934+13415581956*x^935+5382068286*x^936 \
++20152707873*x^937-46081228993*x^938+17160743960*x^939-4906718548*x^940 \
+-22981161630*x^941+39189470825*x^942-15015976743*x^943+36442762021*x^944 \
++14159701449*x^945-20259808043*x^946+19582548075*x^947+7969503721*x^948 \
++15803199913*x^949+9091493711*x^950-11663943215*x^951-5644414749*x^952 \
+-3135411920*x^953+2212086003*x^954-3254521457*x^955-56705145197*x^956 \
++6408789788*x^957+10381413436*x^958-3057504701*x^959+12451307686*x^960 \
++9518096173*x^961-15016723746*x^962+37406257148*x^963+808574925*x^964 \
++8217276211*x^965-5548816739*x^966+8580073344*x^967-16411223685*x^968 \
++7110424112*x^969-8924388605*x^970+20244682123*x^971+16962224189*x^972 \
++21644034171*x^973+10349693065*x^974+14406123922*x^975+17009695542*x^976 \
++10162045861*x^977+5660460802*x^978-1036608219*x^979-1885363228*x^980 \
+-5283058429*x^981-516240895*x^982-15317530637*x^983-11663251903*x^984 \
++4064930580*x^985+7633085681*x^986+8471058375*x^987+20912594799*x^988 \
++3688126507*x^989+11604012893*x^990+5171125016*x^991+7684753357*x^992 \
+-2336834864*x^993+2482449646*x^994-23487081*x^995+41345539*x^996 \
+-1908649318*x^997-1563161986*x^998-3391442566*x^999-1975737484*x^1000");
+
+static const std::string r1_srep("\
+138233755629*x^426-22168686741*x^425-65314032186*x^424+46713467112*x^423 \
++54066842891*x^422+82543269656*x^421+176235947107*x^420+23156315980*x^419 \
+-8714217205*x^418-7917439564*x^417-20923895097*x^416-96817317174*x^415 \
++37671252734*x^414+16053780026*x^47+26648458420*x^46+254608847*x^45 \
+-11343106531*x^174-44222442938*x^173-10656079278*x^172-54688112379*x^171 \
+-72653860271*x^170+70185903368*x^169-66162378498*x^192-19340590695*x^191 \
+-74831870843*x^190-51340722881*x^189-65948469390*x^188-40940690738*x^187 \
+-9541570627*x^24+12358437331*x^23-3840010930*x^22-26103658089*x^333 \
++16787990043*x^332-72471206553*x^331+38195377054*x^330+48906246421*x^329 \
++29212932541*x^328+27943555500*x^327-126086829668*x^326+45642899604*x^325 \
++152779000312*x^324-45599025206*x^323-86920511292*x^322+30167371152*x^321 \
++27416748135*x^320-546541724*x^113+41265938666*x^112-24708554690*x^111 \
+-20961586765*x^110+16946301630*x^109+45088470222*x^108-5349150466*x^107 \
++15365225017*x^106-7995302120*x^105-20232813599*x^104+10081791273*x^114 \
+-3865321947*x^347-87489963865*x^346-30639453185*x^345+3676613013*x^344 \
+-58165676134*x^343-68737381572*x^342-3907635479*x^341+14873150406*x^340 \
+-5503004922*x^339-78473587467*x^338-54025110093*x^337-29151845013*x^336 \
+-67735495295*x^335+73397803045*x^334-27801675473*x^477-14039747517*x^476 \
+-8375986438*x^475+84327817349*x^474+82430096016*x^473+85036210781*x^472 \
++74675551911*x^471-31481207861*x^470+50505881655*x^469+57661203244*x^468 \
++1422790738*x^467+46263290040*x^466+17837475246*x^465+109465309830*x^464 \
++5141857548*x^450-85449781066*x^449+84234728669*x^448-88234927160*x^447 \
+-127641987837*x^446-92744124462*x^445-55229182896*x^444-58231651691*x^443 \
+-71614587111*x^442-19795619691*x^441+16444963184*x^440+7188954710*x^439 \
+-21800762926*x^438+858791107*x^451-75911542139*x^373-9360344384*x^372 \
++121593378315*x^371-13873126064*x^370+26377931906*x^369+65223112057*x^368 \
++54567161420*x^367+81605659307*x^366+50232494189*x^365+22085432850*x^364 \
++68840804661*x^363-15408612740*x^362+86485074789*x^361-15439204155*x^28 \
+-6661325097*x^27+6410229219*x^26+30961129925*x^25+38724464689*x^44 \
++13389600650*x^43-4221359244*x^42-1728086134*x^399-37933493961*x^398 \
+-14669037140*x^397+23734942521*x^396-58830055830*x^395+8467094098*x^394 \
++77771292477*x^393-89683404862*x^392-78155773051*x^391-39478631291*x^390 \
+-67987409649*x^389-64950072499*x^388-12266565939*x^387+11491110518*x^50 \
++23873449940*x^49+22044595358*x^48+14077914429*x^202-57100831007*x^201 \
++13655668351*x^200-22624838544*x^199-51198193976*x^198+4929392620*x^197 \
++61541561422*x^196+58408299147*x^195-2755337167*x^194-2544113778*x^193 \
++38364208184*x^203-39653790505*x^1196+237290860955*x^1197+1445942111*x^1198 \
+-44203650162*x^1199+82332058439*x^1200-8702521180*x^1201+70840770500*x^1202 \
++119211377409*x^1203+62594288529*x^1204-90021858665*x^1205-129281425167*x^1206 \
++136510590125*x^1207-32382101108*x^1208+4377395620*x^1209-94124507363*x^1210 \
+-136821711247*x^1211-62766336520*x^1212+73042766437*x^1213+170448193742*x^1214 \
+-159429807450*x^1215+23801498853*x^1216+83841365444*x^1217-2786331945*x^1218 \
+-110101444536*x^1219+120943591409*x^1220-17972193177*x^1221-17917016958*x^1222 \
++76059557227*x^1223-26278875051*x^1224+28452314938*x^1225+59268213718*x^1226 \
+-14918040641*x^1227+214442906160*x^1228-40652938342*x^1229+96990811343*x^1230 \
+-1760397639*x^1231-21403305270*x^1232+108438376045*x^1233+11163376014*x^1234 \
+-49795674343*x^1235-155428477820*x^1236-46317266895*x^1237-21181283092*x^1238 \
++54803863270*x^1239+77990955099*x^1240+9021816223*x^1241-81330127566*x^1242 \
+-172066502236*x^1243+38125269764*x^1244+126728193806*x^1245+20491510600*x^1246 \
++52585146599*x^1247-188911557303*x^1248-134043853649*x^1249+67603167253*x^1250 \
+-130154245559*x^1251-55153609001*x^1252+163170176229*x^1253-4743088670*x^1254 \
++41209412802*x^1255-10129602317*x^1256+181535124040*x^1257+56212841612*x^1258 \
++71426935568*x^1259-30429980124*x^1260-60832906417*x^1261+67431835761*x^1262 \
++121532246986*x^1263+33159787171*x^1264+79034947915*x^1265+12461193342*x^1266 \
+-75977547043*x^1267-43756049561*x^1268+168122514802*x^1269-48398370299*x^1270 \
++35964935382*x^1271+54347586872*x^1272+44590944224*x^1273+10445353165*x^1274 \
+-26132065869*x^1275-47859095692*x^1276-1718582779*x^1277-41783188995*x^1279 \
++11909834976*x^1278-77982413527*x^500-73027923452*x^499-85982752234*x^498 \
+-88590919157*x^497+18625207103*x^496-19917282031*x^495-203961285889*x^494 \
++92315048982*x^493-113685780846*x^492-35278695612*x^491-4343198835*x \
++8372388799*x^437-7765335812*x^436+122688463230*x^435+143085745466*x^434 \
+-15940623925*x^433+59911209151*x^432+41198459053*x^431+86637043974*x^430 \
+-19150403305*x^429-9590187908*x^428+72843435206*x^427-18969078712*x^281 \
+-45111690065*x^280-29657990745*x^279-29667542848*x^278-14810537128*x^277 \
++38201688736*x^276-3959944314*x^275+75115374863*x^274+13874014995*x^273 \
++9466913592*x^272+40932968214*x^271-124744392985*x^270+42790568189*x^269 \
++14764851450*x^268-56964896169*x^360+107236900075*x^359+64188502464*x^358 \
+-19966311943*x^357-89292693652*x^356+37459485658*x^355+9602002258*x^354 \
++8694265442*x^353+104669007441*x^352+25291836948*x^351-18712737803*x^350 \
++72885504388*x^349-6701955331*x^348+16019376388*x^21-10276721887*x^20 \
++9332762048*x^19-15679749591*x^18+15800007975*x^168-43019181710*x^167 \
++44135505581*x^166+609100023*x^165+6765959027*x^164-13557946012*x^163 \
++4278574066*x^162+6019496346*x^161+63349714834*x^160+36279456292*x^159 \
+-8605662788*x^158-16446890130*x^157-41810449045*x^156-7095450334*x^155 \
+-4077050532*x^41+21830008852*x^39-29092609442*x^186-12826386339*x^185 \
++6695603221*x^184-49972209582*x^183-83136366951*x^182-50423891996*x^181 \
+-18169858920*x^180-78476319819*x^179-21436351653*x^178+7919620529*x^177 \
++28970986638*x^176+79296839091*x^175+77264613819*x^463+116466004826*x^462 \
++55542962016*x^461-13262967705*x^460+36244684198*x^459+83226762576*x^458 \
+-64390551357*x^457-18179417756*x^456-99881894932*x^455+75031794196*x^454 \
++26324508605*x^453-26157248749*x^452-3352003325*x^10-12675513756*x^9 \
+-15441617775*x^8-5613718699*x^7+43860635066*x^154+27940358221*x^153 \
+-2134093560*x^152+54527866704*x^151+2777626391*x^150+38378887212*x^149 \
++49841642562*x^148-30221044274*x^147+21827366162*x^146+17014456405*x^145 \
++30271071817*x^144-27945878711*x^143+51399953423*x^142-57512493*x^3 \
++2646183642*x^2-20412139833*x^294-93210725051*x^293-34887615044*x^292 \
+-47910215801*x^291-6350488002*x^290-13981009447*x^289-155911910590*x^288 \
++34327352071*x^287-43586097508*x^286-23319014164*x^285-56002153978*x^284 \
++81803548303*x^283-71820207962*x^282-10617748524*x^217-34889926744*x^216 \
+-43806949611*x^215+12004331776*x^214+29950034237*x^213-32867273114*x^212 \
+-34298658181*x^211+21233130475*x^210-15987453386*x^209-28840589378*x^208 \
++1865221090*x^207+5310473345*x^206+21898421919*x^205-7574068856*x^204 \
++69079520037*x^490-77180539242*x^489-3940662000*x^488-74380408842*x^487 \
++46029555022*x^486+22962337328*x^485-121388716462*x^484-114696481860*x^483 \
+-4968867689*x^482+69556807304*x^481+57719690408*x^480+83880745421*x^479 \
+-90995723818*x^478+16426027446*x^17-9008826521*x^16+3125040990*x^15 \
+-10087115771*x^14+7507131425*x^1364+5491038077*x^1365+23299185767*x^1366 \
++158679796477*x^1367+124242620006*x^1368-34138235836*x^1369-104792195268*x^1370 \
++44072214558*x^1371+30242736127*x^1372+74669209902*x^1373-28102587847*x^1374 \
+-39469546681*x^1375+52533883313*x^1376-80940926697*x^1377+78402169540*x^1378 \
++58161497695*x^1379-78127274957*x^1380+187195727863*x^1381+34839827097*x^1382 \
++97631469873*x^1383-132261723396*x^1384-243403867184*x^1385+101905407375*x^1386 \
+-103768707126*x^1387+140665326183*x^1388+38246904662*x^1389+94463316851*x^1390 \
++42616536629*x^1391+75720607770*x^1392+75120834886*x^1393+57978068569*x^1394 \
++82557166839*x^1395+14150729258*x^1396+27266620054*x^1397-18339937355*x^1398 \
++167325111479*x^1399-172482710865*x^1400+26706898368*x^1401+49778092097*x^1402 \
+-153703751430*x^1403-61886877598*x^1404-81585576994*x^1405+19946334906*x^1406 \
+-69565555266*x^1407+94052269487*x^1408-113507716080*x^1409-17501141543*x^1410 \
+-137588116092*x^1411+165758417577*x^1412+35485042515*x^1413+61433836565*x^1414 \
++90286860422*x^1415+2551044222*x^1416-77880307583*x^1417-50298698782*x^1418 \
++83096470495*x^1419+115239475320*x^1420+72164396736*x^1421+189899241723*x^1422 \
+-56373869311*x^1423+97019679656*x^1424-48247967357*x^1425+154619324085*x^1426 \
+-67236039222*x^1427-47410964957*x^1428+169855658430*x^1429+30322992840*x^1430 \
+-63052501875*x^1431+222129643467*x^1432+4192274277*x^1433-75770181677*x^1434 \
++64933458610*x^1435+77098206606*x^1436-27720674116*x^1437-5749263490*x^1438 \
++125660847820*x^1439-34531000515*x^1440-124220079488*x^1441-138169543755*x^1442 \
++17069521947*x^1443+47935404425*x^1444+52181081902*x^1445+16289942255*x^1446 \
+-15900660870*x^51+32923650103*x^52+27554024107*x^53+18237379971*x^54 \
++20628678703*x^55+1475901766*x^56-15828776045*x^57+38774503478*x^58 \
+-26045359531*x^59-23045701898*x^60-24089408197*x^61+34446523234*x^62 \
++40957087639*x^63+11389117440*x^64+9820681224*x^65+16429339120*x^66 \
++26545401357*x^67-32362862895*x^68-26680758766*x^69-13927308596*x^70 \
++57526789510*x^71-2089874730*x^72+77834083653*x^73+1750624845*x^74 \
+-16803601217*x^75-60811888974*x^76-30511923805*x^77-49471168139*x^78 \
++295087634*x^79-2230079022*x^80+8101489602*x^81+1848095682*x^82 \
+-13546237573*x^83-64824054906*x^84-1604410156*x^85-13212803439*x^86 \
+-28859271440*x^87-21647178880*x^88-2728763159*x^89+20896727129*x^90 \
++17467604913*x^91+17068807003*x^92-6893543875*x^93+47303976287*x^94 \
++24117835126*x^95-42839904766*x^96+73128945825*x^97+16819953882*x^98 \
++23690754989*x^99+43674412612*x^386+125292875686*x^385-6868632145*x^384 \
++6792231538*x^383+13345729255*x^382+100308206906*x^381-36410281681*x^380 \
++151329173416*x^379+34770326061*x^378-31189291341*x^377+41062130384*x^376 \
++12585820391*x^375-25741536606*x^374+7011683808*x^40+3801986823*x^38 \
+-13975966697*x^37+860658280*x^36+7772384392*x^35+70631237268*x^308 \
++8038593583*x^307+9785270382*x^306+7562096391*x^305+18097750087*x^304 \
+-36486540217*x^303+21014018569*x^302-50758761074*x^301+31281420904*x^300 \
++53709825490*x^299+52888377853*x^298-74951274347*x^297+12921546086*x^296 \
+-76415705347*x^295+15826680805*x^141-8143429483*x^140-1266967067*x^139 \
+-52609851275*x^138-127235369220*x^137-5562487640*x^136+15459500426*x^135 \
+-34261922713*x^134-26128935470*x^133-31766069313*x^132-46271941901*x^131 \
++11210102504*x^130-66673301013*x^129-52689509960*x^128+60511652766*x^244 \
+-75008847608*x^243-20985226623*x^242+7192516942*x^241-161582525421*x^240 \
+-49134000625*x^239-9420319932*x^238-52466552215*x^237+20737248665*x^236 \
++4518034715*x^235-86981206669*x^234-65413662872*x^233-55595224849*x^232 \
++48838613905*x^413-89117174044*x^412-28371635419*x^411+58369364519*x^410 \
+-63080675673*x^409-30544354398*x^408-45382170441*x^407-18873560244*x^406 \
++18026475289*x^405-50705159627*x^404+38696002656*x^403+526588856*x^402 \
+-21240649788*x^401-43406345490*x^400+74297814205*x^100+6264961896*x^267 \
+-1021895999*x^266+86122332454*x^265+38169747213*x^264+64147932916*x^263 \
++58378689172*x^262+24226397033*x^261-29422870170*x^260-47943224531*x^259 \
++26452750294*x^258+105345226861*x^257+43954658692*x^256-20434482832*x^255 \
++8127775817*x^34+30199475755*x^33-12223507015*x^32+22756827882*x^127 \
+-32719507346*x^126-49802125175*x^125+60597935861*x^124-74864424168*x^123 \
++13477644513*x^122+5355799358*x^121+10198619648*x^120+20797815942*x^119 \
++1011263561*x^118-6797018716*x^117-9127452274*x^116+22527387258*x^115 \
++10256659433*x^102+29285807465*x^101+7541734764*x^103+17761344886*x^254 \
+-17286568131*x^253+25433230102*x^252-40561054425*x^251+11031323376*x^250 \
++23702567137*x^249-60198922511*x^248+28633857562*x^247+47422980942*x^246 \
+-9295089069*x^245-10089830249*x^13-23491786545*x^12+4224016794*x^11 \
++81467257701*x^319+63655491886*x^318-66641279796*x^317+144469815422*x^316 \
+-77290195044*x^315+70923255017*x^314+15984076870*x^313+14434564477*x^312 \
++36604017606*x^311+103558138654*x^310-51454408044*x^309-3209161334*x^31 \
++15201977479*x^30+28627262797*x^29-906050188*x^6-10466791945*x^5 \
+-8215574614*x^4+6088611949*x^1280-155043352048*x^1281-118198059014*x^1282 \
++141985007241*x^1283-20206827728*x^1284-22529445083*x^1285+3357709716*x^1286 \
++20047180952*x^1287+20996464819*x^1288-23941814014*x^1289-95188363707*x^1290 \
++40630147116*x^1291-14052413668*x^1292-21048701821*x^1293+100140633841*x^1294 \
++167338922803*x^1295+33226558*x^1296-128357266656*x^1297+81105983581*x^1298 \
++31392576204*x^1299-21641561406*x^1300+235587348445*x^1301+161935696996*x^1302 \
+-128703673247*x^1303-39346114561*x^1304+42054040866*x^1305-12956319862*x^1306 \
++65064708855*x^1307+44115412714*x^1308-39733064653*x^1309+3355869893*x^1310 \
+-161862258823*x^1311+97885854896*x^1312-102623735650*x^1313-108185508417*x^1314 \
++108464851653*x^1315-112704576169*x^1316+131875786827*x^1317+60270345360*x^1318 \
++20669673912*x^1319+21026875646*x^1320+75295304489*x^1321+43782162551*x^1322 \
+-61132288089*x^1323+24355164025*x^1324+63346171944*x^1325+85327679328*x^1326 \
++97712315102*x^1327+99189458373*x^1328-160846738551*x^1329-141296521216*x^1330 \
++20245830585*x^1331-52143723845*x^1332-76834814333*x^1333+41461601925*x^1334 \
++18631439711*x^1335-178840949428*x^1336-66799837449*x^1337+106991716450*x^1338 \
+-153373473969*x^1339-50991501172*x^1340+136263482777*x^1341+40392134464*x^1342 \
+-83367427546*x^1343+28165179356*x^1344+120448869294*x^1345-139735638019*x^1346 \
++55812330303*x^1347+115565807139*x^1348+80171150937*x^1349-29320222386*x^1350 \
++85845037273*x^1351-56994419699*x^1352-1430513579*x^1353+5782046987*x^1354 \
+-38239520543*x^1355-80217085657*x^1356-66662368035*x^1357+73040143027*x^1358 \
++31583949065*x^1359+22409165365*x^1360-52189298813*x^1361-30600519487*x^1363 \
+-160877387612*x^1362-130745878790*x^1447-164421846143*x^1448+58826335534*x^1449 \
+-121078622350*x^1450-92870208218*x^1451+63205043793*x^1452-47504622824*x^1453 \
+-40792276413*x^1454+132243469959*x^1455-50122842754*x^1456-25457647727*x^1457 \
++75460123980*x^1458+92360457423*x^1459-47123614245*x^1460+27742628194*x^1461 \
++70699349259*x^1462-60815737692*x^1463-169591512815*x^1464+120636922587*x^1465 \
++2874472932*x^1466-107608428068*x^1467-5720975123*x^1468+79093930048*x^1469 \
+-56584218802*x^1470-170994826684*x^1471+72209169257*x^1472-49673733343*x^1473 \
+-90870320816*x^1474+157355941752*x^1475+110866008554*x^1476+16569857191*x^1477 \
+-30490578506*x^1478+76530403441*x^1479-162248432265*x^1480+93640590463*x^1481 \
+-15744202469*x^1482+8788690056*x^1483-70664515415*x^1484+35129616345*x^1485 \
+-39685588353*x^1486-10030759315*x^1487+88476545624*x^1488-37767780482*x^1489 \
++85460102492*x^1490-154368097388*x^1491-101122282432*x^1492-17958917193*x^1493 \
++15758996309*x^1494-52478307769*x^1495-40381137773*x^1496-133030420549*x^1497 \
+-24719543246*x^1498-8096296417*x^1499+101004857673*x^1500+86200685962*x^1501 \
+-25972251955*x^1502-84505928738*x^1503+4038114310*x^1504-1730887646*x^1505 \
++34280919324*x^1506-10546638656*x^1507+33864769034*x^1508+37325029980*x^1509 \
++52990264954*x^1510+78875435896*x^1511-23552799978*x^1512+18021688980*x^1513 \
+-70918050095*x^1514+37377330996*x^1515+147115987122*x^1516+59886319925*x^1517 \
++69247156063*x^1518+44264194675*x^1519-5321836395*x^1520+49605413611*x^1521 \
++16106834226*x^1522-127288542421*x^1523+10517014560*x^1524-33826730451*x^1525 \
++17362491215*x^1526+11259519069*x^1527-111850411663*x^1528+169788136728*x^1529 \
+-61627977383*x^1530-83949340540*x^1531-203179287438*x^1532+65741933623*x^1533 \
+-43116357571*x^1534-40480690150*x^1535-41131362243*x^1536+79032181440*x^1537 \
+-59212226430*x^1538+15954047280*x^1539+58552174868*x^1540-2763240020*x^1541 \
+-70634496472*x^1542+61309662059*x^1543-116329612672*x^1544-3218593493*x^1545 \
++88470810821*x^1546+39987733363*x^1547-110861185999*x^1548+67527613693*x^1549 \
+-5618360677*x^1550+34760731651*x^1551+101313541809*x^1552+57123487946*x^1553 \
+-73138213965*x^1554-113152834893*x^1555+85732909325*x^1556+17860086653*x^1557 \
+-112504565378*x^1558+55883545171*x^1559-65178434517*x^1560-39660841716*x^1561 \
+-63794649779*x^1562+46366489306*x^1563-13439935357*x^1564+88339338684*x^1565 \
+-57150594822*x^1566+30622063640*x^1567-16625632272*x^1568-119377667973*x^1569 \
++224593656399*x^1570+53193487159*x^1571+65126081701*x^1572+62970399092*x^1573 \
++68191968832*x^1574-2532739610*x^1575+182827386055*x^1576+88816579011*x^1577 \
+-89385510567*x^1578+66143786656*x^1579+126309891941*x^1580+5804094044*x^1581 \
++97890664428*x^1582+85726994348*x^1583-23154770060*x^1584-117108787907*x^1585 \
++13971227562*x^1586+38219978507*x^1587-29292257027*x^1588-45584106398*x^1589 \
++226543786384*x^1590-123525218087*x^1591-106279675553*x^1592+59009279185*x^1593 \
+-21501846244*x^1594-58215906325*x^1595+10168443133*x^1596+14253963923*x^1597 \
+-103607933374*x^1598-23820552704*x^1599+73298115017*x^1600-76073336462*x^1601 \
++27722337160*x^1602+30665618287*x^1603-40718538083*x^1604-10845646905*x^1605 \
++103841915855*x^1606-88690958814*x^1607+15639683979*x^1608+63587256763*x^1609 \
++79584369720*x^1610-3856065377*x^1611+3277105804*x^1612+49374804337*x^1613 \
++22208269344*x^1614-103803342247*x^1615-18126304778*x^1616-2637468237*x^1617 \
++1194910718*x^1618+49396303997*x^1619-59067168846*x^1620-151244829011*x^1621 \
+-61107141831*x^1622+6516627549*x^1623-46932605166*x^1624+40009442716*x^1625 \
++10816141849*x^1626-13881407844*x^1627+19588816684*x^1628-30762755573*x^1629 \
+-3498132458*x^1630-51828207675*x^1631-143896344594*x^1632+13062299884*x^1633 \
++118213321141*x^1634+20450936554*x^1635-22769649400*x^1636+24410873563*x^1637 \
++61409701263*x^1638+62682111645*x^1639-12555885646*x^1640+81231121875*x^1641 \
+-87265869575*x^1642-50101835778*x^1643+23208178290*x^1644+47909319630*x^1645 \
+-56149574095*x^1646-5387312186*x^1647+45155954494*x^1648-26506247987*x^1649 \
+-24655453114*x^1650+64438306450*x^1651+933006957*x^1652+88649043790*x^1653 \
++33722720231*x^1654-67168346690*x^1655+20490156374*x^1656+58590799138*x^1657 \
+-35113882356*x^1658+86769469196*x^1659-31677323009*x^1660+68172444087*x^1661 \
++30384983461*x^1662+65971494796*x^1663+29114405715*x^1664-72273691319*x^1665 \
++8637409991*x^1666+102558776528*x^1667+25534632508*x^1668-150062568831*x^1669 \
++149103774958*x^1670+76826656126*x^1671-9206966427*x^1672+47754890342*x^1673 \
++143906292602*x^1674-47363760887*x^1675-100347436928*x^1676+49034963661*x^1677 \
+-30032825100*x^1678+1904447368*x^1679-16465929892*x^1680+115898668860*x^1681 \
+-15427200819*x^1682+78327171484*x^1683+40114906121*x^1684-115194215170*x^1685 \
+-11250164384*x^1686-61135885162*x^1687-25229902390*x^1688-80960554583*x^1689 \
++46627919488*x^1690+12640135253*x^1691-12106872032*x^1692+657736289*x^1693 \
+-61068471661*x^1694-69864159279*x^1695-132350791169*x^1696+98340842400*x^1697 \
+-70012959047*x^1698-2783637838*x^1699+3610440908*x^1700-47500311360*x^1701 \
+-27795498744*x^1702-8059436836*x^1703+31022917786*x^1704+11882840379*x^1705 \
++32303942074*x^1706+85260001288*x^1707+34515935101*x^1708-48862338609*x^1709 \
+-37609344377*x^1710+26243060316*x^1711-93968692092*x^1712+7263670481*x^1713 \
++14186751888*x^1714+50504820421*x^1715-97325627322*x^1716-7505006522*x^1717 \
+-22987526264*x^1718-25885379938*x^1719-60493345579*x^1720-35418112892*x^1721 \
++84502334154*x^1722-76073278035*x^1723-14606929933*x^1724+66548501808*x^1725 \
++5528600957*x^1726-8215155843*x^1727-59490241426*x^1728-28466163634*x^1729 \
+-70616897676*x^1730-8577546165*x^1731-17443872540*x^1732+45985496045*x^1733 \
+-25689081146*x^1734+31463778961*x^1735-11994818364*x^1736+26963273177*x^1737 \
+-14658991498*x^1738+3071653886*x^1739+10415294559*x^1740-11371033244*x^1741 \
+-63444243140*x^1742+6028056803*x^1743+43009638114*x^1744+134916900978*x^1745 \
++17343194494*x^1746+80265572665*x^1747-34809795749*x^1748-105843176239*x^1749 \
+-825331310*x^1750-4839163988*x^1751-62409624690*x^1752-20792219308*x^1753 \
+-97773424039*x^1754-40261609853*x^1755-43580213332*x^1756-35959090815*x^1757 \
+-38749485599*x^1758-36327596188*x^1759-37274972348*x^1760+40676817240*x^1761 \
++83402203312*x^1762+68572573193*x^1763-13232334596*x^1764+26432741583*x^1765 \
+-5897475378*x^1766-61972444406*x^1767+58535013523*x^1768+19602260192*x^1769 \
+-8318743400*x^1770+7803001425*x^1771+76563637063*x^1772-113144033283*x^1773 \
+-71048872512*x^1774+37755540165*x^1775+19330521255*x^1776-56127401651*x^1777 \
++18888644242*x^1778+31817399525*x^1779+10800209238*x^1780+42691003617*x^1781 \
++33764982495*x^1782+46697603267*x^1783-25632574756*x^1784+33073816150*x^1785 \
++60790438629*x^1786+52911597033*x^1787+36269227256*x^1788+24513405600*x^1789 \
+-62856298604*x^1790+40347138135*x^1791+47204525731*x^1792-44078709555*x^1793 \
+-70239814448*x^1794-16761046243*x^1795-40213099308*x^1796-70370190048*x^1797 \
++88560337870*x^1798-43789585801*x^1799-26066270170*x^1800-12513783195*x^1801 \
++40117642516*x^1802+1078125116*x^1803+51122854580*x^1804+49031149283*x^1805 \
+-14630551725*x^1806+83787049535*x^1807+64190880486*x^1808+72057188859*x^1809 \
++10305597348*x^1810+79560003326*x^1811+27992723763*x^1812-40123535204*x^1813 \
++6540213580*x^1814-12201813772*x^1815-62863210776*x^1816-9530516684*x^1817 \
++26089647341*x^1818+8240990342*x^1819-16988726374*x^1820+25502485674*x^1821 \
++21819935364*x^1822+7578747975*x^1823-7924234392*x^1824-4583916789*x^1825 \
++27312267438*x^1826+27028394122*x^1827+36340332694*x^1828+34569493970*x^1829 \
+-24317197250*x^1830-73040883806*x^1831+119152928326*x^1832-27999217300*x^1833 \
+-66377712512*x^1834+19049296317*x^1835-1499967276*x^1836-101411288144*x^1837 \
+-9893623936*x^1838-12904600465*x^1839-65098811535*x^1840-10374614407*x^1841 \
+-63493256502*x^1842-20925111013*x^1843-43545631503*x^1844-56380343071*x^1845 \
+-78765502946*x^1846-61513189902*x^1847-53296444805*x^1848-22832568686*x^1849 \
++35971486958*x^1850+15588623624*x^1851+53739674006*x^1852-27920615672*x^1853 \
++20232297980*x^1854-24748814662*x^1855+6432159679*x^1856+14056122601*x^1857 \
++16908873134*x^1858-54999071671*x^1859-3428715644*x^1860-19509913014*x^1861 \
+-2921305636+10285270533*x^1862+54449949829*x^1863-16556984981*x^1864 \
+-45632321047*x^1865-37192326359*x^1866-89167294735*x^1867+28988566970*x^1868 \
++33580738542*x^1869+17847650506*x^1870-2590933698*x^1871+60479028111*x^1872 \
+-74174252419*x^1873-51005953957*x^1874+34076527326*x^1875-12501722418*x^1876 \
++11997164778*x^1877+11106537537*x^1878-67544802654*x^1879-28559326960*x^1880 \
++25496394971*x^1881-7743517594*x^1882-60700405990*x^1883-3306265111*x^1884 \
+-52601213422*x^1885-48504437343*x^1886-33628794516*x^1887-6175399721*x^1888 \
+-42427338898*x^1889+2438088321*x^1890-10879611090*x^1891-50114291787*x^1892 \
++8139307516*x^1893+699677484*x^1894+27742148976*x^1895+2363683066*x^1896 \
++23142955138*x^1897-13125418109*x^1898-8068365620*x^1899-26376527681*x^1900 \
+-16879977313*x^1901-13899647882*x^1902+55501082808*x^1903+20977999945*x^1904 \
+-41959603668*x^1905+42141731465*x^1906-65252748680*x^1907-5713058482*x^1908 \
++5531788408*x^1909+1048150468*x^1910-34295154871*x^1911+43795245653*x^1912 \
+-4033095400*x^1913+72651409*x^1914+31984617590*x^1915+71930374776*x^1916 \
++54517887941*x^1917+63333532478*x^1918+28984482038*x^1919-3608878013*x^1920 \
++53698106501*x^1921-6222405514*x^1922-7430102368*x^1923+1402958879*x^1924 \
++24008303304*x^1925-26827491519*x^1926-18648926565*x^1927-3823394849*x^1928 \
++5733309563*x^1929-6299547658*x^1930-6962395749*x^1931-40969231686*x^1932 \
+-45285051134*x^1933+10564829658*x^1934-30748565479*x^1935+26388805425*x^1936 \
+-10363567687*x^1937-2246446609*x^1938+52290201133*x^1939-17786261909*x^1940 \
++17176068018*x^1941+64179974707*x^1942-1578020234*x^1943-2645079212*x^1944 \
++4997898669*x^1945+10466153459*x^1946-27279279576*x^1947+13143215693*x^1948 \
++25305770043*x^1949-7792611978*x^1950-3367810548*x^1951+23045646458*x^1952 \
++2489207763*x^1953-9625209614*x^1954+17800677290*x^1955+26661651216*x^1956 \
++10046368551*x^1957+42990303916*x^1958+25595010235*x^1959+10610259914*x^1960 \
++48515299215*x^1961+18912135820*x^1962-32456695901*x^1963+43323673755*x^1964 \
+-21642505920*x^1965-52393990137*x^1966-9367854579*x^1967-10325914747*x^1968 \
+-16523379626*x^1969+22693063102*x^1970+20643925200*x^1971-19137060196*x^1972 \
+-39466187671*x^1973-22674273729*x^1974-13174940089*x^1975-28945458193*x^1976 \
++21790522131*x^1977+17410100411*x^1978-12046307125*x^1979-1835929094*x^1980 \
++12380357301*x^1981+373817436*x^1982+14048331587*x^1983+20998406345*x^1984 \
+-20185931652*x^1985-17385658538*x^1986-6371722529*x^1987-11640878021*x^1988 \
++11243150741*x^1989+19803816827*x^1990+548583054*x^1991+5438200196*x^1992 \
+-640602400*x^1993-9126628108*x^1994+4447085824*x^1995-398990035*x^1996 \
+-5395080531*x^1997-2441931417*x^1998-1200282319*x^1999-655038612*x^2000 \
++5366597811*x^231+68706406617*x^230+17345409974*x^229-48143185759*x^228 \
++44737410494*x^227-68056841842*x^226-19799043985*x^225-49804885873*x^224 \
++47061365105*x^223-4032111915*x^222-3623332613*x^221-23047211828*x^220 \
+-33602755354*x^219-53260548964*x^218+11121679469*x^1001+211391200411*x^1002 \
+-121806627697*x^1003-7593859366*x^1004-68089674863*x^1005-93535081213*x^1006 \
+-100904889771*x^1007+205151348397*x^1008-26911086523*x^1009+20992481200*x^1010 \
+-26975210049*x^1011+9802944823*x^1012-99339217781*x^1013-28676624812*x^1014 \
+-106268955620*x^1015-28064424851*x^1016+149985720354*x^1017-10056890284*x^1018 \
+-25972392754*x^1019-60442506971*x^1020+24876839939*x^1021-140451184537*x^1022 \
++139436860282*x^1023+102456153010*x^1024+143113275735*x^1025-43874834829*x^1026 \
+-120467763129*x^1027+82361748186*x^1028+70759866448*x^1029-132303541720*x^1030 \
++62109348740*x^1031-2307679959*x^1032-43220551985*x^1033-3105105156*x^501 \
+-115056774450*x^502+112590551437*x^503+5074319239*x^504-65050446174*x^505 \
++27525467715*x^506+67043788704*x^507+73109872394*x^508+4454612231*x^509 \
+-166827879565*x^510+48004509602*x^511+80073196338*x^512+84629877684*x^513 \
++24953136452*x^514-13404546936*x^515-60152470306*x^516+103604258158*x^517 \
++30378727630*x^518+96105639988*x^519+86931170303*x^520+1851307686*x^521 \
+-10704467449*x^522+48099516842*x^523+25278865072*x^524-21023665046*x^525 \
+-27596977843*x^526+65317392068*x^527+56996468517*x^528-23541114280*x^529 \
+-4528634244*x^530-49979244811*x^531-1372409230*x^532+108626443622*x^533 \
++38697103934*x^534+5617360642*x^535-31315823926*x^536+6522344835*x^537 \
+-50005336880*x^538-96453605654*x^539+28390028376*x^540+167430623705*x^541 \
+-79419733246*x^542-24583477278*x^543+63017279331*x^544-12241800025*x^545 \
+-40444796471*x^546-198616484429*x^547-9239010524*x^548+39965042629*x^549 \
+-33945600302*x^550-12524550727*x^551+3446319229*x^552-45586186264*x^553 \
++95379898956*x^554-105411519522*x^555+28743671574*x^556-56347937800*x^557 \
++82076691560*x^558-74986185221*x^559-53554425965*x^560-4171382516*x^561 \
++47050272907*x^562-141507918105*x^563-68329670995*x^564-21468094592*x^565 \
+-42005013644*x^566+1988928389*x^567+89304325452*x^568+46242523185*x^569 \
+-64871208337*x^570-10239983494*x^571-70479561912*x^572+56681858933*x^573 \
++97804124796*x^574+171255081488*x^575-130052127051*x^576-14919774499*x^577 \
++18415158122*x^578-14270012626*x^579-9826133185*x^580+10877406520*x^581 \
+-37520045371*x^582+172353597026*x^583+190781179637*x^584+86006600201*x^585 \
+-63038348575*x^586+36324085954*x^587+25668119488*x^588-75472073699*x^589 \
++94604145076*x^590+31201682136*x^591-66618040256*x^592-45927957789*x^593 \
+-30451201238*x^594+124888776542*x^595+106197365428*x^596-46438347803*x^597 \
+-18424519559*x^598+2639003013*x^599-27907496745*x^600-18199794457*x^601 \
+-103880772629*x^602+23137884650*x^603-1512635630*x^604-147696867223*x^605 \
++80829019035*x^606-161525424590*x^607-100434984435*x^608+29614936899*x^609 \
+-6137679862*x^610+60715360985*x^611+34868225692*x^612-58893614200*x^613 \
+-32696951034*x^614+29320270324*x^615-87130316336*x^616+113482677724*x^617 \
+-160405479943*x^618-123613848093*x^619+93085583175*x^620+6456833758*x^621 \
++39419082730*x^622+68534416102*x^623-25600393374*x^624+90189542563*x^625 \
++188413710505*x^626+47761747853*x^627+133884897114*x^628+103302592307*x^629 \
++838529232*x^630+99793611131*x^631-30322268075*x^632+111356852748*x^633 \
++43231984135*x^634+110500432225*x^635+84573167353*x^636+437111929*x^637 \
++88828390775*x^638+150357932904*x^639+69321584552*x^640+4998543409*x^641 \
++77507164385*x^642-5551641217*x^643+133533084525*x^644-148039019687*x^645 \
++34184755625*x^646+58913273467*x^647-144075969804*x^648-81457644110*x^649 \
+-88064205997*x^650-76970723677*x^651-135555167488*x^652-4963071211*x^653 \
+-71129120*x^654-25524718409*x^655+63345713205*x^656+61571118817*x^657 \
+-107047528701*x^658-16064516713*x^659-22356065855*x^660-96298139547*x^661 \
++117212160499*x^662+23069062197*x^663+67098662581*x^664+60095764808*x^665 \
++4311023429*x^666-13452349998*x^667+91235201366*x^668-122795422087*x^669 \
+-9005240476*x^670-99246025367*x^671+90306081579*x^672-113597846449*x^673 \
+-31798545519*x^674-71234065451*x^675+20415132246*x^676+171318088198*x^677 \
++76440873812*x^678+86723386966*x^679+60768372398*x^680+38646393133*x^681 \
++46034963485*x^682+161267463461*x^683-95395669596*x^684+43300902681*x^685 \
++1364577202*x^686+89232456559*x^687+20757990799*x^688+168914572153*x^689 \
+-37448321567*x^690-15404071512*x^691-673765572*x^692-22284471241*x^693 \
+-45418634390*x^694-51127164178*x^695-54766988245*x^696+23452651883*x^697 \
++82054856051*x^698+28585810080*x^699-128474952409*x^700-66068244980*x^701 \
+-62286757834*x^702+10446524482*x^703-23350333885*x^704-49357457852*x^705 \
+-20412291318*x^706+72438491276*x^707-9712277514*x^708+99856984639*x^709 \
++12531900104*x^710+15860752484*x^711+92139497336*x^712-22087999262*x^713 \
+-189651791840*x^714+431932231*x^715-79802249583*x^716+31582207314*x^717 \
++71827172753*x^718+88606853762*x^719+121148429011*x^720-20480789552*x^721 \
+-85506256319*x^722-22747058943*x^723+22272625680*x^724+75106833715*x^725 \
+-87815085198*x^726-18573784977*x^727+51790194453*x^728-34926769490*x^729 \
++156368605389*x^730-89883516474*x^731-106204257960*x^732+126409684589*x^733 \
++99590987979*x^734+76044515259*x^735+134493643759*x^736+80505851731*x^737 \
+-7948293309*x^738+28390988236*x^739+158320452938*x^740+45025281010*x^741 \
++79496671226*x^742-48239197544*x^743+78128671709*x^744-250719796024*x^745 \
+-161889144663*x^746+121290695138*x^747+89224446335*x^748-12017264890*x^749 \
++8836137575*x^750-186287680017*x^751+79370288211*x^752+81231119965*x^753 \
++45969331743*x^754-84293927522*x^755-175094284570*x^756-77777720697*x^757 \
++96346229248*x^758-98800364838*x^759+13503370732*x^760-117936272490*x^761 \
+-187387525590*x^762+16390728965*x^763-41826835741*x^764-108395149961*x^765 \
+-107880166963*x^766-76149324709*x^767-88276194375*x^768+33191031138*x^769 \
+-204617761996*x^770+161285750732*x^771-48140097503*x^772+11077755135*x^773 \
++12757803021*x^774-43152311232*x^775-271935037932*x^776+1831433875*x^777 \
++65100048254*x^778+17917219486*x^779+104345191161*x^780-19736603553*x^781 \
+-36421925355*x^782-26813686138*x^783+263563040875*x^784+192297311726*x^785 \
+-95972724582*x^786+17848985752*x^787-84432409440*x^788+111804445366*x^789 \
++245846106331*x^790+91609765067*x^791+63679570834*x^792+10523814205*x^793 \
+-106441552262*x^794+115586926862*x^795+677538038*x^796+6853856052*x^797 \
+-39814859093*x^798+15816033482*x^799+147593524975*x^800-73234648246*x^801 \
+-53137394100*x^802+58091667262*x^803+37495621759*x^804-217416974216*x^805 \
+-66396397229*x^806-91927898947*x^807+54149805354*x^808-123901425066*x^809 \
+-51475545581*x^810-186300013422*x^811-126705120470*x^812-189510422*x^813 \
++11338404677*x^814+6325441981*x^815+91232083427*x^816-133780522659*x^817 \
+-86298399414*x^818-44135279153*x^819+76816814544*x^820-138195966434*x^821 \
+-75684218038*x^822-126386426657*x^823-44809130231*x^824-83490163212*x^825 \
+-34351203484*x^826-41719317981*x^827-120688936869*x^828-14489273602*x^829 \
++106470084813*x^830+41964660903*x^831+33403043858*x^832+151505022397*x^833 \
++87862913140*x^834+120445537076*x^835-98566276077*x^836+4697632177*x^837 \
++44046773581*x^838+73352678462*x^839-11410306650*x^840+22742711623*x^841 \
+-51216881846*x^842-147550591892*x^843+26476191234*x^844+193153996499*x^845 \
+-35927538398*x^846-6194176598*x^847-221667022042*x^848-14015578041*x^849 \
+-5698749713*x^850+26363594400*x^851+14645715378*x^852+48470068979*x^853 \
+-138256378354*x^854-132853825554*x^855+57482839352*x^856+34735643796*x^857 \
++86752172547*x^858+60835536589*x^859-63791336423*x^860+23481544832*x^861 \
++378282280*x^862+23239795711*x^863+88713416598*x^864-48468401808*x^865 \
++43928927469*x^866+11773049307*x^867-62470361270*x^868+177145273813*x^869 \
+-194358054372*x^870+18849309164*x^871-61004124650*x^872-89154730183*x^873 \
+-180073144042*x^874+10857839862*x^875-11488914470*x^876-105388656993*x^877 \
++29610973464*x^878-179112409056*x^879+27490437080*x^880+6130882402*x^881 \
+-73717395879*x^882-24727395241*x^883+6427407478*x^884+27774977309*x^885 \
++26171001560*x^886+285300862204*x^887+250920282226*x^888+69247036204*x^889 \
+-68353373325*x^890-19660487923*x^891-199313228024*x^892+185922127103*x^893 \
+-56927953551*x^894+60519873690*x^895+77728652690*x^896-105603952672*x^897 \
+-63339878187*x^898-74519679962*x^899-45764977904*x^900+17864107983*x^901 \
++10133013854*x^902-144667843119*x^903+33769537229*x^904+116016157352*x^905 \
+-109345484017*x^906+104654868950*x^907-961106931*x^908+31965621838*x^909 \
+-6900915942*x^910+39708679388*x^911+165967464883*x^912-13498312464*x^913 \
+-167799799320*x^914-131936289889*x^915+89614618044*x^916+85016248695*x^917 \
+-79954038780*x^918-209591894768*x^919-71794807620*x^920-23283477500*x^921 \
++12638220555*x^922-95752230735*x^923-116899891043*x^924-101215036532*x^925 \
+-119610153404*x^926+54021790022*x^927-21789255788*x^928-260168043271*x^929 \
++34842031670*x^930-47465526644*x^931+79209496048*x^932-162752101811*x^933 \
+-175986001160*x^934+48825705322*x^935-136513818801*x^936-52160690022*x^937 \
++72550039192*x^938+94214685087*x^939+198826572346*x^940+57618960407*x^941 \
+-89924832368*x^942+15802881411*x^943-62911879311*x^944+32899449993*x^945 \
++126311503110*x^946+78846277994*x^947+141308676066*x^948+70641162803*x^949 \
++5724759068*x^950-49633865841*x^951+95173521056*x^952+161015858353*x^953 \
+-29202803241*x^954-12952363057*x^955+133465863039*x^956-87901324933*x^957 \
++69820941995*x^958+3949578988*x^959-8912902751*x^960-227471782047*x^961 \
+-4215427616*x^962-36853070177*x^963-115632004639*x^964-137399830344*x^965 \
++37813828221*x^966-134999621522*x^967-81129702306*x^968+2906545160*x^969 \
++183426496219*x^970-58439170144*x^971-77898139208*x^972+27989592415*x^973 \
+-114857219664*x^974-45221435974*x^975-39064281171*x^976-144100939667*x^977 \
++96900598155*x^978-9683692867*x^979+32505144597*x^980+75767337062*x^981 \
++1732485201*x^982+94598116663*x^983-104431472515*x^984+45112579763*x^985 \
+-8325398155*x^986-25719591452*x^987+137274743203*x^988+63077282203*x^989 \
++49611802496*x^990-56530688200*x^991-187825062699*x^992+63000663541*x^993 \
++60988168565*x^994-38033047686*x^995+130178588597*x^996+38679439189*x^997 \
++32500163168*x^998+252301658883*x^999-2212947761*x^1000+85808058970*x^1034 \
+-19483972835*x^1035-41683691103*x^1036+87145067951*x^1037-137328803807*x^1038 \
++73968879794*x^1039+36957534556*x^1040+130660430707*x^1041-166476549509*x^1042 \
++107108386321*x^1043+22690853232*x^1044-107648941612*x^1045-864971871*x^1046 \
+-26346541667*x^1047+10871561131*x^1048+97767553492*x^1049-32532248732*x^1050 \
+-1904971938*x^1051-103073957349*x^1052+86313670653*x^1053+62536836*x^1054 \
+-42832050487*x^1055+121155288006*x^1056+26990131150*x^1057-214613212658*x^1058 \
++105777147715*x^1059+36621520780*x^1060+132811335476*x^1061+103729451809*x^1062 \
+-38953804569*x^1063-92616845436*x^1064-16510771977*x^1065+58930939417*x^1066 \
++37085549174*x^1067+24888041169*x^1068-66607238646*x^1069+124192560702*x^1070 \
+-68000929614*x^1071+81195252365*x^1072+125144994277*x^1073-237062572076*x^1074 \
++53610096124*x^1075+225331588922*x^1076-17707032826*x^1077-89973693921*x^1078 \
++19974317710*x^1079+102021238351*x^1080-93050149638*x^1081-98539649902*x^1082 \
+-94653473795*x^1083-44306474118*x^1084+38414544973*x^1085+135628798013*x^1086 \
+-70487053525*x^1087-72092697500*x^1088-192271505385*x^1089-62340659589*x^1090 \
++29834574943*x^1091-22322653140*x^1092-34947157570*x^1093-24287759319*x^1094 \
+-47068473067*x^1095+154054328835*x^1096+164245063199*x^1097-51273349848*x^1098 \
+-196203282068*x^1099-24096070070*x^1100-99584984772*x^1101+98129847697*x^1102 \
+-65702953785*x^1103-10789632775*x^1104+44241978999*x^1105+37558102317*x^1106 \
+-9505736359*x^1107-25199280665*x^1108+74235442860*x^1109-54694524996*x^1110 \
++2264402295*x^1111-128996845643*x^1112-71285266617*x^1113+67661071648*x^1114 \
+-54492210583*x^1115+22513724859*x^1116+34033473659*x^1117+43758233629*x^1118 \
+-41516781021*x^1119-42784639112*x^1120+123644068072*x^1121-14247218617*x^1122 \
++83808200085*x^1123-183298893778*x^1124-46735100971*x^1125-62031928641*x^1126 \
+-99474744881*x^1127+17800004552*x^1128+106525151324*x^1129-251246407755*x^1130 \
+-25580077568*x^1131-81843377333*x^1132+26788118746*x^1133+19182872780*x^1134 \
+-59925937362*x^1135-50058300773*x^1136-101822550837*x^1137+657933280*x^1138 \
++19564861148*x^1139+35046428744*x^1140+2682475585*x^1141-56992102077*x^1142 \
++35860931273*x^1143+203789134219*x^1144-6727336873*x^1145-109903742856*x^1146 \
++47719560439*x^1147+13527975161*x^1148+98260043934*x^1149-58366673275*x^1150 \
+-130127164351*x^1151+83455071177*x^1152-68823162825*x^1153-60225615746*x^1154 \
+-74042831871*x^1155-12014905342*x^1156+23388731515*x^1157-8626013014*x^1158 \
++21953195679*x^1159-155980220910*x^1160-217972125487*x^1161+89682346870*x^1162 \
+-37658668031*x^1163+58027967881*x^1164-90378430633*x^1165-43341202030*x^1166 \
++16523493943*x^1167-18906640960*x^1168+212117365642*x^1169-33986370441*x^1170 \
++45185768856*x^1171+4763319487*x^1172+1371747234*x^1173+148876972098*x^1174 \
++95191837796*x^1175-123809421852*x^1176+79843098120*x^1177-41267372840*x^1178 \
+-121155059136*x^1179-65482206391*x^1180-79113584784*x^1181+11116916638*x^1182 \
+-92738566955*x^1183+3388410239*x^1184+19005832198*x^1185+66751715230*x^1186 \
+-96920966455*x^1187-184353824811*x^1188+29600147939*x^1189-36474471319*x^1190 \
+-75094557509*x^1191-55155813058*x^1192-139796362527*x^1193-36990042600*x^1194 \
+-149308311610*x^1195 \
+");
+
+static const std::string r2_srep("\
+-12298243395*x^426-33246261919*x^425+14881216216*x^424+100717315398*x^423 \
++32435341799*x^422+11306102069*x^421-42857343048*x^420-23027068074*x^419 \
+-121525059139*x^418+41062828633*x^417-9120088623*x^416+38127915034*x^415 \
+-53332525642*x^414+10667345234*x^47+20250868505*x^46+28797169308*x^45 \
+-43235989359*x^174+38758957270*x^173-29243855534*x^172-46185370245*x^171 \
+-47223973616*x^170-10368178271*x^169-10557528292*x^192+37487979771*x^191 \
+-16245699850*x^190-55729045478*x^189+36012407938*x^188+72614386131*x^187 \
+-15204240841*x^24-8711949900*x^23+14257174071*x^22+56377120052*x^333 \
++14839742003*x^332-38325417931*x^331+54176364398*x^330-53620700530*x^329 \
++17198633981*x^328-15450486288*x^327+15372974977*x^326+5921781285*x^325 \
++81501682291*x^324-66626158040*x^323-20609502025*x^322-109523674165*x^321 \
++56875705806*x^320-23244792061*x^113-19309284277*x^112-38916326672*x^111 \
++44091306530*x^110-34827830974*x^109+32699097269*x^108-72721416508*x^107 \
++17265636833*x^106-36617312032*x^105-41573561571*x^104+12279258834*x^114 \
++82436036606*x^347-31261753091*x^346-44500371183*x^345-125274002688*x^344 \
+-31133631871*x^343+128460249050*x^342+100179005762*x^341-114828839354*x^340 \
++108064336275*x^339+90994968967*x^338-44508032271*x^337+85772561126*x^336 \
+-14871801916*x^335-21281913217*x^334+17047025764*x^477-26275017578*x^476 \
++101182365586*x^475+88231498193*x^474-59806242426*x^473+113427095614*x^472 \
++116163017856*x^471+53708041635*x^470-154328984869*x^469+56803301458*x^468 \
+-35861674205*x^467-88315900409*x^466-33792693422*x^465-132786811376*x^464 \
+-109585745531*x^450+37453216778*x^449+2927086149*x^448-59663587909*x^447 \
+-99229589433*x^446+22434345521*x^445+3804407873*x^444-22843316212*x^443 \
++15023409723*x^442+79744521756*x^441-89156003460*x^440-62409603681*x^439 \
+-22865453841*x^438-62845550343*x^451-10075612299*x^373+90241752514*x^372 \
++3172648684*x^371-64532174127*x^370+72446697772*x^369-44304010100*x^368 \
+-94564984737*x^367-19761536748*x^366+26376102015*x^365-158229005056*x^364 \
+-62154676691*x^363-40346077174*x^362-33481542412*x^361+13571997673*x^28 \
++8161213787*x^27+1023845397*x^26-16720514075*x^25-2383844588*x^44 \
++8356875255*x^43-26827438588*x^42+44585618338*x^399+37434341256*x^398 \
++48503836694*x^397+64340759602*x^396+70497118845*x^395+58332730505*x^394 \
++37917909552*x^393-17951385993*x^392-72126324042*x^391+83367616252*x^390 \
++54914454358*x^389-80690399086*x^388+3788723413*x^387+6657597500*x^50 \
+-27587838729*x^49-11015114987*x^48-62834670333*x^202+14506585098*x^201 \
++6123240614*x^200-23983987723*x^199-8895963188*x^198+74318166429*x^197 \
+-59835752920*x^196-29296586194*x^195-28410809765*x^194-57005146105*x^193 \
+-58918383547*x^203+10630344160*x^1196-18556978555*x^1197-164043335170*x^1198 \
+-87839930075*x^1199+4152300286*x^1200+99517087469*x^1201-73797793712*x^1202 \
+-25260491411*x^1203+76114220378*x^1204+40133672638*x^1205-230680916222*x^1206 \
++219293086650*x^1207+3638620539*x^1208-6652308741*x^1209+12775249723*x^1210 \
++3251379936*x^1211-75721519451*x^1212-163406006228*x^1213-165491770209*x^1214 \
++46054734359*x^1215-741970731*x^1216+99721318208*x^1217-48283084345*x^1218 \
+-201279475291*x^1219+57418480238*x^1220-134680981668*x^1221+34536313632*x^1222 \
++10430882187*x^1223+70914285740*x^1224-108730001945*x^1225+184561606957*x^1226 \
+-50600427283*x^1227+27438909544*x^1228+3869947176*x^1229-99212395993*x^1230 \
+-122356266132*x^1231+190721719645*x^1232+10663679376*x^1233+171017341569*x^1234 \
+-61192181164*x^1235+100411947630*x^1236-85397438998*x^1237+106275225374*x^1238 \
++3419807107*x^1239+36976923465*x^1240+57882249834*x^1241-107227057330*x^1242 \
+-45892223123*x^1243+39898058432*x^1244-25685770417*x^1245-15437084634*x^1246 \
++79678067292*x^1247+53459571441*x^1248-9772387681*x^1249-8634944328*x^1250 \
+-103233454566*x^1251+80654434021*x^1252-30348898500*x^1253+31622090094*x^1254 \
+-59747674770*x^1255+50418039889*x^1256-131270697937*x^1257+73386317355*x^1258 \
+-33268294896*x^1259+220123546149*x^1260-47814110905*x^1261+31648485555*x^1262 \
++50736345265*x^1263+12957979612*x^1264-12352680940*x^1265+8954284112*x^1266 \
++4405063605*x^1267-66479748368*x^1268+98898741778*x^1269+137071640600*x^1270 \
+-13677831086*x^1271-32633620324*x^1272+100644420930*x^1273-101006678220*x^1274 \
++57929446438*x^1275-46456850356*x^1276+119383219795*x^1277-68889453480*x^1279 \
++27403268808*x^1278-9452745528*x^500+12505989143*x^499-88746500517*x^498 \
++36522434736*x^497+105148848765*x^496-31099548526*x^495-29920704228*x^494 \
+-84722298862*x^493-14005980691*x^492+18668364817*x^491+2284051770*x \
+-33852801349*x^437+24746815214*x^436+14725842338*x^435+71589114295*x^434 \
++95344800351*x^433-103870206918*x^432-2292807366*x^431+122702353734*x^430 \
+-39127758310*x^429+71141989765*x^428+91775420843*x^427+29584402698*x^281 \
++34879992632*x^280-7929148263*x^279-62511168551*x^278+75173708697*x^277 \
++2210745302*x^276+47365447862*x^275+34770067078*x^274+15629493834*x^273 \
++123387217284*x^272-83879189754*x^271+90474389247*x^270+20723731518*x^269 \
+-13648232822*x^268+135048430531*x^360+9779963494*x^359-79763997627*x^358 \
++80167613186*x^357+59427033891*x^356-56617078458*x^355+70792836473*x^354 \
+-42721386790*x^353+18854232633*x^352-27799012434*x^351-7540762106*x^350 \
++51000825517*x^349-61789935211*x^348+6364435339*x^21-8596138092*x^20 \
+-13862640657*x^19+12972909594*x^18+25640262624*x^168+73106364011*x^167 \
++50996630476*x^166-46522919587*x^165-2318061818*x^164-46439765345*x^163 \
++3018635654*x^162-51033321714*x^161-54420823241*x^160-25754428117*x^159 \
+-20957251811*x^158-56979883142*x^157-113069491386*x^156+78310111278*x^155 \
++8791974299*x^41-20484038584*x^39+65329554945*x^186+63604634904*x^185 \
++67548191757*x^184-46287362343*x^183+86853548227*x^182-78112812263*x^181 \
+-39054030995*x^180+70082669285*x^179+4991564873*x^178+35132330683*x^177 \
++5220672794*x^176+27538233543*x^175+45604753836*x^463-72517449336*x^462 \
+-172648125640*x^461+77371325704*x^460+103318563842*x^459-47970420952*x^458 \
+-173692529*x^457-16267041286*x^456-39608578784*x^455-44014507517*x^454 \
+-40698179828*x^453+64997452090*x^452-16621185638*x^10-5839518904*x^9 \
++7779380684*x^8+7805287316*x^7-931618705*x^154+77399210009*x^153 \
+-12286080400*x^152-15618003169*x^151-44221287122*x^150+44169698801*x^149 \
+-77234959789*x^148+19578529715*x^147-2795707215*x^146-11375091988*x^145 \
++21793365806*x^144+31454951276*x^143+6091116508*x^142+7402060559*x^3 \
+-15638332394*x^2-16846517099*x^294-6573457577*x^293-36345200919*x^292 \
++104115784551*x^291-32337698003*x^290+17593183564*x^289+90879035663*x^288 \
++124574515327*x^287-2750093470*x^286+74836130434*x^285+28760033840*x^284 \
++76932285409*x^283+70510978158*x^282+2131234223*x^217-47160319189*x^216 \
+-4500367537*x^215-10694873972*x^214-13052396086*x^213-119312329735*x^212 \
+-12249530649*x^211-58377372451*x^210+61312423521*x^209-62735937652*x^208 \
+-18739775224*x^207+19541226826*x^206+52687803759*x^205-48487381888*x^204 \
++49838817064*x^490+103336940622*x^489-114398006939*x^488+40164473234*x^487 \
++22188458973*x^486+102241404959*x^485-132777915090*x^484+77723628319*x^483 \
++29176152754*x^482+116603267994*x^481-14526032223*x^480-45775708833*x^479 \
+-267391385*x^478+22100788607*x^17-11428840425*x^16-954947579*x^15 \
++6057723695*x^14+63494717499*x^1364-10349348333*x^1365-11354317920*x^1366 \
++90668431927*x^1367-92110654585*x^1368+231933389918*x^1369+19189606214*x^1370 \
++37836457811*x^1371-41835147412*x^1372-64829306413*x^1373-99539521475*x^1374 \
++14786388671*x^1375+213836900645*x^1376+22624850100*x^1377+4395435896*x^1378 \
+-93161939597*x^1379+89789272863*x^1380-63671202085*x^1381-18208723976*x^1382 \
++102193294445*x^1383+42149570567*x^1384-57427709585*x^1385-101096944615*x^1386 \
++62581117784*x^1387-58899807423*x^1388+115177108233*x^1389-19168792202*x^1390 \
++38132618085*x^1391-50907816003*x^1392-23737421785*x^1393-65750929733*x^1394 \
+-8568961669*x^1395-37662793882*x^1396+101039333860*x^1397-47341688773*x^1398 \
++9724870415*x^1399-15791202897*x^1400+13843025496*x^1401-128893801207*x^1402 \
+-32183995709*x^1403-139023659805*x^1404-42684304557*x^1405-14610977549*x^1406 \
++57122422992*x^1407+128491635951*x^1408+3614885611*x^1409-36404761221*x^1410 \
+-112811070097*x^1411+153443879256*x^1412+164794102332*x^1413+134470678635*x^1414 \
+-88690316169*x^1415-74374605027*x^1416-90950545612*x^1417-104814317576*x^1418 \
+-177228350594*x^1419-11835540964*x^1420+20873445658*x^1421-195114255686*x^1422 \
++87306904630*x^1423+59376189861*x^1424-117251826188*x^1425+57626371798*x^1426 \
++17253066619*x^1427-65717447508*x^1428+38123913202*x^1429+64257781929*x^1430 \
+-110886945374*x^1431+70757769597*x^1432+10322610698*x^1433-48134918817*x^1434 \
+-56503764527*x^1435+117474984824*x^1436+33765540181*x^1437+107731007106*x^1438 \
++96338855448*x^1439+8934843329*x^1440-30541434613*x^1441+72531211591*x^1442 \
++30197093191*x^1443+72368177095*x^1444-76451969600*x^1445-92672018447*x^1446 \
+-1744298703*x^51+26882297486*x^52-18398383509*x^53+3005642217*x^54 \
++3593805670*x^55-21740657388*x^56+6314837654*x^57-14388840020*x^58 \
+-48213795147*x^59-11593118081*x^60-1502891403*x^61+37639792348*x^62 \
++4590584128*x^63+62090294921*x^64+31955540056*x^65-8921556943*x^66 \
++21988615968*x^67-23025433031*x^68+38334620159*x^69+19779920702*x^70 \
+-16146115882*x^71+18104295332*x^72-20379887728*x^73+28122778533*x^74 \
+-22233760331*x^75+2601350324*x^76-23301155844*x^77+27813631959*x^78 \
+-37895927213*x^79-2648750595*x^80+24636697824*x^81+17895391597*x^82 \
++8568029391*x^83+36393556404*x^84+17452747156*x^85-49612336092*x^86 \
+-10886997637*x^87-11130667420*x^88+29158789170*x^89-5400236199*x^90 \
++77812065577*x^91-49643768511*x^92-13107221267*x^93-52311659384*x^94 \
++34469782323*x^95-35571894501*x^96+53972502564*x^97+30760824828*x^98 \
++100388019377*x^99+97252215701*x^386-116099602858*x^385+76103387516*x^384 \
+-11150909008*x^383-43760747755*x^382+30435548717*x^381+105763654230*x^380 \
++62286795532*x^379+76050666216*x^378+37247029295*x^377+2903246935*x^376 \
++17740821225*x^375-67645627457*x^374+1068927231*x^40-21411907744*x^38 \
++30329881614*x^37-30031713761*x^36+18856879565*x^35+28958849017*x^308 \
+-11122674865*x^307+16515984422*x^306-44335554221*x^305+54476123312*x^304 \
+-20904234081*x^303+61391311771*x^302-16775061346*x^301+3210400498*x^300 \
++56658482015*x^299-105337656712*x^298+33759085293*x^297+61939776273*x^296 \
+-41177733805*x^295-59566196142*x^141+18476269572*x^140-23088141060*x^139 \
+-11801865656*x^138+30847010853*x^137+21929475729*x^136+31313930007*x^135 \
+-2990246614*x^134-14929686587*x^133+38476911951*x^132-46205516843*x^131 \
+-13904775963*x^130+10524952653*x^129+40066745986*x^128+1970323384*x^244 \
++1446777973*x^243+2391572443*x^242-89493321216*x^241+39101186256*x^240 \
++98222226415*x^239-9239552468*x^238+5916325669*x^237+36005795144*x^236 \
++45537168101*x^235-40607567937*x^234-3750879706*x^233+57951296798*x^232 \
+-7755123318*x^413-37469436811*x^412+70016616413*x^411-42829701116*x^410 \
+-40550876166*x^409-36147696900*x^408+65981234023*x^407-122609177512*x^406 \
+-32890978471*x^405+89421010177*x^404+24395518617*x^403+97415643004*x^402 \
+-61366468342*x^401-68686837546*x^400-24197772525*x^100-55496272864*x^267 \
++11842466716*x^266+11739104212*x^265+45395994939*x^264-2462010012*x^263 \
+-46901504750*x^262+2194886178*x^261-43818646770*x^260-64456303482*x^259 \
+-42678178437*x^258+16930473337*x^257-79111479558*x^256+55486339504*x^255 \
+-6531034828*x^34+27035707153*x^33-29177734926*x^32-102519500337*x^127 \
+-25120666485*x^126-30579535492*x^125+9392730819*x^124-19261680565*x^123 \
++9092366703*x^122-13808837057*x^121-10767506476*x^120+9387090911*x^119 \
++5861529627*x^118+30570618150*x^117+9821369125*x^116+27953902351*x^115 \
++25585821707*x^102-9147523101*x^101-43069458046*x^103-77197009243*x^254 \
++41768972254*x^253-51107733143*x^252+2179732347*x^251-73246837376*x^250 \
+-76028238883*x^249-15944993585*x^248-122980270638*x^247+29301117006*x^246 \
+-10775309722*x^245+18396353043*x^13-16862760430*x^12+15452547818*x^11 \
+-10527226187*x^319+101533968365*x^318+45962612479*x^317-40854272816*x^316 \
++29357583774*x^315-98334493728*x^314-26844181578*x^313+152535370585*x^312 \
+-48558849904*x^311-65465771182*x^310+48084068810*x^309-798955677*x^31 \
++35715352173*x^30-41114886366*x^29-10576978086*x^6-11825376542*x^5 \
++7286512470*x^4+18388806457*x^1280+161794076352*x^1281-28337710306*x^1282 \
+-17255976845*x^1283-76008915764*x^1284+55400148387*x^1285-60639021891*x^1286 \
+-101066145720*x^1287-123972185159*x^1288+87115039832*x^1289-155574783014*x^1290 \
++23730856463*x^1291+309102172*x^1292-106791492726*x^1293-237381096018*x^1294 \
++28548371390*x^1295-330246556*x^1296-29689811838*x^1297-189254819970*x^1298 \
+-30865123604*x^1299-44582502556*x^1300-111505655799*x^1301-44557592539*x^1302 \
++53733507680*x^1303+20819197021*x^1304+1395361755*x^1305-49184624216*x^1306 \
+-40903280869*x^1307-93317035741*x^1308-28525136465*x^1309+46815641959*x^1310 \
+-37147646401*x^1311-171269226982*x^1312+55545463284*x^1313+26432914392*x^1314 \
++63358274704*x^1315-21229429338*x^1316-128600950288*x^1317-42113338606*x^1318 \
+-140824193885*x^1319-2326798220*x^1320+64192104658*x^1321-51630561209*x^1322 \
+-49498217773*x^1323-90416752098*x^1324+83991720563*x^1325+150608820483*x^1326 \
++65119613397*x^1327+20967841540*x^1328-95934246964*x^1329-177636442910*x^1330 \
+-104683025381*x^1331+46752411240*x^1332-71028555511*x^1333-80536733392*x^1334 \
+-60889544079*x^1335-22450515462*x^1336-61149950566*x^1337-23445736673*x^1338 \
+-50742295044*x^1339+41001013374*x^1340+94763809142*x^1341+77883336357*x^1342 \
+-53873424849*x^1343-85586877816*x^1344+147245896720*x^1345+103273157293*x^1346 \
++49487544766*x^1347-129528420075*x^1348-61945581330*x^1349-76408360080*x^1350 \
++84312569941*x^1351+3005072928*x^1352+21564682198*x^1353-99865781821*x^1354 \
+-96904486038*x^1355-67290910420*x^1356+121809010991*x^1357-201280052*x^1358 \
+-25659166014*x^1359-7854234250*x^1360+83496185253*x^1361-156457302131*x^1363 \
+-130043471771*x^1362-116623034666*x^1447+63340754284*x^1448+29056858824*x^1449 \
+-14463741969*x^1450+101462718016*x^1451-69374438503*x^1452-104332978401*x^1453 \
++14930947674*x^1454+32883271359*x^1455+37930611868*x^1456-16920913941*x^1457 \
+-80230082425*x^1458+46610161083*x^1459+19972507802*x^1460-59510262751*x^1461 \
++10916713060*x^1462+57866464903*x^1463-10394342923*x^1464-90970881156*x^1465 \
++37858629616*x^1466-106679590218*x^1467-24913741790*x^1468+109967614373*x^1469 \
++48890249817*x^1470+1848149679*x^1471-98549032445*x^1472+60720768502*x^1473 \
++137842172780*x^1474+5243491906*x^1475-59750299327*x^1476+45228722812*x^1477 \
++27935880244*x^1478+80537672690*x^1479-20295991643*x^1480-87845315347*x^1481 \
++50218956865*x^1482-38373564442*x^1483-20957663060*x^1484+27711035106*x^1485 \
++95016265056*x^1486+55710516985*x^1487+82619750454*x^1488+110859243542*x^1489 \
++53435806482*x^1490-133528838222*x^1491+158330827120*x^1492-97083117015*x^1493 \
++111387362388*x^1494+85479818296*x^1495-10482105703*x^1496-2572665530*x^1497 \
++133068208484*x^1498+4146821725*x^1499+68330996935*x^1500-28065751920*x^1501 \
++15974361469*x^1502-85929799702*x^1503-28686472019*x^1504+148667781296*x^1505 \
+-10084131821*x^1506-94793837277*x^1507-84791761144*x^1508-63678878999*x^1509 \
++39694015413*x^1510+446659189*x^1511+95377871547*x^1512+9666212199*x^1513 \
++161795671654*x^1514-91000484021*x^1515+145579875230*x^1516+81265093794*x^1517 \
+-998831496*x^1518-128803139300*x^1519+52770776790*x^1520-146403349418*x^1521 \
++32587886089*x^1522-75251805801*x^1523+166805166779*x^1524-57035303250*x^1525 \
++57521577337*x^1526+21285234901*x^1527+3027584246*x^1528+105899112243*x^1529 \
++14781758392*x^1530-22683394179*x^1531-25210689640*x^1532+99935945643*x^1533 \
+-84021930147*x^1534+42259497554*x^1535+45907068922*x^1536+84279071229*x^1537 \
+-29539017121*x^1538+45338942887*x^1539-24806480906*x^1540+87977283203*x^1541 \
++62516484079*x^1542+159450661656*x^1543-23655833088*x^1544-44112269864*x^1545 \
++10606111566*x^1546-8499088313*x^1547+96101127142*x^1548-89377300943*x^1549 \
+-59851591087*x^1550-56214120248*x^1551-157507855204*x^1552-62249119108*x^1553 \
+-85445577597*x^1554-4401721329*x^1555-101536174643*x^1556-58119121629*x^1557 \
+-114925796667*x^1558+48574709630*x^1559-34280314464*x^1560+14766752770*x^1561 \
+-30236783234*x^1562-14509377591*x^1563-209749274080*x^1564-37393636602*x^1565 \
+-59883917907*x^1566+90592372530*x^1567-125327647858*x^1568-144372630004*x^1569 \
++17757782785*x^1570+32530054069*x^1571-103160474054*x^1572+27004259534*x^1573 \
++36592332602*x^1574-49900527049*x^1575+109450983286*x^1576+87454580007*x^1577 \
+-22429929394*x^1578-90955942668*x^1579-52085998619*x^1580+7542444291*x^1581 \
+-129095640958*x^1582-116117273631*x^1583-15362293016*x^1584-75422573875*x^1585 \
++104080240756*x^1586+29567135838*x^1587-85533231646*x^1588-14007407713*x^1589 \
+-72167537141*x^1590+15578436550*x^1591+37099609795*x^1592+5366651746*x^1593 \
+-80006924851*x^1594+21429342288*x^1595+30269096496*x^1596-56303168087*x^1597 \
+-32192045909*x^1598-24090181314*x^1599-91201040971*x^1600-90424483245*x^1601 \
+-41789191466*x^1602+48796472891*x^1603+6667317240*x^1604-20054404612*x^1605 \
++90717205115*x^1606-45574268144*x^1607+96577965375*x^1608-84937868700*x^1609 \
++15254114769*x^1610-85324218128*x^1611-36100598429*x^1612+59140120545*x^1613 \
++28348387068*x^1614-25936772983*x^1615+14152778910*x^1616+93013422289*x^1617 \
++5325703012*x^1618+5299012928*x^1619-114456880810*x^1620+24631873118*x^1621 \
++71187736583*x^1622+44454005446*x^1623-65564007677*x^1624-18686868545*x^1625 \
+-38320190467*x^1626-11068635951*x^1627+38623912436*x^1628+128145741026*x^1629 \
+-47444447640*x^1630-69911372525*x^1631+73982054085*x^1632+67625321661*x^1633 \
+-43780921866*x^1634+42499209425*x^1635+112438203531*x^1636-29637261064*x^1637 \
++29717059942*x^1638+73064218527*x^1639+78354730927*x^1640-23583391619*x^1641 \
++51406219011*x^1642-49806860311*x^1643-22338703465*x^1644-37561475541*x^1645 \
++87296115958*x^1646-25055231815*x^1647-26132634595*x^1648+51665990532*x^1649 \
+-172652705651*x^1650-104663637871*x^1651+11737785837*x^1652+47284031389*x^1653 \
+-125440895392*x^1654-42350923347*x^1655+22245934791*x^1656+50062160311*x^1657 \
++26993180274*x^1658+93916764416*x^1659+17723933407*x^1660-7709629970*x^1661 \
+-10925189482*x^1662-87095313733*x^1663-24424934930*x^1664+138103101710*x^1665 \
++9725815469*x^1666-95975878178*x^1667+111443666516*x^1668-96028904366*x^1669 \
+-61862950969*x^1670+20517212289*x^1671+85165260123*x^1672-168755515234*x^1673 \
+-45383540058*x^1674-14246010186*x^1675+5321412602*x^1676-97837120785*x^1677 \
++63051474234*x^1678-11622330015*x^1679-6813440517*x^1680-158000336988*x^1681 \
+-61045444490*x^1682-16113615735*x^1683+42790018648*x^1684-55289921194*x^1685 \
+-55354435735*x^1686+7663298003*x^1687-75007919562*x^1688+155177776611*x^1689 \
++58476171975*x^1690+2632834366*x^1691+18899732593*x^1692+26511602610*x^1693 \
++105064498377*x^1694+61127828457*x^1695+6326945505-959052659*x^1696 \
+-73433944554*x^1697+17547912794*x^1698-54354897407*x^1699-58838742934*x^1700 \
++94679918763*x^1701+42039556955*x^1702-130770900613*x^1703-54147770285*x^1704 \
++31508315675*x^1705+18763864996*x^1706-22723355698*x^1707+23015897095*x^1708 \
+-73252327021*x^1709-66778379186*x^1710-33519375139*x^1711+8936095442*x^1712 \
+-54146328075*x^1713+3330235304*x^1714-19390098322*x^1715+48324815570*x^1716 \
+-22141912841*x^1717-37722070562*x^1718+26839695493*x^1719+76090925762*x^1720 \
++88225567190*x^1721+47256653156*x^1722+30627370862*x^1723-63714216871*x^1724 \
+-18205624350*x^1725+59802680427*x^1726+53057549555*x^1727+14174441194*x^1728 \
++75765825464*x^1729+32963108753*x^1730-12499134875*x^1731+27273333256*x^1732 \
++9234764883*x^1733-22990113287*x^1734-30534003983*x^1735+5390988324*x^1736 \
++51965774003*x^1737+36123492542*x^1738+23495532313*x^1739+24538679309*x^1740 \
++48466824303*x^1741+25810926063*x^1742-12309341239*x^1743+71863273789*x^1744 \
++27521706644*x^1745+51703817418*x^1746+31047946433*x^1747-17225947158*x^1748 \
++113616875883*x^1749+48119672693*x^1750+32640697894*x^1751+5838339810*x^1752 \
++35494583363*x^1753+35996883701*x^1754+64454412007*x^1755+67672887170*x^1756 \
++24852637977*x^1757+39599198948*x^1758+100612424867*x^1759+61066112206*x^1760 \
+-47730662897*x^1761-75220323201*x^1762-7637941778*x^1763-13208589131*x^1764 \
++55098518018*x^1765+102817175067*x^1766-46374680712*x^1767+7922233525*x^1768 \
++12354251760*x^1769-17497361436*x^1770-59990480700*x^1771-2475917864*x^1772 \
+-53137166580*x^1773-65697709393*x^1774+8377278120*x^1775-39634303915*x^1776 \
++27494498566*x^1777-6623951999*x^1778-2860049814*x^1779+45174937843*x^1780 \
++19218150182*x^1781+31009745617*x^1782-57914680622*x^1783-93027860213*x^1784 \
+-32466824482*x^1785-87664162092*x^1786-40426743792*x^1787+22191823745*x^1788 \
+-4385019263*x^1789+40619736886*x^1790-59537851776*x^1791+29407007656*x^1792 \
++25083658856*x^1793+16109214404*x^1794-2628597691*x^1795+90593408292*x^1796 \
++73529865188*x^1797+69070203891*x^1798-22715686937*x^1799-47275795580*x^1800 \
++24349081011*x^1801+37519310529*x^1802-30466082586*x^1803+16849925300*x^1804 \
++52411382847*x^1805-49758979601*x^1806+15679528686*x^1807+76574645775*x^1808 \
++46732065431*x^1809-67248446805*x^1810-41574164595*x^1811-45948531070*x^1812 \
+-91525781500*x^1813-98636828248*x^1814-62341009634*x^1815-106737947357*x^1816 \
++5944715919*x^1817+27959962466*x^1818-18281456838*x^1819+43419080798*x^1820 \
++8238895067*x^1821+57794363933*x^1822-3885695019*x^1823-16620769333*x^1824 \
++20617426129*x^1825+31772378717*x^1826-77659311932*x^1827-2614944050*x^1828 \
+-53541082178*x^1829+47415264521*x^1830+19297049465*x^1831-50744052035*x^1832 \
+-14699341644*x^1833-20185897392*x^1834+11304473461*x^1835-8417793205*x^1836 \
++42208138630*x^1837+40010050281*x^1838+8580892377*x^1839+744941642*x^1840 \
++13372194202*x^1841+14518343301*x^1842-12610498299*x^1843-19180304452*x^1844 \
++25853574415*x^1845-39663241273*x^1846-51735769060*x^1847+28701486795*x^1848 \
++34631767452*x^1849+30665603097*x^1850-31737130343*x^1851-11359635277*x^1852 \
+-53356680586*x^1853+34804124525*x^1854-29905007001*x^1855-16020507432*x^1856 \
+-11717124778*x^1857+34454112900*x^1858-29236460046*x^1859-27386914094*x^1860 \
++48525768547*x^1861+28213658802*x^1862+8947787875*x^1863+57150247624*x^1864 \
++8348708750*x^1865+8808792586*x^1866+25213586793*x^1867+56635111548*x^1868 \
+-9337443075*x^1869+21165923060*x^1870+18588461938*x^1871+30858411086*x^1872 \
++3419917365*x^1873+77549765533*x^1874-7998236281*x^1875-19374386693*x^1876 \
+-35418234974*x^1877+38577714149*x^1878+15358209695*x^1879+34405664552*x^1880 \
++4306560036*x^1881-60158002*x^1882-22204346895*x^1883+9575772188*x^1884 \
++38275674214*x^1885+76935802774*x^1886-8688725759*x^1887+4641950168*x^1888 \
++26752524534*x^1889+11976777389*x^1890+47203277801*x^1891+34427926908*x^1892 \
+-10684178562*x^1893+11127497799*x^1894+42062545265*x^1895-53825407401*x^1896 \
++4989669095*x^1897+55453648034*x^1898+20983145705*x^1899-14958562665*x^1900 \
++8355251080*x^1901+24031795321*x^1902-29739158452*x^1903+21980289986*x^1904 \
+-17205919827*x^1905+7346027701*x^1906+11569319363*x^1907+13614834645*x^1908 \
+-35975188961*x^1909+46603311768*x^1910+30120456597*x^1911-8478220385*x^1912 \
+-56827863625*x^1913+30296155243*x^1914-36287579039*x^1915-24672161998*x^1916 \
++24469720179*x^1917-35478863962*x^1918-54234895242*x^1919-66565864759*x^1920 \
+-40947685264*x^1921-19971682562*x^1922+2385658644*x^1923-29296192350*x^1924 \
++1423940493*x^1925-10597630015*x^1926-20525914191*x^1927+2929730657*x^1928 \
++16463714177*x^1929+12681038897*x^1930-19145947289*x^1931-13466142524*x^1932 \
+-20222110298*x^1933-19251726839*x^1934-37002885076*x^1935-7802339043*x^1936 \
+-47523780291*x^1937+8321382372*x^1938+13992616571*x^1939+26068955056*x^1940 \
+-8086679459*x^1941+286270153*x^1942-2705340674*x^1943+255535813*x^1944 \
+-34493130463*x^1945-8359391510*x^1946+32075412687*x^1947+3157786517*x^1948 \
+-5134583707*x^1949+20294329376*x^1950-5719300052*x^1951-3610361046*x^1952 \
++19714585416*x^1953+31029310975*x^1954+6525668645*x^1955-17551589763*x^1956 \
++6326740399*x^1957+4078698282*x^1958-19314799201*x^1959-3581682397*x^1960 \
+-18696461472*x^1961-45787235498*x^1962-39343868284*x^1963-25552626240*x^1964 \
+-47676215824*x^1965-6535189504*x^1966-20440671693*x^1967-27850667563*x^1968 \
+-2284895619*x^1969+12350652323*x^1970+10616601145*x^1971+34114023739*x^1972 \
++31816702425*x^1973+26974067096*x^1974+29215489795*x^1975+23576334729*x^1976 \
++34095198361*x^1977+21863597299*x^1978+23856960019*x^1979+25344212108*x^1980 \
++15345894525*x^1981+2452061679*x^1982-7870355413*x^1983-19430775349*x^1984 \
+-11433900994*x^1985-14519775288*x^1986-12549755734*x^1987+1850026837*x^1988 \
+-7355516784*x^1989-5810824702*x^1990+512283203*x^1991-246928108*x^1992 \
++2728608*x^1993-1528915243*x^1994-3274467887*x^1995+111483392*x^1996 \
++204389413*x^1997-1867708432*x^1998+274767516*x^1999-407080161*x^2000 \
++9253740790*x^231+13104137650*x^230+34300405699*x^229-8555184450*x^228 \
++43336832551*x^227-56284596497*x^226-25147990866*x^225+60729543880*x^224 \
+-33106841378*x^223+6879339359*x^222+66221993617*x^221+78495102233*x^220 \
++59060525921*x^219-45581015054*x^218-32695677520*x^1001+5858837086*x^1002 \
++11101676909*x^1003+54178409615*x^1004-102677317737*x^1005+49344188139*x^1006 \
+-51959708001*x^1007+105417515933*x^1008+46478254597*x^1009+128535749044*x^1010 \
+-94364594821*x^1011+33413669637*x^1012-45620718356*x^1013-100703155988*x^1014 \
++182697936406*x^1015-4328691289*x^1016-10572913320*x^1017+140226913701*x^1018 \
++53616253797*x^1019+20429764848*x^1020-12296179015*x^1021-28995067707*x^1022 \
++60058804070*x^1023+946107762*x^1024-123343657863*x^1025-119844451014*x^1026 \
+-25586132061*x^1027+228044249670*x^1028-78424973402*x^1029+15544042868*x^1030 \
+-156169819256*x^1031+133624252178*x^1032+134097573058*x^1033+10968367799*x^501 \
+-18881216863*x^502+33402630296*x^503+76127322783*x^504+159555881935*x^505 \
+-49965731760*x^506+115209281005*x^507-76077580384*x^508-78116158821*x^509 \
++117550323107*x^510+26979777455*x^511-155912045504*x^512+103479368669*x^513 \
++57621022564*x^514-13401704476*x^515+45474459041*x^516-96550433410*x^517 \
+-33742521550*x^518-151057690994*x^519-56249009463*x^520-18145952124*x^521 \
+-34496211522*x^522-37529073802*x^523-60399419461*x^524+76579518486*x^525 \
++9508878552*x^526-135885189822*x^527+46048035428*x^528-30487445718*x^529 \
+-109948921884*x^530+70391869697*x^531-98966950587*x^532-44645403425*x^533 \
++5885105007*x^534-70206621840*x^535+132109982423*x^536+5785503183*x^537 \
++43805605951*x^538-212103940095*x^539+2924498758*x^540-35677811233*x^541 \
++95766897237*x^542+77061233199*x^543+150823590075*x^544+51669758591*x^545 \
++16098118870*x^546+62776931078*x^547+37921177915*x^548-72391602956*x^549 \
++103759653977*x^550+118007269422*x^551+74135478514*x^552+37851770609*x^553 \
+-27151771323*x^554+135262774533*x^555-148721705333*x^556-57897207026*x^557 \
++213375944794*x^558+2012721198*x^559-180168011470*x^560-208947464842*x^561 \
++5976005785*x^562-122773099578*x^563-66719865278*x^564-44726841245*x^565 \
++48311917869*x^566-183072526346*x^567+76608052065*x^568-103253918977*x^569 \
+-105765112928*x^570-109313878463*x^571-83146150392*x^572-79800305957*x^573 \
++12469814261*x^574-57834727129*x^575+31234388882*x^576-29973254616*x^577 \
+-27479417998*x^578+85884874224*x^579-149843470993*x^580+139085218821*x^581 \
++36488567498*x^582-140867295982*x^583-81036140847*x^584-14734953476*x^585 \
++68113949406*x^586+76145793396*x^587+44037201888*x^588-58467597905*x^589 \
++57456355271*x^590-46396703755*x^591+218686220932*x^592-103656661497*x^593 \
++27260907290*x^594-74244694267*x^595+75519577923*x^596-31958208950*x^597 \
++56019215687*x^598-17061668425*x^599+105139109203*x^600+77415602565*x^601 \
+-108954493245*x^602+85140330302*x^603-79572683246*x^604+114764444877*x^605 \
+-45484289011*x^606-91760986422*x^607-94315977182*x^608+878602400*x^609 \
++16704751100*x^610-45166613346*x^611-79452542049*x^612-64363757544*x^613 \
+-82091593450*x^614-66991607227*x^615-33107406460*x^616-84308321740*x^617 \
++41248072469*x^618+151606030721*x^619-20963307199*x^620-76780636743*x^621 \
+-60506307359*x^622-65639868144*x^623+77307497014*x^624-120629395172*x^625 \
+-58920551146*x^626-72152119854*x^627-13784023413*x^628-29723302902*x^629 \
+-59103450945*x^630-42263718431*x^631+90530664298*x^632+2162738628*x^633 \
+-58826755300*x^634-28237680670*x^635-104924312614*x^636+100208929059*x^637 \
+-70312120136*x^638+77455696272*x^639-63510025164*x^640+13962573264*x^641 \
++51758925013*x^642-19656476291*x^643-90116387134*x^644+41548179409*x^645 \
++167043690167*x^646-13106079927*x^647-12639563298*x^648-31532919796*x^649 \
+-81943547371*x^650+2659468451*x^651-72797097105*x^652-17552611729*x^653 \
+-68871406970*x^654-78926317536*x^655-51871988682*x^656+10073360063*x^657 \
++117133535357*x^658-39610605270*x^659-124819309047*x^660+186332751132*x^661 \
+-5951967439*x^662-48169310072*x^663+20768672093*x^664-91409373144*x^665 \
++19524139200*x^666+127619304757*x^667-98128438655*x^668-4904617268*x^669 \
+-57989017792*x^670+73729690684*x^671+89333834959*x^672+99716011285*x^673 \
++103503472300*x^674-84453399907*x^675+8258389068*x^676-9450340905*x^677 \
++7822296540*x^678-78821470413*x^679-83133235896*x^680-80330275908*x^681 \
++22914959031*x^682-152091289333*x^683-36005600658*x^684+127080114963*x^685 \
+-68043079905*x^686+49836751263*x^687-51469985682*x^688-6616590590*x^689 \
+-69655808220*x^690+115173723007*x^691-45634640258*x^692-21385988093*x^693 \
+-300962360849*x^694+58893380816*x^695+62393657508*x^696+48036552547*x^697 \
+-134579469584*x^698+140621673048*x^699+7912276958*x^700-21132961576*x^701 \
++65127930334*x^702+131378452178*x^703-15011857309*x^704+30180971097*x^705 \
+-80521071636*x^706-11613585664*x^707+7782812135*x^708-19836259198*x^709 \
++76867406939*x^710-192663376*x^711+115884985152*x^712-200807422928*x^713 \
++24839446685*x^714+118564095011*x^715-16582885964*x^716+8953308047*x^717 \
++2612524258*x^718+75668312401*x^719-103182809527*x^720+51780158587*x^721 \
++161189143724*x^722-16275946972*x^723-181335131597*x^724-182505534903*x^725 \
++59091110661*x^726-64607113177*x^727-2296140395*x^728-68790652631*x^729 \
+-103730693290*x^730-207388846791*x^731-14552975373*x^732-62805658879*x^733 \
++18781202924*x^734-128986271973*x^735+31639320741*x^736-83104477502*x^737 \
+-9885651183*x^738+137707546857*x^739+97735595675*x^740+112807494432*x^741 \
++68402438627*x^742+35895157342*x^743+12428002821*x^744-72588844028*x^745 \
+-79799800966*x^746+42629111745*x^747+195740197570*x^748-39606216107*x^749 \
++13892037724*x^750-3213907310*x^751+143251925064*x^752+83337773036*x^753 \
++55289116209*x^754+111071736278*x^755+47114731432*x^756+46017675542*x^757 \
++106534303190*x^758+65005886163*x^759-75480068719*x^760-32231292099*x^761 \
+-187585046063*x^762+106574561203*x^763-46410997680*x^764+132837442879*x^765 \
++78280061721*x^766+7680405380*x^767-42516357685*x^768+128713753555*x^769 \
+-9029278097*x^770+47246046167*x^771+187701638909*x^772+19911051190*x^773 \
+-30984914944*x^774-2484314352*x^775+7170418460*x^776-1284643600*x^777 \
++89116539289*x^778-20001530400*x^779-90466507480*x^780-74012539600*x^781 \
++57274308958*x^782-24727523350*x^783+128683569525*x^784-103054717034*x^785 \
+-142511386724*x^786+73690538474*x^787-89229469699*x^788-74963796774*x^789 \
++71970802266*x^790+133757287893*x^791+187098918939*x^792+132291921645*x^793 \
++107833456866*x^794+64137348734*x^795-45340423408*x^796-20368785860*x^797 \
+-35482501796*x^798+104548164657*x^799-225828818492*x^800+83058094351*x^801 \
++197238886430*x^802+71570704333*x^803-14855122348*x^804-11330859909*x^805 \
++73194349886*x^806-85465641976*x^807+195052602572*x^808+181032739569*x^809 \
++15148060162*x^810-148378949751*x^811+51042083256*x^812-69786758*x^813 \
++97712314954*x^814-101202436100*x^815-98106306738*x^816-80219160719*x^817 \
+-46257669081*x^818-168779267268*x^819+151005793010*x^820+97144323363*x^821 \
++6301125373*x^822-127837257500*x^823+40902091406*x^824-101906053776*x^825 \
+-23279213783*x^826-73850280596*x^827+21474507157*x^828-3710280111*x^829 \
++125929627807*x^830-65005088220*x^831+112378373235*x^832-130261726208*x^833 \
+-103928057603*x^834+88732873688*x^835+123408542087*x^836-113183605499*x^837 \
+-72717691074*x^838+78681040025*x^839+73703419129*x^840+127758960193*x^841 \
++17259409183*x^842-17726090931*x^843+162215334739*x^844-51931981106*x^845 \
+-104999647147*x^846-38897884082*x^847+11139645386*x^848+117700946259*x^849 \
++109990176394*x^850-71799635745*x^851-459245032*x^852-69367307377*x^853 \
+-2027522216*x^854-7461919795*x^855+129571738032*x^856+95090476040*x^857 \
+-95589373455*x^858+144520675739*x^859+8580136460*x^860-76481988297*x^861 \
+-80888061958*x^862+175337057530*x^863+39161149387*x^864+46724848451*x^865 \
+-25067481720*x^866+109073193366*x^867-20110082142*x^868-2065440519*x^869 \
++196039832496*x^870+51287378325*x^871+226840092695*x^872-85044341352*x^873 \
++36582038212*x^874+22454235962*x^875-37614234565*x^876-12154781489*x^877 \
+-92525662835*x^878+43210605729*x^879-29503086808*x^880+47536718905*x^881 \
+-119488430617*x^882+41802893764*x^883-36749803555*x^884+96596043730*x^885 \
++46051300012*x^886+90602974436*x^887-53608972981*x^888-5306460651*x^889 \
++98749285110*x^890+131701203007*x^891+25773458094*x^892-46977988482*x^893 \
++6670499818*x^894-68968602211*x^895+21468836009*x^896-70795434629*x^897 \
+-151229340489*x^898-79365642073*x^899+89379856502*x^900+180727114848*x^901 \
++19745037556*x^902+20006492259*x^903-68966001684*x^904+130265998317*x^905 \
+-117371414201*x^906-7030328681*x^907-56677471592*x^908+19528257927*x^909 \
++44475269947*x^910+3470169206*x^911+22467959607*x^912+98656618915*x^913 \
+-13743860146*x^914+23552943848*x^915-138242276800*x^916-88277644417*x^917 \
++47255373796*x^918-31977886816*x^919-115363640056*x^920+25243901225*x^921 \
+-105295249154*x^922-36136467784*x^923+52453236830*x^924+80777038439*x^925 \
++44837049142*x^926-55254888309*x^927-68234489848*x^928-92165707190*x^929 \
+-179410896808*x^930-6303111717*x^931-80199610328*x^932-15380092970*x^933 \
+-33938724551*x^934+17931510779*x^935-96931631295*x^936-48687303542*x^937 \
+-19820879797*x^938+37877911542*x^939-143694146707*x^940+113317058619*x^941 \
++20429285363*x^942-171716251844*x^943-84741152883*x^944-40418477950*x^945 \
++78524492177*x^946+22451226106*x^947-92140592429*x^948-224175995509*x^949 \
+-94751427805*x^950-40689590157*x^951-160025438504*x^952+101043700206*x^953 \
++174023744486*x^954-42827761752*x^955-14794443421*x^956+243752790124*x^957 \
++61496900473*x^958-36377552247*x^959-58121282080*x^960+144994090046*x^961 \
++92486830236*x^962-149072168741*x^963+50911986581*x^964+63775356240*x^965 \
++97687261817*x^966-46280177159*x^967-7688043430*x^968-39472067128*x^969 \
++73201769053*x^970-58880360399*x^971+170840419458*x^972-54292746092*x^973 \
+-103821886252*x^974-83322943096*x^975+76066200343*x^976+165315085358*x^977 \
++5424131554*x^978-67459706942*x^979+159323933212*x^980-107491571445*x^981 \
+-55118253633*x^982-17278583408*x^983+19225845993*x^984-114988147351*x^985 \
+-79315655096*x^986+11088007172*x^987-60859418995*x^988-145858383656*x^989 \
++113692045711*x^990-75018497310*x^991-365437868380*x^992+35092192414*x^993 \
+-110082408015*x^994+51647441793*x^995-184568312640*x^996+99653476797*x^997 \
++38507247220*x^998+123929024786*x^999+172382798537*x^1000-15653697225*x^1034 \
+-40712974939*x^1035-84481983259*x^1036-183059486597*x^1037+306329739993*x^1038 \
+-86809010253*x^1039-193596563569*x^1040+77147957893*x^1041+71846054998*x^1042 \
+-37049094394*x^1043-44803582029*x^1044+15081867854*x^1045-216710094742*x^1046 \
+-47796798084*x^1047-96211690279*x^1048-189635981392*x^1049-88214456018*x^1050 \
++63138650430*x^1051-141086932675*x^1052+179045473644*x^1053+152961766238*x^1054 \
++42049851016*x^1055-12923309793*x^1056+77822981644*x^1057+49606124226*x^1058 \
++64949849127*x^1059+139832839733*x^1060-79078674035*x^1061-63872053437*x^1062 \
++5880968210*x^1063+77059684059*x^1064+118861193169*x^1065-67361913998*x^1066 \
+-170366309445*x^1067-34162286067*x^1068-69460395006*x^1069+97779302218*x^1070 \
++216724014279*x^1071+58118563580*x^1072-206554378418*x^1073+3910530696*x^1074 \
++9692241373*x^1075+250051138068*x^1076-24386215253*x^1077-109899509519*x^1078 \
+-3113733500*x^1079+71737845657*x^1080+65818722190*x^1081-42083406251*x^1082 \
++114681977929*x^1083+111087402900*x^1084-36208556668*x^1085+67189586885*x^1086 \
+-95415909459*x^1087-39930935857*x^1088+61175159309*x^1089-119992012339*x^1090 \
++85494280676*x^1091-141608604262*x^1092+17013318480*x^1093-38635221143*x^1094 \
+-48453647574*x^1095+21051206372*x^1096-158416995981*x^1097+70402137413*x^1098 \
++49633932323*x^1099-86748492368*x^1100+104553685254*x^1101-63949144239*x^1102 \
++419956495*x^1103+16552807277*x^1104-74328747961*x^1105+75400756459*x^1106 \
++34917686845*x^1107+37471578275*x^1108-73580767536*x^1109+77174108880*x^1110 \
++148715919329*x^1111-66428402497*x^1112+165172263241*x^1113-26783742086*x^1114 \
++190088576166*x^1115+54515121646*x^1116+101483331390*x^1117-108689512350*x^1118 \
++53249730955*x^1119+72222967172*x^1120-5526562207*x^1121-207861618362*x^1122 \
++39979297711*x^1123-131526399820*x^1124+89213762352*x^1125-62167567794*x^1126 \
+-30249775241*x^1127-2196583404*x^1128+15230073656*x^1129+60729041258*x^1130 \
++88532730048*x^1131+10217062509*x^1132-60718111019*x^1133-57474242537*x^1134 \
++79431153433*x^1135+80845158176*x^1136+97779807512*x^1137-56322792891*x^1138 \
+-164156429512*x^1139-19878255222*x^1140+78282404374*x^1141+98799976154*x^1142 \
+-95492650246*x^1143+93751186963*x^1144-4498456358*x^1145-65869796255*x^1146 \
++169995598057*x^1147-50203042871*x^1148+109603182180*x^1149-111413589428*x^1150 \
++98314563037*x^1151+67616351563*x^1152+181622227355*x^1153+20284657424*x^1154 \
+-61079727667*x^1155+147106285121*x^1156-17573539453*x^1157-30144779725*x^1158 \
+-2161067542*x^1159+39349893244*x^1160-27707519713*x^1161+94277219419*x^1162 \
++134402588238*x^1163+179705148708*x^1164-162624387842*x^1165-67400319401*x^1166 \
++131747136365*x^1167-38125149979*x^1168-67302505083*x^1169-70487051743*x^1170 \
++8837205881*x^1171+83316371332*x^1172+50807693411*x^1173-52447034078*x^1174 \
+-14301265462*x^1175-147487671006*x^1176-23113128499*x^1177+8300673447*x^1178 \
++56955833747*x^1179-12038131262*x^1180+47065770458*x^1181-157303901005*x^1182 \
++37559510536*x^1183-148257314211*x^1184+34849913846*x^1185+45007732808*x^1186 \
+-115806825639*x^1187-161598801109*x^1188-18347919490*x^1189+60028556357*x^1190 \
++30303822679*x^1191+161206159164*x^1192-1888494396*x^1193-4658087012*x^1194 \
+-61288806540*x^1195");
+
+class sym_finder : public visitor, public symbol::visitor
+{
+protected:
+       inline void visit(const symbol& s)
+       {
+               found.insert(s);
+       }
+public:
+       sym_finder() { }
+       exset found;
+};
+
+static void ex2upoly(upoly& p, const ex& e)
+{
+       sym_finder sfinder;
+       e.traverse(sfinder);
+       assert(sfinder.found.size() == 1);
+       const ex x = *(sfinder.found.begin());
+       assert(e.ldegree(x) >= 0);
+       p.resize(e.degree(x) + 1);
+       for (int i = e.ldegree(x); i <= e.degree(x); ++i) {
+               const numeric n = ex_to<numeric>(e.coeff(x, i));
+               p[i] = cln::the<cln::cl_I>(n.to_cl_N());
+       }
+}
+
+static void
+read_srep(ex& e1, ex& e2, upoly& a, upoly& b, const std::string& s1, const std::string& s2)
+{
+       parser reader;
+       e1 = reader(s1);
+       e2 = reader(s2);
+       a.resize(e1.nops());
+       b.resize(e2.nops());
+       ex2upoly(a, e1);
+       ex2upoly(b, e2);
+       canonicalize(a);
+       canonicalize(b);
+}
+
+namespace GiNaC
+{
+extern upoly sr_gcd(const upoly& a, const upoly& b);
+extern bool heur_gcd_z(upoly& g, const upoly& a, const upoly& b);
+}
+
+
+/// Check if polynomial @a g divides polynomials @a a and @a b
+/// Used as GCD sanity check
+static bool
+gcd_sanity_check(const upoly& g, const upoly& a, const upoly& b,
+                const std::string& label)
+{
+       upoly r1, r2;
+       remainder_in_ring(r1, a, g);
+       bug_on(!r1.empty(), "bug: " << label << " : gcd g = \"" << g <<
+               "\"does not divide a =\"" << a << "\"");
+
+       remainder_in_ring(r2, b, g);
+       bug_on(!r2.empty(), "bug: " << label << " : gcd g = \"" << g <<
+               "\"does not divide b =\"" << b << "\"");
+       return true;
+}
+
+struct mod_gcd_test
+{
+       const upoly& a, b;
+       upoly g;
+
+       inline void run()
+       {
+               mod_gcd(g, a, b);
+       }
+
+       bool check() const
+       {
+               gcd_sanity_check(g, a, b, std::string("mod_gcd"));
+               return true;
+       }
+
+       void print_result(const double t) const
+       {
+               std::streamsize display_digits = std::cout.precision(2);
+               std::cout << std::scientific;
+               std::cout << "mod_gcd\t\t: " << g.size() << " " << t << std::endl;
+               std::cout.precision(display_digits);
+       }
+
+       mod_gcd_test(const upoly& a_, const upoly& b_) : a(a_), b(b_),
+               g(std::min(degree(a_), degree(b_)))
+       { }
+};
+
+struct heur_gcd_test
+{
+       const upoly& a, b;
+       upoly g;
+       const upoly& g_check;
+       bool found;
+
+       inline void run()
+       {
+               found = heur_gcd_z(g, a, b);
+       }
+
+       bool check() const
+       {
+               if (!found)
+                       return false;
+
+               gcd_sanity_check(g, a, b, std::string("heur_gcd"));
+               bug_on(g != g_check, 
+                       "modular and heuristic GCD disagree: " <<
+                       "a = \"" << a << "\", b = \"" << b << "\", " <<
+                       "mod_gcd = \"" << g_check << "\", " <<
+                       "heur_gcd = \"" << g << "\"");
+               return true;
+       }
+
+       void print_result(const double t) const
+       {
+               if (!found)
+                       return;
+               std::streamsize display_digits = std::cout.precision(2);
+               std::cout << std::scientific;
+               std::cout << "heur_gcd\t: " << g.size() << " " << t << std::endl;
+               std::cout.precision(display_digits);
+       }
+
+       heur_gcd_test(const upoly& a_, const upoly& b_, const upoly& g_) :
+               a(a_), b(b_), g(std::min(degree(a_), degree(b_))),
+               g_check(g_), found(false)
+       { }
+};
+               
+
+struct sr_gcd_test
+{
+       const upoly& a, b;
+       const upoly& g_check;
+       upoly g;
+       
+       sr_gcd_test(const upoly& a_, const upoly& b_, const upoly& g_) : 
+               a(a_), b(b_), g_check(g_), g(std::min(degree(a_), degree(b_)))
+       { }
+
+       inline void run()
+       {
+               g = sr_gcd(a, b);
+       }
+
+       bool check() const
+       {
+               gcd_sanity_check(g, a, b, std::string("sr_gcd"));
+               bug_on(g != g_check, 
+                       "modular and PRS GCD disagree: " <<
+                       "a = \"" << a << "\", b = \"" << b << "\", " <<
+                       "mod_gcd = \"" << g_check << "\", " <<
+                       "sr_gcd = \"" << g << "\"");
+               return true;
+       }
+
+       void print_result(const double t) const
+       {
+               std::streamsize display_digits = std::cout.precision(2);
+               std::cout << std::scientific;
+               std::cout << "sr_gcd:\t\t: " << g.size() << " " << t << std::endl;
+               std::cout.precision(display_digits);
+       }
+};
+
+struct ex_sr_gcd_test
+{
+       ex a, b;
+       ex g;
+       const upoly& g_check;
+       unsigned options;
+       ex_sr_gcd_test(const ex& a_, const ex& b_, const upoly& g_) :
+               a(a_), b(b_), g(0), g_check(g_), options(gcd_options::no_heur_gcd)
+       { }
+
+       inline void run()
+       {
+               // always use subresultant PRS (to estimate the overhead
+               // due to bad polynomial representation)
+               g = gcd(a, b, 0, 0, false, options);
+       }
+
+       bool check() const
+       {
+               upoly g_gin;
+               ex2upoly(g_gin, g);
+
+               bug_on(g_gin != g_check, "modular and old PRS GCD disagree: " <<
+                       "a = \"" << a << "\", b = \"" << b << "\", " <<
+                       "old sr_gcd = \"" << g_gin << "\", " <<
+                       "mod_gcd = \"" << g_check << "\"");
+               return true;
+       }
+
+       void print_result(const double t) const
+       {
+               std::streamsize display_digits = std::cout.precision(2);
+               std::cout << std::scientific;
+               if (options)
+                       std::cout << "sr_gcd (old)";
+               else
+                       std::cout << "heur_gcd (old)";
+               std::cout << "\t: " << g.nops() << " " << t << std::endl;
+               std::cout.precision(display_digits);
+       }
+};
+
+
+static void
+run_test(const std::string& s1, const std::string& s2,
+        bool use_sr_gcd = true, bool use_ex_sr_gcd = false)
+{
+       upoly a, b;
+       ex ea, eb;
+       read_srep(ea, eb, a, b, s1, s2);
+
+       std::cout << "Non-trivial GCD, degree(a) = " << degree(a) <<
+               ", degree(b) = " << degree(b) << std::endl << std::flush;
+       
+       mod_gcd_test b_mod_gcd(a, b);
+       run_benchmark(b_mod_gcd);
+
+       heur_gcd_test b_heur_gcd(a, b, b_mod_gcd.g); 
+       run_benchmark(b_heur_gcd);
+
+       // Compute GCD using heuristic algorithm which operates on ex
+       ex_sr_gcd_test b_ex_sr_gcd2(ea, eb, b_mod_gcd.g);
+       b_ex_sr_gcd2.options = 0;
+       run_benchmark(b_ex_sr_gcd2);
+
+       if (use_sr_gcd) {
+               sr_gcd_test b_sr_gcd(a, b, b_mod_gcd.g);
+               run_benchmark(b_sr_gcd);
+       }
+
+       // GiNaC::sr_gcd (which operates on ex) is way too slow.
+       if (use_ex_sr_gcd) {
+               ex_sr_gcd_test b_ex_sr_gcd(ea, eb, b_mod_gcd.g);
+               run_benchmark(b_ex_sr_gcd);
+       }
+}
+
+static upoly make_random_upoly(const std::size_t deg);
+// Make random polynomials, most likely they will be relatively prime.
+// Check how different algorithms behave on such inputs.
+static void
+run_with_random_intputs(const unsigned d1, const unsigned d2)
+{
+       std::cout << "GCD of relatively prime polynomials a and b" <<
+               std::endl << "degree(a) = " << d1 <<
+               ", degree(b) = " << d2 << std::endl << std::flush;
+       upoly a = make_random_upoly(d1);
+       upoly b = make_random_upoly(d2);
+       mod_gcd_test b_mod(a, b);
+       run_benchmark(b_mod);
+       heur_gcd_test b_heur(a, b, b_mod.g);
+       run_benchmark(b_heur);
+       sr_gcd_test b_sr(a, b, b_mod.g);
+       run_benchmark(b_sr);
+}
+
+int main(int argc, char** argv)
+{
+       std::cout << "timing univarite GCD" << std::endl << std::flush;
+       run_with_random_intputs(100, 50);
+       // run PRS gcd tests, both with upoly and ex
+       run_test(p1_srep, p2_srep, true, true);
+       bool tolerant_p = (run_expensive_timings_p() >= 1);
+       bool masochist_p = (run_expensive_timings_p() >= 2);
+       // By default PRS gcd tests are disabled, they are way too slow
+       run_test(q1_srep, q2_srep, tolerant_p, masochist_p);
+       // ditto
+       run_test(r1_srep, r2_srep, masochist_p, masochist_p);
+       std::cout << ". " << std::flush;
+       return 0;
+}
+
+static upoly make_random_upoly(const std::size_t deg)
+{
+       static const cln::cl_I biggish("987654321098765432109876543210");
+       upoly p(deg + 1);
+       for (std::size_t i = 0; i <= deg; ++i)
+               p[i] = cln::random_I(biggish);
+
+       // Make sure the leading coefficient is non-zero
+       while (zerop(p[deg])) 
+               p[deg] = cln::random_I(biggish);
+       return p;
+}
+
index b683d9b..7ab16d6 100644 (file)
@@ -29,6 +29,12 @@ polynomial/mod_gcd.hpp \
 polynomial/cra_garner.hpp \
 polynomial/upoly_io.hpp \
 polynomial/upoly_io.cpp \
+polynomial/prem_uvar.h \
+polynomial/eval_uvar.h \
+polynomial/interpolate_padic_uvar.h \
+polynomial/sr_gcd_uvar.h \
+polynomial/heur_gcd_uvar.h \
+polynomial/gcd_uvar.cpp \
 polynomial/debug.hpp
 
 libginac_la_LDFLAGS = -version-info $(LT_VERSION_INFO) -release $(LT_RELEASE)
diff --git a/ginac/polynomial/eval_uvar.h b/ginac/polynomial/eval_uvar.h
new file mode 100644 (file)
index 0000000..0a3bcec
--- /dev/null
@@ -0,0 +1,38 @@
+#ifndef GINAC_EVAL_UPOLY_TCC
+#define GINAC_EVAL_UPOLY_TCC
+#include "upoly.hpp"
+#include "ring_traits.hpp"
+
+namespace GiNaC
+{
+
+/// Evaluate the polynomial using Horner rule.
+/// TODO: 
+/// - a better algorithm for small polynomials (use SIMD instructions)
+/// - a better algorithm for large polynomials (use Karatsuba trick)
+/// - a better algorithm for modular polynomials (especially for small
+///     moduli and GFN)
+template<typename T> static typename T::value_type
+eval(const T& p, const typename T::value_type& x)
+{
+       // p(x) = c_n x^n + c_{n-1} x^{n-1} + \ldots + c_0 =
+       // c_0 + x (c_1 + x (c_2 + x ( \ldots (c_{n-1} + c_n x) \ldots )))
+       // (AKA Horner rule)
+       typedef typename T::value_type ring_t;
+       if (p.empty())
+               return 0;
+       if (degree(p) == 0)
+               return p[0];
+
+       ring_t y = lcoeff(p);
+       // read the formula above from the right to the left
+       for (std::size_t i = p.size() - 1; i-- != 0; )
+               y = x*y + p[i];
+
+       return y;
+}
+
+} // namespace GiNaC
+
+#endif // GINAC_EVAL_UPOLY_TCC
+
diff --git a/ginac/polynomial/gcd_uvar.cpp b/ginac/polynomial/gcd_uvar.cpp
new file mode 100644 (file)
index 0000000..1443852
--- /dev/null
@@ -0,0 +1,33 @@
+#include "upoly.hpp"
+#include "sr_gcd_uvar.h"
+#include "heur_gcd_uvar.h"
+#include <stdexcept>
+
+namespace GiNaC
+{
+
+upoly sr_gcd(const upoly& a, const upoly& b)
+{
+       upoly g;
+       bool found = sr_gcd_priv(g, a, b);
+       if (found)
+               return g;
+
+       throw std::runtime_error("failed to compute gcd");
+}
+
+bool heur_gcd_z(upoly& g, const upoly& a, const upoly& b)
+{
+       return heur_gcd_z_priv(g, a, b);
+}
+
+upoly pseudoremainder(const upoly& a, const upoly& b)
+{
+       upoly r;
+       pseudoremainder(r, a, b);
+       return r;
+
+}
+
+}
+
diff --git a/ginac/polynomial/heur_gcd_uvar.h b/ginac/polynomial/heur_gcd_uvar.h
new file mode 100644 (file)
index 0000000..1aa7348
--- /dev/null
@@ -0,0 +1,66 @@
+#ifndef GINAC_UPOLY_HEUR_GCD
+#define GINAC_UPOLY_HEUR_GCD
+#include "upoly.hpp"
+#include "ring_traits.hpp"
+#include "normalize.tcc"
+#include "remainder.tcc"
+#include "eval_uvar.h"
+#include "interpolate_padic_uvar.h"
+#include <algorithm>
+
+namespace GiNaC
+{
+
+/// Compute GCD of primitive univariate polynomials.
+template<typename T> static bool
+heur_gcd_z_pp(T& g, const T& a, const T& b, unsigned max_tries = 66)
+{
+       typedef typename T::value_type ring_t;
+       const ring_t n73794 = get_ring_elt(b[0], 73794);
+       const ring_t n27011 = get_ring_elt(b[0], 27011);
+       const std::size_t maxdeg = std::max(degree(a), degree(b));
+       T r, gg;
+       gg.reserve(maxdeg);
+       r.reserve(maxdeg);
+
+       // find the evaluation point
+       ring_t xi = (std::min(max_coeff(a), max_coeff(b)) + 1) << 1;
+
+       do {
+               const ring_t av = eval(a, xi);
+               const ring_t bv = eval(b, xi); 
+               const ring_t gamma = gcd(av, bv);
+               interpolate(gg, gamma, xi, maxdeg);
+               normalize_in_ring(gg);
+               remainder_in_ring(r, a, gg);
+               if (r.empty()) {
+                       swap(g, gg);
+                       return true;
+               }
+               // next evaluation point
+               xi = truncate1(xi*isqrt(isqrt(xi))*n73794, n27011);
+       } while (--max_tries != 0);
+       return false;
+}
+
+template<typename T> static bool
+heur_gcd_z_priv(T& g, const T& a, const T& b, const unsigned max_tries = 66)
+{
+       typedef typename T::value_type ring_t;
+       ring_t acont, bcont;
+       T a_(a), b_(b);
+       normalize_in_ring(a_, &acont);
+       normalize_in_ring(b_, &bcont);
+       const ring_t gc = gcd(acont, bcont);
+       bool found = heur_gcd_z_pp(g, a_, b_, max_tries);
+       if (found) {
+               g *= gc;
+               return true;
+       }
+       return false;
+}
+
+} // namespace GiNaC
+
+#endif // GINAC_UPOLY_HEUR_GCD
+
diff --git a/ginac/polynomial/interpolate_padic_uvar.h b/ginac/polynomial/interpolate_padic_uvar.h
new file mode 100644 (file)
index 0000000..46c2777
--- /dev/null
@@ -0,0 +1,40 @@
+#ifndef GINAC_UPOLY_INTERPOLATE_PADIC_TCC
+#define GINAC_UPOLY_INTERPOLATE_PADIC_TCC
+#include "ring_traits.hpp"
+
+namespace cln
+{
+static inline cln::cl_I smod(const cln::cl_I& x, const cln::cl_I y)
+{
+       cln::cl_I r = mod(x, y);
+       const cln::cl_I y_2 = y >> 1;
+       if (r > y_2)
+               r = r - y;
+       return r;
+}
+
+} // namespace cln
+
+namespace GiNaC
+{
+
+template<typename T> static void
+interpolate(T& g, const typename T::value_type& gamma,
+           const typename T::value_type& modulus,
+           const std::size_t degree_hint = 1)
+{
+       typedef typename T::value_type ring_t;
+       g.clear();
+       g.reserve(degree_hint);
+       ring_t e = gamma;
+       while (!zerop(e)) {
+               const ring_t gi = smod(e, modulus);
+               g.push_back(gi);
+               e = exquo(e - gi, modulus);
+       }
+}
+
+} // namespace GiNaC
+
+#endif // GINAC_UPOLY_INTERPOLATE_PADIC_TCC
+
diff --git a/ginac/polynomial/prem_uvar.h b/ginac/polynomial/prem_uvar.h
new file mode 100644 (file)
index 0000000..c1a74cd
--- /dev/null
@@ -0,0 +1,47 @@
+#ifndef GINAC_POLYNOMIAL_PREM_TCC
+#define GINAC_POLYNOMIAL_PREM_TCC
+#include "upoly.hpp"
+#include "debug.hpp"
+#include "remainder.tcc"
+
+namespace GiNaC
+{
+
+/// Compute the pseudo-remainder of univariate polynomials @a a and @a b
+/// Pseudo remainder \f$r(x)\f$ is defined as 
+/// \f$\beta^l a(x) = b(x) q(x) + r(x) \f$, where \f$\beta\f$ is leading
+/// coefficient of \f$b(x)\f$ and \f$l = degree(a) - degree(b) + 1\f$
+/// FIXME: this implementation is extremely dumb.
+template<typename T> bool pseudoremainder(T& r, const T& a, const T& b)
+{
+       typedef typename T::value_type ring_t;
+       bug_on(b.size() == 0, "division by zero");
+       if (a.size() == 1 && b.size() == 1) {
+               r.clear();
+               return true;
+       }
+       if (a.size() == 1) {
+               r = b;
+               return false;
+       }
+       if (degree(b) > degree(a)) {
+               r = b;
+               return false;
+       }
+
+       const ring_t one = get_ring_elt(b[0], 1);
+       const std::size_t l = degree(a) - degree(b) + 1;
+       const ring_t blcoeff = lcoeff(b);
+       const ring_t b_lth = expt_pos(blcoeff, l);
+       if (b_lth == one)
+               return remainder_in_ring(r, a, b);
+
+       T a_(a);
+       a_ *= b_lth;
+       return remainder_in_ring(r, a_, b);
+}
+
+}
+
+#endif // GINAC_POLYNOMIAL_PREM_TCC
+
diff --git a/ginac/polynomial/sr_gcd_uvar.h b/ginac/polynomial/sr_gcd_uvar.h
new file mode 100644 (file)
index 0000000..128e036
--- /dev/null
@@ -0,0 +1,95 @@
+#ifndef GINAC_UPOLY_SR_GCD_TCC
+#define GINAC_UPOLY_SR_GCD_TCC
+#include "upoly.hpp"
+#include "ring_traits.hpp"
+#include "normalize.tcc"
+#include "prem_uvar.h"
+#include <limits>
+
+namespace GiNaC
+{
+
+/// Calculate GCD of two univariate polynomials @a a and @a b using
+/// subresultant pseudo-remainder sequence method
+template<typename T> static bool
+sr_gcd_priv(T& g, T a, T b,
+           unsigned tries = std::numeric_limits<unsigned>::max())
+{
+       // handle zero polynomials
+       if (a.empty()) {
+               g.clear();
+               return true;
+       }
+       if (b.empty()) {
+               g.clear();
+               return true;
+       }
+
+       typedef typename T::value_type ring_t;
+       if (degree(a) < degree(b))
+               swap(a, b);
+       ring_t acont, bcont;
+       normalize_in_ring(a, &acont);
+       normalize_in_ring(b, &bcont);
+
+       const ring_t one = get_ring_elt(b[0], 1);
+
+       const ring_t gamma = gcd(acont, bcont);
+       if (degree(b) == 0) {
+               g.resize(1);
+               g[0] = gamma;
+               return true;
+       }
+
+       T r(std::min(degree(a), degree(b)));
+
+       ring_t ri = one, psi = one;
+
+       do {
+               std::size_t delta = degree(a) - degree(b);
+               pseudoremainder(r, a, b);
+               if (r.empty()) {
+                       normalize_in_ring(b);
+                       b *= gamma;
+                       swap(b, g);
+                       return true;
+               }
+               a = b;
+
+               ring_t ri_psi_delta = delta > 0 ?  ri*expt_pos(psi, delta) : ri;
+
+               bool divisible_p = divide(b, r, ri_psi_delta);
+               bug_on(!divisible_p, "division failed: r = " << r <<
+                       ", ri = " << ri << ", psi = " << psi);
+
+               if ((degree(b) == 0) && (degree(r) == 0)) {
+                       g.resize(1);
+                       g[0] = gamma;
+                       return true;
+               }
+               if (degree(b) == 0) {
+                       normalize_in_ring(r);
+                       r *= gamma;
+                       swap(r, g);
+                       return true;
+               }
+
+               ri = lcoeff(a);
+               if (delta == 1)
+                       psi = ri;
+               else if (delta) {
+                       const ring_t ri_delta = expt_pos(ri, delta);
+                       const ring_t psi_delta_1 = expt_pos(psi, delta - 1);
+                       bool sanity_check = div(psi, ri_delta, psi_delta_1);
+                       bug_on(!sanity_check, "division failed: ri = " << ri
+                               << ", psi = " << psi << ", delta = " << delta);
+               }
+               if (--tries == 0)
+                       return false;
+       } while (true);
+}
+
+}
+
+#endif // GINAC_UPOLY_SR_GCD_TCC
+