����������: ������ �����: ������� ����������.

��������� - ���������� �������� �������� ����������� ������� � (!) ��������� �������-��������� ������ � ���.

������ ������������� ������� �� ����� �����. ������, ������� ����� N �������������� � ����

B - ��������� ������� ���������, � ������� ������������ �����. ��� x_i - ����������� ����� /long ��� double, ��������/ � 0 <= x_i < B

��� ������ ������� ����� ������ ������ �����, ������ �������� e - ����� �������, � ����������� �� ������� �� ������ �� ������ ���� '�������' � ������� ����� y, ������ ��������� ��������.

���� ����� ���� �������� ��������, ���� ��� x_i < 0.

��������� B ������ ������� �� ������������� ������� �������� ���� ������ �� ����������, � ����������, ������ �� ��������� �����������:

• ��������� B ��������� ��� ���� �� ������� ����� ������
  
  
• B ������ ���� ��� ����� ������, ����� ��������� ������ ������������� �������� ����� � ��������� �������� �������� � ����, �� ���������� ������ �������, ����� ��� �������� � �������������� ������������ ������� ��� ������.
  
  
• ��� �������� ����� ������� B ��� ������� 10 ( ����� ����������, ������� ). B - ������� ������ ��������� ��������� ������� �������� �� ������ ������. ����� ����� � ����, ��� ������� ������� �� ��������� B = 2^m � B = 10ⁿ ��� ������� ����� ����������� ������ � ������ ��������.
  ��������� ������, �������� ����������� ��������, ����� ������������ ���������� ��� B = 2^m, ��� ��� ����� - ���������� �� ��� ���.

��� ������������� x_i ����������� ������� ��� long (� C�). ������, long ������ �������� 32 ����, � ������������� double (�� - ������ 53 ����) ���� ����������� �������� ������� ���������.

����� ����, ��������� ���������� ( ����. pentium ) ���������� �������������� ��� �������� � ��������� ������, ������� ����� �������� double.

typedef double Real;
typedef struct BigIntTag {
  Real * Coef;
  long Size, SizeMax;
} BigInt;

#define BASE 10000.
#define invBASE 0.0001   //   B-1
#define NBDEC_BASE 4     //  ����� ������ � B

2.1   �������������� � ������������� ����

������� �� ��������������� �������������

������� � i = 0, ����� � �������� x_i �� B � ������������ ������� �� x_i+1.

void UpdateBigInt(BigInt * A)
{
  long i;
  Real carry=0., x;

  for (i=0; i<A->Size; i++) {
    x = A->Coef[i] + carry;
    carry = floor(x*invBASE);
    A->Coef[i] = x-carry*BASE;
  }
  if (carry!=0) {
    while (carry!=0.) {
      x = carry;
      carry = floor(x*invBASE);
      A->Coef[i] = x-carry*BASE;
      i++;
      A->Size=i;
    }
    if (A->Size > A->SizeMax) {
      printf("Error in UpdateBigInt, Size > SizeMax\n");
    }
  }
  else {
    while (i>0 && A->Coef[i-1]==0.) i--;
    A->Size=i;
  }
}

2.2   ����� � ��������.

C��������� ������������ � ������������ �������������� � ������������� ���� ��� ��������, ���������� - ��������.

/*
 *  C = A + B
 */
void AddBigInt(BigInt * A, BigInt * B, BigInt * C)
{
  long i;

  if (A->Size < B->Size) {
    AddBigInt(B,A,C);
    return;
  }
  /* We now have B->Size < A->Size */
  for (i=0; i < B->Size; i++)
    C->Coef[i] = A->Coef[i] + B->Coef[i];
  for (; i < A->Size; i++) 
    C->Coef[i] = A->Coef[i];

  C->Size = A->Size;
  UpdateBigInt(C);
}

2.3   ��������� �� ����� �����.

����� q - ����� �����, ��� qB �������� ��� ��� ������ �������������. ����� ������������ x �� q ��������, ������� ������ x_i �� q � ����������� ������� � i = 0 � �����.

2.4   ������� �� ����� �����.

������� � i = n, ����� ������ x_i �� q � ������������ �������, ���������� �� B � x_i-1 � ��� �����.

2.5   ������� ������������ ���� ������� �����.

����� ���� 2 ������� ����� � ������������ �����:

������� ����� Z = X*Y ����� ���� ��������� �� �������:

����� ������.

• Generalized Arithmetic in C++
����� ������������� ������� �����, ������� ��� ����������������. �����������, ��� ������������: ���������� ��� ������� �����, ����� �����, ����������� ��� ��������.

����� �� ��������, � ���������� � ���������