Decomporre l'intero in due byte

Question

Sto lavorando a un progetto incorporato in cui devo scrivere un valore di timeout in due registri byte di alcuni micro-chip.

Il timeout è definito come:

timeout = REG_a * (REG_b +1) 

Voglio programmare questi registri utilizzando un numero intero nella gamma di 256 a consente di dire 60000. Sto cercando un algoritmo che, dato un timeout- valore, calcola REG_a e REG_b.

Se una soluzione esatta è impossibile, mi piacerebbe ottenere il prossimo valore di timeout più ampio possibile.

Che cosa ho fatto finora:

mia soluzione attuale calcola:

temp = integer_square_root (timeout) +1; 
    REG_a = temp; 
    REG_b = temp-1; 

questo si traduce in valori che funzionano bene in pratica. Comunque mi piacerebbe vedere se voi ragazzi poteste trovare una soluzione più ottimale.

Oh, e io sono limitato dalla memoria, quindi i tavoli di grandi dimensioni sono fuori questione. Anche il tempo di esecuzione è importante, quindi non posso semplicemente forzare la soluzione.

Answer 1

È possibile utilizzare il codice utilizzato in tale risposta Algorithm to find the factors of a given Number.. Shortest Method? per trovare un fattore di timeout.

n = timeout 
initial_n = n 
num_factors = 1; 
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number 
{ 
    power = 0; // suppose the power i appears at is 0 
    while (n % i == 0) // while we can divide n by i 
    { 
     n = n/i // divide it, thus ensuring we'll only check prime factors 
     ++power // increase the power i appears at 
    } 
    num_factors = num_factors * (power + 1) // apply the formula 
} 

if (n > 1) // will happen for example for 14 = 2 * 7 
{ 
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2 
} 
REG_A = num_factor 

Il primo fattore sarà il vostro REG_A, così allora avete bisogno di trovare un altro valore che moltiplicato uguale timeout.

for (i=2; i*num_factors != timeout;i++); 
REG_B = i-1 

Answer 2

Interessante problema, Nils!

Supponiamo di iniziare fissando uno dei valori, ad esempio Reg_a, quindi calcolare Reg_b per divisione con roundup: Reg_b = ((timeout + Reg_a-1)/Reg_a) -1.

Allora sai che sei vicino, ma quanto vicino? Bene, il limite superiore dell'errore sarebbe Reg_a, giusto? Perché l'errore è il resto della divisione.

Se si imposta uno dei fattori il più piccolo possibile, quindi si calcola l'altro fattore, si otterrebbe il limite superiore dell'errore il più piccolo possibile.

D'altra parte, rendendo i due fattori vicini alla radice quadrata, si sta rendendo il divisore più grande possibile, e quindi si rende l'errore il più grande possibile!

Quindi:

In primo luogo, qual è il valore minimo per Reg_a? (timeout + 255)/256;

Quindi calcolare Reg_b come sopra.

Questa non sarà la combinazione minima assoluta in tutti i casi, ma dovrebbe essere migliore dell'utilizzo della radice quadrata e anche più veloce.