0

タイプab-cdの違いを解決するアルゴリズムを探しています。ここで、a、b、c、およびdは、タイプ容量の端にある整数です。つまり、マシン上の実際の表現に応じて、abがオーバーフローするか、桁が失われます。 。任意精度の数学を使用することはできません。プラットフォームの1つはSQLデータベースになります。

製品を（a'+ a''）b-（c' + c''）dに分解してから、どういうわけか下に向かって反復するようなものを考えます。しかし、おそらくはるかに効率的な方法、または少なくとも分解を行うための賢いアイデアがあります。残念ながら、ほとんどの場合a、b; CD; 交流; b、dは互いに素であるため、少なくとも削減は単純ではありません。

何か案は？

4

5 に答える 5

2

警告

この方法は部分的にしか機能しません。解決できない場合があります。

あなたのテキストから取られた：

タイプab-cdの違いを解決するアルゴリズムを探しています。ここで、a、b、c、およびdは、タイプ容量の端にある整数です。

(a * b) - (c * d)私が理解しているように、あなたは数値オーバーフローを避けて計算したいと思っています。そして、あなたはこれをアルゴリズムで解決したいと思っています。

最初に認識する必要があるのは、の結果が(a * b) - (c * d)データ型に適合しない可能性があるということです。私はそれらのケースを解決しようとはしません。

そこで、「ab-cd」を計算するさまざまな方法を探します。私が見つけたのはこれです：

(a * b) - (c * d) = ((a - c) * b) - (c * (d - b))

変数を並べ替えてさまざまな製品を取得できるため、恐ろしい数値オーバーフローなしで演算を計算できるケースを見つける可能性が高くなります。

((a - d) * b) - (d * (c - b))
((b - c) * a) - (c * (d - a))
((a - c) * b) - (c * (d - b))
((b - d) * c) - (b * (c - a))
((a - d) * c) - (a * (c - b))
((b - c) * d) - (b * (d - a))
((a - c) * d) - (a * (d - b))

また、これはまだ製品の違いであることに注意してください。つまり、機能する製品が見つかるまで、それらを再帰的に適用できます。例えば：

    Starting with:
        (a * b) - (c * d)
    =>
    Using the transformation:
        ((a - d) * b) - (d * (c - b))
    =>
    By substitution:
        (e * b) - (d * f)
    =>
    Rinse an repeat:
        ((e - f) * b) - (f * (d - b))

もちろん、これを行うことで数値オーバーフローが発生しないようにする必要があります。ありがたいことに、次のアプローチを使用して、特定の製品が（実際に製品を実行せずに）数値オーバーフローを引き起こすかどうかをテストすることもできます。

        var max = MaxValue;
        var min = MinValue;
        if (a == 0 || b == 0)
        {
            return false;
        }
        else
        {
            var lim = a < 0 != b < 0 ? min : max;
            if ((a < 0 == b < 0) == a < 0)
            {
                return lim / a > b;
            }
            else
            {
                return lim / a < b;
            }
        }

また、次の方法で、特定の違いが（実際に違いを実行せずに）数値オーバーフローを引き起こすかどうかをテストすることもできます。

        var max = MaxValue;
        var min = MinValue;
        if (a < 0 == b < 0)
        {
            return true;
        }
        else
        {
            if (a < 0)
            {
                if (b > 0)
                {
                    return min + b < a;
                }
                else
                {
                    return min - b < a;
                }
            }
            else
            {
                if (b > 0)
                {
                    return max - b > a;
                }
                else
                {
                    return max + b > a;
                }
            }
        }

これにより、数値オーバーフローなしで計算できる上記の8つの式から式を選択することができます。

しかし...時々それらのどれもうまくいきません。そして、それらの組み合わせでさえうまくいかない場合があるようです（つまり、すすぎと繰り返しがうまくいかない）*。たぶん、絵を完成させることができる他のアイデンティティがあります。

