Форум программистов, компьютерный форум, киберфорум
Наши страницы

C для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 276, средняя оценка - 4.95
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
#1

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

12.07.2010, 19:01. Просмотров 38161. Ответов 44

Здравствуйте, форумчане!

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

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

Начальный план действий будет таков:
  • Представление длинных чисел на языке Си
  • Основные математические операции

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

PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута.
15
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.07.2010, 19:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длинная арифметика на Си (C (СИ)):

Длинная арифметика - C (СИ)
Доброе время суток. Я разбираю длинную арифметику. И есть некоторые вопросы. К примеру возьмем Сложение. int a, b, length, i=0,...

Простая Длинная арифметика - C (СИ)
Доброго времени суток! У меня задача. Вводим 3 числа,достаточно больших,чтобы они не помещались в стандартные типы данных. Далее надо...

Умножение (длинная арифметика) - C (СИ)
Работа с массивами из десяти элементов в 12-ричной системе, реализация функции умножения Результатом возвращается число, указанное в...

Арифметические действия (длинная арифметика) - C (СИ)
Хай програмеры!!!! кто может помогите мне с таким заданием: Написать программу, которая выполняет указанные арифметические действия...

Длинная арифметика (возведение в степень) - C (СИ)
Возведение 2 в степень N. Мой код на СИ. Выдаёт правильный результат, но при выводе добавляется куча мусора, берущаяся невесть откуда....

Длинная арифметика, подключение и работа с библиотекой - C (СИ)
Доброго времени суток. Принудительно занялся изучением длинной арифметики. Пишу на СИ с Вижуалки. Скачал пакет gmp. #include...

44
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
12.07.2010, 20:01 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
The GNU Multiple Precision Arithmetic Library http://gmplib.org/
5
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.07.2010, 20:07  [ТС] #3
Цитата Сообщение от odip Посмотреть сообщение
The GNU Multiple Precision Arithmetic Library
Все это понятно, я и сам могу перечислить еще как минимум три подобных пакета. Однако, если требуется собственная реализация, то они не помогут. Да и "тупое" их использование мало покажет основные принципы.
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
12.07.2010, 20:20 #4
А "тупое" использование твоей библиотеки покажет основные принципы ?
Все кому лень разбираться будут просто копировать ТВОЙ код и использовать.
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
12.07.2010, 20:20 #5
fasked, а может лучше на цпп? С объектами? Думаю, для тебя же самого это будет куда полезнее.
0
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.07.2010, 20:23  [ТС] #6
Цитата Сообщение от odip Посмотреть сообщение
А "тупое" использование твоей библиотеки покажет основные принципы ?
Все кому лень разбираться будут просто копировать ТВОЙ код и использовать.
Я же сказал, что в первую очередь делаю это для себя. А если уж кому будет не лень, то разобраться в моей библиотеке будет куда проще, чем в том же GMP. К тому же я все таки надеюсь на какую-то помощь. Потому что библиотеки как таковой еще не существует.
Цитата Сообщение от Хохол Посмотреть сообщение
а может лучше на цпп? С объектами? Думаю, для тебя же самого это будет куда полезнее.
Нет, тему я задумал не для того, чтобы научиться пользоваться и строить классы. Арифмитические операции одинаковы и в Си и в Си++.
2
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
12.07.2010, 20:32 #7
Ну а какой план ?
Нужно: сложение, вычитание, умножение на обычное число, деление на обычное число, умножение двух длинных чисел, деление двух длинных чисел
Вывод длинного в строку, чтение длинного из строки

Да - еще преобразование обычного числа в длинное
0
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.07.2010, 21:00  [ТС] #8
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от odip Посмотреть сообщение
Ну а какой план ?
Нужно: сложение, вычитание, умножение на обычное число, деление на обычное число, умножение двух длинных чисел, деление двух длинных чисел
Вывод длинного в строку, чтение длинного из строки
Да - еще преобразование обычного числа в длинное
Для начала именно так

