Re: [LONG][Solution et programme] solve a + k b ~ entier ( i.e. à moins d'epsilon d'un entier )

Le 13/11/2023 à 22:08, Olivier Miakinen a écrit :
 > Le 13/11/2023 10:59, Fabrice NEYRET a écrit :
 >>  Olivier Miakinen a écrit :
 >>> Le nombre k cherché vaut 32 × 106 = 3392
 >>
 >> et on est alors certain qu'il n'y en a pas de plus petit ?
 >
 > Alors non.

alors ça c'est embêtant. en fait, j'aimerais pouvoir énumérer ( ou au moins encadrer ) les valeurs de k pertinentes.
bon, le plus simple que j'y revienne sur un cas concret (je retombe régulièrement sur ce problème).
mais typiquement, il s'agit en gros de tracer efficacement des figures en Eulérien plutôt qu'en Lagrangien.
Ex, tracer une figure déposant des points régulièrement le long d'une trajectoire ( courbe en polaire, par ex ) est facile en programmation ordinaire.
Mais quand on écrit des /shaders/ (par ex pour GPU) le programme s'exécute en parallélisme massif pour chaque pixel simultanément. Pour un pixel en (x,y) donné, le shader appelé au pixel doit choisir s'il trace qqchose ou pas. Re-parcourir toute une boucle de construction de figure pour voir si un point tombe dans le pixel courant serait très inefficace. L'idée est plutôt de connaitre l'indice du point tombant le plus proche de (x,y), et la couleur du pixel sera alors 1 si on est a une distance de moins de epsilon du point (en fait, c'est rayon du petit disque tracé au point ) sinon 0.
Et si on sait trouver directement la distance au point le plus proche, c'est encore mieux.
Mais en pratique si on obtient déjà un subset ou un range de points potentiels, c'est déjà mieux que la grosse boucle, du moment qu'on est conservatif.
Evidemment, comme c'est un problème inverse, ça n'est pas toujours facile, ni faisable. Mais pour un certain nombre de constructions on y arrive... parfois. ex: points le long d'une spirale de Fibonacci:
https://www.shadertoy.com/view/fdjSRW
( plutôt que
https://www.shadertoy.com/view/wtsczN )
mais tracer sans boucle un trefoil en shader, par ex, même la courbe continue P = (2+cos3a)* [ cos(2a), sin(2a) ], c'est plus coton.
( i.e. trouver les a tel que |P(a)-pix| < eps )
--
Fabrice