Арифметика великих чисел - Методи розв'язування задач

Відомо, що операції з числовими значеннями в комп’ютері відбувається з обмеженою кількістю розрядів. Але трапляються випадки, коли приходиться обчислювати числа де кількість знаків становить 20, 100, 1000. Такі числа використовуються в астрономії, мікрофізиці, комбінаториці.

Для реалізації операцій з довгими числами необхідно розмістити довге число в пам’яті комп’ютера. Розмістимо довге число в цілочисельний масив. В кожну комірку пам’яті помістимо по декілька цифр (для початку 1 цифру) В нульовій комірці пам’яті будемо зберігати кількість цифр довгого числа. Розвернемо масив для зручності уявлення розміщення цифр.

Запишемо число: 475739541

Масив M:

Номер елементів масиву	9	8	7	6	5	4	3	2	1	0
Елементи масиву	4	7	5	7	3	9	5	4	1	9

Для реалізації довгої арифметики створимо такі функції:

занесення довгого числа в масив;
виведення довгого числа;
додавання двох довгих чисел;
порівняння довгих чисел;
множення довгого числа на коротке;
множення двох довгих чисел;
ділення довгого числа на коротке;
ділення довгого на довге число.

Довге число зручно вводити у вигляді рядка, при цьому у нульовій комірці розміщується цифра самого високого розряду, а останньою розміщена цифра першого розряду. Розвернемо (реверсуємо) рядок і запишемо кожну цифру в окрему комірку цілочисельного масиву. Для цього напишемо функцію:

// Переведення з рядка в масив int

