Número aproximado de coma flotante con precisión de n dígitos

9

Tenemos un número de coma flotante rentre 0 y 1, y un número entero p.

Encuentre la fracción de enteros con el mínimo denominador, que se aproxima rcon al menos pprecisión de dígitos.

  • Entradas: r(un número de coma flotante) y p(entero).
  • Salidas: ay benteros, donde
    • a/b(como flotante) se aproxima rhasta los pdígitos.
    • b es el menor entero positivo posible más pequeño.

Por ejemplo:

  • si r=0.14159265358979y p=9,
  • entonces el resultado es a=4687y b=33102,
  • debido 4687/33102=0.1415926530119026.

Cualquier solución tiene que funcionar en teoría con tipos de precisión arbitraria, pero las limitaciones causadas por los tipos de precisión fija de las implementaciones no importan.

Precisión significa el número de dígitos después de " 0." en r. Por lo tanto, si r=0.0123y p=3, entonces a/bdebería comenzar con 0.012. Si los primeros pdígitos de la parte fraccional de rson 0, el comportamiento indefinido es aceptable.

Criterio de victoria:

  • El algoritmo algorítmicamente más rápido gana. La velocidad se mide en O (p).
  • Si hay varios algoritmos más rápidos, entonces gana el más corto.
  • Mi propia respuesta está excluida del conjunto de posibles ganadores.

PD: la parte de matemáticas es en realidad mucho más fácil de lo que parece, sugiero leer esta publicación.

peterh - Restablece a Monica
fuente

Respuestas:

7

JavaScript, O (10 p ) y 72 bytes

r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}

Es trivial demostrar que el ciclo se realizará después de como máximo O (10 p ) iteraciones.

Muchas gracias a la idea de Neil, ahorre 50 bytes.

tsh
fuente
¿Por qué estás jugando con padEndy match? ¿No puede simplemente slicecada cadena a la longitud correcta y luego restarlas?
Neil
@Neil Lo siento, no entendí tu punto. El agregado padEndse usa para testcase f(0.001,2)y f(0.3,2).
tsh
Estaba pensando que podría simplificarse a algo (r,p)=>{for(a=0,b=1;`${a/b}`.slice(0,p+2)-`${r}`.slice(0,p+2);a/b<r?a++:b++);return[a,b]}similar a (no totalmente golfizado).
Neil
@Neil 120 -> 70 bytes. :)
tsh
¡Vaya, eso está mucho mejor!
Neil
4

Haskell , O (10 p ) en el peor de los casos 121 119 bytes

g(0,1,1,1)
g(a,b,c,d)r p|z<-floor.(*10^p),u<-a+c,v<-b+d=last$g(last$(u,v,c,d):[(a,b,u,v)|r<u/v])r p:[(u,v)|z r==z(u/v)]

Pruébalo en línea!

Guardado 2 bytes gracias a Laikoni

Usé el algoritmo de /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .

En cada paso, el nuevo intervalo es la mitad del intervalo anterior. Por lo tanto, el tamaño del intervalo es 2**-n, donde nestá el paso actual. Cuando 2**-n < 10**-p, estamos seguros de tener la aproximación correcta. Sin embargo, si n > 4*pentonces 2**-n < 2**-(4*p) == 16**-p < 10**-p. La conclusión es que el algoritmo es O(p).

EDITAR Como lo señaló orlp en un comentario, la afirmación anterior es falsa. En el peor de los casos, r = 1/10**p( r= 1-1/10**pes similar), habrá 10**petapas: 1/2, 1/3, 1/4, .... Hay una mejor solución, pero no tengo tiempo en este momento para solucionarlo.

jferard
fuente
Sé que el golf de código es solo el objetivo secundario, pero puede descartar f=y guardar dos bytes con z<-floor.(*10^p),u<-a+c,v<-b+d.
Laikoni
@Laikoni No conté los dos bytes. No sé cómo eliminar f=en TIO en el código Haskell.
jferard
Puede agregar el -cppindicador del compilador y escribir f=\ en el encabezado: ¡ Pruébelo en línea!
Laikoni
"En cada paso, el nuevo intervalo es la mitad del intervalo anterior". ¿Cómo sabes esto? El primer paso es 1/2, sí, pero luego el siguiente paso es, por ejemplo, el mediador de 1/2 y 1/1 dando 2/3, que no es reducir a la mitad el intervalo.
orlp
@orlp Tienes toda la razón. Era demasiado optimista y la complejidad es O (10 ^ p) en el peor de los casos. Tengo una mejor solución, pero no tengo tiempo para escribirla en este momento.
jferard
0

C, 473 bytes (sin contexto), O (p), no competidora

Esta solución utiliza la parte matemática detallada en esta excelente publicación. Calculé solo calc()en el tamaño de la respuesta.

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

void calc(float r, int p, int *A, int *B) {
  int a=0, b=1, c=1, d=1, e, f;
  int tmp = r*pow(10, p);
  float ivl = (float)(tmp) / pow(10, p);
  float ivh = (float)(tmp + 1) / pow(10, p);

  for (;;) {
    e = a + c;
    f = b + d;

    if ((ivl <= (float)e/f) && ((float)e/f <= ivh)) {
      *A = e;
      *B = f;
      return;
    }

    if ((float)e/f < ivl) {
      a = e;
      b = f;
      continue;
    } else {
      c = e;
      d = f;
      continue;
    }
  }
}

int main(int argc, char **argv) {
  float r = atof(argv[1]);
  int p = atoi(argv[2]), a, b;
  calc(r, p, &a, &b);
  printf ("a=%i b=%i\n", a, b);
  return 0;
}
peterh - Restablece a Monica
fuente
También se acerca a la solución probablemente más rápida posible en el sentido de ciclos de CPU, al menos en máquinas convencionales.
peterh - Restablecer Monica