Il più grande divisore in modo tale che due numeri siano divisi intorno allo stesso valore?

Question

Ho un algoritmo che può essere interpretato come dividere la linea del numero in un numero uguale di blocchi. Per semplicità, mi bastone con [0,1), sarà suddiviso in questo modo:

0|----|----|----|----|1 

Che cosa devo fare è prendere una serie di numeri [J, K) e trovare il più grande numero di pezzi, N, fino ad un massimo di M, che dividerà la linea del numero in modo che [j, k) cadano tutti sempre nello stesso "bin". Questo è più complicato di quanto sembri, in quanto la gamma può cavalcare un bidone in questo modo:

j|-|k 
0|----|----|----|----|1 

In modo che si può avere per arrivare a un numero piuttosto basso prima che la gamma è interamente contenuto. Inoltre, dato che il numero di bin sale, l'intervallo può spostarsi dentro e fuori da un singolo bin, in modo che ci siano minimi locali.

La risposta ovvia è quella di iniziare con i bin M e diminuire il numero fino a quando l'intervallo non rientra in un unico bin. Tuttavia, mi piacerebbe sapere se c'è un modo più veloce di enumerare tutte le possibili divisioni, in quanto il mio numero massimo può essere ragionevole (80 milioni circa).

Esiste un algoritmo migliore per questo?

Answer 1

Qui vorrei dare un'altra euristica, che è diversa da quella di btilly.

Il compito è quello di trovare interi m e n tale che m/n <= j < k <= (m + 1)/n, con n più grande possibile (ma ancora in fase di M).

Intuitivamente, è preferibile che la frazione m/n sia vicina a j. Questo porta all'idea di utilizzare continued fractions.

L'algoritmo che vi propongo è molto semplice:

