Быстрый способ вручную изменить номер

Question

Мне нужно иметь возможность рассчитать (a ^ b)% c для очень больших значений a и b (которые по отдельности устанавливают предел и вызывают ошибки переполнения при попытке вычислить a ^ b). Для достаточно малых чисел использование идентификатора (a ^ b)% c = (a% c) ^ b% c работает, но если c слишком велико, это действительно не поможет. Я написал цикл для выполнения операции мод вручную, по одному:

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

но это занимает очень много времени. Есть ли простой и быстрый способ выполнить эту операцию, не прибегая к степени b и не используя трудоемких циклов? Если ничего не помогает, я могу создать массив bool для представления огромного типа данных и выяснить, как сделать это с помощью побитовых операторов, но должен быть лучший способ.

Answer 1

Можете ли вы множить a, b или c? Имеет ли C известный диапазон?

Это 32-битные целые числа! Проверьте этот сайт

Например, вот как вы получаете мод n% d, где d 1 >> s (1,2,4,8, ...)

  int n = 137;     // numerator
  int d = 32;      // denom d will be one of: 1, 2, 4, 8, 16, 32, ...
  int m;           // m will be n % d
  m = n & (d - 1); 

Существует код для n% d, где d равно 1 >> s - 1 (1, 3, 7, 15, 31, ...)

Это действительно поможет, только если c мало, как вы сказали.