Добавлено через 21 минуту
Перед тем, как приступить конкретно к реализации, хотелось (или необходимо) бы немного теории.

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

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

Максимальное значение, которое умещается в 16-битовом числе равно 0xFFFF. Соответственно максимально возможный результат математической операции над 16-битовыми числами равен 0xFFFE0001. (0xFFFF * 0xFFFF = 0xFFFE0001). Такое число аккурат помещается в 32 бита регистра процессора. Процессору не понадобятся дополнительные операции по перемещению битов в регистрах, что даст ощутимый результат в скорости.

16-битовые числа в языке Си представлены типом unsigned short, 32-х битовые типом unsigned long. Таким образом за основной тезис можно взять выражение f(USHORT, USHORT) < ULONG, где f() - любая арифметическая операция. Думаю, это очень удобно.

Проверить данное отношение для конкретного компилятора можно открыв заголовочный файл limits.h. Там найти значения, подобные этим:

C
1
2
3
#define USHRT_MAX     0xffff        /* maximum unsigned short value */
#define UINT_MAX      0xffffffff    /* maximum unsigned int value */
#define ULONG_MAX     0xffffffffUL  /* maximum unsigned long value */
Беззнаковые типы данных беруться также для удобства работы: отсутствие потерь при арифметических операциях.

Следует отметить, что в 64-разрядных системах, можно ускорить время выполнения, аналогично используя базовые типы длиной 32 и 64 бита соответственно.

Следующий вопрос - это упорядочение разрядов в массиве.
Существует два варианта:
- порядок от старшего к младшему
- порядок от младшего к старшему

Рассмотрим эти варианты. Возьмем для примера число 0xFFFFFFFF
При порядке от старшего к младшему число в ячейках памяти будет выглядеть следующим образом

Код
0        1        2        0        1        2        3 
+--------+--------+-       +--------+--------+--------+-
| 0xFFFF | 0xFFFF |  ----> | 0x0001 | 0xFFFF | 0xFFFF | 
+--------+--------+-       +--------+--------+--------+-
Здесь мы сталкиваемся с очевидной проблемой. Попробуем прибавить к такому числу 1. 0xFFFFFFFF + 0x100000000 = 0x1FFFFFFFF. Для формирования результата понадобится смещать весь массив. Как видно размер числа можно менять, не сдвигая массив.
Другой порядок избавляет нас от такой проблемы.

Код
0        1        2        0        1        2        3 
+--------+--------+-       +--------+--------+--------+-
| 0xFFFF | 0xFFFF |  ----> | 0xFFFF | 0xFFFF | 0x0001 | 
+--------+--------+-       +--------+--------+--------+-
Значит выбор очевиден.
Далее займемся непосредственно программированием.
9
usernet009
24 / 24 / 1
Регистрация: 28.12.2009
Сообщений: 85
12.07.2010, 21:13 #9
Ооо..... а я когда то пытался сделать такое. Была задача, написать класс для хранения очень больших чисел ( целых ). Ии... перегрузка основных операций ( + - / * ). Сделал.. но, не полностью, реализовал только + и -. Дальше шло деление но, на нем я остановился ибо деление давало дробный результат а цисла то у меня целые... поразмыслив над этой проблемой несколько часов и найдя "кривое" решения я подумал что цель не стоит затраченого на нее времени. Умножение "крутилось" в голове но, так как НОРМАЛЬНО сделать деление не получилось, я решил забить и на умножение. Ведь.... зачем делать недоделаную программу ?
Таким образом, будет очень интересно посмотреть на ваш пакет. Ну, конечно же в исходных кодах
0
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.07.2010, 21:16  [ТС] #10
Цитата Сообщение от usernet009 Посмотреть сообщение
Таким образом, будет очень интересно посмотреть на ваш пакет. Ну, конечно же в исходных кодах
Весь код по мере написания будут выкладываться в этой теме.
1
accept
4828 / 3249 / 165
Регистрация: 10.12.2008
Сообщений: 10,569
13.07.2010, 03:23 #11
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
отсюда, откомментированный, 3 ^ 100
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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);
    /* возвращает статус успешного завершения
       в операционную среду */
}
21
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.07.2010, 14:31  [ТС] #12
Итак, простейшее представление длинного числа в языке Си будет выглядеть следующим образом.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
#define SIZE 3
 
