Puissance de 2 commençant par 777777 (1998-08-15)

In article <6r1a27$hcc$1@nef.ens.fr>, David Madore wrote:

> En clair, trouver une puissance de 2 qui commence par 1000000, c'est
> facile.  Par 999999 aussi.  Mais pour trouver la premiere puissance de
> 2 qui commence par 777777, on fait comment, en pratique ?

Voilà une petite modification de mon algo; j'espère qu'il n'y a pas
d'erreur. Comme il n'est pas long, je donne directement le source C
(c'est mieux pour ceux qui veulent tester), mais ce n'est pas tout à
fait rigoureux à cause des erreurs d'arrondi (mais en point fixe, il
n'y a aucun problème, et comme toutes les variables flottantes sont
entre 0 et 1, c'est intéressant)...

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

int approx(double x, double b, double d)
{
  int u = 1, v = 1, r = 0;
  double y;

  b -= floor(b);
  x -= floor(x);
  y = 1.0 - x;
  for (;;)
    if (b < x)
    {
      while (x < y)
        { y -= x; u += v; }
      x -= y;
      if (b >= x) r += v;
      v += u;
    }
    else
    {
      if ((b -= x) <= d) return r+u;
      while (y < x)
        { x -= y; v += u; }
      y -= x;
      if (b < x) r += u;
      u += v;
    }
}

int main(int argc, char **argv)
{
  double a, b, d;
  if (argc != 4) exit(1);
  a = atof(argv[1]);
  b = atof(argv[2]);
  d = atof(argv[3]);
  printf("%d\n", approx(a,b,d));
  return 0;
}

On donne comme arguments 3 réels a, b et d, et l'entier renvoyé est
censé être le plus petit entier tel que {b - n.a} <= d, où {x} désigne
la partie fractionnaire positive de x, i.e. {x} = x - floor(x).

Voici l'application pratique pour une puissance de 2 qui commence
par 777777. On écrit (je n'explique pas les notations, j'espère que
vous les comprenez): 2^n = (777777 + [0,1[).10^k

On passe au logarithme décimal, que je note "log":
n.log(2) = log(777777+[0,1[) + k

On applique l'algo à:
  a = log(2)                     approx. 0.30102999566
  b = log(777778)                approx. 5.89085565466
  d = log(777778) - log(777777)  approx. 0.00000055838

On obtient: 26399.
Voici les premiers chiffres de 2^26399: 7777777829...