Задать вопрос
@pinkhead_psd

Как сделать побитовое умножение и сложение большого числа decimal?

Пытаюсь реализовать функции сложения, вычитания, умножения и деления для структуры decimal, в общем как оригинальная библиотека, только у меня число не превышает 96 разряд, то есть у числа экспонента не выше 28 (это так для справки). Структура выглядит таким образом:
typedef struct {
  unsigned int bits[4];
} decimal;

Создал я два числа decimal num1 = {{45,55,0,0}}; decimal num2 = {{6,20,0,0}}, и хочу их умножить, чтобы получить в ответе 2 824 100, если бы была экспонента, то просто число представляло такой вид: decimal/10^exp. В одном объяснение предлагалось взять первое число = num1.bits[i], проходится побитово по нему, и если там 1, то к сумме прибавлять результат сдвига второго числа на индекс бита первого, то есть sum += num2.bits[i] * 2^j (sum += num2.bits[i] << j). Я попробовал сделать двумя представлениями, однако получаю либо число 2 701 370 137, а структура ответа выглядит таким образом decimal result = {{270, 1370, 1370,0}}, либо просто 200 decimal result = {{20, 0, 0,48}} (полная ерунда). Я так понимаю, проблема в том, что мне нужно учитывать переход одного разряда в другой, и делать правильное сложение и заполнение всей мантисы
Вот код умножения:
int mul(decimal value_1, decimal value_2, decimal *result)
{
    int ret = 0;
    *result = (decimal){0};
    decimal res = {0};
    int sum = 0;
    
    for (int i = 0; i < 3; i++)
    {
        int a = value_1.bits[i];
        int b = value_2.bits[i];
        
        for (int i = 0; i < 32; i++)
        {
            int bit = (a & (1u << i)) >> i;
            if (bit == 1)
            {
                sum += b * pow(2,i);//тут простое мат. умножение и в результате каждый int умножается правилно, но общее число не корректно
                // res.bits[i] += b << i;//здесь я сделал попытку побитово умножать, но делаю это заведомо неправильно
            }
        }
            printf("SUM: %d\n",sum);

        res.bits[i] = sum;
        printf("\n");
    }

    int sign = sign_1 ^ sign_2;
    *result = res;
    set_sign(result, sign);

    return ret;
}


Вот код сложения:
int add(decimal value_1, decimal value_2, decimal *result)
{
    ret = decimal_normalize(&value_1, &value_2);//нормализация, то есть если у одного числа экспонента больше, то я у другог увелчиваю ее пока они не станут равны и умножаю его на 10
   
    if (sign1 == sign2)
    {
        for (int i = 0; i < 3; i++)
        {

            result->bits[i] = value_1.bits[i] + value_2.bits[i];//просто складываю числа, если знаки равны
        }
        ret = 0;
    }
    else
    {
        decimal temp1 = {0};
        decimal temp2 = {0};
        if (sign1 == 1)
        {
            temp1 = value_1;
            invert_bit(&temp1.bits[3], 31);//инверитрую бит, то есть меняю знак
            temp2 = value_2;
        }
        else
        {
            temp2 = value_2;
            invert_bit(&temp2.bits[3], 31);//инверитрую бит, то есть меняю знак
            temp1 = value_1;
        }

        if (is_less(temp1, temp2))//здесь проверка какой число пол. и отриц. 1 приходит в случае, если temp1 отрицательно, а temp2 пол. или если tepm1 больше мантисой при отриц. знаке или если temp1 меньше при положительном
        {
            decimal copy = value_2;
            int carry = 0;
            for (int i = 0; i < 3; i++)
            {
                copy.bits[i] += carry ? ~(value_1.bits[i] + 1) + 1 : ~value_1.bits[i] + 1;
                carry = 0;
                if (value_2.bits[i] < value_1.bits[i])
                {
                    carry = 1;
                }
            }
            *result = copy;
            sign1 = 0;
        }
        else
        {
            decimal copy = value_1;
            int carry = 0;
            for (int i = 0; i < 3; i++) 
                copy.bits[i] += carry ? ~(value_2.bits[i] + 1) + 1 : ~value_2.bits[i] + 1;
                carry = 0;
                if (value_1.bits[i] < value_2.bits[i])
                {
                    carry = 1;
                }
            }
            *result = copy;
            sign2 = 0;
        }
    }

    int sign = sign1 | sign2;

    set_sign(result, sign);//ставит нужный знак числу, то есть делает decimal = {{1,2,3,-2147483648}} или если положительный не трогает

    return ret;
}
  • Вопрос задан
  • 1303 просмотра
Подписаться 2 Простой Комментировать
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вот эти побитовые сдвиги работли бы, если бы вы хранили число в двоичной системе счисления. Допустим, по 16 бит в каждом int. В таком виде вычисления побыстрее будут немного, но при выводе надо переводить число в 10-ую систему счисления. Судя по примеру ответа, вы храните по 3 десятичных знака в каждой ячейке. Т.е. у вас основание системы счисления 1000. И тут нужны сдвиги не битовые, а тысячные (которых не существует).

Вообще, основной цикл умножения должен быть примерно такой:

for (i = 0; i < len1; ++i)
  for (j = 0; j < len2; ++j) 
    c[i+j] += a[i]*b[j];


И потом надо сделать все переносы. Вот тут и происходят сдвиг на i позиций (в системе счисления 1000) - это то самое +i в индексе у массива результата. И вместо выполнения прибавления, когда бит равен 1, тут происходит умножение на a[i]. В битовом случае оно как раз вырождается в умножение на 1 или 0 - прибавление или пропуск прибавления.

Это работает даже если вы в массивах a,b храните по несколько бит в каждой ячейке, или даже десятичных знаков. Это просто умножение в столбик в произвольной системе счисления.

Правда, тут проблема, что вот такое вот умножение, если вы храните по 32 бита, оно переполнится, и ответ надо в 64-битном типе получать. И даже если вы храните по 16 бит, то сумма может переполниться из-за большого количества слагаемых. Ну это решается выполнением переноса сразу же:
const int BASE = 1000; // База системы счисления. Оно же максимальное число в ячейке +1.
for (i = 0; i < len1; ++i) {
  int carry = 0;
  for (j = 0; j < len2; ++j) {
    carry += c[i+j] + a[i]*b[j];
    c[i+j] = carry % BASE; 
    carry /= BASE;
  }
  int i = len1+len2-1;
  while (carry > 0) {
    carry += c[i];
    c[i] = carry % BASE;
    carry /= BASE;
    ++i;
  }
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы