5

我正在做一个嵌入式项目，我必须将超时值写入一些微芯片的两个字节寄存器中。

超时定义为：

   timeout = REG_a * (REG_b +1)

我想使用 256 到 60000 范围内的整数对这些寄存器进行编程。我正在寻找一种算法，该算法在给定超时值的情况下计算 REG_a 和 REG_b。

如果不可能找到精确的解决方案，我想获得下一个可能更大的超时值。

到目前为止我做了什么：

我目前的解决方案计算：

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

这导致在实践中运行良好的值。但是，我想看看你们是否可以提出更优化的解决方案。

哦，我的内存有限，所以大表是不可能的。运行时间也很重要，所以我不能简单地暴力破解解决方案。

4

2 回答 2

2

您可以使用该答案算法中使用的代码来查找给定数字的因子。最短方法？找到一个超时因素。

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

第一个因素将是您的 REG_A，因此您需要找到另一个乘以等于超时的值。

for (i=2; i*num_factors != timeout;i++);
REG_B = i-1
于 2013-04-06T14:21:56.017 回答
1

有趣的问题，尼尔斯！

假设您首先固定其中一个值，例如 Reg_a，然后通过除法计算 Reg_b 并使用 roundup: Reg_b = ((timeout + Reg_a-1) / Reg_a) -1。

然后你知道你很接近，但有多接近？那么错误的上限是Reg_a，对吗？因为错误是除法的余数。

如果你使一个因素尽可能小，然后计算另一个因素，你就会使误差的上限尽可能小。

另一方面，通过使这两个因子接近平方根，您可以使除数尽可能大，从而使误差尽可能大！

所以：

首先，Reg_a 的最小值是多少？ (timeout + 255) / 256;

然后如上所述计算 Reg_b。

这不会是所有情况下的绝对最小组合，但它应该比使用平方根更好，而且速度也更快。

于 2013-04-06T17:29:18.400 回答