Приблизительное число с плавающей запятой с точностью до n цифр

9

У нас есть число с плавающей запятой rот 0 до 1 и целое число p.

Найти дробь целых чисел с наименьшим знаменателем, которая аппроксимируется rс pточностью не менее цифры.

  • Входные данные: r(число с плавающей запятой) и p(целое число).
  • Выходы: aи bцелые числа, где
    • a/b(как float) приблизительно rдо pцифр.
    • b является возможным наименьшим таким положительным целым числом.

Например:

  • если r=0.14159265358979и p=9,
  • тогда результат a=4687и b=33102,
  • потому что 4687/33102=0.1415926530119026.

Любое решение должно теоретически работать с типами произвольной точности, но ограничения, вызванные типами с фиксированной точностью реализации, не имеют значения.

Точность означает количество цифр после " 0." в r. Таким образом, если r=0.0123и p=3, то a/bследует начать с 0.012. Если первые pцифры дробной части r0, неопределенное поведение приемлемо.

Критерии выигрыша:

  • Алгоритмически быстрый алгоритм выигрывает. Скорость измеряется в O (p).
  • Если есть несколько самых быстрых алгоритмов, то самый короткий выигрывает.
  • Мой собственный ответ исключен из множества возможных победителей.

Ps математическая часть на самом деле намного проще, как кажется, я предлагаю прочитать этот пост.

Петер - Восстановить Монику
источник

Ответы:

7

JavaScript, O (10 p ) и 72 байта

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

Тривиально доказать, что цикл будет выполнен после максимум O (10 p ) итераций.

Большое спасибо идее Нила, сэкономить 50 байтов.

ТТГ
источник
Почему ты возился с padEndи match? Разве вы не можете просто sliceкаждую строку на правильную длину, а затем вычесть их?
Нил
@Neil Извини, я не понял твою точку зрения. Добавленный padEndиспользуется для теста f(0.001,2)и f(0.3,2).
17
Я думал, что вы могли бы упростить до чего-то вроде (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]}(не полностью гольф).
Нил
@Neil 120 -> 70 байтов. :)
TSH
Вау, это намного лучше!
Нил
4

Haskell , O (10 p ) в худшем случае 121 119 байт

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

Попробуйте онлайн!

Сохранено 2 байта благодаря Laikoni

Я использовал алгоритм из /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .

На каждом шаге новый интервал составляет половину предыдущего интервала. Таким образом, интервал размер 2**-n, где nнаходится текущий шаг. Когда 2**-n < 10**-pмы обязательно получим правильное приближение. Еще если n > 4*pпотом 2**-n < 2**-(4*p) == 16**-p < 10**-p. Вывод таков, что алгоритм есть O(p).

РЕДАКТИРОВАТЬ Как указал orlp в комментарии, утверждение выше ложно. В худшем случае r = 1/10**p( r= 1-1/10**pаналогично), будет 10**pшаги: 1/2, 1/3, 1/4, .... Есть лучшее решение, но сейчас у меня нет времени, чтобы это исправить.

jferard
источник
Я знаю, что гольф кода - это только второстепенная цель, но вы можете сбросить f=и сэкономить два байта z<-floor.(*10^p),u<-a+c,v<-b+d.
Лайкони
@Laikoni Я не считал два байта. Я не знаю, как удалить f=на TIO в коде на Haskell.
Jferard
Вы можете добавить -cppфлаг компилятора и написать f=\ в шапке: Попробуйте онлайн!
Лайкони
«На каждом этапе новый интервал составляет половину предыдущего интервала». Откуда ты это знаешь? Первый шаг - 1/2, да, но затем следующим шагом является, например, медиант 1/2 и 1/1, дающий 2/3, который не делит интервал пополам.
17
@orlp Ты прав абсолютно. Я был слишком оптимистичен и сложность O (10 ^ p) в худшем случае. У меня есть лучшее решение, но у меня нет времени, чтобы написать его прямо сейчас.
jferard
0

C, 473 байта (без контекста), O (p), не конкурирует

Это решение использует математическую часть, подробно описанную в этом прекрасном посте. Я рассчитал только calc()на размер ответа.

#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;
}
Петер - Восстановить Монику
источник
Это также приближает к, вероятно, наиболее быстрому решению в смысле циклов процессора, по крайней мере, на обычных машинах.
Петер - Восстановить Монику