Разделение двух чрезвычайно больших чисел, представленных как связанный список беззнаковых длинных длин

Question

Я работаю в c и, как сказано в названии, у меня есть struct, который является узлом для двусвязного списка unsigned long longs, которые представляют чрезвычайно большие числа.

Мне нужно выполнить базовую арифметику на них и достигло +, -, *, но мне все еще нужно деление. Я видел ответы на арифметику на большие числа, представленные как связанные списки, но у моей проблемы есть другая часть, переполнение.

В настоящее время я пытаюсь использовать длинное разделение, и моя проблема заключается в том, что когда первая цифра (unsigned long long) не делится равномерно, то есть остаток, который переносится на две цифры (два unsigned long long). Я не знаю, как разделить большое количество, представленное как ull s на ull, сохраняя точность. Функция деления будет когда-либо вызываться только на двух числах, где вторая делит первое равномерно.

Не знаете, какую другую информацию мне нужно дать, но я застрял здесь, и любая интуиция поможет, спасибо.

Редактировать: Я приношу свои извинения за свою кажущуюся новизну в StackOverflow, но для тех, кто любопытно, каким образом я решил проблему, это обрабатывать числа как двоичные и выполнять разделение по частям. Это решение устраняет проблемы, которые у меня были.

Answer 1

Простым решением может быть - с учетом того, что вы уже сделали , есть - делать все подразделения в два этапа. В основном вы действуете так, как будто ваши длинными длинными беззнаковыми ints являются только long unsigned ints.

Это удваивает длину цепочки, в которой вы должны работать, и увеличивает число операций, необходимое в четыре раза, но если это не проблема, вы можете выполнить разделение остальной части lu плюс следующего lu внутри llu, что снова дает вам остаток меньше, чем lu.

Других слов, вам нужно что-то большее, чем Ил, но нет ничего, делать всю работу с л, а потом это нечто большее для этой операции в наличии - в Ила.