C: Преобразование большого числа из строки в int modulo n

Question

Я пытаюсь преобразовать реальные большие числа (> 100 цифр) из строки в целое число в Z _n additive group (modulo n). n гарантированно будет в стандартном диапазоне C int (скажем n = 12345).

Ни простой подход atoi, ни «%», ни BigIntiger не работают здесь.

Любые идеи, как реализовать это?

Answer 1

Я собираюсь предположить, что вы имели в виду C++ в своем вопросе (нет такой вещи, как C/C++). atoi преобразует строку в число, которое может вписываться в стандартное целое (32 бита), так что это не то, что вы хотите. Вам нужно будет написать свою собственную функцию преобразования.

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

unsigned int convert(const char* s, int n) { 
    long long x = 0; 
    for (char *p = s; *p; p++) { 
     x *= 10; 
     x += (int)(*p - '0'); 
     x %= n; 
    } 
    return x; 
} 

Я покончил с ошибкой для проверки. В качестве упражнения напишите дополнительный код, чтобы убедиться, что s является допустимой строкой с нулевым символом, представляющей большое целое число без какого-либо пробела/дополнительного форматирования.