Intentando multiplicar un número de 0..4096 por 0.3 usando solo números enteros

integer scaling

Question

Estoy tratando de comprender cómo multiplicaría un número de 0..4096 por 0.3 usando solo enteros con operaciones de cambio y escalado, sin dividir , en C. Soy nuevo en esto y en cualquier entrada o paso Las sugerencias paso a paso serían extremadamente útiles.

Answer 1

Multiplicar por 0.3 es lo mismo que multiplicar por (0.3*2^n) , luego dividir por 2^n . La segunda etapa es equivalente a un cambio a la derecha de n .

Pero, ¿cuál es el mejor valor de n ?

Para encontrar esto, tome su número entero más grande y encuentre el valor más grande de n tal que pueda multiplicar por (0.3*2^n) sin un desbordamiento. Con enteros sin signo de 64 bits y 4096 como valor máximo, necesita

0.3*2^n <= 2^(64-12)

o

0.3 <= 2^(64-12-n)

Esa desigualdad tiene un máximo de n cuando el RHS es igual a 0.5, entonces

2^-1 = 2^(64-12-n)

entonces -1 = 64-12-n , n = 64-12+1 = 53 .

Entonces la respuesta es multiplicar por 2^53*0.3 luego cambiar a la derecha por 53, es decir

/* designed to work with input values 0 .. 4096 only */
uint64_t
multiplyby0_3 (uint64_t x)
{
    return (x * 2702159776422297ULL) >> 53;
}

Para comprobar que no se desborda y tenemos la mejor n , de bc :

2702159776422297*4096 = 11068046444225728512
2^64                  = 18446744073709551616

IE no se desbordará, pero si lo multiplicamos por 2 nuevamente, lo haría.

Para enteros de 32 bits, la respuesta es multiplicar por 2^21*0.3 luego cambiar a la derecha por 21, es decir

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    return (x * 629146U) >> 21;
}

Y, por último, puede descomponer cualquier multiplicación en una cantidad de adiciones si observa el 1 binario en el multiplicador. Así que permites el ''escalado'' y asumí que eso significaba multiplicarse. Si no, aquí está la versión de 32 bits (la versión de 64 bits se deja como un ejercicio para el lector) que explota el hecho de que 629146 es 10011001100110011010 (un patrón ordenado debido a la fracción binaria recurrente). 10011001100110011001 el otro lado y usaremos 10011001100110011001 en 10011001100110011001 lugar.

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    uint32_t y;
    x += x<<3;    /* * 1001 */
    y = x<<4 + x; /* * 10011001 */
    y += y<<8;    /* * 1001100110011001 */
    y += x<<16;   /* * 10011001100110011001 */
    return y >> 21;
}

Answer 2

Sé que este no es un ejemplo de codificación, lamento eso, pero si el conjunto es tan pequeño (rango [0; 4096]), ¿por qué no crear un bloque de resultados y usar un puntero para extraer valores? Reducirá en gran medida los ciclos de GPU, ya que no hay restricciones de memoria.

Answer 3

Si tiene una multiplicación rápida de enteros, pero no tiene una división de enteros, puede obtener una aproximación razonable al multiplicar por 1229 y luego desplazarse a la derecha por 12 bits. Por ejemplo:

>> 100 * 1229
122900
>> 122900 >> 12
30

Esto funciona porque 1229 es alrededor de 0.3 * 1 << 12 . El valor "real" es 1228.8, por lo que la estimación será alta en 1 en algunos casos (68 de 4097 valores). Sin embargo, nunca será apagado por más de 1.

Answer 4

Simplemente probé muchas combinaciones del formulario (A*x + B) >> n con el siguiente código de prueba y se nos ocurrió:

// Scale by 4915, then shift 14.
int Mult3Tenths(int x) {
  return (x*4915 + 0) >> 14;  // Use 4915L if `int` is 16 bit.
}

Código de prueba

#define N3 (4096)
int main(void) {
  int target[N3 + 1];
  unsigned i;
  for (i = 0; i <= N3; i++) {
    target[i] = 0.3 * i;
  }

  // form (A*x + B) >> n
  int A, B, n;
  int besti = 0;
  for (n = 0; n < 31; n++) {
    int Amin = ((N3 * 0.3 - 1) * (1 << n) - (1 << n)) / N3 - 1;
    int Amax = ((N3 * 0.3 + 1) * (1 << n) + (1 << n)) / N3 + 1;
    for (A = Amin; A <= Amax; A++) {
      int Bmax = 1 << n;
      for (B = -Bmax; B <= Bmax; B++) {
        for (i = 0; i <= N3; i++) {
          int y = (A * i + B) >> n;
          if (y != target[i])
            break;
          if (i > besti) {
            besti = i;
            if (i == N3) {
              printf("i:%i A:%d B:%d n:%d/n", i, A, B, n);
              printf("!!!/n");
              exit(0);
            }
          }
        }
      }
    }
  }
  printf("???/n");
  return 0;
}

Answer 5

Usando un hack clásico para divu10() continuación. Prefiero el enfoque de * n y shift, pero pensé que ofrezco otro punto de vista.

unsigned mult3tenths(unsigned x) {
  return divu10(x*3);
}

unsigned divu10(unsigned n) {
  unsigned q, rem;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  rem = n - q*10;
  return q + ((rem + 6) >> 4);  
}