Алгоритм деления для вычисления коэффициента без учета остатка

Question

В качестве проекта свободного времени я пытаюсь реализовать некоторые криптографические алгоритмы с использованием автономного C - то есть варианта C без стандартных библиотечных функций (стандартные типы библиотек и константы по-прежнему доступны) и без дополнительныхтакие функции, как VLA (массив переменной длины).

Одна из вещей, которые я сделал, - реализовал несколько функций для больших целых чисел (размер> 128 бит).Однако функция целочисленного деления в этом параметре требует отслеживания остатка в его текущей форме, и, поскольку я использую автономную среду, вызывающая сторона должна предоставить для нее место.

Возможно ли реализовать алгоритм деления для вычисления коэффициента, не полагаясь на отслеживание остатка, и, возможно, используя технику бит-среза?Допустимо использовать рекурсию вызовов для хранения переменных в стеке.

Предположим, что тип большого целого - bigint_t:

#define N 8
typedef uint32_t bigint_t[N]; // least-significant word first. 

Answer 1

Я понимаю, что вы озабочены дополнительным пространством, которое требуется для остатка, потому что вы не можете вызвать malloc.

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

Если вы сохраняете остаток деления дивидендов и растущий коэффициент в одном и том же массиве, вам понадобится только пара переменных для дополнительных цифр.

Answer 2

Вы можете использовать бинарный поиск.Выберите число, умножьте его на делитель.Если результат слишком велик, уменьшите число;если результат слишком мал, увеличьте число.Управляйте приращением / уменьшением, так что оно стремится к нулю в геометрической прогрессии.