Raiz Cuadrada

[samsaga2]

 A ver si podeis echarme una mano. Estoy liado haciendo chorraditas via j2me y me encuentro que me hace falta la funcion para calcular una raiz cuadrada pero esta no viene con el API del j2me.

¿Sabeis algun algoritmo para calcular la raiz cuadrada de dos numeros enteros? Es para un juego asi que prima la velocidad sobre la exactitud.

[gdl]

 Cuando te refieres a calcular la raíz cuadrada de dos números... ¿es a dos números por separado o es el módulo de un vector de dos componentes?

[samsaga2]

Cuando te refieres a calcular la raíz cuadrada de dos números... ¿es a dos números por separado o es el módulo de un vector de dos componentes?

Perdon, se me colo lo de los dos numeros  :rolleyes:. Necesito el calculo normal de la raiz cuadrada de un numero.

[Pogacha]

 Deseas calcular la distancia del vector ...

Aproximacion usada en el doom:

Código [Seleccionar] Expand

ax = abs(x);
ay = abs(y);

if(ax>ay) Distancia = ax + ay/2;
else Distancia = ay + ax/2;

En flotante tengo:

Código [Seleccionar] Expand

// Fast reciprocal square root
__inline float RSqrt( float number ) {
   long i;
   float x2, y;
   const float threehalfs = 1.5f;
   x2 = number * 0.5f;
   y  = number;
   i  = * (long *) &y;
   i  = 0x5f3759df - (i >> 1);
   y  = * (float *) &i;
   y  = y * (threehalfs - (x2 * y * y));
   return y;
}

Edit: reviendo el ultimo post ... necesitas raiz cuadrada ... la inversa no te sirve ?

Saludos

[Pogacha]

 Tambien piensa que puedes usar una tabla de precalculo ...
Pero aquí tienes una :

long sqrt(long r)
{
   long t,b,c=0;

   for (b=0x10000000;b!=0;b>>=2) {
      t = c + b;
      c >>= 1;
      if (t <= r) {
         r -= t;
         c += b;
      }
   }
   return c;
}

[Pogacha]

 Paper de la raiz cuadrada reciproca rapida

Ojo que a cualquiera que le pongas sqrt(-10) terminara en crash o blop.

Saludos

[senior wapo]

 Te pego esto de la vieja "Snippets Collection", os sonará a los que hallais crecido viendo Barrio Sésamo o la Cometa Blanca... (twist)
Está en C y es para enteros, pero con J2ME no creo que uses floats...

Código [Seleccionar] Expand


#include <string.h>
#include "snipmath.h"

#define BITSPERLONG 32

#define TOP2BITS(x) ((x & (3L << (BITSPERLONG-2))) >> (BITSPERLONG-2))


/* usqrt:
   ENTRY x: unsigned long
   EXIT  returns floor(sqrt(x) * pow(2, BITSPERLONG/2))

   Since the square root never uses more than half the bits
   of the input, we use the other half of the bits to contain
   extra bits of precision after the binary point.

   EXAMPLE
       suppose BITSPERLONG = 32
       then    usqrt(144) = 786432 = 12 * 65536
               usqrt(32) = 370727 = 5.66 * 65536

   NOTES
       (1) change BITSPERLONG to BITSPERLONG/2 if you do not want
           the answer scaled.  Indeed, if you want n bits of
           precision after the binary point, use BITSPERLONG/2+n.
           The code assumes that BITSPERLONG is even.
       (2) This is really better off being written in assembly.
           The line marked below is really a "arithmetic shift left"
           on the double-long value with r in the upper half
           and x in the lower half.  This operation is typically
           expressible in only one or two assembly instructions.
       (3) Unrolling this loop is probably not a bad idea.

   ALGORITHM
       The calculations are the base-two analogue of the square
       root algorithm we all learned in grammar school.  Since we're
       in base 2, there is only one nontrivial trial multiplier.

       Notice that absolutely no multiplications or divisions are performed.
       This means it'll be fast on a wide range of processors.
*/

void usqrt(unsigned long x, struct int_sqrt *q)
{
     unsigned long a = 0L;                   /* accumulator      */
     unsigned long r = 0L;                   /* remainder        */
     unsigned long e = 0L;                   /* trial product    */

     int i;

     for (i = 0; i < BITSPERLONG; i++)   /* NOTE 1 */
     {
           r = (r << 2) + TOP2BITS(x); x <<= 2; /* NOTE 2 */
           a <<= 1;
           e = (a << 1) + 1;
           if (r >= e)
           {
                 r -= e;
                 a++;
           }
     }
     memcpy(q, &a, sizeof(long));
}