1. calcolare tutte le continue frazioni di j utilizzando segni meno (in modo che le frazioni sono sempre approching j dall'alto), fino a quando il denominatore supera M;
2. per ogni tale frazione m/n, trovare il più grande intero i >= 0 tale che k <= (m * i + 1)/(n * i) e n * i <= M, e sostituire la frazione m/n con (m * i)/(n * i);
3. tra tutte le frazioni in 2, trova quella con il più grande denominatore.

L'algoritmo non è simmetrico in j e k. Quindi c'è una simile versione , che in generale non dovrebbe dare la stessa risposta, in modo che tu possa scegliere quella più grande tra i due risultati.

---

Esempio: Qui mi prenderò del btilly esempio: j = 0.6 e k = 0.65, ma io prenderò M = 10.

Per prima cosa analizzerò la procedura j. Per calcolare l'espansione frazione continua di j, calcoliamo:

0.6 
= 0 + 0.6 
= 0 + 1/(2 - 0.3333) 
= 0 + 1/(2 - 1/(3 - 0)) 

Dal 0.6 è un numero razionale, l'espansione termina in fintely molti passi. Le frazioni corrispondenti sono:

0 = 0/1 
0 + 1/2 = 1/2 
0 + 1/(2 - 1/3) = 3/5 

Computing corrispondenti i valori nel passaggio 2, si sostituisce le tre fazioni con:

0/1 = 0/1 
1/2 = 3/6 
3/5 = 6/10 

Il più grande denominatore è dato da 6/10.

---

Continuare con l'esempio precedente, la corrispondente k -procedure va come segue:

0.65 
= 1 - 0.35 
= 1 - 1/(3 - 0.1429) 
= 1 - 1/(3 - 1/(7 - 0)) 

Quindi le corrispondenti frazioni:

1 = 1/1 
1 - 1/3 = 2/3 
1 - 1/(3 - 1/7) = 13/20 

Passando passo 2, si ottiene:

1/1 = 2/2 
2/3 = 6/9 
13/20 = 0/0 (this is because 20 is already bigger than M = 10) 

Il più grande denominatore è dato da 6/9.

---

MODIFICA: risultati sperimentali.

Con mia sorpresa, l'algoritmo funziona meglio di quanto pensassi.

Ho fatto il seguente esperimento, con il limite M ignorato (equivalentemente, uno può prendere M abbastanza grande).

In ogni round, viene generata una coppia (j, k) di numeri casuali distribuiti uniformemente nell'intervallo [0, 1) con j < k. Se la differenza k - j è inferiore a 1e-4, scartare questa coppia, rendendo questo turno inefficace. In caso contrario, calcolo il vero risultato trueN utilizzando l'algoritmo naive e calcola il risultato euristico heurN utilizzando il mio algoritmo e li aggiungo ai dati statistici. Questo vale per 1e6 round.

Ecco il risultato:

effective round  = 999789 
sum of trueN  = 14013312 
sum of heurN  = 13907575 
correct percentage = 99.2262 % 
average quotient = 0.999415 

Il correct percentage è la percentuale di giri effettivi tale che trueN è uguale a heurN, e il average quotient è la media del quoziente heurN/trueN per tutti i turni efficaci.

Così il metodo fornisce la risposta corretta nel 99% + casi.

Ho eseguito anche esperimenti con valori minori M e i risultati sono simili.

Answer 2

Il caso migliore per la dimensione del cassetto deve essere maggiore di k-j.

Considerare i segmenti di linea numerica [0..j] e [k..1). Se siamo in grado di dividere entrambi i segmenti parziali in parti usando la stessa dimensione bin, dovremmo essere in grado di risolvere il problema.

Quindi, se consideriamo gcd((j-0)/(k-j), (1-k)/(k-j)), (dove usiamo la funzione con numero intero maggiore dopo la divisione), dovremmo essere in grado di ottenere una buona stima o il valore migliore. Ci sono casi d'angolo: se (k-j) > j o (k-j) > (1-k), il valore migliore è 1 stesso. Quindi una buona stima dovrebbe essere min(1, (k-j) * gcd((j-0)/(k-j), (1-k)/(k-j)))

Answer 3

Giriamo un po '.

Vorresti trovare m, n grande come si può (anche se n < M) con m/n vicino ma meno di j e k <= (m+1)/n.

Tutti i candidati promettenti saranno nello https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree. In effetti otterrai una risposta abbastanza buona solo camminando sull'albero di Stern-Brocot per trovare l'ultimo "grande razionale" che corrisponde al tuo limite appena sotto j il cui vertice è a k o superiore.

C'è una complicazione. Di solito l'albero converge rapidamente. Ma a volte l'albero Stern-Brocot ha sequenze lunghe con spazi molto piccoli. Ad esempio, la sequenza per arrivare a 1/3, 2/5, 3/7, 4/9, ... includerà 1/3, 2/5, 3/7, 4/9, ... Entriamo sempre in queste sequenze quando a/b < c/d, quindi prendiamo la mediana (a+c)/(b+d) e poi camminiamo verso un lato, quindi (a+i*c)/(b+i*d). Se sei intelligente, invece di percorrere l'intera sequenza, puoi semplicemente fare una ricerca binaria per la giusta potenza di i da utilizzare.

Il trucco per che bravura è quello di visualizzare la traversata:

1. Inizia con 2 frazioni "uguali".
2. Prendere la loro mediana. Se quello supera M allora ho finito. Else capisce da che parte sto andando.
3. Provare le potenze di 2 in (a+i*c)/(b+i*d) fino a quando non conosco l'intervallo i per il mio intervallo e le condizioni M.
4. Fare una ricerca binaria per trovare l'ultimo i che posso usare.
5. (a+i*c)/(b+i*d) e (a+i*c+c)/(b+i*d+d) sono le mie due nuove frazioni uguali. Torna al primo passaggio.

Le frazioni uguali iniziali sono, ovviamente, 0/1 e 1/1.

Ciò troverà sempre una risposta decente nelle operazioni O(log(M)). Purtroppo questa risposta ragionevolmente buona NON è sempre corretta. Considerare il caso in cui M = 3, j=0.6 e k=0.65. In questo caso l'euristica si fermerebbe a 1/2 mentre la risposta migliore effettiva è 1/3.

Un altro modo in cui può fallire è che trova solo risposte ridotte. Nell'esempio sopra se M era 4 allora si pensa ancora che la risposta migliore sia 1/2 quando è effettivamente 1/4. È facile gestirlo testando se funzionerà un multiplo della risposta finale. (Questo passaggio migliorerà la tua risposta in modo fisso, ma ragionevolmente grande, frazione del tempo.)