Para establecer los registros de divisor/multiplicador adecuados en un bucle de bloqueo de fase, utilizo una expansión de fracción continua, que detengo si el numerador o el denominador de la fracción es mayor que 4095. Esto funciona realmente bien. Mi pregunta es: ¿Existe algún algoritmo/estrategia que me dé el siguiente valor más bajo y/o más alto?
Ejemplo: con registros de tamaño 32, para aproximar pi, encuentro 22/7 = 3,1429. El siguiente más bajo sería 25/8 = 3,1250 El siguiente más alto sería 19/6 = 3.1667 Actualmente resuelvo esto mediante una búsqueda exhaustiva, lo siguiente es el código equivalente de matlab/octave. La implementación real del código c es más eficiente, pero esto es sólo una forma corta de expresar el principio.
lo = unique((1:31)./floor((1:31)/pi));
hi = unique((1:31)./ceil((1:31)/pi));
rats(lo(2))
rats(hi(end-1))Así que repitiendo mi pregunta de otra manera: ¿Cómo evitar la búsqueda exhaustiva para encontrar estos valores?
Normalmente lo que veo es que para valores hasta 4096, es que los valores más cercanos son multiplico el mejor valor hasta 4096. Por ejemplo para pi ~ 22/7 = 4092/1302 Entonces las respuestas parecen ser en muchos casos
lo = round(pi*(1302+1))/(1302+1)
hi = round(pi*(1302-1))/(1302-1)Pero no siempre es así.
Edición: El mensaje original utilizaba unique(sort(...)). Dado que unique ya ordena esto era redundante.
0 votos
¿Podría explicar las reglas de "siguiente superior" y "siguiente inferior"? Las fracciones continuas siempre darán la mejor aproximación racional, ¿qué es lo que buscas? Usar 4096 como límite significa que serán aproximaciones muy precisas - es un número bastante grande para ver en una fracción continua.
0 votos
Para mi aplicación, necesito ajustar la frecuencia del sintetizador en pasos muy pequeños. Necesito seguir una frecuencia de entrada de varios GHz. La constante de tiempo del bucle es de varios minutos. Si veo que mi bucle se retrasa, quiero cambiar la relación de mi bucle de bloqueo de fase a la siguiente frecuencia más alta/baja. En cuestión de días, el bucle debería rastrear dentro de 10^-9 en promedio. La forma de fuerza bruta puede lograr esto, pero me preguntaba si hay una manera más elegante.
0 votos
No veo por qué necesitas una clase. Digamos que estás aproximando 3.14 usando a/b donde a y b son menores de 32.
0 votos
No veo por qué necesitas una clase. Si buscas a/b donde a y b son menores que 32, entonces si a/b = 3,14 puedes calcular el valor de a a partir de b, que es a =[3,14 * b] si quieres una frecuencia menor y [3,14 * b] + 1 si quieres una frecuencia mayor, donde los corchetes significan la función suelo. Así que también puedes calcular el error a medida que calculas la aproximación y llevar la cuenta del error más pequeño. Esto simplemente implica recorrer los 32 valores posibles, lo que supone una mejora respecto a la ordenación de 32 valores.
0 votos
Mi problema no son sólo 32, sino 4096. Necesitaba la ordenación, ya que la función no era monótona. El unique también ordena, así que esto es doble. La implementación de c realmente itera y encuentra el mínimo. Como se dijo el código sólo mostró el principio. No entiendo muy bien lo que haces con el floor(3,14 * b) + 1. ¿Podría dar un ejemplo más elaborado en el que dada la relación 123/456 encuentre 1083/4015, que es el vecino más cercano?
0 votos
OK Peter, ahora entiendo lo que estás tratando de hacer con tu respuesta. Pensaba que era demasiado difícil. En realidad, este fue también mi primer intento muy ingenuo. Pero esto no se acerca a los vecinos más cercanos. Como dije, ya tengo una solución que funciona (fuerza bruta), pero en general para este tipo de preguntas algún matemático inteligente ya ha encontrado alguna forma ingeniosa de resolverlo. Solo me aseguro de no estar pasando por alto lo obvio.
1 votos
¡Utiliza el árbol de la popa-brota!
0 votos
Gracias Xoff. A esto me refería con lo de la forma ingeniosa. Acabo de hacer una implementación rápida y esto encuentra la respuesta correcta de manera muy eficiente. A primera vista parece una complejidad log(N) en lugar de N.