Implementation of the binary division in C

Question

Here is the code which implements binary division: Here is the function where I print the final number at the end.

On Windows I get the correct answer: 60000000 7948AECA D269AE4A 6B41DD10 64209812 293E346 1C0000
but on Linux I get only zeroes.

#define SIZE_BIG_DECIMAL 7

typedef struct {
  uint64_t bits[SIZE_BIG_DECIMAL];
  uint16_t scale;
  uint16_t sign;
} s21_big_decimal;

void binary_div(s21_big_decimal *value_1, s21_big_decimal value_2,
                s21_big_decimal *result) {
  init_s21_decimal(result);
  s21_big_decimal Q;
  s21_big_decimal R;
  int scaleDiv = -1;
  do {
    init_s21_decimal(&R); // fill with 0 the array
    init_s21_decimal(&Q);
    scaleDiv++;
    int lastBit = (SIZE_BIG_DECIMAL - 1) * 32 - 1;
    int currentBit = get_bit_big(*value_1, lastBit);
    while (currentBit == 0 && lastBit >= 0) {
      currentBit = get_bit_big(*value_1, lastBit);
      if (currentBit == 0)
        lastBit--;
    }
    for (int i = lastBit; i >= 0; i--) {
      change_left_big(&R, 1);
      set_bit_big(&R, 0, get_bit_big(*value_1, i));
      if (is_less_or_equal_big(value_2, R)) {
        s21_big_decimal res = { 0 };
        init_s21_decimal(&res);
        s21_sub_big(R, value_2, &res);

        init_s21_decimal(&R);
        copy_bits(res, &R);
        set_bit_big(&Q, i, 1);
      }
    }
    if (scaleDiv > 0) {
      mul_10_big(result);
    }
    s21_big_decimal res;
    init_s21_decimal(&res);
    add_big(*result, Q, &res);
    copy_bits(res, result);
    if (!is_zero_big(R)) {
      init_s21_decimal(value_1);
      mul_10_big(&R);
      copy_bits(R, value_1);
    }
  } while (!is_zero_big(R) && scaleDiv < 28);
  set_scale_big(result, scaleDiv);
  for (int i = 0; i < 7; i++) {
    printf("%lX ", result->bits[i]);
  }
  printf("\n");
}

I work with bits so here are some helper functions:

int mul_10_big(s21_big_decimal *dec)
{
  s21_big_decimal temp = *dec;
  for (int i = 0; i < SIZE_BIG_DECIMAL - 1; i++)
  {
    temp.bits[i] *= 10;
  }
  temp.scale++;
  int overflowed = 0;
  if (getoverflow(&temp))
  {
    overflowed = 1;
  }
  else
  {
    *dec = temp;
  }
  return overflowed;
}

int div_10_big(s21_big_decimal *dec)
{
  uint64_t remained = 0;
  for (int i = SIZE_BIG_DECIMAL - 2; i >= 0; i--)
  {
    dec->bits[i] += remained << 32;
    remained = dec->bits[i] % 10;
    dec->bits[i] /= 10;
  }
  dec->scale--;
  return remained;
}

int getoverflow(s21_big_decimal *dec)
{
  int overflow = 0;
  int count = 0;
  for (int i = 0; i < SIZE_BIG_DECIMAL - 1; i++)
  {
    dec->bits[i] += overflow;
    overflow = (dec->bits[i] >> 32);
    dec->bits[i] &= MAX4BITE;
    count++;
  }
  int result = 0;
  if (overflow != 0 && count == 6)
  {
    result = 1;
  }
  return result;
}

void set_scale_big(s21_big_decimal *big_dec, int scale_value)
{
  big_dec->bits[SIZE_BIG_DECIMAL - 1] &= MINUS;
  big_dec->bits[SIZE_BIG_DECIMAL - 1] |= (scale_value << 16) & SCALE;
}

The problem is not in the way I print, I guess the problem is in the size of the variable. it has to work on Linux, what I have to change? Should I divide large binary numbers not this way?

Answer 1

There are multiple problems:

• The return type of div_10_big should be uint64_t instead of int but this does not pose a problem because the return value, the remainder of the division in in the range 0..9.

• It is unclear why you do not iterate on all elements in the loops in functions div_10_big, getoverflow, and mul_10_big.

• It is unclear why set_scale_big modifies the array instead of just the scale member.

• The type s21_big_decimal can handle values much larger than the traditional one for s21_decimal, i.e. -79,228,162,514,264,337,593,543,950,335 to 79,228,162,514,264,337,593,543,950,335, with a scale from 0 to 28, but using uint64_t for the bits seems overkill as you only use 32 bits for each of these bits. Tracking overflow in the individual operation handlers would allow for a more compact representation.

• The printf in the output code actually has undefined behavior on Windows: in printf("%lX ", result->bits[i]), you pass an unsigned long long where printf expects an unsigned long. For a portable version you should use:

    for (int i = 0; i < SIZE_BIG_DECIMAL; i++) {
        printf("%08llX ", (unsigned long long)result->bits[i]);
    }