Обработка переполнения с% - PullRequest
Новая
       45

Обработка переполнения с%

3 голосов
/ 20 октября 2011

У меня есть функция Java, которая выглядит следующим образом: 

private static long fieldPrime = 4294967291L; // 2^32-5
public final static long modMult(long a, long b) {
    long r = (a*b) % fieldPrime;        
    return r;
}

Она умножает два значения (которые гарантированно находятся в диапазоне от 0 до 2 ^ 32-5), а затем выполняет по модулю большое простое число.

Это работает для большинства чисел, но иногда a * b переполняется, и это заставляет функцию возвращать неправильное значение.К сожалению, Java не поддерживает unsigned long (что могло бы решить проблему), а BigInteger слишком медленный.Могу ли я решить эту проблему другим способом?Т.е. можно ли как-то настроить r при обнаружении переполнения (в этом случае a * b <0 всегда означает, что оно переполнено). </p>

Ответы [ 2 ]

4 голосов
/ 20 октября 2011

Это должно работать (если и a, и b находятся между 0 и fieldPrime-1): 

  private static long fieldPrime = 4294967291L; // 2^32-5
  private static long correctionFactor = fieldPrime+25; //fieldPrime + (2^64) mod fieldPrime 

  public final static long modMult(long a, long b) {
      long r = (a*b);
      if (r>=0)
      {
        return r % fieldPrime;
      }
      else
      {
        return ((r% fieldPrime)+correctionFactor)%fieldPrime;  
      }
  }

Когда происходит переполнение, a * b фактически будет a * b - 2 ^ 64, поэтому необходимо добавить (2 ^ 64 mod fieldPrime). Добавление еще одного fieldPrime и еще одной операции% необходимо для получения результата в диапазоне от 0 до fieldPrime-1 (в противном случае он может быть отрицательным).

(Это не будет работать, если fieldPrime> 2 ^ 32.)

EDIT Другая часть также может быть изменена на: 

    return (fieldPrime-a)*(fieldPrime-b)%fieldPrime;

(я не знаю, что быстрее.)

0 голосов
/ 20 октября 2011

Вы можете конвертировать a, b и fieldPrime в удвоенные значения и приводить результат к длинному, если вы снова знаете, что находитесь в безопасном диапазоне (по модулю).Однако возможно, что в некоторых случаях удвоение может вызвать ошибки округления.

Кроме того, я бы сказал, что BigInteger - ваша лучшая ставка, если она слишком медленная, возможно, вы могли бы сделать что-то, что работало бы с байтовыми массивами вместодолго, но я сомневаюсь, что это будет гораздо быстрее.

...