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

@fasked · Регистрация: 07.10.2009

Студворк — интернет-сервис помощи студентам

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

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

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

Начальный план действий будет таков:

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

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

PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута.

@fasked · 28.07.2010, 02:48 **[ТС]**

Немного освободился сейчас. Продолжаю тему

Обещанная "модная" реализация сложения (далее весь код пойдет в таком же стиле)

Сложение

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
void bi_add(PBIGINT a, PBIGINT b, PBIGINT c)
{
    PBIGINT lsda, msda, lsdb, msdb;
    
    PBIGINT ptrc  = BI_LSDPTR(c);
    ULONG   carry = 0;
 
    if(BI_GETLEN(a) < BI_GETLEN(b))
    {
        lsda = BI_LSDPTR(b);
        lsdb = BI_LSDPTR(a);
        msda = BI_MSDPTR(b);
        msdb = BI_MSDPTR(a);
    }
    else
    {
        lsda = BI_LSDPTR(a);
        lsdb = BI_LSDPTR(b);
        msda = BI_MSDPTR(a);
        msdb = BI_MSDPTR(b);
    }
 
    while(lsdb <= msdb)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ + *lsdb++ + 
                                   (ULONG)(USHORT)(carry >> BI_BITPERREG));
 
    while(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ + 
                                   (ULONG)(USHORT)(carry >> BI_BITPERREG));
 
    if(carry >> BI_BITPERREG)
        *ptrc++ = 1;
 
    BI_SETLEN(c, ptrc - BI_LSDPTR(c));
}

Сложение длинного числа с простым

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bi_add_us(PBIGINT a, USHORT b, PBIGINT c)
{
    PBIGINT lsda = BI_LSDPTR(a), msda = BI_MSDPTR(a);
    PBIGINT ptrc = BI_LSDPTR(c);
    ULONG  carry = 0;
 
    if(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ + (ULONG)b + 
                                   (ULONG)(USHORT)(carry >> BI_BITPERREG));
    else
        *ptrc++ = (USHORT)(b);
 
    while(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ + 
                                   (ULONG)(USHORT)(carry >> BI_BITPERREG));
 
    if(carry >> BI_BITPERREG)
        *ptrc++ = 1;
 
    BI_SETLEN(c, ptrc - BI_LSDPTR(c));
}

Умножение

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
void bi_mul(PBIGINT a, PBIGINT b, PBIGINT c)
{
    PBIGINT lsda, msda, lsdb, msdb;
    PBIGINT ptra, ptrb, ptrc, ptrct;
 
    ULONG carry = 0;
 
    if(BI_GETLEN(a) < BI_GETLEN(b))
    {
        ptra = b;
        ptrb = a;
    }
    else
    {
        ptra = a;
        ptrb = b;
    }
 
    msdb = BI_MSDPTR(ptrb);
    msda = BI_MSDPTR(ptra);
 
    for(ptrc = BI_LSDPTR(c), lsda = BI_LSDPTR(ptra), lsdb = BI_LSDPTR(ptrb); lsdb <= msdb; ++lsdb, ++ptrc)
        *ptrc = (USHORT)(carry = (ULONG)*lsda * (ULONG)*lsdb +
                                 (ULONG)(USHORT)(carry >> BI_BITPERREG));
    
    *ptrc = (USHORT)(carry >> BI_BITPERREG);
 
    for(ptrc = BI_LSDPTR(c) + 1, lsda = BI_LSDPTR(ptra) + 1; lsda <= msda; ++lsda, ++ptrc)
    {
        carry = 0;
        for(ptrct = ptrc, lsdb = BI_LSDPTR(ptrb); lsdb <= msdb; ++lsdb, ++ptrct)
            *ptrct = (USHORT)(carry = (ULONG)*lsda * (ULONG)*lsdb + (ULONG)*ptrct +
                                      (ULONG)(USHORT)(carry >> BI_BITPERREG));
 
        *ptrct = (USHORT)(carry >> BI_BITPERREG);
    }
 
    if(carry >> BI_BITPERREG)
        ++ptrc;
 
    BI_SETLEN(c, ptrc - BI_LSDPTR(c));
}

