Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5

Длинная арифметика на Си

12.07.2010, 19:01. Показов 103949. Ответов 81

Студворк — интернет-сервис помощи студентам
Здравствуйте, форумчане!

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

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

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

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

PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута.
16
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
12.07.2010, 19:01
Ответы с готовыми решениями:

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

Длинная арифметика
Необходимо реализовать операции сложения, вычитания и умножения двух чисел a и b. Каждое число содержит не более 10000 десятичных знаков,...

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

81
2493 / 1157 / 709
Регистрация: 25.04.2016
Сообщений: 3,339
26.03.2026, 17:16
Студворк — интернет-сервис помощи студентам
Extazy25, думается мне, что от вас ожидали увидеть что-то такое:

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
#include <stdio.h>
// Functions_Plus_Or_Minus
 
#define MAXDIG 256
// Числа в массивы записывать в обратной последовательности, и каждый разряд
// нужно записывать в свою ячейку:
int mhigh[MAXDIG] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9
};
int mlow[MAXDIG] = {9, 7, 5, 3, 1, 9, 7, 5, 3, 1, 9, 7, 5, 3, 1};
 
void plus(void) {
    for (int i = 0; i < MAXDIG; i++)
    {
        mhigh[i] = mhigh[i] + mlow[i];
        if (mhigh[i] > 9)
        {
            int k = i + 1;
            mhigh[i] = mhigh[i] - 10;
            mhigh[k] = mhigh[k] + 1;
        }
    }
}
 
void minus(void)
{
    for (int i = 0; i < MAXDIG; i++)
    {
        mhigh[i] = mhigh[i] - mlow[i];
        if (mhigh[i] < 0)
        {
            int k = i + 1;
            mhigh[i] = mhigh[i] + 10;
            mhigh[k] = mhigh[k] - 1;
        }
    }
}
 
void print(void)
{
    int bw = 0;
    for (int iw = MAXDIG-1; iw >= 0; iw--)
    {
        if (mhigh[iw] != 0 || bw == 1)
        {
            printf("%i", mhigh[iw]);
            bw = 1;
        }
    }
    printf("\n\n");
}
 
 
int main(void)
{
    print();
    return 0;
}
но это не точно.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,319
26.03.2026, 20:41
Цитата Сообщение от stake-k26 Посмотреть сообщение
Extazy25, думается мне, что от вас ожидали увидеть что-то такое:

C
1
#define MAXDIG 256
Для классического С - именно так. В современном С уже можно

C
1
constexpr int MAXDIG = 256;
1
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
26.03.2026, 21:16
Можете ещё добавить разбор числа по разрядам %10 и /10, чтобы можно было в каждую ячейку записать не только кодировку числа от 0 до 9, а побольше.
0
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
29.03.2026, 20:03
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
//prog_big_integer_original_plus_clone
#include<stdio.h>
 
#define MAXDIG 256
 
//Запись числа в массив ahigh производится в обратном порядке, и каждый разряд нужно записать в свою ячейку.
int ahigh[MAXDIG]={0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9};
int  alow[MAXDIG];
 
int copyarr(){for(int i=MAXDIG-1; i>=0; i--){alow[i]=ahigh[i];}}
 
int original_plus_clone(){
  for(int i=0; i<MAXDIG; i++){
     ahigh[i]=ahigh[i]+alow[i];
   if(ahigh[i]>9){ahigh[i]=-10+ahigh[i];
    ahigh[i+1]=ahigh[i+1]+1;
}}}
 
int print(){int bw=0;for(int iw=MAXDIG-1; iw>=0; iw--){if((ahigh[iw]!=0)||(bw==1)){printf("%i",ahigh[iw]); bw=1;}}printf("\n\n");}
 