*：いくつかのヒューリスティックを使用して組み合わせを探索し、ランダムな探索も試みました。適切なヒューリスティックを選択しなかった可能性があり、ランダムで「運」がなかった可能性があります。だからはっきりとは言えません。

私はある程度の進歩を遂げたと思いたいです...しかし、元の問題に関しては、私は最終的に失敗しました。時間があればこの問題に戻るかもしれません...あるいはビデオゲームをプレイするだけかもしれません。

于 2012-10-06T22:04:44.607 に答える
1

製品がInt32の制限に近い場合は、Int64を使用できます。

于 2012-10-06T21:48:05.257 に答える
1

この種の問題に対処するために私が知っている標準的な方法は、人間が1桁を超える数字で行うことを行うことです。これは、指で数える自然な限界です。carry番号を先に進めます。

たとえば、電卓の数値の制限が256（2 ^ 8）であるとします。（243 * 244）-（242 * 245）の差を得るには、数値を次のように分解する必要があります。

Label | Part 1 (shifted 2 right) | Part 2 (remainder)
a       2                           43
b       2                           44
c       2                           42
d       2                           45

結果の個々の数字を格納するための配列、または文字列が必要になります。配列の方が高速だと思いますが、文字列の方が便利で見やすくなっています（デバッグ用）。

   (a*b)-(c*d)
=>   a1*b1 shift4 + a1*b2 shift2 + a2*b1 shift2 + a2*b2
   - c1*d1 shift4 + c1*d2 shift2 + c2*d1 shift2 + c2*d2
=> 987654321 (right-aligned string positioning)
  +    4xxxx
  +     88xx
  +     86xx
  +     1892
  -    4xxxx
  -     90xx
  -     84xx
  -     1890
  ==========
           2

単純な実装では、各ステップを個別に実行し、各桁を所定の位置に押し込み、必要に応じて進めます。これらのアルゴリズムの最適化については、おそらくそれぞれ2桁の配列スロットに分割するなどの文献があります（number-limit 256のレジスタは2つの2桁の数値の加算を簡単に処理できるため）。

于 2012-10-06T23:34:20.223 に答える
0

BC数学関数を使用して、32ビットシステムと64ビットシステムの両方で多数を処理できます。

多数の例

$a = "4543534543543534543543543543545";
$b = "9354354546546756765756765767676";
$c = "5654656565656556565654656565656";
$d = "4556565656546546546546546356435" ;


var_dump(calculate($a, $b, $c, $d));

出力

string '257010385579862137851193415136408786476450997824338960635377204776397393100227657735978132009487561885957134796870587800' (length=120)

使用した機能

function calculate($a, $b, $c, $d) 
{
    return bcmul(bcmul(bcmul(bcsub($a, $c),bcsub($a, $d)),bcsub($b, $c)),bcsub($b, $d));
}
于 2012-10-06T21:57:39.117 に答える
0

もう少し遊んだ後、私は自分の元のアイデアに従ったより単純なアルゴリズムを見つけました。シフトと加算だけでなく、実際の乗算と除算が必要なため、結合乗算よりも多少遅い場合がありますが、抽象言語でのパフォーマンスに関しては、これまでベンチマークを行いませんでした。

アイデアは次のように書き直しますab-cd=（a'+ q * d）b-cd = a'b-（c-qb）d = a'b-c'd

ab-cdをa>bおよびc>dとして注文した場合、つまり最大数を減らしてqを最大化した場合、アルゴリズムは最も速く変換されるようです。

q=(int)floor((a>c)? a/d : c/b);
a -= q*d;
c -= q*b;

今すぐ注文してやり直してください。すべての数値が安全な乗算のために十分に小さいか、任意の数値が2より小さいか、さらには負になるか、または両側のいずれかの数値に同じ値が見つかったら、すぐに終了できます。

于 2012-10-09T19:48:39.040 に答える