[P&AM Lab] Бибиотека больших чисел

[Grigoriy A. Sitkarev]

Хорошее начало.

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

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

а) целостным;
б) непротиворечивым;
в) простым для запоминания;
г) соответствовал задачам библиотеки и ожиданиям пользователя;
д) основывался на сложившихся традициях и идиомах (если таковые 
применимы и существуют в практике).

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

Дальше разрабатывается API, т.е. интерфейс к этим функциям, их имена, 
порядок следования аргументов, публичные структуры, перечисления и т.д. 
Прототип будущей библиотеки. Возможно, в ходе реализации отдельных 
функций выяснится что что-то нужно скорректировать на любом из шагов, 
тогда задача выполняется ещё раз, от начала. Возможно, какой-то шаг 
пропускается. Жёсткого алгоритма конечно-же нет, это творчество. То что 
получилось на этом шаге -- выносится в заголовочный файл.

 > Нужно ли писать что-то ещё? есть ли смысл вводить
 > отрицательные числа? Нужно ли писать функции так, что бы они сразу могли
 > складывать разные по размеру числа?

Можно сказать что такие функции точно понадобятся (и ещё будут другие):

bnum_new()
bnum_free()
bnum_unset()
bnum_reset()

bnum_add()
bnum_sub()
bnum_mul()
bnum_div()
bnum_mod()
bnum_gcd()
bnum_exp() или bnum_pow()
bnum_set()
bnum_set_int()
bnum_set_ascii()
bnum_get_ascii()

Что-то вроде... Надо подумать ещё конечно. Это очень важный шаг.

Если например, я беру два положительных числа a и b, и при этом a < b, а 
потом вычитаю из (a - b), то результатом будет отрицательное число. Это 
ответ на вопрос об отрицательных числах. Такая арифметика будет полной. 
Для хранения знака тебе достаточно одного бита.

Базу для чисел скорее всего лучше выбрать 65536 и тогда значения 
разрядов хранить в unsigned short. Числа bignum могут быть разного 
порядка, поэтому складывать и делать прочие операции нужно с числами 
разного размера. Поэтому придётся хранить поле где есть индекс разряда 
последнего использованного. Индекс удобнее потому что в таком случае он 
же будет являться и наибольшей степенью базы у числа. Например, 
65535^0=1 если top равен 0.

#define BNUM_BASE	65536

struct bignum {
	int		sign;	/* 1 = negative, 0 = positive */
	int		nalloc;	/* allocated */
	int		top;	/* last used */
	unsigned short	*val;	/* BNUM_BASE digits */
};

Что-то вроде такого.

Структуры должны передаваться по указателю а не по значению. Сейчас они 
у тебя копируются в стек. Должно быть что-то вроде:

/* res = a + b */
int bnum_add(struct bignum *res, struct bignum *a, struct bignum *b);

Боря, обрати внимание пожалуйста на стиль. У тебя с этим есть проблемы. 
Может быть у тебя какой-то редактор неправильный, не даёт тебе 
возможность писать удобно?

--
Г.А.