Умножение длинного числа и простого

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bi_mul_us(PBIGINT a, USHORT b, PBIGINT c)
{
    PBIGINT lsda = BI_LSDPTR(a), msda = BI_MSDPTR(a);
    PBIGINT ptrc = BI_LSDPTR(c);
 
    ULONG carry = 0;
 
    while(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ * (ULONG)b +
                                   (ULONG)(USHORT)(carry >> BI_BITPERREG));
 
    *ptrc = (USHORT)(carry >> BI_BITPERREG);
 
    if(carry >> BI_BITPERREG)
        ++ptrc;
 
    BI_SETLEN(c, ptrc - BI_LSDPTR(c));
}

Тестирование

Здесь результаты выполнения функций.

Code
1
2
3
4
5
6
7
8
a = 48230029
b = 678418be
c = FFFF
 
a + b = afa718e7
a + c = 48240028
a * b = 4e156621f66e
a * c = 4822b805ffd7

Code
1
2
3
4
5
6
7
8
a = 678418be48230029
b = 72ae2cd63d6c4ae1
c = FFFF
 
a + b = da324594858f4b0a
a + c = 678418be48240028
a * b = 4539a0deb42b5b1afe09
a * c = 6783b13a2f64b805ffd7

Code
1
2
3
4
5
6
7
8
a = 72ae2cd63d6c4ae1678418be48230029
b = 01eb26e941bb5af16df116495f906952
c = FFFF
 
a + b = 749953bf7f27a5d2d5752f07a7b3697b
a + c = 72ae2cd63d6c4ae1678418be48240028
a * b = 78619ef463ffc83378380ddb1af9c456de22
a * c = 72adba2810960d751ca2b13a2f64b805ffd7

Не по теме:

Как всегда жду критики и комментариев.
Если кому интересно могу описать алгоритм умножения.

Добавлено через 1 час 15 минут
А вот про вычитание забыл совсем

Вычитание

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bi_sub(PBIGINT a, PBIGINT b, PBIGINT c)
{
    PBIGINT lsda = BI_LSDPTR(a), msda = BI_MSDPTR(a);
    PBIGINT lsdb = BI_LSDPTR(b), msdb = BI_MSDPTR(b);
    PBIGINT ptrc = BI_LSDPTR(c);
 
    ULONG carry = 0;
 
    BI_SETLEN(c, BI_GETLEN(a));
 
    while(lsdb <= msdb)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ - (ULONG)*lsdb++ - 
                                   ((carry & BI_BASE) >> BI_BITPERREG));
 
    while(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ -
                                   ((carry & BI_BASE) >> BI_BITPERREG));
 
    BI_DELLDZ(c);    
}

Вычитание обычного числа из длинного

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bi_sub_us(PBIGINT a, USHORT b, PBIGINT c)
{
    PBIGINT lsda = BI_LSDPTR(a), msda = BI_MSDPTR(a);
    PBIGINT ptrc = BI_LSDPTR(c);
 
    ULONG carry = 0;
 
    BI_SETLEN(c, BI_GETLEN(a));
 
    *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ - (ULONG)b - 
                               ((carry & BI_BASE) >> BI_BITPERREG));
 
    while(lsda <= msda)
        *ptrc++ = (USHORT)(carry = (ULONG)*lsda++ -
                                   ((carry & BI_BASE) >> BI_BITPERREG));
 
    BI_DELLDZ(c);  
}

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

@abcdeiko · 12.09.2010, 10:21

Просмотрел бегло тему, довольно увлекательно. А никто не делал арифметические операции с большими вещественными числами? А то везде только целочисленные

@fasked · 12.09.2010, 10:57 **[ТС]**

Сообщение от abcdeiko

А никто не делал арифметические операции с большими вещественными числами? А то везде только целочисленные

Основная проблема придумать, как хранить число, остальное не страшно.

@abcdeiko · 12.09.2010, 11:10

В этом то и вся проблема

И еще один вопросик каким образом лучше считывать большие числа с клавиатуры?

@fasked · 12.09.2010, 11:19 **[ТС]**

Сообщение от abcdeiko

