على غرار بيثون قسمة عدد صحيح ومعامل في C

Question

في بايثون وروبي، باقتطاع قسمة عدد صحيح وقعت نحو اللانهاية السالبة، وقعت معامل صحيح له نفس التوقيع المعامل الثاني:

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

ولكن، في C و Java، باقتطاع قسمة عدد صحيح وقعت نحو 0، وقعت معامل عدد صحيح لديه نفس إشارة المعامل الأول:

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

ما هي الطريقة الأسهل والأكثر فعالية في C لأداء نفس النوع من الانقسام ومعامل كما في بايثون وروبي؟

Answer 1

لا تحديد اتجاه التقريب مع قسمة عدد صحيح وقعت في المعايير C القديمة. ومع ذلك، في C99 يتم تحديد ذلك لتقريب باتجاه الصفر.

وهنا كود المحمولة التي تعمل مع كافة إصدارات المعايير C وأبنية وحدة المعالجة المركزية:

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;
}

وفعلت بعض الاختبارات السطحية ويبدو أن يعطي نفس النتائج كما بيثون. هذا الرمز قد لا تكون فعالة الحد الأقصى، ولكن يمكن مترجم C جيد وربما تحسين بشكل كاف، وخاصة إذا كنت وضعت رمز في رأس وظائف ثابتة.

ويمكنك أيضا أن نلقي نظرة على هذا السؤال ترتبط ارتباطا وثيقا: صحيح تقسيم التقريب مع السلبيات في C ++ .

Answer 2

لمودولو، أجد أبسط التالية. لا يهم ما هي اتفاقية علامة تنفيذ، ونحن فقط إجبار نتيجة لعلامة نريد:

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

ومن الواضح أن هذا أمر إيجابي لذلك. لالسلبي تحتاج:

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

والذي (ربما قليلا مشوش) يجمع بين لإعطاء التالية (C ++ C وتفعل الشيء نفسه مع كثافة العمليات، ومن ثم مضجر إرسال نسخة مكررة لفترة طويلة طويلة.):

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;
}

ويمكننا استخدام وظيفة "علامة" البخيل اثنين من قيمتها، لأننا نعلم بالفعل! = 0، أو٪ سيكون غير معرفة.

وتطبيق نفس المبدأ على تقسيم (نظرة على الانتاج بدلا من المدخلات):

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

ووالضرب يمكن القول يمكن أن يكون أكثر تكلفة مما هو ضروري، ولكن يمكن أن يكون الصغير الأمثل في وقت لاحق على أساس لكل الهندسة المعمارية إذا لزم الأمر. على سبيل المثال إذا كان لديك المرجع الانقسام الذي يمنحك حاصل والباقي، ثم كنت فرز للتقسيم.

[تحرير: قد يكون هناك بعض الحالات حافة فيها هذا يذهب على نحو خاطئ، على سبيل المثال إذا كان حاصل أو ما تبقى هو INT_MAX أو INT_MIN. ولكن محاكاة الرياضيات الثعبان للقيم كبيرة هي مسألة أخرى كاملة على أي حال؛ -)]

[تحرير آخر: لا تنفيذ الثعبان معيار المكتوب في C؟ هل يمكن أن الجر مصدر للما يفعلونه]

Answer 3

وهنا هو تطبيق بسيط لتقسيم طوابق ومعامل في 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، يمكنك تجنب استخدام div منذ السلوك الانقسام ومعامل في C لم تعد تعتمد على التنفيذ.

Answer 4

وهناك حل لهذه المسألة التي هي أقصر بكثير (في التعليمات البرمجية) من تلك التي قدمت بالفعل. وسوف تستخدم صيغة الجواب فيل 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;
}

ولسوء الحظ، يبدو أن الحلول السابقة لا يؤدون بشكل جيد. عندما قياس هذا الحل ضد واحد من فيل Laurikari، يصبح من الواضح أن هذا الحل يؤدي سوى نصف بالسرعة.

والدرس هو: على الرغم من تعليمات المتفرعة تجعل كود بطيئة، تعليمات قسم أسوأ بكثير

!

واعتقدت مع ذلك أقوم بنشر هذا الحل إلا إذا كان للأناقة.

Answer 5

والسؤال المطروح حول كيفية محاكاة على غرار بيثون قسمة عدد صحيح ومودولو. كل الإجابات الواردة هنا نفترض المعاملات لهذه العملية أن تكون صحيحة ولكن أنفسهم بيثون يمكن أيضا استخدام عوامات لتشغيلها MODULO. وبالتالي، أعتقد أن الإجابة التالية يحل المشكلة حتى أفضل:

#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));
}

واختبرت البرنامجين المشار ضد كيف يتصرف بيثون باستخدام رمز الاختبار التالي:

#!/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)

ما سبق ومقارنة سلوك تقسيم بيثون وMODULO مع C تطبيقات قدمت في 6320 testcases. منذ المقارنة نجحت، وأعتقد أن حل بي ينفذ السلوك بايثون للبشكل صحيح عمليات منها.

Answer 6

ووتتعمق في العالم القبيح يطفو، ولكن هذه إعطاء الإجابات الصحيحة في جاوة:

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);
}

وأنا جعل أي تأكيدات حول كفاءتها.