API tools faq
paste
Advertisement
peltorator

Long Doubles

peltorator
Oct 7th, 2018
441
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.67 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!