Przybliżona liczba zmiennoprzecinkowa z precyzją n-cyfrową

9

Mamy liczbę zmiennoprzecinkową z zakresu rod 0 do 1 oraz liczbę całkowitą p.

Znajdź ułamek liczb całkowitych o najmniejszym mianowniku, który aproksymuje rz przynajmniej pcyfrową precyzją.

  • Dane wejściowe: r(liczba zmiennoprzecinkowa) i p(liczba całkowita).
  • Wyjścia: ai bliczby całkowite, gdzie
    • a/b(jako liczba zmiennoprzecinkowa) jest przybliżana rdo pcyfr.
    • b jest możliwą najmniejszą taką dodatnią liczbą całkowitą.

Na przykład:

  • jeśli r=0.14159265358979a p=9,
  • Następnie wynik jest a=4687i b=33102,
  • dlatego 4687/33102=0.1415926530119026.

Każde rozwiązanie musi działać teoretycznie z typami o dowolnej precyzji, ale ograniczenia wynikające z typów o stałej precyzji implementacji nie mają znaczenia.

Precyzja oznacza liczbę cyfr po „ 0.” w r. Tak więc, jeśli r=0.0123i p=3, to a/bnależy zacząć od 0.012. Jeśli pierwsze pcyfry części ułamkowej rsą równe 0, nieokreślone zachowanie jest dopuszczalne.

Kryteria wygranej:

  • Algorytm najszybszy algorytm wygrywa. Prędkość jest mierzona w O (p).
  • Jeśli istnieje wiele najszybszych algorytmów, wygrywa najkrótszy.
  • Moja własna odpowiedź jest wykluczona z listy możliwych zwycięzców.

Ps część matematyczna jest w rzeczywistości o wiele łatwiejsza, jak się wydaje, proponuję przeczytać ten post.

peterh - Przywróć Monikę
źródło

Odpowiedzi:

7

JavaScript, O (10 p ) i 72 bajty

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]}

Trywialne jest udowodnienie, że pętla zostanie wykonana po co najwyżej iteracjach O (10 p ).

Wielkie dzięki pomysłowi Neila, oszczędź 50 bajtów.

tsh
źródło
Dlaczego bawisz się z padEndi match? Czy nie możesz po prostu slicekażdego łańcucha do odpowiedniej długości, a następnie odjąć je?
Neil
@Neil Przepraszamy, ale nie zrozumiałem o co ci chodzi. Dodany padEndsłuży do testcase f(0.001,2)i f(0.3,2).
tsh
Myślałem, że możesz uprościć coś w stylu (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]}(nie w pełni golfa).
Neil
@ Neil 120 -> 70 bajtów. :)
tsh
Whoa, to o wiele lepsze!
Neil
4

Haskell , O (10 p ) w najgorszym przypadku 121 119 bajtów

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)]

Wypróbuj online!

Zaoszczędzono 2 bajty dzięki Laikoni

Użyłem algorytmu z /math/2432123/how-to-find-the-fraction-of-integers-w--the-smallest-denominator-matching-an-i .

Na każdym kroku nowy interwał stanowi połowę poprzedniego interwału. Zatem rozmiar interwału to 2**-n, gdzie njest bieżący krok. Kiedy z 2**-n < 10**-ppewnością będziemy mieć odpowiednie przybliżenie. Ale jeśli n > 4*pto 2**-n < 2**-(4*p) == 16**-p < 10**-p. Wniosek jest taki, że algorytm jest O(p).

EDYCJA Jak wskazał orlp w komentarzu, powyższe twierdzenie jest fałszywe. W najgorszym przypadku r = 1/10**p( r= 1-1/10**ppodobnie), nie będzie 10**petapy: 1/2, 1/3, 1/4, .... Jest lepsze rozwiązanie, ale nie mam teraz czasu, aby to naprawić.

Jferard
źródło
Wiem, że kod golf jest tylko drugorzędnym celem, ale możesz upuścić f=i zaoszczędzić dwa bajty z<-floor.(*10^p),u<-a+c,v<-b+d.
Laikoni
@Laikoni Nie policzyłem dwóch bajtów. Nie wiem, jak usunąć f=z TIO w kodzie Haskell.
jferard
Możesz dodać -cppflagę kompilatora i napisać f=\ w nagłówku: Wypróbuj online!
Laikoni
„Na każdym kroku nowy interwał stanowi połowę poprzedniego interwału”. Skąd ty to wiesz? Pierwszym krokiem jest 1/2, tak, ale następnym krokiem jest na przykład mediana 1/2 i 1/1 dająca 2/3, co nie jest o połowę mniejsze.
lub
@orlp Masz absolutną rację. Byłem zdecydowanie zbyt optymistyczny, aw najgorszym przypadku złożoność wynosi O (10 ^ p). Mam lepsze rozwiązanie, ale nie mam teraz czasu, aby je napisać.
jferard
0

C, 473 bajtów (bez kontekstu), O (p), niekonkurujące

To rozwiązanie wykorzystuje część matematyczną opisaną w tym znakomitym poście. Przeliczyłem tylko calc()na rozmiar odpowiedzi.

#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 - Przywróć Monikę
źródło
Zbliża się również do prawdopodobnie możliwie najszybszego rozwiązania w sensie cykli procesora, przynajmniej na konwencjonalnych maszynach.
peterh - Przywróć Monikę