В этом то и вся проблема

Самое первое, что приходит в голову, это раздельное хранение порядка числа и мантисы.

Любое число N в системе счисления с основанием q можно записать в виде N = M*q^p, где M — множитель, содержащий все цифры числа (мантисса), а p - целое число, называемое порядком

Так же число придется нормализовать для более эффективного хранения. То есть первая цифра после точки должна быть отличной от нуля.

Сообщение от abcdeiko

И еще один вопросик каким образом лучше считывать большие числа с клавиатуры?

Читайте сначала в строку, а потом переводите строку в число поразрарядно. Смысл перевода длинного числа ничем не отличается от перевода обычного.

@abcdeiko · 12.09.2010, 18:01

В строку то у нас влезает 256 символов? А если более?
Где-то видел что предлагают посимвольно getch'ем считывать

@ForEveR · 12.09.2010, 18:12

abcdeiko, В строку влезает любое кол-во символов. В зависимости от размера строки

24.09.2010, 21:29

Здравствуйте. Вот вы тут ведете разговор про длинную арифметику. А у меня как раз не получается реализовать алгоритм модулярного умножения. У меня есть его псевдокод,но я не во всем разбираюсь...мне сложнова-то... Может вы сможете разобраться.
Вот собственно сам псевдокод:

Pascal
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
m_shifts:=0;
while n[m_shifts]=0 do
begin
shift_left(N and A);
m_shifts:=m_shifts+1;
end;
m:=m_shifts;
reset(P);
n_short:=N[m];
for i:= down to 1 do
begin
shift_left(P):{сдвиг на 1 элемент влево или умножение P*r}
if b<>0 then
addk(A*B[i],{to}P);
let p_short represent the 2 high assimilated digits of P;
k:=abs(p_short)div n_short;
if p_short-k*n_short>n_short div 2 then k:=k+1;
if k>0 then
begin
if p_short<0 then
addk(k*N,{to}P)
else
addk(-k*N,{to}P);
end;
end;{for}
right shift P,N by m_shifts;
if P<0 then
P:=P+N;
white(P); {P - результат}
Псевдокод P+k*N (процедуры addk) тож имеется
carry:=0;
for i:=1 to m do
begin
t:=P[i]+k*N[i]+carry;
P[i]:=t mod r;
carry:=t div r;
end;
P[m+1]:=carry;
write(P);{P-результат}

А вот что у меня получилось перевести на С++:

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
void addk(_______)
{
int carry = 0, t;
for (int i = 0; i < m; i++)
{
t = P[i] + k * N[i] + carry;
P[i] = t % r;
carry = t / r;
}
P[m + 1] = carry;
}
 
void P()
{
int m_shifts = 0;
while (n[m_shifts] == 0)
{
shift_left(N & A);
m_shifts++;
}
m = m_shifts;
reset(P) - не знаю че такое
n_short = N[m];
for (int i = n; i > 0; i--)
{
shift_left(P);
if (b != 0)
addk(______);
let.... - тоже не знаю че за строчка
k = abs(p_short) / n_short;
if (p_short - k*n_short > n_short / 2)
k++;
if (k > 0)
{
if (p_short < 0)
{
addk(_____);
}
else
{
addk(_____);
}
}
}
//right shift P, N by m_shift - тоже не знаю что
if (P < 0)
P += N;
}

Сам этот псевдокод взят из книги Казарина,из 2 главы. Вот такая не простая задачка... Очень нужна ваша помощь...

@андреич · 11.03.2011, 17:15

я вот думал, над реализацией вещественных чисел, ведь числа то могут быть реально большими. и я мечусь в выборе :то ли представлять число как список, то ли представлять через динамический массив.

@fasked · 11.03.2011, 18:26 **[ТС]**

Сообщение от андреич

и я мечусь в выборе :то ли представлять число как список

а какой смысл в представлении числа списком?

@Vergil111 · 11.03.2011, 18:37

Если интересует, могу подбросить пару идей и функций по поводу модульной арифметики, которая так же очень популярна в криптографии. А так же реализацию некоторых популярных алгоритмов шифрования(Эль-Гамаля, RSA), основанных как раз на модульной арифметике и арифметики длинных чисел. Просто очень интересуюсь всякими шифрами и их взламыванием и готов помочь любому в данной теме))

