Python と Ruby では、符号付き整数の除算は負の無限大に向かって切り捨てられ、符号付き整数のモジュラスは 2 番目のオペランドと同じ符号になります。
>>> (-41) / 3
-14
>>> (-41) % 3
1
ただし、C および Java では、符号付き整数除算は 0 に向かって切り捨てられ、符号付き整数モジュラスは最初のオペランドと同じ符号を持ちます。
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 コンパイラはおそらく適切に最適化できます。
また、この密接に関連する質問: Integer division rounding with negatives in C++も参照してください。
モジュロについては、次のものが最も簡単です。実装の符号規則が何であるかは関係ありません。結果を必要な符号に強制するだけです。
r = n % a;
if (r < 0) r += a;
明らかにそれは正の 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;
}
a!=0 が既にわかっているため、cheapskate の 2 値の "sign" 関数を使用できます。そうしないと、% が未定義になります。
同じ原則を除算に適用します (入力ではなく出力を見てください)。
q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;
乗算は間違いなく必要以上に高価になる可能性がありますが、必要に応じて後でアーキテクチャごとにマイクロ最適化することができます。たとえば、商と剰余を与える除算演算がある場合、除算のためにソートされます。
[編集: たとえば、商または剰余が INT_MAX または INT_MIN である場合など、これがうまくいかないエッジ ケースがいくつかある可能性があります。しかし、とにかく、大きな値に対してPython数学をエミュレートすることは、まったく別の問題です;-)]
[別の編集: 標準の python 実装は C で書かれていませんか? 彼らが何をしているのかについてソースをトロールすることができます]
質問は、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 除算とモジュロの動作を、6320 テストケースで提示した C 実装と比較します。比較が成功したので、私のソリューションはそれぞれの操作の 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);
}
私はそれらの効率について断言しません。