API tools faq
paste
mramine364

polynomial.cpp

mramine364
Jul 9th, 2016
133
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.88 KB | None | 0 0
raw download clone embed print report
  1. #include "polynomial.h"
  2.  
  3. polynomial::polynomial(){}
  4. polynomial::polynomial(double d)
  5. {
  6.     monomial* m = new monomial(d);
  7.     this->ms.push_back(m);
  8. }
  9. polynomial::polynomial(const polynomial& p){
  10.     for (unsigned int i = 0; i < p.ms.size(); i++){
  11.         monomial* m = new monomial(*p.ms[i]);
  12.         this->ms.push_back(m);
  13.     }
  14. }
  15. polynomial::polynomial(const polynomial& p, int s, int e, int d){
  16.     for (int i = s; i <= e; i++){
  17.         monomial* m = new monomial(*p.ms[i]);
  18.         m->setDeg(m->getDeg() - d);
  19.         this->ms.push_back(m);
  20.     }
  21. }
  22. polynomial::polynomial(const monomial& m){
  23.     monomial* nm = new monomial(m);
  24.     this->ms.push_back(nm);
  25. }
  26. polynomial::polynomial(double** t, int n){
  27.     for (int i = 0; i < n; i++){
  28.         monomial* m = new monomial(t[i][0], (int)t[i][1]);
  29.         this->ms.push_back(m);
  30.     }
  31. }
  32.  
  33. int polynomial::dt = 0;
  34.  
  35. polynomial::~polynomial()
  36. {
  37.     clock_t t = clock();
  38.     for (unsigned int i = 0; i < this->ms.size(); i++){
  39.         delete this->ms[i];
  40.     }
  41.     this->ms.clear();
  42.     polynomial::dt += (int)(clock() - t);
  43. }
  44.  
  45. ostream& operator<<(ostream& out, const polynomial& p){
  46.     unsigned int i = 0;
  47.     for (; i < p.ms.size() - 1; i++){
  48.         out << *p.ms[i] << " + ";
  49.     }
  50.     if (i < p.ms.size())
  51.         out << *p.ms[i];
  52.     return out;
  53. }
  54.  
  55. polynomial* polynomial::operator+=(const monomial& m){
  56.     if (m.getCoef() == 0)
  57.         return this;
  58.     int low = 0;
  59.     int high = this->ms.size() - 1;
  60.     double mid2 = 0; int mid = 0;
  61.  
  62.     if (this->ms.size() == 0){
  63.         monomial* nm = new monomial(m);    
  64.         this->ms.push_back(nm);
  65.         return this;
  66.     }
  67.  
  68.     while (this->ms[low]->getDeg() <= m.getDeg() && this->ms[high]->getDeg() >= m.getDeg()) {
  69.         mid2 = round(low + ((m.getDeg() - this->ms[low]->getDeg()) * (high - low)) / (double)(this->ms[high]->getDeg() - this->ms[low]->getDeg()));
  70.         mid = (int)mid2;
  71.         if (this->ms[mid]->getDeg() < m.getDeg()) {
  72.             low = mid + 1;
  73.         }
  74.         else if (this->ms[mid]->getDeg() > m.getDeg()) {
  75.             high = mid - 1;
  76.         }
  77.         else {
  78.             monomial* tm = this->ms[mid];
  79.             tm->setCoef(tm->getCoef() + m.getCoef());
  80.             return this;
  81.         }      
  82.     }
  83.  
  84.     if (this->ms[low]->getDeg() == m.getDeg()) {
  85.         monomial* tm = this->ms[low];
  86.         tm->setCoef(tm->getCoef() + m.getCoef());
  87.     }
  88.     else {
  89.         monomial* nm = new monomial(m);
  90.         if (m.getDeg() > this->ms[high]->getDeg()){
  91.             this->ms.insert(this->ms.begin() + (high+1), nm);
  92.         }
  93.         else{
  94.             this->ms.insert(this->ms.begin() + low, nm);
  95.         }
  96.     }
  97.     return this;
  98. }
  99. polynomial* polynomial::operator+(const polynomial& p){
  100.     polynomial* r = new polynomial(*this);
  101.     unsigned int i = 0;
  102.     while (i < p.ms.size()){
  103.         *r += *p.ms[i];
  104.         i++;
  105.     }
  106.     return r;
  107. }
  108. polynomial* polynomial::operator-=(const monomial& m){
  109.     if (m.getCoef()==0)
  110.         return this;
  111.     int low = 0;
  112.     int high = this->ms.size() - 1;
  113.     double mid2 = 0; int mid = 0;
  114.  
  115.     if (this->ms.size() == 0){
  116.         monomial* nm = new monomial(-m.getCoef(),m.getDeg());
  117.         this->ms.push_back(nm);
  118.         return this;
  119.     }
  120.     while (this->ms[low]->getDeg() <= m.getDeg() && this->ms[high]->getDeg() >= m.getDeg()) {
  121.         mid2 = round(low + ((m.getDeg() - this->ms[low]->getDeg()) * (high - low)) / (double)(this->ms[high]->getDeg() - this->ms[low]->getDeg()));
  122.         mid = (int)mid2;
  123.         if (this->ms[mid]->getDeg() < m.getDeg()) {
  124.             low = mid + 1;
  125.         }
  126.         else if (this->ms[mid]->getDeg() > m.getDeg()) {
  127.             high = mid - 1;
  128.         }
  129.         else {
  130.             this->ms[mid]->setCoef(this->ms[mid]->getCoef() - m.getCoef());
  131.             return this;
  132.         }
  133.     }
  134.  
  135.     if (this->ms[low]->getDeg() == m.getDeg()) {
  136.         this->ms[low]->setCoef(this->ms[low]->getCoef() - m.getCoef());
  137.     }
  138.     else {
  139.         monomial* nm = new monomial(-m.getCoef(), m.getDeg());
  140.         if (m.getDeg() > this->ms[high]->getDeg()){
  141.             this->ms.insert(this->ms.begin() + (high + 1), nm);
  142.         }
  143.         else{
  144.             this->ms.insert(this->ms.begin() + low, nm);
  145.         }
  146.     }
  147.     return this;
  148. }
  149. polynomial* polynomial::operator-(const polynomial& p){
  150.     polynomial* r = new polynomial(*this);
  151.     unsigned int i = 0;
  152.     while (i < p.ms.size()){
  153.         *r -= *p.ms[i];
  154.         i++;
  155.     }
  156.     return r;
  157. }
  158. polynomial* polynomial::operator*=(const monomial& m){
  159.     unsigned int i = 0;
  160.     while (i < this->ms.size()){
  161.         this->ms[i]->setCoef(this->ms[i]->getCoef()*m.getCoef());
  162.         this->ms[i]->setDeg(this->ms[i]->getDeg() + m.getDeg());
  163.         i++;
  164.     }
  165.     return this;
  166. }
  167. polynomial* polynomial::operator*(const polynomial& p){
  168.     unsigned int i = 0;
  169.     polynomial *res = new polynomial();
  170.     while (i < p.ms.size()){
  171.         polynomial *thi = new polynomial(*this);
  172.         *thi *= *p.ms[i];
  173.         polynomial *tmp = *res + *thi;
  174.         delete res;
  175.         delete thi;
  176.         res = tmp;
  177.         i++;
  178.     }
  179.     return res;
  180. }
  181.  
  182. unsigned int polynomial::size(){
  183.     return this->ms.size();
  184. }
  185.  
  186. polynomial* polynomial::mul(const polynomial& p){
  187.     return this->mul(p, 0, this->ms.size() - 1, 0, p.ms.size() - 1);
  188. }
  189. int polynomial::steps = 0;
  190. polynomial* polynomial::mul(const polynomial& p, int s, int e, int sp, int ep) const{  
  191.     if (s >= e - 31 || sp >= ep - 31){
  192.         polynomial *a = new polynomial(*this, s, e);
  193.         polynomial *b = new polynomial(p, sp, ep);
  194.         polynomial *c = *a * *b;
  195.         delete a;
  196.         delete b;
  197.         return c;
  198.     }
  199.     if (e - s != ep - sp){
  200.     polynomial* a0b0 = this->mul(p, s, (e - s) / 2 + s, sp, (ep - sp) / 2 + sp);
  201.     polynomial* a0b1 = this->mul(p, s, (e - s) / 2 + s, (ep - sp) / 2 + sp+1, ep);
  202.     polynomial* a1b0 = this->mul(p, (e - s) / 2 + s+1, e, sp, (ep - sp) / 2 + sp);
  203.     polynomial* a1b1 = this->mul(p, (e - s) / 2 + s+1, e, (ep - sp) / 2 + sp+1, ep);
  204.     polynomial* r1 = *a0b0 + *a0b1;
  205.     polynomial* r2 = *a1b0 + *a1b1;
  206.     polynomial* r = *r1 + *r2;
  207.     delete a0b0;
  208.     delete a0b1;
  209.     delete a1b0;
  210.     delete a1b1;
  211.     delete r1;
  212.     delete r2;
  213.     return r;
  214.     }
  215.     polynomial* a0 = new polynomial(*this, s, (e - s) / 2 + s);
  216.     polynomial* a1 = new polynomial(*this, (e - s) / 2 + s + 1, e, this->ms[(e - s) / 2 + s + 1]->getDeg());
  217.     polynomial* b0 = new polynomial(p, sp, (ep - sp) / 2 + sp);
  218.     polynomial* b1 = new polynomial(p, (ep - sp) / 2 + sp + 1, ep, p.ms[(ep - sp) / 2 + sp + 1]->getDeg());
  219.  
  220.     polynomial* a0pa1 = *a0 + *a1;
  221.     polynomial* b0pb1 = *b0 + *b1;
  222.  
  223.     polynomial* y = a0pa1->mul(*b0pb1);
  224.     polynomial* u = a0->mul(*b0);
  225.     polynomial* z = a1->mul(*b1);
  226.     monomial *xz = new monomial(1, this->ms[(e - s) / 2 + s ]->getDeg()*p.ms[(ep - sp) / 2 + sp ]->getDeg() ),
  227.         *xy = new monomial(1, this->ms[(e - s) / 2 + s]->getDeg());
  228.     polynomial *ymu = *y - *u, *ymumz = *ymu - *z;
  229.     *ymumz *= *xy;
  230.     *z *= *xz;
  231.     polynomial *upz = *u + *z, *res = *upz + *ymumz;
  232.     delete a0; delete a1; delete b0; delete b1;
  233.     delete a0pa1; delete b0pb1;
  234.     delete y; delete u; delete z;
  235.     delete xz; delete xy;
  236.     delete ymu; delete ymumz; delete upz;
  237.     return res;
  238. }
  239. polynomial* polynomial::add(const polynomial& p, int s, int e, int sp, int ep, int d) const{
  240.     polynomial* r = new polynomial(p, s, e);
  241.     for (int i = sp; i <= ep; i++){    
  242.         if (d==0)
  243.             *r += *p.ms[i];
  244.         else{
  245.             monomial *m = new monomial(*p.ms[i]);
  246.             m->setCoef(m->getCoef() - d);
  247.             *r += *m;
  248.         }
  249.     }
  250.     return r;
  251. }
  252.  
  253. polynomial* polynomial::simplify(){
  254.     for (int i = 0; i < this->ms.size(); i++){
  255.         if (this->ms[i]->getCoef() == 0){
  256.             this->ms.erase(this->ms.begin() + i);
  257.             i--;
  258.         }
  259.     }
  260.     return this;
  261. }
  262. double polynomial::eval(double x){
  263.     int i = 0;
  264.     double res = 0, nx = x;
  265.     while (i<this->ms.size()){
  266.         int p = 0; double tmp = this->ms[i]->getCoef();
  267.         while (p<this->ms[i]->getDeg()){
  268.             tmp *= nx;
  269.             p++;
  270.         }
  271.         res += tmp;
  272.         i++;
  273.     }
  274.     return res;
  275. }
  276.  
  277. polynomial* polynomial::sort(){
  278.     std::sort(this->ms.begin(), this->ms.end(), [](monomial* a, monomial* b) { return a->getDeg() < b->getDeg(); });
  279.     return this;
  280. }
  281.  
  282. polynomial* polynomial::rand(int n){
  283.     polynomial* r = new polynomial;
  284.     mt19937 rng;
  285.     rng.seed(random_device()());
  286.     uniform_int_distribution<mt19937::result_type> dist1(0, 5); // distribution in range [0, 5]
  287.     uniform_int_distribution<mt19937::result_type> dist2(1, n * 2);
  288.     for (int i = 0; i < n; i++){
  289.         int ra = std::rand();
  290.         double coef = dist1(rng);
  291.         double deg = dist2(rng);
  292.         monomial* m = new monomial(coef, (int)deg);
  293.         *r += *m;
  294.         delete m;
  295.     }
  296.     return r;
  297. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!