void _print_real (unsigned short * num, size_t size) 
{
    while (size--)
        printf("%0.4X ", num[size]);
    printf("\n");
}
 
int main(void)
{
    unsigned short real[SIZE] = { 0xFFFF, 0x0FFF, 0x1 };
    _print_real(real, SIZE);
}
Однако это не очень удобно и понятно, поэтому надо поработать с typedef и define.
Для начала нам хватит следующих определений.

C
1
2
#define REAL_BASE      0x10000  /* база или "система счисления" длинного числа */
#define REAL_MAX_ORDER 4        /* максимальное количество разрядов в одном длинном числе */
REAL_BASE - как подписано в комментарии - это некая система счисления длинных чисел. то есть максимальное значение, которое хранится в одном разряде равно REAL_BASE - 1 = 0xFFFF.
REAL_MAX_ORDER - количество разрядов в одном длинном числе. Число может быть произвольным, но для начала можно взять значение поменьше (в демонстративных целях).

Далее определены синонимы базовым типам, для более удобного написания.
C
1
2
3
4
5
6
#ifndef USHORT
typedef unsigned short USHORT;
#endif /* !defined USHORT */
#ifndef ULONG 
typedef unsigned long ULONG;
#endif /* !defined ULONG */
И наконец определения длинным числам.
C
1
2
3
4
typedef unsigned short _real_int;               /* один разряд длинного числа */
typedef _real_int      REALINT[REAL_MAX_ORDER]; /* одно длинное число */
typedef _real_int *    PREALINT;                /* указатель на длинное число */
typedef _real_int **   LPREALINT;               /* двойной указатель на длинное число */
Чтобы не заморачиваться с выделением памяти (ведь тема не об этом) мы представим длинное число, как статический массив. Однако семантика функций будет включать в себя возможность будущего изменения.

Теперь простейшее представление длинного числа выглядит следующим образом
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
#define REAL_BASE      0x10000  /* база или "система счисления" длинного числа */
#define REAL_MAX_ORDER 4        /* максимальное количество разрядов в одном длинном числе */
 
#ifndef USHORT
typedef unsigned short USHORT;
#endif /* !defined USHORT */
#ifndef ULONG 
typedef unsigned long ULONG;
#endif /* !defined ULONG */
 
typedef unsigned short _real_int;               /* один разряд длинного числа */
typedef _real_int      REALINT[REAL_MAX_ORDER]; /* одно длинное число */
typedef _real_int *    PREALINT;                /* указатель на длинное число */
typedef _real_int **   LPREALINT;               /* двойной указатель на длинное число */
 
/* ФУНКЦИЯ ВЫВОДА */
void _print_real (PREALINT num, size_t size) 
{
    while (size--)
        printf("%0.4X ", num[size]);
    printf("\n");
}
 
int main(void)
{
    REALINT real = { 0xAABB, 0xCCDD, 0xEEFF, 0x1111 };
    _print_real(real, REAL_MAX_ORDER);
}
Конечно, изменилось немногое, но зато теперь видно то, что массив real является длинным числом.
Все определения вынесены в отдельный заголовочный файл по имени real.h

Содержимое файла real.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef _REAL_H
#define _REAL_H
 
/*************************************************************/
/*                         CONSTANTS                         */
/*************************************************************/
 
#define REAL_BASE      0x10000
#define REAL_MAX_ORDER 4
 
/************************************************************/
/*                        DATA TYPES                        */
/************************************************************/
 
#ifndef USHORT
typedef unsigned short USHORT;
#endif /* !defined USHORT */
#ifndef ULONG 
typedef unsigned long ULONG;
#endif /* !defined ULONG */
 