07.04.2011, 02:26

Здравствуйте.
очень интересная тема - как раз с ней разбираюсь сейчас....
Есть вопрос - не могу найти где вы определили такие макросы как BI_BITPERREG и BI_SETLEN.... - которые используются в операциях умножения, деления и вычитания..... - для целостной картины их не хватает - не могли бы вы их выложить?

@fasked · 07.04.2011, 10:23 **[ТС]**

Сообщение от yakobian

BI_BITPERREG

Количество бит в одном регистре большого числа, если используете USHORT то должно быть равно 16, ну или для точности:

C
1
#define BI_BITPERREG (sizeof(USHORT) * 8)

Сообщение от yakobian

BI_SETLEN

Изменяет значение регистра, в котором хранится длина числа, если длина хранится в первом разряде, то выглядеть должен примерно так:

C
1
#define BI_SETLEN(bi, len) (*(bi) = len)

@vananabu · 09.05.2011, 00:10

Сообщение от Vergil111

Если интересует, могу подбросить пару идей и функций по поводу модульной арифметики, которая так же очень популярна в криптографии. А так же реализацию некоторых популярных алгоритмов шифрования(Эль-Гамаля, RSA), основанных как раз на модульной арифметике и арифметики длинных чисел. Просто очень интересуюсь всякими шифрами и их взламыванием и готов помочь любому в данной теме))

Если можешь, поделись, пожалуйста исходниками для RSA. Время поджимает. Просто не успеваю. Буду очень благодарен!

23.05.2011, 21:16

Да, кстати, еще непонятно по поводу BI_BASE, и BI_DELLDZ ?
В данный момент занимаюсь реализацией на базе этой схемы деления, степени, модуля и алгоритма Карацубы-Оффмана - надеюсь тема еще попудярна - есть ли смысл выкладывать?

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

@fasked · 24.05.2011, 03:23 **[ТС]**

Сообщение от yakobian

BI_BASE

Максимальное значение в одном разряде + 1. Для unsigned short будет равна 1 << 16.

Сообщение от yakobian

BI_DELLDZ

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

Сообщение от yakobian

есть ли смысл выкладывать?

Если не жалко - выкладывайте, почему нет

Может кому пригодится.

Сообщение от yakobian

А какой вы использовали алгоритм для генерации случайных чисел в них?

Это самая сложная часть в RSA, надо сказать.

@taras atavin · 24.05.2011, 05:46

Сообщение от fasked

Арифмитические операции одинаковы и в Си и в Си++.

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

Добавлено через 5 минут

Сообщение от fasked

Поэтому подходящим выбором будут 16-битовые числа. Сейчас я попытаюсь объяснить почему.

Не согласен, так как большинство современных процессоров умеют складывать и вычистать 32-х разрядные числа, причём, одна 32-х разрядна операция требует меньше времени, чем две 16-ти разрядные.

Добавлено через 3 минуты

Сообщение от fasked

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

и совсем весело физический массив иметь старший в младшем, а его шесдесят пять тысяч пятьсот шесдесят пятеричные цифры - младший в младшем.

Добавлено через 5 минут

Сообщение от usernet009

Дальше шло деление но, на нем я остановился ибо деление давало дробный результат

Целый тип не имеет операции деления, это операция с действительными чисслами, а в целом типе вместо него есть операция деления на цело, возвращающая только целую часть той самой дроби.

@fasked · 24.05.2011, 05:50 **[ТС]**

taras atavin,

Не по теме:

Толсто. Ничего не скажешь...

Сообщение от taras atavin

Операции и на плюсах будут чисто сёвыми, но всё таки елси ты делаешь свой тип данных, то их целесообразно завернуть в класс.

В Си уже есть ООП и классы?

А как ты собираешься на чистых сях опеределять свои операторы?

В Си уже и операторы и их перегрузка появилась?

Или вместо них будут функции?

Ну вроде больше ничего и не остается.

Да и стандартные математические функции как будешь перегружать? Или для того же синуса введёшь новое имя?

