Decompose integer into two bytes

Question

I'm working on an embedded project where I have to write a time-out value into two byte registers of some micro-chip.

The time-out is defined as:

   timeout = REG_a * (REG_b +1)

I want to program these registers using an integer in the range of 256 to lets say 60000. I am looking for an algorithm which, given a timeout-value, calculates REG_a and REG_b.

If an exact solution is impossible, I'd like to get the next possible larger time-out value.

What have I done so far:

My current solution calculates:

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

This results in values that work well in practice. However I'd like to see if you guys could come up with a more optimal solution.

Oh, and I am memory constrained, so large tables are out of question. Also the running time is important, so I can't simply brute-force the solution.

Answer 1

You could use the code used in that answer Algorithm to find the factors of a given Number.. Shortest Method? to find a factor of 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

The first factor will be your REG_A, so then you need to find another value that multiplied equals timeout.

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

Answer 2

Interesting problem, Nils!

Suppose you start by fixing one of the values, say Reg_a, then compute Reg_b by division with roundup: Reg_b = ((timeout + Reg_a-1) / Reg_a) -1.

Then you know you're close, but how close? Well the upper bound on the error would be Reg_a, right? Because the error is the remainder of the division.

If you make one of factors as small as possible, then compute the other factor, you'd be making that upper bound on the error as small as possible.

On the other hand, by making the two factors close to the square root, you're making the divisor as large as possible, and therefore making the error as large as possible!

So:

First, what is the minimum value for Reg_a? (timeout + 255) / 256;

Then compute Reg_b as above.

This won't be the absolute minimum combination in all cases, but it should be better than using the square root, and faster, too.