Densidad de fracciones entre 2 números dados
Estoy tratando de hacer un análisis sobre un simpleFraction
clase y quiero algunos datos para comparar ese tipo condoubles
.
Bien, sé que estoy buscando una buena manera de obtener la densidad de fracciones entre 2 números. Las fracciones son básicamente 2 enteros (p. Ej.pair< long, long>
), y la densidad entres
yt
es la cantidad de números representables en ese rango. Y debe ser una aproximación exacta, o muy buena, realizada en O (1) o muy rápida.
Para hacerlo un poco más simple, digamos que quiero todos los números (no fracciones) a / b entre syt, donde 0 <= s <= a / b <t <= M, y 0 <= a, b < = M (b> 0, a y b son enteros)
EjemploSi mis fracciones fueran de un tipo de datos que solo cuentan hasta 6 (M = 6), y quiero la densidad entre 0 y 1, la respuesta sería 12. Esos números son:
0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6.
Lo que ya pensabaUn enfoque muy ingenuo sería recorrer todas las fracciones posibles y contar las que no pueden simplificarse. Algo como:
long fractionsIn(double s, double t){
long density = 0;
long M = LONG_MAX;
for(int d = 1; d < floor(M/t); d++){
for(int n = ceil(d*s); n < M; n++){
if( gcd(n,d) == 1 )
density++;
}
}
return density;
}
Perogcd()
es muy lento, por lo que no funciona. También trato de hacer algunas matemáticas pero no pude llegar a nada bueno.
Gracias a la respuesta @ m69, hice este código paraFraction = pair<Long,Long>
:
//this should give the density of fractions between first and last, or less.
double fractionsIn(unsigned long long first, unsigned long long last){
double pi = 3.141592653589793238462643383279502884;
double max = LONG_MAX; //i can't use LONG_MAX directly
double zeroToOne = max/pi * max/pi * 3; // = approx. amount of numbers in Farey's secuence of order LONG_MAX.
double res = 0;
if(first == 0){
res = zeroToOne;
first++;
}
for(double i = first; i < last; i++){
res += zeroToOne/(i * i+1);
if(i == i+1)
i = nextafter(i+1, last); //if this happens, i might not count some fractions, but i have no other choice
}
return floor(res);
}
El cambio principal es el siguiente, que es importante con números grandes (1e17)
El resultadoComo expliqué al principio, estaba tratando de compararFractions
condouble
. Aquí está el resultado paraFraction = pair<Long,Long>
(yaquí cómo obtuve la densidad de dobles):
Density between 0,1: | 1,2 | 1e6,1e6+1 | 1e14,1e14+1 | 1e15-1,1e15 | 1e17-10,1e17 | 1e19-10000,1e19 | 1e19-1000,1e19
Doubles: 4607182418800017408 | 4503599627370496 | 8589934592 | 64 | 8 | 1 | 5 | 0
Fraction: 2.58584e+37 | 1.29292e+37 | 2.58584e+25 | 2.58584e+09 | 2.58584e+07 | 2585 | 1 | 0