Использование префиксов в именах при программировании на Си это общепринятое явление. И, кстати, вот так сразу я не могу припомнить задачи, для решения которой требуется вычислять синус длинного числа.

Сообщение от taras atavin

Не согласен, так как большинство современных процессоров умеют складывать и вычистать 32-х разрядные числа, причём, одна 32-х разрядна операция требует меньше времени, чем две 16-ти разрядные.

Процессоры то они, конечно, умные железяки и многое умеют, но переполнение в разряде контролировать Вы предлагаете ассемблерной вставкой?

Сообщение от taras atavin

и совсем весело физический массив иметь старший в младшем, а его шесдесят пять тысяч пятьсот шесдесят пятеричные цифры - младший в младшем.

Не понял о чем это Вы здесь.

Не по теме:

Сообщение от taras atavin

Целый тип не имеет операции деления, это операция с действительными чисслами, а в целом типе вместо него есть операция деления на цело, возвращающая только целую часть той самой дроби.

А Вам не надоедает спорить и разводить трололо?

@taras atavin · 24.05.2011, 05:58

Сообщение от fasked

В Си уже есть ООП и классы?

Ваще то это аргумент в пользу плюсов.

Добавлено через 41 секунду

Сообщение от fasked

В Си уже и операторы и их перегрузка появилась?

Опять таки о том и речь, что на чистых сях это не предусмотрено.

Добавлено через 3 минуты

Сообщение от fasked

Использование префиксов в именах при программировании на Си это общепринятое явление. И, кстати, вот так сразу я не могу припомнить задачи, для решения которой требуется вычислять синус длинного числа

А собираешься ограничиться длинными целыми? Представь себе такой проект:
1. Подкласс - игра.
2. Мир - галактика, представлен единой локацией.
3. Можно двигаться под углом к координатным осям.
4. Требуется имимтировать непрерывность такого движения.

Добавлено через 1 минуту

Сообщение от fasked

Процессоры то они, конечно, умные железяки и многое умеют, но переполнение в разряде контролировать Вы предлагаете ассемблерной вставкой?

А как без сисемблера?

@fasked · 24.05.2011, 06:01 **[ТС]**

Сообщение от taras atavin

Ваще то это аргумент в пользу плюсов.

Сообщение от taras atavin

Опять таки о том и речь, что на чистых сях это не предусмотрено.

Во-вторых, аргументы не существенны, чтобы использовать Си++, а не Си. А во-первых, здесь обсуждается не выбор языка для решения задачи. Читайте заголовок топика и вообще весь топик целиком.

В связи с добавлением еще одного сообщения предлагаю Вам еще раз перечитать топик, о каких именно задачах шла речь, а также обратить внимание на дату создания топика в частности.

В связи с добавлением еще одной части сообщения:

Сообщение от taras atavin

А как без сисемблера?

Использовать 16-битовые разряды длинного числа на архитектуре x86 и 32-битовые разряды на архитектуре x64.

Новые блоги и статьи Все статьи Все блоги /
Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .	Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .	Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .	Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой anaschu 23.05.2026 Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .
Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15 anaschu 23.05.2026 Внезапно хорошее здоровье сотрудников не нужно капиталистам?))	Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул anaschu 23.05.2026 Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .	Диалоги с ИИ zorxor 23.05.2026 Насколько я понимаю - Вы - Искусственный Интеллект. Это так? Да, всё верно. Я — искусственный интеллект. Я представляю собой большую языковую модель, созданную для помощи в самых разных задачах. . . .	Модель здравосохранения 14. Собираем всю модель вместе. anaschu 22.05.2026 Модель собрана. В будущих постах на видео я покажу, как она работает. В этом посте запускаем её, проверяем результаты и разбираем что можно с ней делать дальше. Перед запуском проверяем. . .

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

Решение

Решение

