整数を2バイトに分解する

Question

私はいくつかのマイクロチップの2バイトレジスタにタイムアウト値を書き込む必要がある埋め込みプロジェクトに取り組んでいます。

タイムアウトは次のように定義されています

timeout = REG_a * (REG_b +1) 

私は256までの範囲の整数を使用して、これらのレジスタをプログラムしたい私はtimeout-与えられた、アルゴリズムを探しています60000言うことができますREG_aとREG_bを計算します。

正確な解決策が不可能な場合は、次に可能なタイムアウト値を大きくしたいと考えています。

は、私がこれまで行ってきた：

私の現在のソリューションは、計算：

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

これは実際にはうまく機能した値になります。しかし、皆さんがより最適なソリューションを考え出すことができるかどうかを確認したいと思います。

ああ、私は記憶が制約されているので、大きなテーブルは問題になりません。また、実行時間が重要なので、私は単にソリューションをブルートフォースすることはできません。

Answer 1

その回答Algorithm to find the factors of a given Number.. Shortest Method?で使用されているコードを使用して、タイムアウトの要因を見つけることができます。

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 

Answer 2

面白い問題、Nils！

値の1つ、たとえばReg_aを修正してから、regunbをroundup：Reg_b = ((timeout + Reg_a-1)/Reg_a) -1で除算して計算するとします。

あなたはあなたが近くにいることは知っていますが、どれくらい近いですか？さて、エラーの上限はReg_aでしょうか？エラーは除算の残りの部分であるためです。

のいずれかをできるだけ小さくしてとすると、他の要因が計算されるため、エラーの上限はできるだけ小さくします。

一方、2つの要素を平方根に近づけると、除数ができるだけ大きくなるため、エラーは可能な限り大きくなります！

So：

まず、Reg_aの最小値は何ですか？ (timeout + 255)/256;

次に、上記のようにReg_bを計算します。

これはすべての場合で絶対最小限の組み合わせではありませんが、平方根を使用するよりも優れていて、高速です。