#ifdef TEST

#include <stdio.h>
#include <stdlib.h>

main(void)
{
     int i;
     unsigned long l = 0x3fed0169L;
     struct int_sqrt q;

     for (i = 0; i < 101; ++i)
     {
           usqrt(i, &q);
           printf("sqrt(%3d) = %2d, remainder = %2d\n",
                 i, q.sqrt, q.frac);
     }
     usqrt(l, &q);
     printf("\nsqrt(%lX) = %X, remainder = %X\n", l, q.sqrt, q.frac);
     return 0;
}

#endif /* TEST */


La colección entera está en la web, AQUI (www.snippets.org seccion C)

[Pogacha]

 En punto fijo! si lo mismo ...

Código [Seleccionar] Expand

typedf int fixed16;

fixed16 sqrt(int r)
{
  long t,b,c=0;
  r<<=8;
  for (b=0x10000000;b!=0;b>>=2) {
     t = c + b;
     c >>= 1;
     if (t <= r) {
        r -= t;
        c += b;
     }
  }
  return c;
}

Edit:

La colección entera está en la web, AQUI (www.snippets.org seccion C)

Muy interesante

[Warchief]

 http://www.rart.com/j2me-presentation/html...P60ME_java.html ?

http://henson.newmail.ru/j2me/Float.htm ?

[fiero]

 La raiz cuadrada de un número entero, es el número de valores impares que puedes restarle. Por ejemplo:

raiz de 4: -1-3 = 2 números
raiz de 8: -1-3 = 2 numeros
raiz de 9: -1-3-5 = 3 números
raiz de 15: -1-3-5 = 3 números
raiz de 16: -1-3-5-7 = 4 números

un saludo

[shephiroth]

 Fiero, muy bueno eso  (ole)  (ole)  (ole)

Pasandolo a codigo seria algo como:

Código [Seleccionar] Expand


int sqrt(int a)
{
int c;
for(c=1;a>=c;a-=c,c+=2);
return c/2;
}


[Pogacha]

 

Fiero, muy bueno eso   

Pasandolo a codigo seria algo como:
CODE 

int sqrt(int a)
{
int c;
for(c=1;a>=c;a-=c,c+=2);
return c/2;
}

Si, en esto se basa el algoritmo que postee yo y el del senior wapo que es casi lo mismo, excepto que el del señor wapo tiene parte decimal y me parece mas integro, el algoritmo de shephiroth tiene el problema de que no aprovecha las propiedades de la potencia ... para calcular una raiz n demora raiz de n o sea la raiz de 65536 en 256 iteraciones, los algoritmos de arriba utilizan las propiedades de la potencia para realizar el calculo en tiempo fijo por radix o sea en un k * numero de bits, para nuestro caso 16 iteraciones sin importar el numero que sea.

Saludos

[shephiroth]

 Wenas

Vuestro codigo no termino de entenderlo, >>= y <<= que hacen??

[Warchief]

Wenas

Vuestro codigo no termino de entenderlo, >>= y <<= que hacen??

Son contracción de operador.

a += 1; // es lo mismo que a = a+1;

entonces

a >>= 1; // deberia ser lo mismo que a = a >> 1;

No los he usado nunca, huyo de la oscuridad, pero supongo que son eso.

[Pogacha]

 incluso :

Código [Seleccionar] Expand

a<<=1;  es igual a

Código [Seleccionar] Expand

a*=2;
y mas interesante aun

Código [Seleccionar] Expand

a<<=n;  es igual a

Código [Seleccionar] Expand

a*=pow(2,n);

Código [Seleccionar] Expand

a<<=0;  es igual a

Código [Seleccionar] Expand

a*=pow(2,0); lo que es

Código [Seleccionar] Expand

a*=1;  

Código [Seleccionar] Expand

a>>=n;  es igual a

Código [Seleccionar] Expand

a<<=-n; lo que es

Código [Seleccionar] Expand

a/=pow(a,n);

lo que me da que puedo multiplicar y dividir por potencias de 2 a gusto y placer ...

Saludos