Деление произвольных больших чисел, хранящихся в массивах символов в C - PullRequest
Новая
       7

Деление произвольных больших чисел, хранящихся в массивах символов в C

0 голосов
/ 04 декабря 2018

Часть моего домашнего задания требует деления больших целых чисел на такие длинные, что я могу хранить их только в символьных массивах (я не могу использовать библиотеку GNU Bignum).И делитель, и делитель могут иметь длину от одной до тысячи цифр, поэтому результат деления также должен храниться в массиве символов, поскольку он также может быть очень длинным.Я хочу сохранить одну цифру для каждого индекса.

Я пытаюсь использовать повторяющиеся вычитания, пока делитель не станет меньше делителя, и подсчитываю обороты.Наихудший случай - когда делитель равен 2, поэтому я должен выделить «длину делителя / 2» объема памяти для массива счетчиков.

У меня уже есть вычитание , *Реализована функция 1007 * getLength и lengthCompare , и они работают нормально.Вот что я сделал до сих пор: 

char *division(char *divident, char *divisor, int len_divident, int len_divisor)
{
    if (divident == NULL || divisor == NULL)
    {
        return NULL;
    }

    char *cnt = (char*)malloc((len_divident/ 2) * sizeof(char));
    char *res = subtraction(divident, divisor, len_divident, len_divisor);
    int i = 0;

    do
    {
        res = subtraction(res, divisor, getLength(res), len_divisor);

        if (cnt[i] == 9)
        {
            i++;
        }

        cnt[i]++;

    } while (lengthCompare(res, divisor) == 1 || lengthCompare(res, divisor) == 0);

    cnt->digits[i + 1] = '\0';
    return cnt;
}

Функция lengthCompare возвращает 1, если первый параметр длиннее второго, или 2, если второй длиннее, и 0, еслиих длина равна.

Этот код не работает - каждый раз, когда я компилирую, я получаю сообщение «ОШИБКА - недостаточно места».Изменить: если быть точным, это исключение из функции вычитания: Необработанное исключение: нарушение прав записи.результат был 0x1110112.

Обратите внимание, что я новичок в C, и это, вероятно, не лучший способ делать то, что я хочу, но я не мог придумать лучшего.

Я очень ценю любой критицизм и предложение!

Редактировать: n и a переименованы в divident и divisor.

1 Ответ

0 голосов
/ 04 декабря 2018

Худший случай - это ..., поэтому я должен выделить объем памяти 'длина деления / 2' для массива счетчиков.

Не совсем, худший случай -ближе к вычитанию.

Код не выделяет достаточно памяти.

char *cnt = (char*)malloc((len_divident / 2) * sizeof(char));  // Bad

После страхования делителя представляет значение без начальных нулей ... 

while (len_divisor > 0 && divisor == '0') {
  len_divisor--;
  divisor++;
}

...., необходимое пространство занимаетне более: 

// As it looks like code is using strings
#define SPACE_FOR NULL_CHARACTER 1

size_t length = 1 + SPACE_FOR NULL_CHARACTER;
if (len_dividend > _len_divisor) {
  length = len_dividend - len_divisor + 1 + SPACE_FOR NULL_CHARACTER;
}

Нет необходимости в C для броска.Если вы хотите масштабировать по типу указателя, лучше использовать sizeof *pointer *, а затем * sizeof(type).Правильнее кодировать, просматривать и обслуживать проще. 

char *cnt = malloc(sizeof *cnt * length);

Надежный код проверяет успешность выделения. 

if (cnt == NULL) {
  Handle_OutOfMemory_Somehow();
}
...