@fasked 5045 / 2624 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 5

	Длинная арифметика на Си 12.07.2010, 19:01. Показов 102819. Ответов 81 Метки длинная арифметика, длинные числа, математические операции (Все метки) Здравствуйте, форумчане! Хотелось бы мне начать топик, сообщения в котором я планирую пополнять постоянно (по возможности и уровню занятости, разумеется). Тема топика, как видно из заголовка, длинная арифметика. Я не хочу подробно описывать, что такое длинная арифметика и зачем она нужна. Об этом любой может прочитать на той же википедии. Но небольшое вступление сделать все таки надо. В длинной арифметике вычисления производятся над очень большими числами. С точки зрения программирования на языке Си такими числами можно считать любые, которые "не помещаются" в стандартные типы данных, то есть те, которые больше 32-х (64-х) бит. Наиболее популярно применение длинной арифметики, пожалуй, в криптографии. Я знаю, что очень многим студентам в университетах дают задания на длинную арифметику и надеюсь, что кто-то наткнется на эти сообщения и они ему помогут (сам в свое время мучился). Под конечной целью буду предполагать создание библиотеки или пакета (набора функций) для работы с длинными числами, возможно реализация каких-либо криптографических алгоритмов для примера. Начальный план действий будет таков: Представление длинных чисел на языке Си Основные математические операции PS. Я нисколько не претендую на специалиста в данной области. В первую очередь создаю топик для самого себя, чтобы изучить данную тему и как следует в ней разобраться. Но я надеюсь, что это заитересует многих. Я знаю, что только начинаю осваивать языки программирования, поэтому очень надеюсь на поддержку наших гуру во всех аспектах задачи. PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута. 16

@abcdeiko 0 / 0 / 0 Регистрация: 14.02.2010 Сообщений: 8
	12.09.2010, 10:21
	Просмотрел бегло тему, довольно увлекательно. А никто не делал арифметические операции с большими вещественными числами? А то везде только целочисленные 0

@abcdeiko 0 / 0 / 0 Регистрация: 14.02.2010 Сообщений: 8
	12.09.2010, 11:10
	В этом то и вся проблема И еще один вопросик каким образом лучше считывать большие числа с клавиатуры? 0

@abcdeiko 0 / 0 / 0 Регистрация: 14.02.2010 Сообщений: 8
	12.09.2010, 18:01
	В строку то у нас влезает 256 символов? А если более? Где-то видел что предлагают посимвольно getch'ем считывать 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	12.09.2010, 18:12
	abcdeiko, В строку влезает любое кол-во символов. В зависимости от размера строки 0

@андреич 1 / 1 / 0 Регистрация: 31.07.2010 Сообщений: 36
	11.03.2011, 17:15
	я вот думал, над реализацией вещественных чисел, ведь числа то могут быть реально большими. и я мечусь в выборе :то ли представлять число как список, то ли представлять через динамический массив. 0

@Vergil111 31 / 31 / 16 Регистрация: 30.11.2010 Сообщений: 81
	11.03.2011, 18:37
	Сообщение было отмечено как решение Решение Если интересует, могу подбросить пару идей и функций по поводу модульной арифметики, которая так же очень популярна в криптографии. А так же реализацию некоторых популярных алгоритмов шифрования(Эль-Гамаля, RSA), основанных как раз на модульной арифметике и арифметики длинных чисел. Просто очень интересуюсь всякими шифрами и их взламыванием и готов помочь любому в данной теме)) 3

yakobian
	07.04.2011, 02:26
	Здравствуйте. очень интересная тема - как раз с ней разбираюсь сейчас.... Есть вопрос - не могу найти где вы определили такие макросы как BI_BITPERREG и BI_SETLEN.... - которые используются в операциях умножения, деления и вычитания..... - для целостной картины их не хватает - не могли бы вы их выложить?

yakobian
	23.05.2011, 21:16
	Да, кстати, еще непонятно по поводу BI_BASE, и BI_DELLDZ ? В данный момент занимаюсь реализацией на базе этой схемы деления, степени, модуля и алгоритма Карацубы-Оффмана - надеюсь тема еще попудярна - есть ли смысл выкладывать? Добавлено через 2 минуты Vergil111, Вы писали про реализацию криптоалгоритмов.... - интересно посмотреть Ваш вариант - как раз сейчас делаю эти два. А какой вы использовали алгоритм для генерации случайных чисел в них?