typedef unsigned short _real_int;
 
typedef _real_int      REALINT[REAL_MAX_ORDER];
typedef _real_int *    PREALINT;
typedef _real_int **   LPREALINT;
 
 
#endif /* _REAL_H */
1
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
13.07.2010, 15:06 #13
odip, предлагаю засунуть это тему в раздел "Большая коллекция решенных задач".
Топик очень познавательныйй вышел...
0
fasked
Эксперт С++
4963 / 2543 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.07.2010, 16:37  [ТС] #14
Цитата Сообщение от nikkka Посмотреть сообщение
предлагаю засунуть это тему в раздел "Большая коллекция решенных задач".
Топик очень познавательныйй вышел...
Я думаю, что если и стоит будет это сделать, то намного позже. Потому что решенных задач здесь ровно ни одной.

Добавлено через 1 час 30 минут
Сложение двух длинных неотрицательных чисел

Сложение двух чисел производится по классическому "школьному" алгоритму.
Сначала разберем простейшую реализацию такого алгоритма.
Допустим есть два числа: число U и число V. Над ними необходимо произвести заданную арифметическую операцию. Число W будет содержать результат операции.

В соответствии с исходными данными прототип функции сложения выглядит следующим образом:
C
1
void add (PREALINT u, PREALINT v, PREALINT w)
Теперь рассмотрим простейшую реализацию (по Д. Кнуту с сохранением имен переменных)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* сложение неотрицательных чисел */
void add (PREALINT u, PREALINT v, PREALINT w)
{
    _real_int j = 0, k = 0;
 
    for (j = 0; j < REAL_MAX_ORDER; ++j)
    {
        w[j] = u[j] + v[j] + k;
        k = (u[j] + v[j] + k)/REAL_BASE;
    }
 
    if (k != 0)
        w[j] = k;
}
Переменная j в данном случае является счетчиком и пробегается по разрядам чисел.
Переменная k - знак переноса. По свойству операции сложения переменная k может содержать только два значения, либо 0, либо 1.

Попробуем протестировать получившуюся функцию.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdlib.h>
#include <stdio.h>
#include "real.h"
 
void _print_real (PREALINT num, size_t size); /* функция вывода */
 
/* сложение неотрицательных чисел */
void add (PREALINT u, PREALINT v, PREALINT w)
{
    _real_int j = 0, k = 0;
 
    for (j = 0; j < REAL_MAX_ORDER; ++j)
    {
        w[j] = u[j] + v[j] + k;
        k = (u[j] + v[j] + k)/REAL_BASE;
    }
 
    if (k != 0)
        w[j] = k;
}
 
int main(void)
{
    REALINT real_a = { 0x1111, 0xEEFF }; /* первый операнд */
    REALINT real_b = { 0x234F, 0xFFFF }; /* второй операнд */
 
    REALINT real_c = { 0 }; /* результат */
    
    _print_real(real_a, REAL_MAX_ORDER); 
    _print_real(real_b, REAL_MAX_ORDER);
 
    add (real_a, real_b, real_c); /* операция сложения */
 
    _print_real(real_c, REAL_MAX_ORDER);
}
 
void _print_real (PREALINT num, size_t size) 
{
    while (size--)
        printf("%0.4X ", num[size]);
    printf("\n");
}
В результате на экране должно появиться следующее:
Код
0000 0000 EEFF 1111
0000 0000 FFFF 234F
0000 0001 EEFE 3460
Как видно сложение прошло успешно, перенос учтен, результат верный (проверить можно на любом калькуляторе).

Однако же эта функция нуждается в определенных улучшениях. Все ее недостатки связаны с длинами чисел.
В таком виде функция проходится по максимально возможному количеству разрядов числа. То есть по старшим нулям, фактически работает вхолостую. Значит следует учесть длину чисел.

