acelerar la "conversión base" para enteros grandes

Question

Estoy usando un algoritmo de conversión de base para generar una permutación a partir de un entero grande (dividido en palabras de 32 bits).

utilizo un algoritmo relativamente estándar para esto:

/* N = count,K is permutation index (0..N!-1) A[N] contains 0..N-1 */ 
i = 0; 
while (N > 1) { 
    swap A[i] and A[i+(k%N)] 
    k = k/N 
    N = N - 1 
    i = i + 1 
} 

Por desgracia, la brecha y Modulo cada iteración se suma, en especial de trasladarse a grandes números enteros - Pero, al parecer tan sólo pudiera utilizar multiplican!

/* As before, N is count, K is index, A[N] contains 0..N-1 */ 
/* Split is arbitrarily 128 (bits), for my current choice of N */ 
/* "Adjust" is precalculated: (1 << Split)/(N!) */ 
a = k*Adjust; /* a can be treated as a fixed point fraction */ 
i = 0; 
while (N > 1) { 
    a = a*N; 
    index = a >> Split;   
    a = a & ((1 << Split) - 1); /* actually, just zeroing a register */  
    swap A[i] and A[i+index] 
    N = N - 1 
    i = i + 1 
} 

Esto es mejor, pero hacer multiplicaciones de números enteros grandes es todavía lento.

Pregunta 1:
¿Hay alguna manera de hacerlo más rápido?

Por ejemplo. Como sé que N * (N-1) es menor que 2^32, ¿podría sacar esos números de una palabra y unirme a los "restos"?
O, ¿hay alguna manera de modificar un decodificador aritético para extraer las indicaciones de a una por vez?

Pregunta 2:
En aras de la curiosidad - si uso la multiplicación para convertir un número de base 10 sin el ajuste, entonces el resultado se multiplica por (10^dígitos/2^turno). ¿Hay alguna manera complicada de eliminar este factor trabajando con los dígitos decimales? Incluso con el factor de ajuste, parece que sería más rápido: ¿por qué las bibliotecas estándar no usarían esto frente a dividir y modificar?

Answer 1

No se conocen los algoritmos, pero los que se usan parecen bastante simples, así que realmente no veo cómo se puede optimizar el algoritmo.

Es posible utilizar enfoques alternativos:

• uso ASM (ensamblador) - a partir de mi experiencia, después de mucho tiempo tratando de averiguar cómo debe un cierto algoritmo sería escrito en ASM, que terminó siendo más lenta que la versión generada por el compilador :) Probablemente porque el compilador también sabe cómo diseñar el código para que el caché de la CPU sea más eficiente y/o qué instrucciones son realmente más rápidas y qué situaciones (esto fue en GCC/linux).
• uso multi-procesamiento:
  • hacer su multiproceso algoritmo, y asegúrese de que se ejecuta con el mismo número de hilos como el número de núcleos de CPU disponibles (hoy en dia de la mayor parte de la CPU tienen múltiples núcleos/multihilo)
  • maquillaje usted algoritmo capaz de ejecutarse en múltiples máquinas en una red, y diseñar una forma de enviar estos números a las máquinas en una red, por lo que puede utilizar su poder de CPU.

Answer 2

Al ver que se está hablando de números como 2^128/(N!), Parece que en su problema N va a ser más bien pequeño (N < 35 según mis cálculos). Sugiero tomar el algoritmo original como punto de partida; primero cambie la dirección del ciclo:

i = 2; 
while (i < N) { 
    swap A[N - 1 - i] and A[N - i + k % i] 
     k = k/i 
     i = i + 1 
} 

Ahora cambie el ciclo para hacer varias permutaciones por iteración. Supongo que la velocidad de división es la misma independientemente del número i, siempre que yo < 2^32.
Dividir el rango 2 ...N-1 en sub-rangos de modo que el producto de los números en cada sub-intervalo es menor que 2^32:

2, 3, 4, ..., 12: product is 479001600 
13, 14, ..., 19: product is 253955520 
20, 21, ..., 26: product is 3315312000 
27, 28, ..., 32: product is 652458240 
33, 34, 35:  product is 39270 

Luego, se divide el número de larga k por los productos en lugar de dividir por i. Cada iteración arrojará un resto (menos de 2^32) y un número más pequeño k. Cuando tenga el resto, puede trabajar con él en un bucle interno utilizando el algoritmo original; que ahora será más rápido porque no involucra una división larga.
Aquí hay un código:

static const int rangeCount = 5; 
static const int rangeLimit[rangeCount] = {13, 20, 27, 33, 36}; 
static uint32_t rangeProduct[rangeCount] = { 
    479001600, 
    253955520, 
    3315312000, 
    652458240, 
    39270 
}; 

for (int rangeIndex = 0; rangeIndex < rangeCount; ++rangeIndex) 
{ 
    // The following two lines involve long division; 
    // math libraries probably calculate both quotient and remainder 
    // in one function call 
    uint32_t rangeRemainder = k % rangeProduct[rangeIndex]; 
    k /= rangeProduct[rangeIndex]; 

    // A range starts where the previous range ended 
    int rangeStart = (rangeIndex == 0) ? 2 : rangeLimit[rangeIndex - 1]; 

    // Iterate over range 
    for (int i = rangeStart; i < rangeLimit[rangeIndex] && i < n; ++i) 
    { 
     // The following two lines involve a 32-bit division; 
     // it produces both quotient and remainder in one Pentium instruction 
     int remainder = rangeRemainder % i; 
     rangeRemainder /= i; 
     std::swap(permutation[n - 1 - i], permutation[n - i + remainder]); 
    } 
} 

Por supuesto, este código puede extenderse a más de 128 bits.
Otra optimización podría implicar la extracción de potencias de 2 de los productos de rangos; esto podría agregar una ligera aceleración haciendo que los rangos sean más largos. No estoy seguro de si esto vale la pena (tal vez para valores grandes de N, como N = 1000).