Зона кода
В замечательном языке Python на уровне синтаксиса поддерживаются операции со сколь угодно большими целыми числами. В C99 такая поддержка отсутствует. Поддерживаемые целые числа ограничены сверху максимальным значением встроенного восьмибайтового типа unsigned long long int . Оно равно 18446744073709551615. А что, если хочется получить возможность оперировать в C99 числами, превышающими это значение? Ответ очевиден: реализовать её самостоятельно!
Этим мы и займёмся. Пока что ограничимся реализацией операции сложения больших чисел. Для этого нам, разумеется, придётся создать и структуру данных, предназначенную для их хранения и некоторые функции, позволяющие взаимодействовать с этой структурой (например, помещать в неё данные и читать их).
Статья адресована читателям, уже имеющим определённый опыт программирования на C99, разбирающимся в операциях динамического распределения памяти и желающим укрепить свои навыки. Кроме того, будем предполагать, что читатели знакомы с различными системами исчисления и со способами перевода чисел из одной системы в другую.
Под «большими числами» мы будем понимать множество беззнаковых целых чисел, не ограниченное сверху. Разумеется, поскольку речь идёт о компьютерной реализации, верхний предел, обусловленный конечностью памяти компьютера, существовать будет. Именно формальная неограниченность сверху породила термин «большие», хотя, в описанное множество будут входить и «не очень большие» (в бытовом смысле) числа, например, 0, 1, 2, 3.
Тип big_int
Начнём с построения структуры данных, предназначенной для хранения целых чисел. Способ хранения чисел в памяти компьютера мы выберем тот, который уже используется в языке C99 для хранения любых беззнаковых целых типов. Заключается он в следующем.
Число записывается в двоичной форме, после чего «справа налево» разбивается на группы, содержащие по 8 двоичных цифр (крайняя слева группа может состоять, разумеется, менее, чем из 8-ми цифр). Затем, в том же порядке, (т. е. «справа налево») группы помещаются в подряд идущие однобайтовые ячейки памяти.
Рассмотрим, в качестве примера, способ хранения в памяти числа «квадриллион» (10 15 ). Для краткости будем использовать не двоичную форму записи, а шестнадцатеричную, в которой триллион выглядит так: 38D7EA4C68000. Поскольку одна шестнадцатеричная цифра соответствует 4-м двоичным, разбиение будем проводить на группы из 2-х цифр (в последней группе будет содержаться одна цифра):
3 | 8D| 7E| A4 | C6| 80 | 00
Видно, что для записи числа нам потребуется 7 байт. Поместим теперь наше число в память, начиная с ячейки, имеющей адрес n:
| Адрес ячейки | n | n+1 | n+2 | n+3 | n+4 | n+5 | n+6 |
| Содержимое ячейки | 00 | 80 | C6 | A4 | 7E | 8D | 03 |
Преимущества данного способа хранения чисел («справа налево») проявятся, когда мы будем реализовывать операцию сложения больших чисел. Если памяти, выделенной для суммы, не хватит, то нам при таком способе хранения потребуется добавить дополнительную ячейку со стороны старших разрядов числа, т. е. «справа». А добавить ячейку «справа» очень просто: мы можем воспользоваться для этой цели функцией realloc() . Добавление же ячейки «слева» было бы более проблематичным.
Хранить большие числа мы будем в массиве, каждый элемент которого является однобайтовым целым числом. При сложении чисел нам будет нужно, чтобы байты интерпретировались как беззнаковые целые, поэтому в качестве типов элементов мы выберем unsigned char . Заметим, что, в соответствии со стандартом C99, размер типа char всегда равен 1 байту, поэтому наш выбор будет корректным во всех реализациях стандарта.
Массив будет создаваться динамически, поэтому обращаться к нему мы будем через указатель. Нам потребуется также переменная для хранения размера массива. Создадим структуру big_int , содержащую эти 2 поля: указатель на массив ( bytes ) и его размер ( size ):
Имя нового типа мы задали с помощью спецификатора typedef . Благодаря этому в дальнейшем обращаться к типу можно будет через идентификатор big_int ; предварять его ключевым словом struct не потребуется.
Создание больших чисел: функция hcreate()
Перед тем, как реализовывать суммирование больших чисел, мы должны научиться их создавать и выводить на печать. За создание чисел будет отвечать функция hcreate() . Она будет преобразовывать текстовое представление числа в переменную типа big_int . Текстовое представление будет содержаться в строке, адрес которой функция будет принимать в качестве параметра. Переменная типа big_int будет создаваться динамически, а функция hcreate() будет возвращать её адрес.
Префикс h в названии функции hcreate() означает, что функция работает со строками, содержащими представление чисел в шестнадцатеричной (hex) форме. Обрабатывать шестнадцатеричную запись числа гораздо проще, чем десятичную, и мы пока пойдём по пути наименьшего сопротивления.
Функция hcreate() будет также проверять строку, содержащую текстовую запись числа в шестнадцатеричной форме, на корректность. В случае, если строка некорректна, будет возвращаться нулевой адрес. Корректной считается непустая строка, состоящая из шестнадцатеричных цифр (т. е. символов ‘0’ — ‘9’, ‘a’ — ‘d’ и ‘A’ — ‘D’). Кроме того, для упрощения обработки запретим строке начинаться с нуля, если только ноль не является единственным символом строки.
Для проверки символов строки на корректность будет использоваться стандартная библиотечная функция isxdigit () , определённая в заголовочном файле ctype.h . Она возвращает ненулевое значение, если переданный ей символ является шестнадцатеричной цифрой или ноль в противном случае.
В ходе работы функции будет динамически создан массив байтов для хранения числа, указатель на который в дальнейшем (в случае отсутствия ошибок) будет сохранён в соответствующем поле переменной типа big_int . Затем будут перебираться символы строки в направлении от начала к концу, и каждая пара символов будет преобразована в один байт массива, который будет заполняться, наоборот, от конца к началу (если количество символов строки окажется нечётным, то сначала будет отдельно обработан первый символ строки; он будет преобразован в последний байт массива).
Преобразование символов в байты будет осуществляться с помощью функции sscanf () . Для пары символов будет использован спецификатор преобразования » %2x «, а для одного символа — » %1x «. В стандарте языка C99 описан модификатор формата » hh «, который, при добавлении его к спецификатору, принуждает функции семейства scanf() расценивать адрес, ответствующий спецификатору, как адрес переменной типа char или unsigned char . В результате, запись по этому адресу затрагивает лишь один байт.
Однако опыт показывает, что данный модификатор игнорируется компилятором MinGW64: при его использовании модифицируются сразу четыре байта. Но, поскольку нам требуется записывать информацию в однобайтовые ячейки памяти, мы прибегнем к следующему трюку. Посредством функции sscanf () и спецификатора » %2x » (» %1x «) сохраним информацию в буферной переменной типа int , а потом перепишем её в переменную типа unsigned char .
Поскольку наши функции, работающие с большими числами, будут неоднократно использовать функции динамического распределения памяти, мы позаботимся об обработке ситуаций, при которых выделение памяти окажется невозможным. Для этой цели напишем функцию mem_error() , которая будет вызываться каждый раз, когда функция, распределяющая память, будет возвращать нулевой адрес:
Как мы видим, функция mem_error() выводит сообщение о проблеме и аварийно завершает работу программы.
Приведём теперь код функции hcreate() .
Принципы работы функции hcreate() были описаны выше, поэтому прокомментируем её код достаточно кратко.
В строках 3-9 обрабатываются ошибки, вызванные передачей функции некорректного аргумента. К ним относятся: нулевой адрес, пустая строка, строка, начинающаяся с нуля и имеющая более одного символа. Попутно устанавливается размер строки и записывается в переменную len .
В строках 10-16 создаётся переменная odd , содержащая 1, если значение len нечётно или 0 в противном случае, вычисляется размер массива байтов, а также динамически создаётся сам массив.
В строках 17, 18 создаются переменные count (счётчик цикла) и buf (буферная переменная, назначение которой мы уже описали ранее).
В строках 20-30 первый символ строки преобразуется в последний байт массива; это происходит только в случае, если количество символов в строке нечётно. Попутно происходит проверка символа на корректность.
В цикле, занимающем строки с 31 по 45, перебираются пары символов, содержащиеся в строке и преобразуются в байты массива. Попутно символы проверяются на корректность.
Наконец, в строках 46-51 динамически создаётся переменная типа big_int , её поля заполняются сформированной ранее информацией, а её адрес возвращается вызывающей функции.
Переменная типа big_int , созданная функцией hcreate() , после использования должна быть «уничтожена», т. е. память, выделенная для неё, должна быть освобождена. Освобождение памяти проводится в 2 приёма: сначала освобождается память, адресуемая полем bytes , а потом — память, занятая самой переменной. Разумно эти 2 операции объединить в функцию, принимающую в качестве единственного параметра адрес уничтожаемой переменной типа big_int :
Печать больших чисел: функция hprint()
Займёмся теперь созданием функции hprint() , принимающей в качестве параметра адрес переменной типа big_int и печатающей её, т. е. создающей строку, содержащую текстовое представление числа. Как читатель уже догадался, префикс h в названии функции означает, что печататься число будет в шестнадцатеричной форме. Строка будет создаваться динамически, а функция hprint() будет возвращать её адрес.
Функция hprint() будет выполнять преобразование, обратное тому, которое выполняется в функции hcreate() . Снова будем перебирать элементы массива байтов в обратном порядке и для каждого байта записывать в строку 2 шестнадцатеричные цифры (если количество цифр нечётно, то в начало строки предварительно записывается единственная цифра из последнего байта массива). Теперь уже для преобразования байтов в символы будем использовать функцию sprintf() .
Ниже приведён код функции hprint() .
В строке 3 сохраняем в переменной count размер массива байтов, а в 4-й строке записываем в переменную len предварительный размер памяти (учитывающий завершающий нулевой символ), требуемый для формируемой строки. Он корректен для случая, когда количество цифр нечётно.
В 5-й строке уменьшаем значение count на единицу; теперь в count хранится индекс последнего элемента массива. В 6-й строке сохраняем в переменной bytes адрес массива байтов. Это делаем для удобства: чтобы каждый раз не использовать конструкцию bi->bytes .
В 7-й строке выясняем чётность количества цифр. Делаем это, сравнивая значение последнего байта массива с числом F (т. е. с 16 в десятичной системе). Если значение не превышает F, то количество цифр нечётно, и в переменной odd сохраняется единица. Если превышает, то чётно, и в odd записывается ноль.
В строках 8, 9 корректируется (в случае чётности количества цифр) значение переменной len . Теперь объём памяти, требуемый для формируемой строки, окончательно установлен, и можно динамически выделять память.
Именно это выделение памяти и происходит в строке 11. Адрес выделенного участка памяти сохраняется сразу в двух переменных: str и string . Запись символов в строку всегда будет происходить по адресу, содержащемуся в str , поэтому значение str будет изменяться по мере заполнения строки. Переменная string будет неизменна; её значение будет возвращено функцией hprint() после окончания её работы.
В строках 13-18 обрабатывается ситуация, в которой количество символов нечётно. В строках 19-28 происходит заполнение строки парами символов.
Обратите внимание на строки 22, 23. Если значение очередного байта не превышает F, то в строку первым символом записывается ноль, а потом уже — значение байта, преобразованное в односимвольную строку. Если ноль не записать, то в строку запишется лишь один символ, что нас устроить не может.
А если значение байта превышает F (см. строки 24, 25), то оно будет преобразовано в строку, состоящую из двух символов; это, как раз, то, что нам нужно.
Наконец, в строках 29, 30 мы сохраняем в формируемой строке завершающий нулевой символ и возвращаем её адрес в вызывающую функцию.
Суммирование больших чисел: функция sum()
Ну вот, мы и добрались до основной функции нашей статьи — функции sum() . Она будет принимать в качестве аргументов адреса двух переменных типа big_int , складывать эти переменные и сохранять результат в переменной того же типа. Память под результат будет выделяться динамически. Функция sum() будет возвращать адрес переменной, содержащей вычисленную сумму.
Идея функции sum() весьма простая. Каждое из слагаемых представлено массивом байтов. Мы будем к парам байтов, относящихся к разным слагаемым и имеющим одинаковые индексы, применять обычную операцию сложения беззнаковых целых чисел. Перебирать байты мы будем в направлении от младших разрядов чисел к старшим, т. е. от начал массивов к их концам. Результаты сложения будут сохраняться в байтах, принадлежащих третьему массиву, адрес которого, в итоге, будет присвоен соответствующему полю результирующей переменной.
Теперь давайте разберёмся в алгоритме более детально. При его реализации нужно учитывать три очень важных обстоятельства.
Массив, в котором хранится одно из слагаемых, может иметь размер, отличный от массива, содержащего другое слагаемое. В этом случае при побайтовом сложении байты одного из массивов могут «внезапно кончиться».
Для того, чтобы учесть эту возможность, мы поступим следующим образом. Выясним, предварительно, какой из массивов имеет больший размер (если их размеры не равны). Назовём, для определённости, массив, чей размер не превышает размер другого массива, малым, а другой массив — большим (заметим, что, в случае равенства размеров, число, хранящееся в большом массиве, может быть меньше числа, хранящегося в малом).
Операцию сложения будем проводить в два этапа. В первом этапе будут затронуты только те байты массивов, которые имеют одинаковые индексы. После того, как малый массив «закончится», перейдём ко второму этапу, в котором будут задействованы только байты большого массива.
При сложении двух байтов, принадлежащих разным массивам, может произойти переполнение. Оно возникнет в случае, если сумма беззнаковых целых чисел, хранящихся в байтах, превысит число FF (255 в десятичной форме).
Чтобы его корректно обработать, сумму первой пары байтов сохраним в буферной переменной типа int . После этого присвоим соответствующему элементу третьего массива значение буферной переменной. При таком присваивании, при наличии переполнения, этот элемент, очевидно, получит только последние 8 битов буферной переменной (9-й её бит в этом случае будет содержать единицу).
Затем выполним сдвиг буферной переменной вправо на 8 разрядов . В результате этой операции она будет содержать 0, если переполнение отсутствовало или единицу, если оно имело место. Далее следующую пару байтов мы будем складывать уже с буферной переменной, и в неё же поместим результат. Таким образом, если на предыдущем шаге произошло переполнение, то единица будет перенесена в старший разряд (т. е. разряд, следующий за тем, в котором произошло переполнение). Далее этот процесс будет вновь повторяться.
В результате, на первом этапе операции сложения каждый раз будут складываться 3 числа: значения двух элементов массивов и буферной переменной. На втором этапе — уже только 2 числа: значения элемента большого массива и буферной переменной.
Заранее, до завершения операции сложения, невозможно предугадать размер третьего массива, в котором будет храниться результат. Мы можем лишь утверждать, что его размер будет равен размеру большого массива или на единицу превышать его.
В связи с этим обстоятельством мы будем действовать следующим образом. Первоначальный размер третьего массива установим равным размеру большого массива. После завершения операции сложения выясним, содержит ли буферная переменная единицу. Если содержит, то с помощью функции realloc() из стандартной библиотеки > перераспределим динамическую память для третьего массива, увеличив её объём на один байт. После этого в последний элемент массива, соответствующий старшим разрядам числа, занесём единицу.
Ниже приведён код функции sum() .
Кратко прокомментируем код функции sum() . В строке 3 объявляем указатели max и min , которые, в дальнейшем, будут хранить адреса байтовых массивов, содержащих суммируемые числа, причём размер массива, на который указывает max , будет не меньше размера массива, на который указывает min . Переменная bytes предназначена для хранения адреса массива, в который будет помещена сумма чисел. Наконец, переменные s_max и s_min , объявленные в строке 4, будут содержать размеры массивов, на которые указывают max и min соответственно.
В строках 5-18 сравниваются размеры массивов, содержащих слагаемые, и, по результатам этого сравнения, устанавливаются значения переменных max , min , s_max и s_min . В строке 19 переменной size присваивается первоначальное значение размера массива, в который будет помещена сумма. В дальнейшем значение size может быть подкорректировано.
В следующей строке под этот массив динамически выделяется память. В 22-й строке объявляется буферная переменная buf , назначение которой мы уже описали ранее. Далее в 2 этапа: в строках 23-27 (1-й этап) и строках 28-32 (2-й этап) происходит само суммирование, результаты которого помещаются в массив, адресуемый указателем bytes .
В строках 33-39 сначала проверяется, имело ли место переполнение после обработки последнего байта большого массива (адрес которого хранится в max ). О его наличии свидетельствует равенство значения переменной buf единице, а об отсутствии — равенство этого значения нулю. Затем, в случае, если переполнение было, происходит перевыделение памяти для хранения результирующего массива с увеличением её объёма на 1 байт. В этот байт заносится единица.
Наконец, в оставшихся строках функции динамически создаётся переменная типа big_int , предназначенная для хранения результата, её поля заполняются уже полученными ранее значениями, а её адрес возвращается в вызывающую функцию.
Тестирование типа big_int и функций для работы с ним.
Напишем программу, считывающую с консоли 2 числа, находящую их сумму и выводящую результат на консоль. Для считывания строк будем использовать функцию gets_s() , созданию которой была посвящена отдельная статья. В случае, если какое-либо слагаемое будет введено пользователем с ошибкой, программа предложит ему повторить ввод этого слагаемого, и это будет повторяться до тех пор, пока не будет введена корректная строка.
Если не считать функции gets_s() , то наша тестирующая программа будет состоять из единственной функции main() . Ниже приведён её код.
Короткий комментарий. В 3-й строке создаётся символьный массив, в который будут считываться строки с консоли. В строках 4-10 с консоли считывается первое слагаемое и функций hcreate() преобразуется в перменную типа big_int . В строках 11-17 то же повторяется для второго слагаемого. В строке 18 вычисляется сумма, а 19-й строке она выводится на консоль. Наконец, в трёх последующих строках память, занятая обоими слагаемыми и суммой, освобождается.
Запуск программы на выполнение может привести, например, к следующему диалогу с пользователем:
Возможность протестировать программу на корректность обработки слагаемых, набранных с ошибками, предоставляется читателю.
Заключение
Итак, задача, поставленная нами в начале статьи, решена.
Стоит заметить, что средства, позволяющие переводить числа из текстового формата в двоичный и наоборот, а также суммировать их, уже встроены в язык C99. Однако эти средства предназначены для работы с данными, размер которых ограничен. Наша задача сосотяла в том, чтобы добиться обработки данных неоограниченных размеров. По сути, мы, используя уже готовые операции над отдельными байтами, «связали» эти операции «в цепочки», создав, таким образом, операции над массивами байтов.
Конечно же, главный недостаток нашей реализации операций с большими числами очевиден: отсутствие поддержки десятичной записи чисел. Напрашивается создание родственных функциям hcreate() и hprint() функций dcreate() и dprint() , первая из которых обрабатывает строки, содержащие текстовые представления больших чисел в десятичном формате, а вторая их создаёт. Но реализация данных функций — это уже тема для отдельной статьи.
Источник