int main(){  
  copyarr(); 
  original_plus_clone(); 
  print(); 
   
  // ниже, значение взятое с онлайн калькулятора больших чисел, для сверки: 
 printf("1975308642197530864219753086421975308642197530864219753086421975308642197530864219753086420\n\n"); //=((9...0)rep_9) * 2
return 0;}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,319
29.03.2026, 20:31
Цитата Сообщение от Extazy25 Посмотреть сообщение
C
1
int copyarr(){for(int i=MAXDIG-1; i>=0; i--){alow[i]=ahigh[i];}}
А в чем гениальный смысл этой мега-функции копирования массивов? Почему она копирует массив именно в порядке уменьшения индексов?

Отдельный вопрос: почему она объявлена, как возвращающая int, но при этом ничего не возвращает? (Там же самая история и с остальными функциями.)

P.S. Умиляет то, что в main - единственной функции, в которой как раз таки не обязательно было писать явный return, он таки присутствует. А в остальных - нет.
0
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
29.03.2026, 21:09
2^1000:

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
//prog_big_integer_original_plus_clone
#include<stdio.h>
 
#define MAXDIG 1024
 
//Запись числа в массив ahigh производится в обратном порядке, и каждый разряд нужно записать в свою ячейку.
int ahigh[MAXDIG]={2};
int  alow[MAXDIG];
 
int copyarr(){for(int i=MAXDIG-1; i>=0; i--){alow[i]=ahigh[i];}}
 
int original_plus_clone(){
  for(int i=0; i<MAXDIG; i++){
     ahigh[i]=ahigh[i]+alow[i];
   if(ahigh[i]>9){ahigh[i]=-10+ahigh[i];
    ahigh[i+1]=ahigh[i+1]+1;
}}}
 
int print(){int bw=0;for(int iw=MAXDIG-1; iw>=0; iw--){if((ahigh[iw]!=0)||(bw==1)){printf("%i",ahigh[iw]); bw=1;}}printf("\n\n");}
 
int main(){  
for(int rep=0; rep<(1000)-1; rep++){
  copyarr(); 
  original_plus_clone(); }
  print(); 
   
  // ниже, значение взятое с онлайн калькулятора больших чисел, для сверки: 
 
printf("\n\n10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376\n\n"); //2^1000
return 0;}
Совершенно правильные вопросы, но вы всегда можете подправить мой код в своëм представлении, я дело в том, что ищу подход с разных сторон, экспериментирую пока пишу, поэтому там может остаться много мусора, в этом коде, но самое главное, чтобы он не влиял на результат работы этого кода.
0
фрилансер
 Аватар для Алексей1153
6500 / 5731 / 1133
Регистрация: 11.10.2019
Сообщений: 15,332
29.03.2026, 21:49
форматирование - для слабаков
1
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
29.03.2026, 22:21
Согласен, в итоге это получился достаточно долгий метод, поэтому возводить в степень лучше было-бы функцией умножения, а не сложения.
0
2493 / 1157 / 709
Регистрация: 25.04.2016
Сообщений: 3,339
30.03.2026, 21:01
Цитата Сообщение от Extazy25 Посмотреть сообщение
вы всегда можете подправить мой код в своëм представлении
При чем тут наше представление? Если функция объявлена как int foo(void), она должна вернуть целое число. Понимаете? Должна. Если же ваша функция ничего не возвращает, она должна быть объявлена void, например:

C
1
2
3
int print (void) {
    printf("Hello world\n");
}
Неправильно! Должно быть:

C
1
2
3
void print (void) {
    printf("Hello world\n");
}
И это не потому, что у нас представление такое, это требования языка си.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,319
30.03.2026, 21:20
Цитата Сообщение от stake-k26 Посмотреть сообщение
И это не потому, что у нас представление такое, это требования языка си.
Ну если быть педантичным, то язык С (в отличие от С++) на самом деле не требует ничего возвращать из "возвращающих значение" функций, если вызывающий код не пытается использовать результат вызова.

Если вызывающий код будет использовать результат такой функции, то это сразу UB. А если возвращаемое значение игнорируется, то код является формально корректным, хоть и неряшливым.
0
2493 / 1157 / 709
Регистрация: 25.04.2016
Сообщений: 3,339
30.03.2026, 23:19
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ну если быть педантичным
а давайте:

