вычисление с очень большими числами в c - PullRequest
Новая
       23

вычисление с очень большими числами в c

1 голос
/ 28 января 2020

Я новичок в программировании. Я хочу рассчитать по модулю числа, которое находится в диапазоне от [0,10^24]. Например: (12 * 10^22) % 89 Я знаю, что я не могу сделать это с обычными типами данных, такими как long, integer и так далее. Как я могу это сделать? Есть ли способ сделать это?

Заранее спасибо

Ответы [ 3 ]

5 голосов
/ 28 января 2020

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

#include <stdio.h>


int main(void)
{
    //  Initialize a product.
    int t = 1;

    //  Calculate 10^22 (modulo 89) by multiplying by 10 (modulo 89) 22 times.
    for (int i = 0; i < 22; ++i)
        t = t * 10 % 89;

    //  Multiply by 12 (modulo 89).
    t = t * 12 % 89;

    //  Show the result.
    printf("%d\n", t);
}
1 голос
/ 28 января 2020

Как и в предыдущих ответах, в этом случае вы можете обойтись обычными целыми числами.

Если вам действительно нужны очень большие целые числа (как во многих приложениях для шифрования c), существует несколько библиотек с открытым исходным кодом. около. Ознакомьтесь с библиотекой GNU MP или Flint (Быстрая библиотека для теории чисел ), взгляните на (только заголовок!) Пакет точности C ++ или посмотрите в список Википедии . Большинство из них доступны в виде пакетов для вашего любимого Linux distrtibution.

Многие языки прозрачно обрабатывают большие целые числа, GNU b c (в ближайшем Linux коробка) использует их.

1 голос
/ 28 января 2020

Самый большой гарантированный тип данных C - это uint64_t (см. Stdint.h), который поддерживает до 2 ^ 64 - 1. Я думаю, что предпочтительно поддерживать соответствие стандарту C, когда это возможно, поэтому я ' Я бы предложил сначала упростить проблему, чтобы не использовать типы данных шире. Для этого давайте заимствуем из модульного арифметического c доказательства:

xy % z == ((x % z) * (y % z)) % z

Из этого мы можем сделать вывод, что (12 * 10^22) % 89 == (12 % 89 * 10^11 % 89 * 10^11 %89) % 89 Эта новая версия определенно не так хороша, но все факторы хорошо вписываются в стандартные типы данных C. Упрощение перед вычислением, таким как это, может использоваться для всех данных в вашем диапазоне.

Однако существует проблема с сохранением значения, которое вы хотите по модулю в первую очередь. Разъяснение того, что такое вариант использования, может дать более подходящий ответ. Например, хранится ли значение в строке, возможно, из пользовательского ввода?

В качестве альтернативы, вы можете использовать определенные библиотеки, предназначенные для работы с действительно большими числами. Я не знаю, какой из них лучше всего подходит для ваших целей (я даже не знаю, на какой ОС вы работаете), но если вы хотите изучить эти варианты, просто поищите в Интернете «bignum», «произвольно ... библиотеки "precision" или "бесконечной точности" должны дать вам то, что вы хотите.

...