Algorithme défi: Générer fractions continues pour un flotteur

Question

( EDIT : En réponse aux commentaires grincheux, Non, ce n'est pas devoirs Je travaille sur la détection de pas, en prenant une série de pics harmoniques potentiels, et de tenter de construire des candidats pour. fréquence fondamentale. Ainsi, il est en fait une question très pratique.)

Etudiez les meilleures approximations pour des fractions (par exemple) pi, commandé par le dénominateur de plus en plus: 3/1, 22/7, 355/113, ...

Le défi: créer un bien rangé algorithme C qui va générer le rapprochement quotient n'th a / b pour un flotteur donné, retour aussi l'écart

.

calcBestFrac (frac float, int n, int * a, int * b, flotteur * err) {...}

La meilleure technique que je crois est fractions continues

Otez la partie décimale de pi, et vous obtenez 3
Maintenant, le reste est 0,14159 ... = 1 / 7,06251 ..

Donc, la meilleure rationnel est 3 + = 22/7
1/7 Otez le 7 de 7,06251 et vous obtenez 0,06251 .. Environ 1 / 15,99659 ..

Appelez-16, la meilleure approximation est
3 + 1 / (7 + 16/1) = 355/113

Cependant, ce qui est loin d'être anodin pour convertir en code propre C. Je signalerai si je reçois quelque chose de bien rangé. En attendant, quelqu'un peut en profiter comme un casse-tête.

Answer 1

[Depuis que vous avez demandé cela comme une réponse plutôt qu'un commentaire.]

Pour tout nombre réel, p les réduites [k] / q [k] de sa fraction continue sont toujours des approximations plus rationnelles, mais ils ne sont pas tous les meilleures approximations rationnelles. Pour obtenir tous, vous devez aussi prendre les demi-Convergents / mediants - fractions de la forme (p[k]+n*p[k+1])/(q[k]+n*q[k+1]) pour certains n=1 entier. En prenant n = a [k + 2] donne p [k + 2] / q [k + 2], et les nombres entiers n pour prendre sont ceux de chaque étage (a [k + 2] / 2) ou au plafond (a [ k + 2] / 2), à une [k + 2]. Ceci est également mentionné sur Wikipédia .

Approximation p

La fraction continue pour p est [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2 ...] (séquence A001203 dans OEIS ), la séquence de convergents est 3/1, 22/7, 333/106, 355/113, 103993/33102 ... ( A002485 / A002486 ), et la séquence de meilleures approximations est 3/1, 13/4, 16/5, 19/6, 22 / 7 179/57 ... ( A063674 / A063673 ).

l'algorithme dit que les meilleures approximations de p = [3; 7, 15, 1, 292, 1, 1, ...] sont

3/1     = [3]

13/4    = [3; 4]
16/5    = [3; 5]
19/6    = [3; 6]
22/7    = [3; 7]

179/57  = [3; 7, 8]
201/64  = [3; 7, 9]
223/71  = [3; 7, 10]
245/78  = [3; 7, 11]
267/85  = [3; 7, 12]
289/92  = [3; 7, 13]
311/99  = [3; 7, 14]
333/106 = [3; 7, 15]

355/113 = [3; 7, 15, 1]

52163/16604  = [3; 7, 15, 1, 146]
52518/16717  = [3; 7, 15, 1, 147]
… (all the fractions from [3; 7, 15, 1, 148] to [3; 7, 15, 1, 291])…
103993/33102 = [3; 7, 15, 1, 292]

104348/33215 = [3; 7, 15, 1, 292, 1]
...

Programme

Voici un programme C qui donne un nombre réel positif, génère sa fraction continue, ses convergents, et la séquence des meilleures approximations rationnelles. La find_cf fonction trouve la fraction continue (mettre les termes dans un [] et les réduites en p [] et q [] - excusez les variables globales)., Et les imprime all_best fonction toutes les meilleures approximations rationnelles

#include <math.h>
#include <stdio.h>
#include <assert.h>

// number of terms in continued fraction.
// 15 is the max without precision errors for M_PI
#define MAX 15
#define eps 1e-9

long p[MAX], q[MAX], a[MAX], len;
void find_cf(double x) {
  int i;
  //The first two convergents are 0/1 and 1/0
  p[0] = 0; q[0] = 1;
  p[1] = 1; q[1] = 0;
  //The rest of the convergents (and continued fraction)
  for(i=2; i<MAX; ++i) {
    a[i] = lrint(floor(x));
    p[i] = a[i]*p[i-1] + p[i-2];
    q[i] = a[i]*q[i-1] + q[i-2];
    printf("%ld:  %ld/%ld\n", a[i], p[i], q[i]);
    len = i;
    if(fabs(x-a[i])<eps) return;
    x = 1.0/(x - a[i]);
  }
}

void all_best(double x) {
  find_cf(x); printf("\n");
  int i, n; long cp, cq;
  for(i=2; i<len; ++i) {
    //Test n = a[i+1]/2. Enough to test only when a[i+1] is even, actually...
    n = a[i+1]/2; cp = n*p[i]+p[i-1]; cq = n*q[i]+q[i-1];
    if(fabs(x-(double)cp/cq) < fabs(x-(double)p[i]/q[i])) 
      printf("%ld/%ld, ", cp, cq);
    //And print all the rest, no need to test
    for(n = (a[i+1]+2)/2; n<=a[i+1]; ++n) {
      printf("%ld/%ld, ", n*p[i]+p[i-1], n*q[i]+q[i-1]);
    }
  }
}

int main(int argc, char **argv) {
  double x;
  if(argc==1) { x = M_PI; } else { sscanf(argv[1], "%lf", &x); }
  assert(x>0); printf("%.15lf\n\n", x);
  all_best(x); printf("\n");
  return 0;
}

Exemples

Pour p, voici la sortie de ce programme, dans environ 0,003 secondes (à savoir, il est vraiment mieux que boucle à travers tous les dénominateurs possibles!), Enveloppé ligne pour une meilleure lisibilité:

% ./a.out
3.141592653589793

3:  3/1
7:  22/7
15:  333/106
1:  355/113
292:  103993/33102
1:  104348/33215
1:  208341/66317
1:  312689/99532
2:  833719/265381
1:  1146408/364913
3:  4272943/1360120
1:  5419351/1725033
14:  80143857/25510582

13/4, 16/5, 19/6, 22/7, 179/57, 201/64, 223/71, 245/78, 267/85, 289/92, 311/99,
333/106, 355/113, 52163/16604, 52518/16717, 52873/16830, 53228/16943, 53583/17056,
53938/17169, 54293/17282, 54648/17395, 55003/17508, 55358/17621, 55713/17734,
56068/17847, 56423/17960, 56778/18073, 57133/18186, 57488/18299, 57843/18412,
58198/18525, 58553/18638, 58908/18751, 59263/18864, 59618/18977, 59973/19090,
60328/19203, 60683/19316, 61038/19429, 61393/19542, 61748/19655, 62103/19768,
62458/19881, 62813/19994, 63168/20107, 63523/20220, 63878/20333, 64233/20446,
64588/20559, 64943/20672, 65298/20785, 65653/20898, 66008/21011, 66363/21124,
66718/21237, 67073/21350, 67428/21463, 67783/21576, 68138/21689, 68493/21802,
68848/21915, 69203/22028, 69558/22141, 69913/22254, 70268/22367, 70623/22480,
70978/22593, 71333/22706, 71688/22819, 72043/22932, 72398/23045, 72753/23158,
73108/23271, 73463/23384, 73818/23497, 74173/23610, 74528/23723, 74883/23836,
75238/23949, 75593/24062, 75948/24175, 76303/24288, 76658/24401, 77013/24514,
77368/24627, 77723/24740, 78078/24853, 78433/24966, 78788/25079, 79143/25192,
79498/25305, 79853/25418, 80208/25531, 80563/25644, 80918/25757, 81273/25870,
81628/25983, 81983/26096, 82338/26209, 82693/26322, 83048/26435, 83403/26548,
83758/26661, 84113/26774, 84468/26887, 84823/27000, 85178/27113, 85533/27226,
85888/27339, 86243/27452, 86598/27565, 86953/27678, 87308/27791, 87663/27904,
88018/28017, 88373/28130, 88728/28243, 89083/28356, 89438/28469, 89793/28582,
90148/28695, 90503/28808, 90858/28921, 91213/29034, 91568/29147, 91923/29260,
92278/29373, 92633/29486, 92988/29599, 93343/29712, 93698/29825, 94053/29938,
94408/30051, 94763/30164, 95118/30277, 95473/30390, 95828/30503, 96183/30616,
96538/30729, 96893/30842, 97248/30955, 97603/31068, 97958/31181, 98313/31294,
98668/31407, 99023/31520, 99378/31633, 99733/31746, 100088/31859, 100443/31972,
100798/32085, 101153/32198, 101508/32311, 101863/32424, 102218/32537, 102573/32650,
102928/32763, 103283/32876, 103638/32989, 103993/33102, 104348/33215, 208341/66317,
312689/99532, 833719/265381, 1146408/364913, 3126535/995207,
4272943/1360120, 5419351/1725033, 42208400/13435351, 47627751/15160384,
53047102/16885417, 58466453/18610450, 63885804/20335483, 69305155/22060516,
74724506/23785549, 80143857/25510582, 

Tous ces termes sont corrects, mais si vous augmentez MAX vous commencez à obtenir des erreurs en raison de la précision. Je suis moi-même impressionné par le nombre de termes que vous obtenez avec seulement 13 convergents. (Comme vous pouvez le voir, il y a un petit bug où il ne parfois imprime pas le premier « n / 1 » approximation ou l'imprime de façon incorrecte - je laisse pour vous fixer)

Vous pouvez essayer avec v2, dont la fraction continue est [1; 2, 2, 2, 2 ...]:

% ./a.out 1.41421356237309504880
1.414213562373095

1:  1/1
2:  3/2
2:  7/5
2:  17/12
2:  41/29
2:  99/70
2:  239/169
2:  577/408
2:  1393/985
2:  3363/2378
2:  8119/5741
2:  19601/13860
2:  47321/33461

3/2, 4/3, 7/5, 17/12, 24/17, 41/29, 99/70, 140/99, 239/169, 577/408, 816/577, 1393/985, 3363/2378, 4756/3363, 8119/5741, 19601/13860, 47321/33461,

Ou le nombre d'or f = (1 + v5) / 2 dont la fraction continue est [1; 1, 1, 1, ...]:

% ./a.out 1.61803398874989484820
1.618033988749895

1:  1/1
1:  2/1
1:  3/2
1:  5/3
1:  8/5
1:  13/8
1:  21/13
1:  34/21
1:  55/34
1:  89/55
1:  144/89
1:  233/144
1:  377/233

2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89, 233/144, 377/233, 

(Voir les nombres de Fibonacci? Ici les réduites sont tous les approximants.)

Ou avec des nombres rationnels comme [1 = 4/3; 3]:

% ./a.out 1.33333333333333333333
1.333333333333333

1:  1/1
3:  4/3

3/2, 4/3, 

ou = 14/11 [1; 3, 1, 2]:

% ./a.out 1.27272727272727272727
1.272727272727273

1:  1/1
3:  4/3
1:  5/4
2:  14/11

3/2, 4/3, 5/4, 9/7, 14/11, 

Amusez-vous!

Answer 2

Le programme C est très bien, à part le fait que vous ne pouvez pas faire confiance au contrôle sur le reste, comme on peut le voir calculer x * p-q ainsi:

Iteration #1: 3:  3/1 - delta: 0.141592653589793116, rem: 0.141592653589793116
Iteration #2: 7:  22/7 - delta: -0.008851424871448188, rem: 0.062513305931051878
Iteration #3: 15:  333/106 - delta: 0.008821280518070296, rem: 0.996594406684156776
Iteration #4: 1:  355/113 - delta: -0.000030144353377892, rem: 0.003417231014946418
Iteration #5: 292:  103993/33102 - delta: 0.000019129331725765, rem: 0.634590879621879211
Iteration #6: 1:  104348/33215 - delta: -0.000011015021655680, rem: 0.575818424298580694
Iteration #7: 1:  208341/66317 - delta: 0.000008114310077190, rem: 0.736658567704091524
Iteration #8: 1:  312689/99532 - delta: -0.000002900711592702, rem: 0.357480987585133375
Iteration #9: 2:  833719/265381 - delta: 0.000002312886920208, rem: 0.797351564778957706
Iteration #10: 1:  1146408/364913 - delta: -0.000000587824615650, rem: 0.254151925163927682
Iteration #11: 3:  4272943/1360120 - delta: 0.000000549413016415, rem: 0.934654436927838420
Iteration #12: 1:  5419351/1725033 - delta: -0.000000038411599235, rem: 0.069914142051204637
Iteration #13: 14:  80143857/25510582 - delta: 0.000000011648808140, rem: 0.303257833981669641
Iteration #14: 3:  245850922/78256779 - delta: -0.000000003463355824, rem: 0.297524047014214316
Iteration #15: 3:  817696623/260280919 - delta: 0.000000001280568540, rem: 0.361072861287829440
Iteration #16: 2:  1881244168/598818617 - delta: -0.000000000931322575, rem: 0.769524124392304913
Iteration #17: 1:  2698940791/859099536 - delta: 0.000000000232830644, rem: 0.299504418772708979
Iteration #18: 3:  9978066541/3176117225 - delta: 0.000000000000000000, rem: 0.338848902789946401 ******* 'true' deviation below epsilon threshold