peltorator

Long Doubles

Oct 7th, 2018
206
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef __int128 ll;
  2. typedef long double ld;
  3.  
  4. const int D = 10;
  5. const ll T = 1e16, Q = 16, K = 10;
  6.  
  7. void printd(ll k)
  8. {
  9.     vector<int> a;
  10.     for (int i = 0; i < Q; i++)
  11.     {
  12.         a.push_back(k % K);
  13.         k /= K;
  14.     }
  15.     for (int i = Q - 1; i >= 0; i--)
  16.         cout << a[i];
  17. }
  18.  
  19. struct Double
  20. {
  21.     int sgn;
  22.     vector<ll> dig;
  23.     int st;
  24.  
  25.     Double()
  26.     {
  27.         sgn = 0;
  28.     }
  29.  
  30.     void rem()
  31.     {
  32.         while (dig.size() < D)
  33.             dig.push_back(0);
  34.         while (dig.size() > D)
  35.             dig.pop_back();
  36.         for (int i = D - 1; i > 0; i--)
  37.         {
  38.             dig[i - 1] += dig[i] / T;
  39.             dig[i] %= T;
  40.         }
  41.  
  42.         reverse(dig.begin(), dig.end());
  43.         while (dig.back() >= T)
  44.         {
  45.             int z = dig.size() - 1;
  46.             dig.push_back(dig[z] / T);
  47.             dig[z] %= T;
  48.  
  49.         }
  50.         while (dig.size() && !dig.back())
  51.             dig.pop_back(), st--;
  52.         if (!dig.size())
  53.         {
  54.             sgn = 0;
  55.             while (dig.size() < D)
  56.                 dig.push_back(0);
  57.             return;
  58.         }
  59.         reverse(dig.begin(), dig.end());
  60.         while (dig.size() < D)
  61.             dig.push_back(0);
  62.         while (dig.size() > D)
  63.             dig.pop_back();
  64.     }
  65.  
  66.     Double(ll p, ll q = 1)
  67.     {
  68.         if (p == 0)
  69.         {
  70.             sgn = 0;
  71.             dig.assign(D, 0);
  72.             st = 1;
  73.             return;
  74.         }
  75.         sgn = 1;
  76.         if (p < 0)
  77.         {
  78.             p = -p;
  79.             q = -q;
  80.         }
  81.         if (q < 0)
  82.         {
  83.             sgn = -1;
  84.             q = -q;
  85.         }
  86.         ll t = p / q;
  87.         ll a = p % q;
  88.         while (t)
  89.         {
  90.             dig.push_back(t % T);
  91.             t /= T;
  92.         }
  93.         reverse(dig.begin(), dig.end());
  94.         st = dig.size() - 1;
  95.         a *= T;
  96.         ll b = q;
  97.         while (dig.size() < D)
  98.         {
  99.             dig.push_back(a % b);
  100.             a /= b;
  101.             a *= T;
  102.         }
  103.         (*this).rem();
  104.     }
  105.  
  106.     void print()
  107.     {
  108.         (*this).rem();
  109.         if (sgn == 0)
  110.         {
  111.             cout << "0\n";
  112.             return;
  113.         }
  114.         if (sgn == -1)
  115.             cout << "-";
  116.         if (st < 0)
  117.         {
  118.             cout << "0.";
  119.             for (int i = 1; i < abs(st); i++)
  120.                for (int j = 0; j < Q; j++)
  121.                    cout << 0;
  122.             for (ll i : dig)
  123.                 printd(i);//cout << i;
  124.             cout << '\n';
  125.             return;
  126.         }
  127.         if (st + 1 >= dig.size())
  128.         {
  129.             bool ok = 0;
  130.             for (ll i : dig)
  131.             {
  132.                 if (ok)
  133.                     printd(i);//cout << i;
  134.                 else
  135.                     cout << (long long)i;
  136.                 ok = 1;
  137.             }
  138.             for (int i = 0; i <= st - dig.size(); i++)
  139.                 for (int j = 0; j < Q; j++)
  140.                     cout << 0;
  141.             cout << '\n';
  142.             return;
  143.         }
  144.         for (int i = 0; i <= st; i++)
  145.             if (i)
  146.                 printd(dig[i]);//cout << dig[i];
  147.             else
  148.                 cout << (long long)dig[i];
  149.         cout << ".";
  150.         for (int i = st + 1; i < dig.size(); i++)
  151.             printd(dig[i]);//cout << dig[i];
  152.         cout << '\n';
  153.     }
  154.  
  155.     Double operator*(const Double &x) const
  156.     {
  157.         if (sgn == 0)
  158.             return *this;
  159.         if (x.sgn == 0)
  160.             return x;
  161.         Double ans;
  162.         ans.sgn = sgn * x.sgn;
  163.         ans.dig.assign(2 * D, 0);
  164.         ans.st = st + x.st + 1;
  165.         for (int i = 0; i < D; i++)
  166.             for (int j = 0; j < D; j++)
  167.                 ans.dig[i + j + 1] += dig[i] * x.dig[j];
  168.         for (int i = 2 * D - 1; i > 0; i--)
  169.             if (ans.dig[i] >= T)
  170.             {
  171.                 ans.dig[i - 1] += ans.dig[i] / T;
  172.                 ans.dig[i] %= T;
  173.             }
  174.         while (ans.dig.size() > D)
  175.             ans.dig.pop_back();
  176.         ans.rem();
  177.         return ans;
  178.     }
  179.  
  180.     bool operator==(const Double &x) const
  181.     {
  182.         if (sgn == 0)
  183.             return x.sgn == 0;
  184.         return (sgn == x.sgn && x.dig == dig && st == x.st);
  185.     }
  186.  
  187.     bool operator!=(const Double &x) const
  188.     {
  189.         if (sgn == 0 && x.sgn == 0)
  190.             return 0;
  191.         return (sgn != x.sgn || x.dig != dig || st != x.st);
  192.     }
  193.  
  194.     bool operator>(const Double &x) const
  195.     {
  196.         if (sgn != x.sgn)
  197.             return sgn > x.sgn;
  198.         if (sgn == 0)
  199.             return 0;
  200.         if (st != x.st)
  201.             return ((st > x.st) ^ (sgn == -1));
  202.         for (int i = 0; i < D; i++)
  203.             if (dig[i] != x.dig[i])
  204.                 return ((sgn == -1) ^ (dig[i] > x.dig[i]));
  205.         return 0;
  206.     }
  207.  
  208.     bool operator<(const Double &x) const
  209.     {
  210.         if (sgn != x.sgn)
  211.             return sgn < x.sgn;
  212.         if (sgn == 0)
  213.             return 0;
  214.         if (st != x.st)
  215.             return ((st < x.st) ^ (sgn == -1));
  216.         for (int i = 0; i < D; i++)
  217.             if (dig[i] != x.dig[i])
  218.                 return ((sgn == -1) ^ (dig[i] < x.dig[i]));
  219.         return 0;
  220.     }
  221.  
  222.     bool operator>=(const Double &x) const
  223.     {
  224.         return (*this) > x || (*this) == x;
  225.         if (sgn != x.sgn)
  226.             return sgn > x.sgn;
  227.         if (sgn == 0)
  228.             return 1;
  229.         if (st != x.st)
  230.             return ((st > x.st) ^ (sgn == -1));
  231.         for (int i = 0; i < D; i++)
  232.             if (dig[i] != x.dig[i])
  233.                 return ((sgn == -1) ^ (dig[i] > x.dig[i]));
  234.         return 1;
  235.     }
  236.  
  237.     bool operator<=(const Double &x) const
  238.     {
  239.         return (*this) < x || (*this) == x;
  240.         if (sgn != x.sgn)
  241.             return sgn < x.sgn;
  242.         if (sgn == 0)
  243.             return 1;
  244.         if (st != x.st)
  245.             return ((st < x.st) ^ (sgn == -1));
  246.         for (int i = 0; i < D; i++)
  247.             if (dig[i] != x.dig[i])
  248.                 return ((sgn == -1) ^ (dig[i] < x.dig[i]));
  249.         return 1;
  250.     }
  251.  
  252.  
  253.     Double operator-() const
  254.     {
  255.         Double ans = *this;
  256.         ans.sgn = -ans.sgn;
  257.         return ans;
  258.     }
  259.  
  260.    
  261.     Double operator-(Double x)
  262.     {
  263.         if (x.sgn == 0)
  264.             return (*this);
  265.         if (sgn == 0)
  266.             return -x;
  267.         if (sgn != x.sgn)
  268.             return (*this) + (-x);
  269.         if (sgn == -1)
  270.             return (-x) - (-(*this));
  271.         if (x == (*this))
  272.         {
  273.             Double y = x;
  274.             y.sgn = 0;
  275.             return y;
  276.         }
  277.         Double a = (*this), b = x;
  278.         bool cmp = (a > b);
  279.         if (!cmp)
  280.             swap(a, b);
  281.         Double ans;
  282.         reverse(a.dig.begin(), a.dig.end());
  283.         reverse(b.dig.begin(), b.dig.end());
  284.         while (a.st < b.st)
  285.         {
  286.             a.dig.push_back(0);
  287.             a.st++;
  288.         }
  289.         while (a.st > b.st)
  290.         {
  291.             b.dig.push_back(0);
  292.             b.st++;
  293.         }
  294.         reverse(a.dig.begin(), a.dig.end());
  295.         reverse(b.dig.begin(), b.dig.end());
  296.         while (a.dig.size() > D)
  297.             a.dig.pop_back();
  298.         while (b.dig.size() > D)
  299.             b.dig.pop_back();
  300.         ans.dig.assign(D, 0);
  301.         ans.st = a.st;
  302.         for (int i = 0; i < D; i++)
  303.             ans.dig[i] = a.dig[i] - b.dig[i];
  304.         for (int i = D - 1; i > 0; i--)
  305.             while (ans.dig[i] < 0)
  306.             {
  307.                 ans.dig[i] += T;
  308.                 ans.dig[i - 1]--;
  309.             }
  310.         ans.sgn = (cmp ? 1 : -1);
  311.         ans.rem();
  312.         return ans;
  313.     }
  314.  
  315.  
  316.     Double operator+(Double x)
  317.     {
  318.         if (sgn == 0)
  319.             return x;
  320.         if (x.sgn == 0)
  321.             return *this;
  322.         if (sgn != x.sgn)
  323.         {
  324.             return (*this) - (-x);
  325.         }
  326.         vector<ll> dig1 = dig;
  327.         int St = st;
  328.         reverse(dig1.begin(), dig1.end());
  329.         reverse(x.dig.begin(), x.dig.end());
  330.         while (St < x.st)
  331.         {
  332.             dig1.push_back(0);
  333.             St++;
  334.         }
  335.         while (St > x.st)
  336.         {
  337.             x.dig.push_back(0);
  338.             x.st++;
  339.         }
  340.         reverse(dig1.begin(), dig1.end());
  341.         reverse(x.dig.begin(), x.dig.end());
  342.         while (dig1.size() > D)
  343.             dig1.pop_back();
  344.         while (x.dig.size() > D)
  345.             x.dig.pop_back();
  346.         Double ans;
  347.         ans.sgn = x.sgn;
  348.         ans.dig.assign(D + 1, 0);
  349.         ans.st = St + 1;
  350.         for (int i = 0; i < D; i++)
  351.             ans.dig[i + 1] = dig1[i] + x.dig[i];
  352.         ans.rem();
  353.         return ans;
  354.     }
  355.  
  356.     Double rev() const
  357.     {
  358.         if (sgn == 0)
  359.         {
  360.             cerr << "DIVIDING BY ZERO\n";
  361.             exit(0);
  362.         }
  363.         Double x = (*this);
  364.         x.sgn = 1;
  365.         Double div(1);
  366.         Double ans;
  367.         ans.sgn = sgn;
  368.         ans.dig.clear();
  369.         ans.st = 1;
  370.         while (x < Double(1))
  371.         {
  372.             x.st++;
  373.             ans.st++;
  374.         }
  375.         while (div < x)
  376.             div.st++;
  377.         ans.st -= div.st + 1;
  378.         while (ans.dig.size() < D)
  379.         {
  380.             ll nxt = 0;
  381.             ll l = 0, r = T;/*
  382.             while (div >= x)
  383.             {
  384.                 div = div - x;
  385.                 nxt++;
  386.             }*/
  387.             while (r - l > 1)
  388.             {
  389.                 ll mid = (r + l) / 2;
  390.                 if (x * Double(mid) > div)
  391.                     r = mid;
  392.                 else
  393.                     l = mid;
  394.             }
  395.             div = div - x * Double(l);
  396.             nxt = l;
  397.             div.st++;
  398.             ans.dig.push_back(nxt);
  399.         }
  400.         ans.rem();
  401.       /*  cout << ans.sgn << endl;
  402.         cout << ans.st << endl;
  403.         cout << ans.dig.size() << endl;
  404.         for (int i : ans.dig)
  405.             cout << i << ' ';
  406.         cout << endl;
  407.         exit(0);*/
  408.         return ans;
  409.     }
  410.  
  411.     Double operator/(const Double &x) const
  412.     {
  413.         return (*this) * x.rev();
  414.     }
  415.  
  416.     Double operator*(const int &x) const
  417.     {
  418.         return (*this) * Double(x);
  419.     }
  420.  
  421.     Double operator/(const int &x) const
  422.     {
  423.         return (*this) / Double(x);
  424.     }
  425.  
  426. };
  427.  
  428. Double Sqrt(ll x)
  429. {
  430.     if (x <= 0)
  431.         return 0;
  432.     ll t = sqrt(x);
  433.     Double ans(t);
  434.     for (int i = 0; i < ans.dig.size(); i++)
  435.         ans.dig[i] = 0;
  436.     Double X = x;
  437.     for (int i = 0; i < D; i++)
  438.     {
  439.         ll l = 0, r = T;
  440.         while (r - l > 1)
  441.         {
  442.             ll mid = (r + l) / 2;
  443.             ans.dig[i] = mid;
  444.             if (ans * ans > X)
  445.                 r = mid;
  446.             else
  447.                 l = mid;
  448.         }
  449.         ans.dig[i] = l;
  450.     }
  451.     return ans;
  452. }
RAW Paste Data