-#include <string>
-#include <cassert>
-#include <iostream>
-#include "timer.h"
+/** @file time_uvar_gcd.cpp
+ *
+ * Time the different GCD algorithms. */
+
+/*
+ * GiNaC Copyright (C) 1999-2014 Johannes Gutenberg University Mainz, Germany
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
#include "ginac.h"
-#include "error_report.hpp"
+#include "timer.h"
+#include "error_report.h"
#include "test_runner.h"
-#include "polynomial/remainder.tcc"
-#include "polynomial/upoly.hpp"
-#include "polynomial/mod_gcd.hpp"
+#include "polynomial/remainder.h"
+#include "polynomial/upoly.h"
+#include "polynomial/mod_gcd.h"
using namespace GiNaC;
+#include <string>
+#include <cassert>
+#include <iostream>
+
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 \
+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("\
+static const std::string q1_srep_1("\
-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 \
+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 \
++53285909119*x^905+25945946437*x^906-50737201760*x^907-3797518282*x^908");
+static const std::string q1_srep_2("\
-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 \
+4503145470*x^997+91649222*x^998+3092691860*x^999+2111130448*x^1000 \
+7931022064");
-static const std::string q2_srep("\
+static const std::string q2_srep_1("\
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 \
+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 \
+-48845002624*x^905-27099816961*x^906+23031415252*x^907-4460429941*x^908");
+
+static const std::string q2_srep_2("\
-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 \
-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("\
+static const std::string r1_srep_1("\
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 \
+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 \
++13971227562*x^1586+38219978507*x^1587-29292257027*x^1588-45584106398*x^1589");
+
+static const std::string r1_srep_2("\
+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 \
-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 \
+-6900915942*x^910+39708679388*x^911+165967464883*x^912-13498312464*x^913");
+
+static const std::string r1_srep_3("\
-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 \
-149308311610*x^1195 \
");
-static const std::string r2_srep("\
+static const std::string r2_srep_1("\
-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 \
+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 \
++104080240756*x^1586+29567135838*x^1587-85533231646*x^1588-14007407713*x^1589");
+
+static const std::string r2_srep_2("\
-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 \
-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 \
++44475269947*x^910+3470169206*x^911+22467959607*x^912+98656618915*x^913");
+
+static const std::string r2_srep_3("\
-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 \
{
upoly r1, r2;
remainder_in_ring(r1, a, g);
- bug_on(!r1.empty(), "bug: " << label << " : gcd g = \"" << g <<
+ cbug_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 <<
+ cbug_on(!r2.empty(), "bug: " << label << " : gcd g = \"" << g <<
"\"does not divide b =\"" << b << "\"");
return true;
}
return false;
gcd_sanity_check(g, a, b, std::string("heur_gcd"));
- bug_on(g != g_check,
+ cbug_on(g != g_check,
"modular and heuristic GCD disagree: " <<
"a = \"" << a << "\", b = \"" << b << "\", " <<
"mod_gcd = \"" << g_check << "\", " <<
bool check() const
{
gcd_sanity_check(g, a, b, std::string("sr_gcd"));
- bug_on(g != g_check,
+ cbug_on(g != g_check,
"modular and PRS GCD disagree: " <<
"a = \"" << a << "\", b = \"" << b << "\", " <<
"mod_gcd = \"" << g_check << "\", " <<
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)
+ a(a_), b(b_), g(0), g_check(g_), options(gcd_options::no_heur_gcd |
+ gcd_options::use_sr_gcd)
{ }
inline void run()
upoly g_gin;
ex2upoly(g_gin, g);
- bug_on(g_gin != g_check, "modular and old PRS GCD disagree: " <<
+ cbug_on(g_gin != g_check, "modular and old PRS GCD disagree: " <<
"a = \"" << a << "\", b = \"" << b << "\", " <<
"old sr_gcd = \"" << g_gin << "\", " <<
"mod_gcd = \"" << g_check << "\"");
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);
+ run_test(q1_srep_1 + q1_srep_2, q2_srep_1 + q2_srep_2, tolerant_p, masochist_p);
// ditto
- run_test(r1_srep, r2_srep, masochist_p, masochist_p);
+ run_test(r1_srep_1 + r1_srep_2 + r1_srep_3, r2_srep_1 + r2_srep_2 + r2_srep_3, masochist_p, masochist_p);
std::cout << ". " << std::flush;
return 0;
}
p[deg] = cln::random_I(biggish);
return p;
}
-
git://www.ginac.de / ginac.git / blobdiff