Привет, Хабр!
Язык С++, безусловно является одним из передовых языков разработки ПО, занимая пограничное место между языками высокого уровня и языками низкого уровня. Этот язык предоставляет различные типы данных для обработки информации. Для целых чисел существую стандартные операторы обычных арифметических операций.
Ок, а если мне нужно оперировать с числами, длина которых 200 знаков? А если 200 000 знаков?
На мой взгляд, тут есть два пути: либо мы пишем свой низкоуровневый тип данных (аналогично int) и т.д., либо мы создаем отдельный класс по работе с нужными на числами и перегружаем операторы. В любом случае, функции, оперирующие с такими числами, нам придется писать самим.
Гугл интернетов показал, что существуют довольно разные алгоритмы быстрого умножения. Конечно, скорее всего, они в разы лучше того, что предложу я, но мой намного проще для понимания, так как мы его знаем все, и довольно давно :)
Итак, первое что приходит в голову — это то, что умножение есть ничто иное, как сложение первого числа самого с собой n раз, где n равно второму числу. И правда, написать сложение двух больших чисел совсем несложно, если каждое число представляет собой массив int (сложение столбиком):
Этот код будет записывать результат в конец статического массива(т.е. перед результатом будут нули, раз он статичен)
Но это будет настоооолько медленно, что ни в какие рамки не лезет.
Тогда делаем второе, что приходит в голову :) Произведем умножение столбиком.
Но как это сделать?
Да также, как и в уме. Тут будут только две хитрости. Первая и основная — это индексация элементов массивов. Для простоты приведу картинку и код. Думаю, так будет проще, нежели объяснять на словах:
то есть делаем вот что:
Вот и всё! Единственное, что нужно учитывать — в каждом разряде у нас сейчас могут быть двузначные числа. То есть в единицах может быть 89 к примеру, а в десятках 234. Непорядок! Приберем это дело одним циклом:
И остается только результат в массиве сдвинуть в начало. (Я надеюсь, вы еще помните, что у нас статический массив int, и пишем мы в конец?)
Работает такой способ очень шустро. Конечно, можно ускорить код, используя динамические массивы и прочее прочее, но статья направлена на то, чтобы донести сам алгоритм.
Прикрепляю также полный проект программы (VC++ 2010) и exe в архиве отдельно.
upwap.ru/1558125
ПыСы.
В программе также реализовано сложение и вычитание столбиком =) До деления дойти как-то лень стало. Юзаем так: вводим первое число, потом второе, потом знак действия (+-*)
Язык С++, безусловно является одним из передовых языков разработки ПО, занимая пограничное место между языками высокого уровня и языками низкого уровня. Этот язык предоставляет различные типы данных для обработки информации. Для целых чисел существую стандартные операторы обычных арифметических операций.
Ок, а если мне нужно оперировать с числами, длина которых 200 знаков? А если 200 000 знаков?
На мой взгляд, тут есть два пути: либо мы пишем свой низкоуровневый тип данных (аналогично int) и т.д., либо мы создаем отдельный класс по работе с нужными на числами и перегружаем операторы. В любом случае, функции, оперирующие с такими числами, нам придется писать самим.
Гугл интернетов показал, что существуют довольно разные алгоритмы быстрого умножения. Конечно, скорее всего, они в разы лучше того, что предложу я, но мой намного проще для понимания, так как мы его знаем все, и довольно давно :)
Итак, первое что приходит в голову — это то, что умножение есть ничто иное, как сложение первого числа самого с собой n раз, где n равно второму числу. И правда, написать сложение двух больших чисел совсем несложно, если каждое число представляет собой массив int (сложение столбиком):
int i,j=0;
for (i=str_len-1,j=str_len2-1;i>=0;i--,j--)
{
if ((ar1[i]+ar2[i])<10) //если "в уме" ничего держать не надо то просто прибавляем
{
res[j]=(ar1[i]+ar2[i]);
}
else//иначе прибавляем только то, что меньше 10, а стальное-в следующий разряд числа
{
res[j]=(ar1[i]+ar2[i]-10);
for (int s=(i-1);s>=0;s--)
{
if (ar1[s]<9)
{
ar1[s]++;
break;
}
else
{
ar1[s]=0;
continue;
}
}
}
}
Этот код будет записывать результат в конец статического массива(т.е. перед результатом будут нули, раз он статичен)
Но это будет настоооолько медленно, что ни в какие рамки не лезет.
Тогда делаем второе, что приходит в голову :) Произведем умножение столбиком.
Но как это сделать?
Да также, как и в уме. Тут будут только две хитрости. Первая и основная — это индексация элементов массивов. Для простоты приведу картинку и код. Думаю, так будет проще, нежели объяснять на словах:
то есть делаем вот что:
int i,j=0;
{
for (i=0;i<=ras2-1;i++)
{
for (j=0;j<=ras1-1;j++)
{
result[(str_len*str_len-1)-(i+j)]=result[(str_len*str_len-1)-(i+j)]+((ar1[(str_len-1)-j])*(ar2[(str_len-1)-i]));
}
}
}
Вот и всё! Единственное, что нужно учитывать — в каждом разряде у нас сейчас могут быть двузначные числа. То есть в единицах может быть 89 к примеру, а в десятках 234. Непорядок! Приберем это дело одним циклом:
for (i=str_len*str_len;i>=0;i--)
{
if (result[i]>9)
{
result[i-1]=result[i-1]+((result[i]/10));
result[i]=result[i]-(((result[i]/10)*10));
}
}
И остается только результат в массиве сдвинуть в начало. (Я надеюсь, вы еще помните, что у нас статический массив int, и пишем мы в конец?)
Работает такой способ очень шустро. Конечно, можно ускорить код, используя динамические массивы и прочее прочее, но статья направлена на то, чтобы донести сам алгоритм.
Прикрепляю также полный проект программы (VC++ 2010) и exe в архиве отдельно.
upwap.ru/1558125
ПыСы.
В программе также реализовано сложение и вычитание столбиком =) До деления дойти как-то лень стало. Юзаем так: вводим первое число, потом второе, потом знак действия (+-*)