Я знаю это,
(a*b)%m = ((a%m)*(b%m))%m
Но есть вероятность переполнения. Для простоты предположим, что размер целого числа равен 2 битам. Если a = 2 (т.е. 102) и b = 2 (т.е. 102), m = 3 (т.е. 112), то a%m и b%m оказываются равными 2, а после умножения получается 4 (т.е. 100), что не соответствует целочисленному размеру. Окончательный ответ будет 0, если считать 2-младшие из 4. Но фактический ответ равен 1.
Что мне делать, чтобы избежать этой ситуации?
Если m-1 в квадрате не подходит для вашего целочисленного типа, вам нужно выполнить длинное умножение. Для вашего двухбитного примера это означает разбиение ваших двухбитных чисел на пары однобитных чисел (старший бит и младший бит) и умножение всех четырех пар (старший на старший, высокий на низкий, низкий на высокий, низкий по низу) индивидуально. Затем вы можете получить результат по модулю m для каждой пары (отмечая фактические места, которые они представляют, т. е. четверки, двойки или единицы) и добавить результаты по модулю m.
m для каждой пары (отмечая фактические места, которые они представляют, то есть четверки, двойки или единицы): есть ли простой способ сделать это? Если (скажем) я работаю с 16-битными целыми числами, и у меня есть смещение 0x05F4 на один байт (т.е. фактически 0x05F400), как вычислить результат этого мода 0x6C31?
- person ruakh; 01.02.2015
x<<n по модулю m равно x по модулю m, умноженному на 1<<n по модулю m, поэтому вам просто нужно знать значение 1<<n для каждого сдвига n, задействованного в длинном умножении. Для процедуры, которую я описал, есть только один такой n: 1 для двухбитного примера, а также 8, если вы умножали два 16-битных целых числа по модулю m. 1<<n mod m — это единственная константа, которую вы можете предварительно вычислить и жестко закодировать.
- person R.. GitHub STOP HELPING ICE; 01.02.2015
1<<n mod m — это единственная константа, которую вы можете предварительно вычислить и жестко закодировать: я не уверен, почему вы так говорите. Я не вижу никаких указаний на то, что m является более жестко запрограммированным, чем a или b.
- person ruakh; 01.02.2015
1<<n по модулю m, если m не является константой, вы просто используете тот факт, что 1<<n соответствует вашему целочисленному типу (n составляет половину ширины) и вычисляете его напрямую. Это легкая часть. Потенциально сложной частью является умножение результата на x.
- person R.. GitHub STOP HELPING ICE; 01.02.2015
многие реализации C для небольших процессоров могут напрямую проверять результат математической операции на переполнение/недостаточное переполнение.
Другой способ — использовать принимающее поле, длина которого в два раза больше базового размера int IE. для размера int 2 используйте поле результата размером 4 байта. (возможно, с помощью длинного длинного int) или перенести оба числа в поля типа double и умножить их, а затем преобразовать обратно в int (однако некоторая точность в результате (т.е. младшая значащая цифра) может быть неточной.
Другой способ — использовать соответствующую функцию из библиотеки math.h.
Другой способ — использовать длинное умножение с использованием массивов: он был скопирован из http://www.cquestions.com/2010/08/multiplication-of-large-numbers-in-c.html
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000
char * multiply(char [],char[]);
int main(){
char a[MAX];
char b[MAX];
char *c;
int la,lb;
int i;
printf("Enter the first number : ");
scanf("%s",a);
printf("Enter the second number : ");
scanf("%s",b);
printf("Multiplication of two numbers : ");
c = multiply(a,b);
printf("%s",c);
return 0;
}
char * multiply(char a[],char b[]){
static char mul[MAX];
char c[MAX];
char temp[MAX];
int la,lb;
int i,j,k=0,x=0,y;
long int r=0;
long sum = 0;
la=strlen(a)-1;
lb=strlen(b)-1;
for(i=0;i<=la;i++){
a[i] = a[i] - 48;
}
for(i=0;i<=lb;i++){
b[i] = b[i] - 48;
}
for(i=lb;i>=0;i--){
r=0;
for(j=la;j>=0;j--){
temp[k++] = (b[i]*a[j] + r)%10;
r = (b[i]*a[j]+r)/10;
}
temp[k++] = r;
x++;
for(y = 0;y<x;y++){
temp[k++] = 0;
}
}
k=0;
r=0;
for(i=0;i<la+lb+2;i++){
sum =0;
y=0;
for(j=1;j<=lb+1;j++){
if(i <= la+j){
sum = sum + temp[y+i];
}
y += j + la + 1;
}
c[k++] = (sum+r) %10;
r = (sum+r)/10;
}
c[k] = r;
j=0;
for(i=k-1;i>=0;i--){
mul[j++]=c[i] + 48;
}
mul[j]='\0';
return mul;
}
Пример вывода приведенного выше кода:
Введите первое число: 55555555
Введите второй номер: 3333333333
Умножение двух чисел:
185185183314814815
Логика умножения больших чисел
Как мы знаем, в c нет таких типов данных, которые могут хранить очень большие числа. Например, мы хотим решить выражение:
55555555 * 3333333333
Результатом приведенного выше выражения является очень большое число, выходящее за пределы диапазона даже long int или long double. Тогда вопрос в том, как хранить такие большие числа в c?
Решение очень простое, то есть использование массива. Вышеприведенная программа использовала ту же логику, что и мы, как обычную логику, для умножения двух чисел, за исключением того, что вместо сохранения данных в обычных переменных мы сохраняем их в массив.
