Pythonスタイルの整数除算＆amp; Cのモジュラス

StackOverflow https://stackoverflow.com/questions/828092

質問

PythonおよびRubyでは、符号付き整数の除算は負の無限大に向かって切り捨てられ、符号付き整数のモジュラスは第2オペランドと同じ符号を持ちます。

>>> (-41) / 3
-14
>>> (-41) % 3
1

ただし、CおよびJavaでは、符号付き整数の除算は0に向かって切り捨てられ、符号付き整数のモジュラスは第1オペランドと同じ符号を持ちます。

printf("%d\n", (-41) / 3); /* prints "-13" */
printf("%d\n", (-41) % 3); /* prints "-2" */

CでPythonやRubyと同じ種類の除算とモジュラスを実行する最も簡単で効率的な方法は何ですか？

役に立ちましたか？

解決

符号付き整数除算による丸めの方向は、古いC標準では指定されていません。ただし、C99ではゼロに丸めることが指定されています。

C標準およびCPUアーキテクチャのすべてのバージョンで動作するポータブルコードは次のとおりです。

int py_div(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -a / -b;
    else
      return -(-a / b) - (-a % b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a / -b) - (a % -b != 0 ? 1 : 0);
    else
      return a / b;
}

int py_mod(int a, int b)
{
  if (a < 0)
    if (b < 0)
      return -(-a % -b);
    else
      return -a % b - (-a % -b != 0 ? 1 : 0);
  else if (b < 0)
      return -(a % -b) + (-a % -b != 0 ? 1 : 0);
    else
      return a % b;
}

いくつかの表面的なテストを行いましたが、Pythonと同じ結果が得られるようです。このコードは最大限に効率的ではないかもしれませんが、優れたCコンパイラーは、特に静的関数としてヘッダーにコードを置く場合、おそらく適切に最適化できます。

この密接に関連する質問もご覧ください：整数C ++での負数による除算の丸め。

他のヒント

モジュロの場合、以下が最も簡単です。実装の符号規約が何であるかは関係ありません。結果を必要な符号に強制するだけです。

r = n % a;
if (r < 0) r += a;

明らかに、これは肯定的なものです。ネガティブAの場合：

r = n % a;
if (r > 0) r += a;

（おそらく少し混乱するかもしれませんが）以下を与えるために結合します（C ++で。Cでもintで同じことを行い、長い間長い間複製を退屈に書く）：

template<typename T> T sign(T t) { return t > T(0) ? T(1) : T(-1); }

template<typename T> T py_mod(T n, T a) {
    T r = n % a;
    if (r * sign(a) < T(0)) r += a;
    return r;
}

チープスケートの2つの値を持つ「サイン」を使用できます。すでにa！= 0を知っているため、または％が未定義になるためです。

同じ原則を除算に適用する（入力ではなく出力を見る）：

q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;

乗算はおそらく必要以上に高価になる可能性がありますが、必要に応じて後でアーキテクチャごとに微最適化できます。たとえば、商と剰余を与える除算演算がある場合、除算のためにソートされます。

[編集：商または剰余がINT_MAXまたはINT_MINの場合など、これがうまくいかない場合があります。しかし、とにかく大きな値のpython数学をエミュレートすることはまったく別の質問です;-）]

[別の編集：標準のPython実装はCで書かれていませんか？あなたは彼らが何のためにソースをトロールすることができます]

C89のフロア分割とモジュラスの簡単な実装を次に示します。

#include <stdlib.h>

div_t div_floor(int x, int y)
{
    div_t r = div(x, y);
    if (r.rem && (x < 0) != (y < 0)) {
        r.quot -= 1;
        r.rem  += y;
    }
    return r;
}

ここでは、明確な動作があるため、 div が使用されます。

>

C ++ 11を使用している場合、以下にフロア分割とモジュラスのテンプレート実装を示します。

#include <tuple>

template<class Integral>
std::tuple<Integral, Integral> div_floor(Integral x, Integral y)
{
    typedef std::tuple<Integral, Integral> result_type;
    const Integral quot = x / y;
    const Integral rem  = x % y;
    if (rem && (x < 0) != (y < 0))
        return result_type(quot - 1, rem + y);
    return result_type(quot, rem);
}

C99およびC ++ 11では、Cの除算とモジュラスの動作が実装に依存しなくなったため、 div の使用を避けることができます。

この質問には、すでに提示されているものよりもはるかに短い（コードで）解決策があります。私はVille Laurikariの回答の形式を使用します：

int py_div(int a, int b)
{
    return (a - (((a % b) + b) % b)) / b);
}

int py_mod(int a, int b)
{
    return ((a % b) + b) % b;
}

残念ながら、上記のソリューションはうまく機能していないようです。 Ville Laurikariに対してこのソリューションのベンチマークを実行すると、このソリューションのパフォーマンスは半分にしかならないことが明らかになります。

教訓：分岐命令はコードを遅くしますが、除算命令はもっと悪いです！

それでも、エレガントさのためだけにこのソリューションを投稿すると思いました。

質問は、Pythonスタイルの整数除算とモジュロをエミュレートする方法について尋ねました。ここで与えられるすべての答えは、この演算のオペランドが整数であると仮定していますが、Pythonはモジュロ演算に浮動小数点数を使用することもできます。したがって、私は次の答えが問題をさらに良く解決すると思う：

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int pydiv(double a, double b) {
    int q = a/b;
    double r = fmod(a,b);
    if ((r != 0) && ((r < 0) != (b < 0))) {
        q -= 1;
    }
    return q;
}

int main(int argc, char* argv[])
{
    double a = atof(argv[1]);
    double b = atof(argv[2]);
    printf("%d\n", pydiv(a, b));
}

そしてモジュロの場合：

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

double pymod(double a, double b) {
    double r = fmod(a, b);
    if (r!=0 && ((r<0) != (b<0))) {
        r += b;
    }
    return r;
}

int main(int argc, char* argv[])
{
    double a = atof(argv[1]);
    double b = atof(argv[2]);
    printf("%f\n", pymod(a, b));
}

次のテストコードを使用して、Pythonの動作に対して上記の2つのプログラムをテストしました。

#!/usr/bin/python3
import subprocess
subprocess.call(["cc", "pydiv.c", "-lm", "-o", "cdiv"])
subprocess.call(["cc", "pymod.c", "-lm", "-o", "cmod"])
def frange(start, stop, step=1):
    for i in range(0, int((stop-start)/step)):
        yield start + step*i
for a in frange(-10.0, 10.0, 0.25):
    for b in frange(-10.0, 10.0, 0.25):
        if (b == 0.0):
            continue
        pydiv = a//b
        pymod = a%b
        cdiv = int(subprocess.check_output(["./cdiv", str(a), str(b)]))
        cmod = float(subprocess.check_output(["./cmod", str(a), str(b)]))
        if pydiv != cdiv:
            exit(1)
        if pymod != cmod:
            exit(1)

上記では、Pythonの除算とモジュロの動作をCと比較します。 6320テストケースで紹介した実装。比較が成功したため、 私のソリューションは、Pythonの動作を正しく実装すると信じています それぞれの操作。

フロートのい世界を掘り下げますが、これらはJavaで正しい答えを提供します：

public static int pythonDiv(int a, int b) {
    if (!((a < 0) ^ (b < 0))) {
        return a / b;
    }
    return (int)(Math.floor((double)a/(double)b));
}

public static int pythonMod(int a, int b) {
    return a - b * pythonDiv(a,b);
}

それらの効率については断言しません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top