C++: умножение больших чисел

Странно, где-то уже выложен код для умножения больших чисел, но сейчас нашёл только вот это.

Проверено в консоли Visual Studio 2015.

Первая программка просто вычисляет 2 в сотой степени, используя функцию умножения обычного числа int на массив цифр, ответ

2^100 = 1267650600228229401496703205376

#include <iostream>
using namespace std;

#define MAX_DIGITS 100000 /*максимально допустимое количество цифр*/

int multiply(int x, int res[], int res_size) { 
 //Умножаем x на число res[], его количество цифр д.б. в res_size
 //Изменит массив res и вернёт новый res_size
 int temp = 0;
 for (int i = 0; i < res_size; i++) {
  int prod = res[i] * x + temp;
  res[i] = prod % 10;
  temp = prod / 10;
 }
 while (temp) {
  res[res_size] = temp % 10;
  temp = temp / 10;
  res_size++;
 }
 return res_size;
}

void power (int x, int n) { //x в степени n
 int res[MAX_DIGITS];
 int res_size = 0;
 int temp = x;

 while (temp != 0) { //Заполнение массива
  res[res_size++] = temp % 10;
  temp = temp / 10;
 }
 for (int i = 2; i <= n; i++) //Вычисление x в степени n умножением
  res_size = multiply(x, res, res_size);
 
 cout << x << "^" << n << " = ";
 for (int i = res_size - 1; i >= 0; i--) cout << res[i];
}

int main() {
 int exponent = 100;
 int base = 2;
 power(base, exponent);
 cin.get(); return 0;
}

Вторая программа использует работу со строковыми буферами и говорит, что

12345678*87654321=1082152022374638

Excel выводит число на 2 больше, но умножение в столбик легко показывает, что 2 последние цифры именно 38 :)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#define MAX_DIGITS 1000
using namespace std;

void reverse(char *from, char *to) { //обращение строки char *
 int len = strlen(from);
 int l;
 for (l = 0; l<len; l++) to[l] = from[len - l - 1];
 to[len] = '\0';
}

void call_mult(char *first, char *second, char *result) {
 char F[MAX_DIGITS], S[MAX_DIGITS], temp[MAX_DIGITS];
 int f_len, s_len, f, s, r, t_len, hold, res;
 f_len = strlen(first);
 s_len = strlen(second);
 reverse(first, F);
 reverse(second, S);
 t_len = f_len + s_len;
 r = -1;
 for (f = 0; f <= t_len; f++)temp[f] = '0';
 temp[f] = '\0';
 for (s = 0; s<s_len; s++) {
  hold = 0;
  for (f = 0; f<f_len; f++) {
   res = (F[f] - '0')*(S[s] - '0') + hold + (temp[f + s] - '0');
   temp[f + s] = res % 10 + '0';
   hold = res / 10;
   if (f + s>r) r = f + s;
  }
  while (hold != 0) {
   res = hold + temp[f + s] - '0';
   hold = res / 10;
   temp[f + s] = res % 10 + '0';
   if (r<f + s) r = f + s;
   f++;
  }
 }
 for (; r>0 && temp[r] == '0'; r--);
 temp[r + 1] = '\0';
 reverse(temp, result);
}

int main() {
 char first[MAX_DIGITS], second[MAX_DIGITS], result[MAX_DIGITS];
 strcpy (first,"12345678");
 strcpy (second, "87654321");
 call_mult(first, second, result);
 int len = strlen(result);
 cout << first << '*' << second << "=" << result;
 cin.get(); return 0;
}

28.02.2018, 13:56 [5023 просмотра]