12

しばらく前に数学フォーラムで、1 桁になるまで数字を何度も足し合わせるという議論をしている質問を見ました。(つまり、"362" は "3+6+2" になり、"11" になります...次に "11" は "1+1" になり、"2" になり、"362" は 2 を返します...私はこれに対する答えを得るためにいくつかの素敵なコードを書き、モジュロ9の任意の数がこの「無限桁の合計」に等しいと提案したユーザーに負けて投稿しました。私はそれをチェックし、彼は正しかった...ほぼ正しいです。ゼロが返された場合は、「9」で切り替える必要がありましたが、それは非常に迅速な修正でした...

362 = 3+6+2 = 11 = 1+1 = 2

また...

362%9 = 2

とにかく、mod9 メソッドは、1 桁になるまで桁の合計を無限に追加するのに最適です...しかし、それを 1 回だけ行うのはどうでしょうか (つまり、362 は "11" を返すだけです)... 誰も考えられますか?高速アルゴリズムの？

4

4 に答える 4

7

2 進数の 1 桁を固定幅整数で合計するためのクールなトリックがあります。各反復で、数字の半分をそれぞれ 2 つの値に分け、1 つ下の値にビット シフトして加算します。最初の反復では、1 つおきの数字を分離します。2 回目の反復、数字のペアなど。

27 が 8 ビット バイナリとして 00011011 であることを考えると、プロセスは...

00010001 + 00000101 = 00010110  <-  every other digit step
00010010 + 00000001 = 00010011  <-  pairs of digits
00000011 + 00000001 = 00000100  <-  quads, giving final result 4

10 進数でも同様のトリックを行うことができますが、選択した桁をゼロにして桁シフトを行う高速な操作で 10 進数を直接表現しない限り、単純なループよりも効率が悪くなります。したがって、12345678 の場合は...

02040608 + 01030507 = 03071115  <-  every other digit
00070015 + 00030011 = 00100026  <-  pairs
00000026 + 00000010 = 00000036  <-  quads, final result

したがって、1+2+3+4+5+6+7+8 = 36 は正しいですが、数値表現が固定幅の 10 進数である場合にのみ、これを効率的に行うことができます。常に lg(n) 回の繰り返しが必要です。ここで、lg は 2 を底とする対数を意味し、切り上げます。

これを少し拡張するために（コメント内の議論に基づいて）、これが正気であるふりをしましょう...

1 桁の追加を数えると、実際には単純なループよりも多くの作業が必要になります。ビットをカウントするためのビット単位のトリックと同様に、(結合性を使用して) これらの加算の順序を変更し、1 つの全角加算を使用して 2 つの半角加算を実装し、4 つの加算を並列に計算するという考え方です。 4 分の 1 幅の追加など。数字のクリアと数字のシフト操作にはかなりのオーバーヘッドがあり、これをループとして実装するとさらに多くなります (各ステップの数字マスキングとシフト距離の値を計算または検索します)。「ループ」はおそらく完全に展開し、それらのマスクとシフト距離を定数としてコードに含めて、それを回避する必要があります。

Binary Coded Decimal (BCD)をサポートするプロセッサは、これを処理できます。数字のマスキングと数字のシフトは、ビットのマスキングとビットのシフトを使用して実装されます。これは、各 10 進数の数字が、他の数字のエンコードとは無関係に 4 (またはそれ以上) ビットでエンコードされるためです。

1 つの問題は、最近では BCD のサポートが非常にまれであることです。8 ビットと 16 ビットの時代にはかなり一般的でしたが、私の知る限り、現在もサポートしているプロセッサは主に下位互換性のためにサポートしています。理由は次のとおりです...

  1. 非常に初期のプロセッサには、ハードウェアの乗算と除算が含まれていませんでした。これらの演算のハードウェア サポートにより、2 進数から 10 進数への変換がより簡単かつ効率的になりました。バイナリは現在ほとんどすべてに使用されており、BCD はほとんど忘れられています。

  2. ライブラリには 10 進数表現がありますが、ハードウェア BCD に移植可能なサポートを提供した高水準言語はほとんどありません。そのため、ほとんどの開発者にとってアセンブラーが現実世界のオプションではなくなったため、BCD サポートは使用されなくなりました。

  3. 数値が大きくなるにつれて、パックされた BCD でさえ非常に非効率的にパックされます。基数 10^x の数値表現は、基数 10 の最も重要な特性を持ち、10 進数として簡単にデコードされます。2^10 は 1024 であるため、基数 1000 は 3 桁あたり 12 ビットではなく 10 ビットしか必要としません。これで、32 ビットの 10 進数が 8 桁ではなく 9 桁になり、まだ 2 ビットが残っていることがわかります。 、たとえば符号ビットの場合。

問題は、この桁合計アルゴリズムがまったく価値があるためには、おそらく少なくとも 32 ビット (8 桁) の固定幅 10 進数で作業する必要があるということです。これにより、(完全に展開された) 単純なループの 15 の追加ではなく、12 の操作 (6 つのマスク、3 つのシフト、3 つの追加) が得られます。ただし、これは境界線上のゲインです。コード内の他の問題により、実際には遅くなる可能性があります。

64 ビット (16 桁の 10 進数) では、31 ではなく 16 の操作 (マスク 8、シフト 4、加算 4) しかないため、効率の向上は明らかですが、64 ビットの BCD 操作をサポートするプロセッサを見つける可能性は低いようです。たとえそうしたとしても、どのくらいの頻度でこれが必要ですか? 苦労して移植性を失う価値があるとは思えません。

于 2013-02-19T05:52:34.800 に答える
1

短いコードについては、これを試してください：

int digit_sum(int n){
    if (n<10) return n;
    return n%10 + digit_sum(n/10);
}

または、言葉で言えば、

-数が 10 未満の場合、桁の合計は数そのものです。

-それ以外の場合、桁の合計は現在の最後の桁 (別名 n mod10 または n%10) に、その数値の左側にあるすべての桁の合計 (整数除算を使用して n を 10 で割った値) を加えたものになります。

-このアルゴリズムは、基数を 10 に置き換えて、任意の基数に対して一般化することもできます。

于 2013-04-04T04:07:10.963 に答える
1

ここにHaskellの何かがあります：

sumDigits n = 
  if n == 0 
     then 0
     else let a = mod n 10
          in a + sumDigits (div n 10)

ああ、でもあなたはすでにそれをやっていると読みました...

（そして、明らかなこともあります：

sumDigits n = sum $ map (read . (:[])) . show $ n

)

于 2013-02-19T05:35:20.530 に答える
0 
int digit_sum(int n)
Do
    if (n<10) return n;
    Exit do
    else

    n=n%10 + digit_sum(n/10);

Loop
于 2013-04-08T04:35:07.803 に答える