Длинная арифметика на Си - C (СИ)

Формулировка задачи:

Здравствуйте! Хотелось бы мне начать топик, сообщения в котором я планирую пополнять постоянно (по возможности и уровню занятости, разумеется). Тема топика, как видно из заголовка, длинная арифметика. Я не хочу подробно описывать, что такое длинная арифметика и зачем она нужна. Об этом любой может прочитать на той же википедии. Но небольшое вступление сделать все таки надо. В длинной арифметике вычисления производятся над очень большими числами. С точки зрения программирования на языке Си такими числами можно считать любые, которые "не помещаются" в стандартные типы данных, то есть те, которые больше 32-х (64-х) бит. Наиболее популярно применение длинной арифметики, пожалуй, в криптографии. Я знаю, что очень многим студентам в университетах дают задания на длинную арифметику и надеюсь, что кто-то наткнется на эти сообщения и они ему помогут (сам в свое время мучился). Под конечной целью буду предполагать создание библиотеки или пакета (набора функций) для работы с длинными числами, возможно реализация каких-либо криптографических алгоритмов для примера. Начальный план действий будет таков:

Представление длинных чисел на языке Си
Основные математические операции

PS. Я нисколько не претендую на специалиста в данной области. В первую очередь создаю топик для самого себя, чтобы изучить данную тему и как следует в ней разобраться. Но я надеюсь, что это заитересует многих. Я знаю, что только начинаю осваивать языки программирования, поэтому очень надеюсь на поддержку наших гуру во всех аспектах задачи. PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута.

Решение задачи: «Длинная арифметика на Си»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
 
/* длинная арифметика 3^100
   равно 515377520732011331036461129765621272702107522001 */
int main(void) /* C89 ANSI */
{
    int n[100] = { 1 };
    /* число храним в достаточно длинном массиве
       первый элемент станет основанием,
       с которого число будет расти
       в сторону старших разрядов */
    
    int base = 10;
    /* полученное число будет в десятичной системе
       можно устанавливать степени десятки
       100, 1000, 10000 и так далее,
       это повысит скорость вычисления,
       результат будет выглядет одинаково;
       нужно учесть размер одного числа в массиве
       если int, то не более 10000 */
    
    int i, j, flag;
    /* i - внешние счётчики
       j - внутренние счётчики первого уровня
       flag - флажок, который при выводе числа
              помогает пропустить начальные нули в числе
              начальные нули - это разряды, до которых
              число не доросло */
    
    for (i = 0; i < 100; i++) {
        
        for (j = 0; j < 100; j++)
            n[j] *= 3;
        /* умножаем всё число на три,
           как будто в столбик на бумаге,
           для каждого разряда */
            
        for (j = 0; j < 100-1; j++)
            if (n[j] >= base) {
                n[j+1] += n[j] / base;
                n[j] %= base;
            }
        /* для всех разрядов, исключая самый старший,
           выполнить проверку на переполнение;
           
           если переполнение в каком-то из разрядов есть,
           то переполнившую часть перенести
           в соседний, более старший, разряд,
           а в самом разряде оставить остаток,
           который не переполняет разряд;
           
           при переносе переполнившей части
           в более старший соседний разряд,
           она прибавляется к тому, что уже там хранится */
        
    }
    /* умножает число на три сто раз,
       проводя проверки на переполнение его разрядов
       и переносы, в случаях переполнения */
    
    flag = 1;
    /* флаг пропуска начальных нулей
       устанавливается в положение "пропустить" */
    
    for (i = 99; i >= 0; i--) {
        
        if (flag == 1)
            if (n[i] == 0)
                continue;
            else
                flag = 0;
        /* если флаг пропуска начальных нулей
           установлен в положение "пропустить",
           то проверить не началось ли число;
           
           если число началось,
           то есть встречен первый ненулевой разряд,
           то переключить флаг в положение "вывести";
           если число не началось,
           сразу перейти к следующему разряду,
           не выводя ничего */
          
        printf("%d", n[i]);
        /* выводит очередной разряд числа,
           начиная слева */
    }
    /* выводит получившееся число слева направо,
       поразрядно, начиная с первого ненулевого разряда */
    
    putchar('\n');
    /* после числа переводит строку */
    
    exit(EXIT_SUCCESS);
    /* возвращает статус успешного завершения
       в операционную среду */
}

Объяснение кода листинга программы

Объявлены переменные:
- n[100] = {1} (массив для хранения числа)
- base = 10 (основание системы счисления)
- i, j, flag = 0 (счетчики и флажок)
Задается цикл for для умножения числа на 3 и проверки на переполнение разрядов.
Внутренний цикл for выполняется 100 раз для каждого разряда числа.
- Если разряд больше или равен основанию системы счисления, выполняется перенос в следующий разряд.
- Если разряд меньше основания системы счисления, он умножается на 3.
После выполнения всех внутренних циклов выполняется проверка на переполнение в каждом разряде, кроме самого старшего.
- Если разряд переполнился, его значение переносится в следующий разряд, а в самом разряде остается остаток.
Задается флаг=1, который указывает на пропуск начальных нулей числа.
Внешний цикл for выполняется от 99 до 0 для вывода числа слева направо.
- Если текущий разряд равен 0 и флаг=1, то этот разряд пропускается.
- Если текущий разряд не равен 0 и флаг=1, то флаг переключается в состояние 0 для вывода числа.
- Если текущий разряд не равен 0 и флаг=0, то он выводится на экран.
Выводится символ новой строки после вывода числа.
Программа завершается с статусом успешного выполнения.