multiplicación rápida y sustracción módulo un primer

Question

I necesidad de optimizar un cierto código donde multiplicar un vector de enteros (32 bits) por un escalar módulo p (donde p es el número primo (2^32) -5) y luego restar ese vector de otro vector módulo p.

El código es el siguiente:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) { 
    for (int i = 0; i < equationToSubtractFrom.length; i++) { 
     equationToSubtractFrom[i] = modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i])); 
    } 
} 

estoy usando anhela porque Java no soporta enteros sin signo, pero ambos vectores son mod p por lo que se puede esperar que cada número sea 0 = x < < (2^32) -5

¿Alguna idea para optimizar esto? La operación mod p es lo que está ocupando la mayor parte del tiempo de ejecución por lo que una manera de optimizar este posible para hacer de alguna manera no MODP después de la multiplicación y sólo lo hacen después de la sustracción. ¿Alguna idea sobre cómo hacer eso?

Answer 1

Es posible acelerar cálculo y evitar cualquier división en absoluto usando el hecho de que 2^32 = 5 (mod p).

después de la multiplicación y la resta, dividir el resultado a la baja (x% 2^32) y hi (x/2^32) partes. Luego multiplica la parte hi a 5 y suma con la parte baja. Luego repita este procedimiento una vez más. Si el resultado es mayor que p, reste p. Para resultado negativo, agregue p.

Editar: Desde la multiplicación y la resta combinada puede desbordarse, el resultado de la multiplicación debe ser también tomada módulo p. Pero solo un paso del procedimiento anterior es suficiente: simplemente divídalo, multiplíquelo a 5 y agréguelo.

Answer 2

e - (f * e mod p) mod p = (e-e f) mod p 

Ver Wolfram Alpha.

Answer 3

Conozco dos maneras de hacer esto sin necesidad de utilizar la división o módulo:

Método 1: Multiplicación invariante. (see this paper)

La idea básica aquí es precomputar y la aproximación del recíproco del p que le permite hacer una división entera utilizando solo un par de multiplicaciones de números enteros. Luego puedes multiplicar hacia atrás y obtener tu módulo. Este es el enfoque más fácil de implementar.

Método 2: (la que normalmente uso), es el uso de punto flotante. Convierta los números a coma flotante y multiplique por un recíproco precomputado de p. Luego redondee y convierta de nuevo a un número entero. Este enfoque es más difícil de acertar, pero según mi experiencia, es más rápido si se hace correctamente.

Ambos enfoques implican que aquí no hay divisiones, aparte de un pre-cálculo de la inversa ya sea en número entero o de coma flotante.

Si o no cualquiera de estos métodos será más rápido que el uso directo de %, dependerá de qué tan bien los pueda implementar. Así que no puedo garantizar que cualquiera de los dos sea más rápido.