Прототип принимает следующий вид:
C
1
void add (PREALINT u, size_t len_u, PREALINT v, size_t len_v, PREALINT w, size_t len_w);
Релизация (числовыми комментарии означают номер пункта в пояснении, например /* 1 */ - первый пункт, комментарий с восклицательным знаком /* ! */ означает конец поясняемого блока):
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* сложение неотрицательных чисел */
void add (PREALINT u, size_t len_u, PREALINT v, size_t len_v, PREALINT w, size_t len_w)
{
    _real_int j = 0, k = 0;
 
/* 1 */
    if (len_u < len_v)
    {
        add (v, len_v, u, len_u, w, len_w);
        return;
    }
/* ! */
 
/* 2 */
#ifdef _DEBUG
    assert(len_w >= len_u); /* длина результирующего числа недостаточна */
#endif /* defined _DEBUG */
/* ! */
 
/* 3 */
    for (j = 0; j < len_v; ++j)
    {
        w[j] = u[j] + v[j] + k;
        k = (USHORT)((u[j] + v[j] + k) / REAL_BASE);
    }
/* ! */
 
/* 4 */
    for ( ; j < len_u; ++j)
    {
        w[j] = u[j] + k;
        k = (USHORT)((u[j] + k) / REAL_BASE);
    }
/* ! */
 
/* 5 */
    if (k != 0)
        w[j] = k;
/* ! */
}
1. Сравнение длин чисел. Для получения правильного результат нам необходимо знать какое число более длинное, а какое более короткое. Пусть более длинным числом считается число U. Чтобы добиться такого постоянства при невыполнении условия вызывается рекурсия функции, но с обратными аргументами. return необходим, чтобы функция не выполнялась два раза.
2. Проверка длины результирующего числа. Если есть возможность того, что результат не поместиться в число W, то вылетает исключение.
3. Первый цикл работает пока существует более короткое число.
4. Второй цикл уже не учитывает короткое число, а только разряды более длинного + знак переноса.
5. Учет знака переноса для формирования окончательного результата.

Осталось протестировать, вызываем функцию со следующими аргументами:
C
1
2
3
4
5
6
    REALINT real_a = { 0xFFFF }; /* первый операнд */
    REALINT real_b = { 1, 0xFFFF, 0xFFFF }; /* второй операнд */
 
    REALINT real_c = { 0 }; /* результат */
    
    add (real_a, 2, real_b, 3, real_c, 4); /* операция сложения */
При таких значениях чисел и их длин вызывается рекурсивное обращение функции, первый цикл отрабатывает два раза, второй цикл один раз - что соответствует длинам чисел.

Функция сложения двух длинных чисел готова, чуть позже я приведу более "модную" реализацию.
Жду ваших комментариев и критики.
1
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
13.07.2010, 21:57 #15
Мне кажется стоит сделать структуру куда положить массив и длину
Тогда операции будут выглядешь намного проще - почти как целые числа
C
1
2
3
la_int_t la1, la2, la3;
 
la_add( &la1, &la2, &la3 );
Добавлено через 1 минуту
И название realint странное
Это вещественное ( real ) или целое ( int ) ?
0
13.07.2010, 21:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2010, 21:57
Привет! Вот еще темы с ответами:

Длинная арифметика - почему и зачем здесь atoi? - C (СИ)
#include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; using namespace std; const int N=10000; int d; ...

Длинная арифметика. Вычитание двух положительных чисел - C (СИ)
Доброго времени суток! У меня не получается сделать вычитание двух длинных положительных чисел... Пыталась разбираться по чужим кодам -...

Ошибка при вводе чисел разной длины. Длинная арифметика - C (СИ)
Помогите разобраться в чем проблема. Прогоняю алгоритм на листочке, вроде бы должно работать, уже какие идеи только не пробовал. Для чисел...

Самая длинная подстрока - C (СИ)
Помогите решить задачу. Дана строка, состоящая из маленьких латинских букв. Ваша задача — найти длину ее самой длинной подстроки,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru