Ungefähre Gleitkommazahl mit n-stelliger Genauigkeit

9

Wir haben eine Gleitkommazahl rzwischen 0 und 1 und eine ganze Zahl p.

Finden Sie den Anteil der ganzen Zahlen mit dem kleinsten Nenner, der sich rmit peiner Genauigkeit von mindestens einer Ziffer annähert.

  • Eingaben: r(eine Gleitkommazahl) und p(Ganzzahl).
  • Ausgaben: aund bganze Zahlen, wo
    • a/b(als float) ungefähr rbis zu den pZiffern.
    • b ist die mögliche kleinste solche positive ganze Zahl.

Beispielsweise:

  • wenn r=0.14159265358979und p=9,
  • dann ist das Ergebnis a=4687und b=33102,
  • weil 4687/33102=0.1415926530119026.

Jede Lösung muss theoretisch mit Typen mit beliebiger Genauigkeit funktionieren, aber Einschränkungen, die durch Typen mit fester Genauigkeit der Implementierungen verursacht werden, spielen keine Rolle.

Präzision bedeutet die Anzahl der Stellen nach " 0." in r. Also, wenn r=0.0123und p=3, dann a/bsollte mit beginnen 0.012. Wenn die ersten pZiffern des Bruchteils von r0 sind, ist undefiniertes Verhalten akzeptabel.

Gewinnkriterien:

  • Der algorithmisch schnellste Algorithmus gewinnt. Die Geschwindigkeit wird in O (p) gemessen.
  • Wenn es mehrere schnellste Algorithmen gibt, gewinnt der kürzeste.
  • Meine eigene Antwort ist aus dem Satz der möglichen Gewinner ausgeschlossen.

Ps der mathematische Teil ist eigentlich viel einfacher, wie es scheint, ich schlage vor, diesen Beitrag zu lesen .

Peter - Setzen Sie Monica wieder ein
quelle

Antworten:

7

JavaScript, O (10 p ) und 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 ist trivial zu beweisen, dass die Schleife nach höchstens O (10 p ) -Iterationen ausgeführt wird.

Vielen Dank an Neils Idee, sparen Sie 50 Bytes.

tsh
quelle
Warum spielst du mit padEndund herum match? Können Sie nicht einfach slicejede Zeichenfolge auf die richtige Länge bringen und sie dann subtrahieren?
Neil
@Neil Entschuldigung, ich hatte deinen Standpunkt nicht verstanden. Das hinzugefügte padEndwird für Testfall f(0.001,2)und verwendet f(0.3,2).
tsh
Ich dachte, Sie könnten sich auf etwas in der Art von (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]}(nicht vollständig Golf) vereinfachen.
Neil
@Neil 120 -> 70 Bytes. :)
tsh
Whoa, das ist viel besser!
Neil
4

Haskell , O (10 p ) im schlimmsten Fall 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)]

Probieren Sie es online aus!

2 Bytes dank Laikoni gespeichert

Ich habe den Algorithmus von /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i verwendet .

Bei jedem Schritt ist das neue Intervall die Hälfte des vorherigen Intervalls. Somit ist die Intervallgröße 2**-n, wo nder aktuelle Schritt ist. Wann 2**-n < 10**-psind wir sicher, die richtige Annäherung zu haben. Doch wenn n > 4*pdann 2**-n < 2**-(4*p) == 16**-p < 10**-p. Die Schlussfolgerung ist, dass der Algorithmus ist O(p).

BEARBEITEN Wie von orlp in einem Kommentar ausgeführt, ist die obige Behauptung falsch. Im schlimmsten Fall r = 1/10**p( r= 1-1/10**pist ähnlich) gibt es 10**pSchritte : 1/2, 1/3, 1/4, .... Es gibt eine bessere Lösung, aber ich habe momentan nicht die Zeit, dies zu beheben.

jferard
quelle
Ich weiß, dass Code Golf nur das sekundäre Ziel ist, aber Sie können das löschen f=und zwei Bytes mit sparen z<-floor.(*10^p),u<-a+c,v<-b+d.
Laikoni
@ Laikoni Ich habe die zwei Bytes nicht gezählt. Ich weiß nicht, wie ich f=TIO im Haskell-Code entfernen soll .
Jferard
Sie können das -cppCompiler-Flag hinzufügen und f=\ in die Kopfzeile schreiben : Probieren Sie es online aus!
Laikoni
"Bei jedem Schritt ist das neue Intervall die Hälfte des vorherigen Intervalls." Woher weißt du das? Der erste Schritt ist 1/2, ja, aber der nächste Schritt ist zum Beispiel der Mediant von 1/2 und 1/1, was 2/3 ergibt, was das Intervall nicht halbiert.
Orlp
@orlp Du bist absolut richtig. Ich war viel zu optimistisch und die Komplexität ist im schlimmsten Fall O (10 ^ p). Ich habe eine bessere Lösung, habe aber momentan nicht die Zeit, sie zu schreiben.
Jferard
0

C, 473 Bytes (ohne Kontext), O (p), nicht konkurrierend

Diese Lösung verwendet den in diesem ausgezeichneten Beitrag beschriebenen mathematischen Teil . Ich habe nur calc()die Antwortgröße berechnet .

#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;
}
Peter - Setzen Sie Monica wieder ein
quelle
Es nähert sich auch der wahrscheinlich schnellstmöglichen Lösung im Sinne von CPU-Zyklen, zumindest auf herkömmlichen Maschinen.
Peter - Wiedereinstellung Monica