void strtomasiv(char *str, int *T)
{
	int i;

	T[0] = strlen(str); // Знаходження кількості знаків у числі

for (i = 0; i < T[0]; i++)

				T[T[0] - i] = str[ i] -  '0';  // переведення з символів у цифри і занесення їх у числовий масив

// одночасно розвертаємо масив

Функція strtomasiv отримує довге число у вигляді символьного масиву *str, і повертає також через параметри масив *T типу int.

Для прискорення операцій з довгими цифрами у кожну комірку заносять не одну цифру, а декілька. Число типу int (long) у мові С++ може пам’ятати 10 знаків. Враховуючи діапазон данного типу (перша цифра максимального числа не перевищує 2) ми можемо записати у кожну комірку пам’яті массиву по 9 цифр при додаванні та 4 цифри при множенні.

// Переведення з рядка в масив int// із занесенням по K знаків у кожну коміркуvoid strtomasiv(char *str, int *T)
{
  int i, j , p, n, K;
  char temp[10];
  
  K = 2;
  T[0] = (strlen(str) / K) + 1; // кількість "розрядів" довгого числаfor (i = 1; i < T[0] + 1; i++)
  {
    strncpy(temp, str + ((i - 1) * K), K); //копіювання "розряду" довгого числа
  	
    p = 0;
    n = strlen(temp); // розмір "розряду" - може бути меншим за Kfor (j = 0; j < n; j++)
      p = (p * 10) + (temp[j] - '0'); // перетворення рядкового значення "розряду" до числа

    T[i] = p;
  }
}

Для виведення довгих чисел також рекомендується написати окрему функцію.

Під час виведення масиву довгого числа, де в кожній комірці знаходиться лише по одній цифрі не виникає ніяких проблем, необхідно просто вивести масив у зворотному порядку.

// Виведення довгого числаvoid out1(int *T)
{
  int i, j, p;

  // перебираємо всі розряди числа від найстаршогоfor (i = T[0]; i > 0; i--)
  {
  	cout << T[i];
  }
  
  cout << endl;
}

Якщо виводите масив, де в кожній комірці знаходиться по декілька цифр - можливі проблеми з виведенням ведучих нулів. Якщо нам потрібно вивести, наприклад, число 12030002, і в кожній комірці знаходтться по 4 цифри, то ми отримуємо масив з двох комірок, T[1]=2, та T[2]=1203. Під час виведення за допомогою функції, наведеної вище, ми отримаємо 12032. Ми втрачаємо три розряди, значення яких дорівнюють 0. В такому випадку необхідно застосувати форматований вивід. Для цього скористаємось двома флагами форматованого виведення:

void out2(int *T)
{
  int i, p;

  for (i = T[0]; i > 0; i--)
  {
    cout << T[i];
  	
    cout.width(K); //задається ширина поля виведення К знаків з вирівнюванням по правому краю
    cout.fill('0'); //заповнення пустих позицый символом '0'.
  }
  
  cout << endl;
}

void out2(int *T)

{

int i, p;

for (i = T[0]; i > 0; i--)

{

cout << T[i];

cout.width(K); //задається ширина поля виведення К знаків з вирівнюванням по правому краю

cout.fill('0'); //заповнення пустих позицый символом '0'.

}

cout << endl;

}

Додавання цілих довгих чисел. Процес додавання довгих чисел – це реалізація додавання чисел "в стовпчик". Перше число – масив T1, друге число – масив T2, результат – T3.

Наприклад:

longhand_add

void add(int *T1, int *T2, int* T3) //додавання довгих чисел T3=T1+T2;
{
    int n = (T1[0] > T2[0]) ? T1[0] : T2[0]; // знаходиться кількість цифр більшого  числаint p = 0, i, R = pow(10, K);

    for (i = 1; i <= n; i++)
    {
        int temp = T1[i] + T2[i] + p;
		T3[i] = temp % R; // виділення результуючої групи цифр
        p = temp / R; // виділення цифри, що виходить за розрядність групи
    }
    
    if (p > 0) 
    {
    	n++; 
    	T3[n] = p; 
    }
    
    T3[0] = n;
}

Порівняння довгих чисел.

Функція порівняння довгих чисел повертає 0 – коли числа рівні, 1 - коли перше число більше за друге і -1 - коли друге число більше першого. Під час реалізації спершу порівнюється кількість цифр. Якщо кількість цифр різна, то у більшого числа більше кількість цифр. Якщо ж кількість цифр однакова, то порівнюють всі цифри по порядку, починаючи зі старшого розряду. Даний алгоритм буде працювати правильно і у випадку коли в одній комірці пам’яті масиву будемо зберігати декілька цифр.

// Порівняння довгих чисел: 0 - рівні, 1 - (T1 > T2), -1 - (T1 < T2)int compare(int *T1,int  *T2)
{
    int i;

    if (T1[0] > T2[0]) // якщо в T1 цифр більше, ніж в T2return 1;
    elseif (T1[0] < T2[0]) // якщо в Т2 цифр більше, ніж в Т1return -1;
    else
    {
        for (i = 1; i < T1[0]; i++)
        {
            // якщо чергові цифри співпадають - перевіряємо даліif (T1[i] == T2[i])
                continue;
            elseif (T1[i] > T2[i])
                return 1;
            elsereturn -1;
        }

        // якщо перевірили всі цифри, і всі рівні - числа рівніreturn 0;
    }
}

Множення довгого числа на коротке

Виконується множення "в стовпчик" на одноцифрове число. Дана операція може бути корисна для виконання простих операцій, таких як множення на 2 або використана при діленні довгого числа на довге. Різниця між множенням на коротке число і множенням на довге полягає в тому, що при множенні на коротке число нам не потрібно множити розряди довгого числа на відповідні розряди короткого числа.

// Множення довгого числа на коротке: T1 = T1*k

void mult(int *T1, int k)
{
	int i, p = 0, R = pow(10, K);

	for (i = 1; i <= T1[0]; i++)
	{
		int temp = (T1[i] * k) + p;
		T1[i] = temp % R;
		p = temp / R;
	}

	while (p > 0)
	{
		T1[0]++;
		T1[T1[0]] = p % R;
		p /= R;
	}
}

Множення двох довгих чисел

// Множення довгого числа на довге: T3 = T1 * T2

void multDD(int *T1, int *T2, int *T3)
{
    int i, j, p = 0, R = pow(10, K);

    for (i = 1; i <= T2[0]; i++)
    {
        for (j = 1; j <= T1[0]; j++)
        {
            int temp = (T2[i] * T1[j]) + p + T3[j + i - 1];

            T3[i + j - 1] = temp % R;

            p = temp / R;
        }

        T3[i + j - 1] = p;
        
        p = 0;
    }

    int n = T2[0] + T1[0] - 1;

    while (p > 0)
    {
        T3[n] = p % R;
        p /= R;
        n++;
    }

    if (T3[n + 1] > 0)
        T3[0] = n + 1;
    else
        T3[0] = n;
}