Perkiraan angka floating point dengan presisi n-digit

9

Kami memiliki angka floating point rantara 0 dan 1, dan bilangan bulat p.

Temukan fraksi bilangan bulat dengan penyebut terkecil, yang mendekati rdengan setidaknya p-digit presisi.

  • Input: r(angka floating point) dan p(integer).
  • Output: adan bbilangan bulat, di mana
    • a/b(as float) mendekati rhingga pdigit.
    • b adalah bilangan bulat positif terkecil yang mungkin.

Sebagai contoh:

  • jika r=0.14159265358979dan p=9,
  • maka hasilnya adalah a=4687dan b=33102,
  • karena 4687/33102=0.1415926530119026.

Setiap solusi harus bekerja secara teori dengan tipe presisi arbitrer, tetapi batasan yang disebabkan oleh tipe presisi tetap implementasi tidak menjadi masalah.

Presisi berarti jumlah digit setelah " 0." dalam r. Jadi, jika r=0.0123dan p=3, maka a/bharus dimulai dengan 0.012. Jika pdigit pertama dari bagian fraksional radalah 0, perilaku tidak terdefinisi dapat diterima.

Kriteria menang:

  • Algoritme tercepat secara algoritmik menang. Kecepatan diukur dalam O (p).
  • Jika ada beberapa algoritma tercepat, maka yang paling pendek menang.
  • Jawaban saya sendiri dikecualikan dari himpunan pemenang yang mungkin.

Ps bagian matematika sebenarnya jauh lebih mudah seperti yang terlihat, saya sarankan untuk membaca posting ini .

peterh - Pasang kembali Monica
sumber

Jawaban:

7

JavaScript, O (10 p ) & 72 byte

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

Itu sepele untuk membuktikan bahwa loop akan dilakukan setelah paling banyak iterasi O (10 p ).

Banyak terima kasih kepada ide Neil, menghemat 50 byte.

tsh
sumber
Mengapa Anda mengutak-atik padEnddan match? Tidak bisakah Anda hanya slicesetiap string dengan panjang yang benar dan kemudian kurangi?
Neil
@ Neil Maaf aku tidak mengerti maksudmu. Yang ditambahkan padEnddigunakan untuk testcase f(0.001,2)dan f(0.3,2).
tsh
Saya pikir Anda bisa menyederhanakan sesuatu menjadi sesuatu (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]}(tidak sepenuhnya golf).
Neil
@Nil 120 -> 70 byte. :)
tsh
Wah, itu jauh lebih baik!
Neil
4

Haskell , O (10 p ) dalam kasus terburuk 121 119 byte

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

Cobalah online!

Disimpan 2 byte berkat Laikoni

Saya menggunakan algoritma dari /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .

Pada setiap langkah, interval baru adalah setengah dari interval sebelumnya. Jadi, ukuran intervalnya adalah 2**-n, di mana nlangkahnya saat ini. Kapan 2**-n < 10**-p, kami yakin memiliki perkiraan yang tepat. Namun jika n > 4*pdemikian 2**-n < 2**-(4*p) == 16**-p < 10**-p. Kesimpulannya adalah bahwa algoritma tersebut O(p).

EDIT Seperti yang ditunjukkan oleh orlp dalam komentar, klaim di atas salah. Dalam kasus terburuk, r = 1/10**p( r= 1-1/10**pmirip), akan ada 10**plangkah-langkah: 1/2, 1/3, 1/4, .... Ada solusi yang lebih baik, tetapi saya tidak punya waktu sekarang untuk memperbaikinya.

jferard
sumber
Saya tahu golf kode hanyalah tujuan sekunder, tetapi Anda dapat menjatuhkan f=dan menyimpan dua byte dengan z<-floor.(*10^p),u<-a+c,v<-b+d.
Laikoni
@Laikoni Saya tidak menghitung dua byte. Saya tidak tahu cara menghapus f=TIO dalam kode Haskell.
jferard
Anda dapat menambahkan -cppflag kompiler dan menulis f=\ di header: Coba online!
Laikoni
"Pada setiap langkah, interval baru adalah setengah dari interval sebelumnya." Bagaimana kamu tahu ini? Langkah pertama adalah 1/2, ya, tapi kemudian langkah selanjutnya adalah contoh mediant dari 1/2 dan 1/1 memberi 2/3, yang tidak mengurangi separuh interval.
orlp
@ Atau Anda benar-benar benar. Saya terlalu optimis dan kompleksitasnya adalah O (10 ^ p) dalam kasus terburuk. Saya punya solusi yang lebih baik tetapi tidak punya waktu untuk menulisnya sekarang.
jferard
0

C, 473 byte (tanpa konteks), O (p), tidak bersaing

Solusi ini menggunakan bagian matematika yang diperinci dalam pos yang luar biasa ini . Saya menghitung hanya calc()ke dalam ukuran jawaban.

#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 - Pasang kembali Monica
sumber
Itu juga mendekati solusi yang mungkin tercepat dalam arti siklus cpu, setidaknya pada mesin konvensional.
peterh