for (i=Lq-l; i>=0; i--) quot.P[i] = 0; rem = num;

if (rem.P[n] >= denom.P[r]) { rem.SetLen(rem.P.size() + 1); n++;

quot.SetLen(Lq + 1) ;

d = denom.P[r];

for (int k=n; k>r; k--)

{ q = DDquotient(rem.P[k], rem.P[k-l], d); subtractmul(&rem.P[k - r - 1], &denom.P[0],

r + 1, q) ; quot.P[k - r - 1] = q;

quot.reduceO ; quot.neg = QuotNeg; if (RemDesired)

{ unnormalize(rem, x, SecondDone); rem.neg = RemNeg;

bool operator==(const large &x, const large &y)

{ return x.compare(y) == 0;

bool operator<(const large &x, const large &y)

{ return x.compare(y) < 0;

bool operator!=(const large& x, const large& y)

{ return x.compare(y) != 0;

bool operator>(const large& x, const large& y)

{ return x.compare(y) > 0;

Функция num2char преобразует объект x класса large в его символьное представление s в обратном порядке: void large::num2char(vector<char> &s) const { large x = *this;

static uint plO = 1, iplO = 0;

if (x.P.sizeO == 0) s.push back(0); else

{ uint r;

if (plO == 1)

{ while (plO <= UINT MAX/10) { plO *= 10; iplO++;

} plO является максимальной степенью 10, представляемой с помощью uint

LP10 = р10 = powdO, iplO) large R, LPIO = plO; bool neg = x.neg; do

{ X.divide(LPIO, x, R, 1);

r = (R.P.size() ? R.P[0] : 0); for (uint j=0; j<iplO; j++) { s.push back(char(r % 10 + 0 )); r /= 10;

if (r + X.P.sized == 0) break;

} while (x.P.size());

if (neg) s.push back(-) ;

lis содержит строку в обратном порядке

ostream &operator (ostream &os, const large &x) { vector<char> s; x.num2char(s);

vector<char>::reverse iterator i;

for (i=s .rbegin 0 ; i != s.rendO; ++i) os *i;

return os;

istream &operator>>(istream &is, large &x) { char ch; X = 0;

bool neg = 0; is ch;

if (ch == - ) { neg = 1; is.get(ch);

while (isdigit(ch)) { X = X * 10 + (ch - 0); is.get(ch);

if (neg) X = -x; is.putback(ch); return is;

large abs(large a) { if (a < 0) a = -a; return a;

large sqrt(const large &a) { large x = a, b = a, q; b = 1;

while (b >>= 2, b > large(O)) x = 1; while (x > (q = a/x) +1 II x < q - 1) { x += q; x = 1; }

return x < q ? x : q;

large power(large x, uint n) { large y=l; while (n)

{ if (n & 1) у *= x; x *= x; n = 1;

return y;

8.3. Вычисление числа n

Хотя класс large предназначен для представления больших целых чисел, мы можем использовать его для приближенного представления вещественных чисел, если будем использовать соответствующее масштабирование. Давайте продемонстрируем это путем вычисления числа к с произвольной степенью точности. Один из известных способов вычисления этой константы с помощью формулы

7t = 16 arctan - 4 arctan jJg-

Джона Мачина (1680 -1752). Вместо этого мы воспользуемся формулой

7t = 48 arctan fg- + 32 arctan - 20 arctan (1)

которая предпочтительнее, поскольку наименьший знаменатель в этой формуле (18) больше, чем в формуле Мачина (5). Математики, интересующиеся задачей вычисления числа к, могут обратиться к книге Borwein, J.M. and Borwein, Р.В. (1987) Pi and the AGM, в которой приведены более сложные алгоритмы. Поскольку нас интересует программирование, мы просто примем приведенную формулу с тремя арктангенсами без доказательства. В свою очередь, функцию арктангенса мы будем аппроксимировать с помощью алгебраических операций путем приближенного вычисления следующего ряда:

arctan х- + - + ... (2)