C
1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
 
int print (void) {
    printf("Hello world\n");
}
 
int main (void) {
    print();
    return 0;
}
Code
1
gcc -Wall -Werror -Wextra -pedantic -std=c99 file.c -o program
file.c: In function ‘print’:
file.c:5:1: error: control reaches end of non-void function [-Werror=return-type]
5 | }
| ^
cc1: all warnings being treated as errors
make: *** [Makefile:8: program] Ошибка 1
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,319
30.03.2026, 23:58
Цитата Сообщение от stake-k26 Посмотреть сообщение
а давайте:
У вас там -Werror прописан. А -Werror - это не "педантичность", это оголтелая разнузданная солдафонщина.

Хотите педантичность - -pedantic или -pedantic-errors. Но ни в моем случае не -Werror.
0
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
31.03.2026, 07:38
А в скобках int main (void) зачем писать?
В смысле вот так void main() не достаточно?
0
фрилансер
 Аватар для Алексей1153
6500 / 5731 / 1133
Регистрация: 11.10.2019
Сообщений: 15,332
31.03.2026, 07:47
Extazy25, это Сишная фишка, чтобы туда нельзя было что угодно подставить
0
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
31.03.2026, 08:01
Я понял, Си низкоуровневый язык программирования, а низкоуровневый язык программирования очень близко расположен к железу, а ,например, у микроконтроллеров, есть такое правило, то что входные пины должны быть подтянуты резистором, чтобы они не болтались в воздухе, ну а про выходные пины тут дело в том, что вообще зачем делать лишении телодвижения и нагружать систему по пусту, без извлечения из этого полезного действия.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13211 / 6844 / 1824
Регистрация: 18.10.2014
Сообщений: 17,319
31.03.2026, 08:55
Цитата Сообщение от Extazy25 Посмотреть сообщение
А в скобках int main (void) зачем писать?
В классическом языке С объявления с пустыми () являются объявлениями без прототипов. Такие объявления - deprecated, их следует избегать. То есть в классическом С функция без параметров - не (), а именно (void).

Однако начиная с С23 () становится полностью эквивалентно (void). То есть начиная с С23 можно писать просто ().

Цитата Сообщение от Extazy25 Посмотреть сообщение
В смысле вот так void main() не достаточно?
main всегда возвращает int. А далее - см выше.
1
 Аватар для Наталья8
625 / 383 / 67
Регистрация: 09.03.2016
Сообщений: 4,280
02.04.2026, 04:32

И слово - print, мне не кажется хорошим словом для названия функций.
(На всякий случай...)
1
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
02.04.2026, 20:38
Ага, правильно вы подметили, я сам недавно запутался, и полчаса искал ошибку, а оказалось, что там где надо было printf написать, я написал print, и таким образом пытался получить от неë совершенно другое.
Дело не в том что как правильно или не правильно писать, а вот даже больше как-то в таком дело, чтобы самому не запутаться.


Добавлено через 2 часа 40 минут
Продолжим великие дела по теме:

Функция записи строки из массива char в массив int:
char ch[]={"1234567890"};
#define MAXDIG 1024
int ci[MAXDIG];

C
1
void strtoint(void){int couc=(sizeof(ch)/sizeof(char))-1; for(int i=0; i<couc; i++){ci[i]=ch[(couc-1)-i]-48;}}
Добавлено через 50 минут
Как сейчас помню, пятый класс, я беру андройд на линуксе, и пишу прогу, чтобы помочь бабуле, с пирожками, эхх, вот это были времена:

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
#include <stdio.h> 
#include <math.h> 
#include <limits.h>
 
#define NUMSYSTEM 2 //or value input ULLONG_MAX
#define COUDIGIT 3
 
int cou[COUDIGIT][2]={'\0'};
 
