Número aproximado de ponto flutuante com precisão de n dígitos

9

Temos um número de ponto flutuante rentre 0 e 1 e um número inteiro p.

Encontre a fração de números inteiros com o menor denominador, que se aproxima rcom pelo menos pprecisão de dois dígitos.

  • Entradas: r(um número de ponto flutuante) e p(inteiro).
  • Saídas: ae binteiros, em que
    • a/b(flutuante) aproxima-se raté os pdígitos.
    • b é o menor número inteiro positivo possível.

Por exemplo:

  • se r=0.14159265358979e p=9,
  • então o resultado é a=4687e b=33102,
  • porque 4687/33102=0.1415926530119026.

Qualquer solução precisa funcionar em teoria com tipos de precisão arbitrária, mas as limitações causadas pelos tipos de precisão fixa das implementações não importam.

Precisão significa o número de dígitos após " 0." dentro r. Assim, se r=0.0123e p=3, então, a/bdeve começar com 0.012. Se os primeiros pdígitos da parte fracionária de rforem 0, o comportamento indefinido será aceitável.

Critérios de vitória:

  • O algoritmo algoritmicamente mais rápido vence. A velocidade é medida em O (p).
  • Se houver vários algoritmos mais rápidos, os ganhos mais curtos.
  • Minha própria resposta está excluída do conjunto dos possíveis vencedores.

Ps a parte de matemática é realmente muito mais fácil, ao que parece, sugiro ler este post.

peterh - Restabelecer Monica
fonte

Respostas:

7

JavaScript, O (10 p ) e 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]}

É trivial provar que o loop será feito após no máximo O (10 p ) iterações.

Muito obrigado à idéia de Neil, economize 50 bytes.

tsh
fonte
Por que você está brincando com padEnde match? Você não pode apenas slicecada corda no comprimento correto e depois subtraí-las?
Neil
@ Neil Desculpe, eu não tinha entendido o seu ponto. O adicionado padEndé usado para testcase f(0.001,2)e f(0.3,2).
tsh
Eu estava pensando que você poderia simplificar até algo do tipo (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]}(não totalmente jogado).
Neil
@ Neil 120 -> 70 bytes. :)
tsh
Whoa, isso é muito melhor!
Neil
4

Haskell , O (10 p ) na pior das hipóteses 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)]

Experimente online!

Economizou 2 bytes graças a Laikoni

Eu usei o algoritmo de /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .

A cada etapa, o novo intervalo é metade do intervalo anterior. Assim, o tamanho do intervalo é 2**-nonde nestá a etapa atual. Quando 2**-n < 10**-p, temos a certeza de ter a aproximação correta. No entanto, se n > 4*pentão 2**-n < 2**-(4*p) == 16**-p < 10**-p. A conclusão é que o algoritmo é O(p).

EDIT Como apontado pelo orlp em um comentário, a reivindicação acima é falsa. No pior dos casos, r = 1/10**p( r= 1-1/10**pé similar), haverá 10**petapas: 1/2, 1/3, 1/4, .... Existe uma solução melhor, mas não tenho tempo agora para corrigir isso.

jferard
fonte
Eu sei que o código golf é apenas o objetivo secundário, mas você pode soltar o f=e salvar dois bytes com z<-floor.(*10^p),u<-a+c,v<-b+d.
Laikoni
@Laikoni Eu não contei os dois bytes. Não sei como remover f=no TIO no código Haskell.
jferard
Você pode adicionar o -cppsinalizador do compilador e escrever f=\ no cabeçalho: Experimente online!
Laikoni
"Em cada etapa, o novo intervalo é metade do intervalo anterior." Como você sabe disso? O primeiro passo é 1/2, sim, mas o próximo passo é, por exemplo, a mediana de 1/2 e 1/1, fornecendo 2/3, o que não diminui pela metade o intervalo.
orlp 18/09/17
@orlp Você está absolutamente certo. Eu estava otimista demais e a complexidade é O (10 ^ p) no pior dos casos. Eu tenho uma solução melhor, mas não tenho tempo para escrevê-la agora.
jferard
0

C, 473 bytes (sem contexto), O (p), não concorrente

Esta solução usa a parte matemática detalhada neste excelente post. Eu calculei apenas calc()no tamanho da resposta.

#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 - Restabelecer Monica
fonte
Também se aproxima da solução provavelmente mais rápida possível no sentido de ciclos de CPU, pelo menos em máquinas convencionais.
peterh - Restabelece Monica