void mycounter(
unsigned long long assignnumsys, 
unsigned int assigndigitcou){ 
 for(int dc=assigndigitcou-1; dc>=0; dc--){
     printf("%LU ",(int)cou[dc][1]);
  if(cou[dc][0]<pow(assignnumsys,dc)-1){
        cou[dc][0]++;}else{cou[dc][0]=0;  
  if(cou[dc][1]<assignnumsys-1){
        cou[dc][1]++;}else{cou[dc][1]=0;
  }}
 }printf("\n");}
 
int main(void){
for(int ns=0; ns<pow(NUMSYSTEM,COUDIGIT); ns++){
    mycounter(NUMSYSTEM,COUDIGIT);}
}
1
 Аватар для Наталья8
625 / 383 / 67
Регистрация: 09.03.2016
Сообщений: 4,280
02.04.2026, 22:28
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (SetCursorPos(rect.left, rect.top)) {
        POINT cursorPos{};  Sleep(300);
        if (GetCursorPos(&cursorPos)) {
          HWND chrom_hwnd = WindowFromPoint(cursorPos);
            char className[255]{};
            GetClassNameA(chrom_hwnd, className, sizeof(className));
            
            if ((mouse_keys_DOWN == MOUSEEVENTF_RIGHTDOWN && strcmp(className+7, "WindowClass") != 0) ||
                (mouse_keys_DOWN == MOUSEEVENTF_LEFTDOWN && strcmp(className+7, "DropShadowWindowClass") != 0))
            {
        SetCursorPos(cur_Pos.x, cur_Pos.y);
                MessageBox(NULL, L"Не попал!", L"Error", MB_OK |
                    MB_ICONQUESTION | MB_SETFOREGROUND | MB_SYSTEMMODAL);
                return false;
            }   }   }
А какое слово я скушал в строке 8 - 9... Из семи букв.?
0
-50 / 1 / 0
Регистрация: 20.01.2026
Сообщений: 24
08.04.2026, 19:11
Умножим
9876543210987654321098765432109876543210 9876543210987654321098765432109876543210 9876543210
на
123456789:

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
//Умножение обратной записи разрядов числа в массиве на обычное число int:
#include<stdio.h>
 
#define MAXDIG 1024
 
//запись числа в массив arrh производиться в обратном порядке, и каждый разряд нужно записать в свою ячейку массива.
int arrh[MAXDIG]={0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9};
unsigned int intl=123456789; //intl это обычное число, на которое умножается arrh. 
 
int  arrres[MAXDIG]={'\0'}; //массив с результатом
 
int main()
{   
for(int i=0; i<MAXDIG; i++){
   arrres[i]=arrres[i]+(arrh[i]*intl);
   
   
     if(arrres[i]>9){ 
          arrres[i+1]=arrres[i+1]+(arrres[i]/10); 
          arrres[i]=arrres[i]%10;
     }  
}
 
   //вывод результата на экран:
   int bw=0; for(int iw=MAXDIG-1; iw>=0; iw--){if((arrres[iw]!=0)||(bw>0)){printf("%i",arrres[iw]); bw=1;}}
   
   //ниже, для сверки, пропишется значение взятое с онлайн калькулятора больших чисел:
    printf("\n\n121932631124828532112482853211248285321124828532112482853211248285321124828532112482853211126352690");
return 0;}


Тестируя этот код я выявил, что у меня максимально число intl может быть только 217432719
,а дальше при intl=217432720 этот код работает неправильно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
08.04.2026, 19:11

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

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

Длинная арифметика: возведение в степень
Вычислить с помощью алгоритмов длинной арифметики значение числа 3^5000 и представить его в шестнадцатеричной системе счисления. Помогите...

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

Длинная арифметика: вывести n чисел Фибоначчи
Вывести в консоль n чисел Фибоначчи без переполнения #include &lt;stdio.h&gt; int main() { unsigned long long n = 256, i = 0, j =...


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

Или воспользуйтесь поиском по форуму:
80
Ответ Создать тему
Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru