V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cnbatch
V2EX  ›  C

这段话是否正确?「取余这个运算,只有 Python 是对的。当初 C 这个老师教错了,那么一大票学生也就只敢跟着老师错。只有 Python 敢于站出来坚持正确答案。」

  •  
  •   cnbatch · 7 天前 · 4041 次点击

    今天在看一篇公众号文章《性能之王:最快的编程语言》,发现评论区有这么一段对话:

    img

    img2

    然后我找了下在 stackexchange 的真实提问:

    https://math.stackexchange.com/questions/623449/negative-number-divided-by-positive-number-what-would-be-remainder

    从回答来看,C 和 Python 的两种做法在数值计算上都是成立的。两种做法的区别在于是否允许余数为负数,或者说,符号该不该与原数值相同。

    不允许余数出现负数的,是目前广泛使用的欧几里得除法。

    所以“数学洁癖”会认为负值余数是错的?

    50 条回复    2024-11-29 17:18:58 +08:00
    mightybruce
        1
    mightybruce  
       7 天前
    这个取余运算的确在数学上是没有负数,这个的确没有问题。毕竟搞计算机的很多数学水平一般,这也很正常。

    读计算机科学里面一些分支的博士,就会发现基本没有本科学计算机的了, 尤其是密码学、数值分析这些。
    mark2025
        2
    mark2025  
       7 天前
    py 真是性能亡者~
    codehz
        3
    codehz  
       7 天前
    本身就是定义学的问题,太过纠结这种东西没意义。。。
    连 0 是否是自然数,(类似数组下标从 0 还是从 1 开始)都可以有好多说法
    以及 1 是不是素数
    我建议从实用主义出发,别去想这种东西哪个“更合理”
    mightybruce
        4
    mightybruce  
       7 天前
    数学要求体系必须是自洽的, 不像计算机学科,当然数学有一点不行,就是数学符号乱飞,不同体系下的同一个数学符合意思都不一样。
    计算机本身运算你可以认为都是在有限群上的, 所以取余后是正数是没错的, 另外负数的平方根在计算机中是二次剩余也是正数。
    mightybruce
        5
    mightybruce  
       7 天前
    @mark2025 python 也不是非常拉跨,pypy 是 python jit 解释器, 只不过 python 默认的 cpython 那是运行效率低。
    Eureka0
        6
    Eureka0  
       7 天前
    数论里面 -1 与 2 是模 3 同余的,属于同一个同余类,取余等于多少,就是一个怎么选同余类代表数的定义问题,Python 选最小非负整数集(最小剩余系),C 选 {-[n/2], ..., [n/2]+1},数学上其实都没有问题
    dnfQzjPBXtWmML
        7
    dnfQzjPBXtWmML  
       7 天前
    C 不是给无能巨婴用的语言,溢出、越界、CPU 的特性都开放给你,不懂搞出问题了是你自己的问题。
    觉得 CPU 指令设计有问题可以去 intel/amd 门口举牌子。
    从这个上面能总结出 XXX 的多少沾点智慧。
    FalconD
        8
    FalconD  
       7 天前 via Android
    这就是个定义问题,下面是 Haskell 标准库的结果:
    quotRem 3 2 = (1, 1)
    quotRem 3 -2 = (-1, 1)
    quotRem -3 2 = (-1, -1)
    quotRem -3 -2 = (1, -1)
    divMod 3 2 = (1, 1)
    divMod 3 -2 = (-2, -1)
    divMod -3 2 = (-2, 1)
    divMod -3 -2 = (-2, -1)
    和 LLM 的总结一致
    rem: The result has the same sign as the dividend.
    mod: The result has the same sign as the divisor, or is zero
    liprais
        9
    liprais  
       7 天前
    @codehz 大专?
    FalconD
        10
    FalconD  
       7 天前 via Android
    在这种意义下 C 的行为没有问题 因为 -1/3 + -1%3 == -1
    C 只是约定 / 代表 quotation, % 代表 reminder
    zzzsy
        11
    zzzsy  
       7 天前 via Android
    除法又不是只有欧几里得除法一种
    majula
        12
    majula  
       7 天前   ❤️ 1
    编程语言提供的基本数学运算是方便开发者编写程序的,而不是用来进行数学研究的。要想做后者,应当使用专门的软件(比如 Scilab )

    非得要求编程语言中的概念在数学上“正确”,无异于耍流氓

    ----

    题外话,有“数学洁癖”的人最常吐槽的是众多编程语言的“变量”,完全跟数学上的“变量”是不同的东西

    不过在这一点上 C 语言并没有中枪,因为 C 语言并没有“变量”这一概念(翻一翻标准手册,会发现 variable 这个词唯一出现在的地方是 VLA )
    angrylid
        13
    angrylid  
       7 天前
    无奖竞猜:有一种主流编程语言 0/0 不会抛出异常且可以得到合法返回值
    ZE3kr
        14
    ZE3kr  
       7 天前
    错的多了就成标准了。HTTP 里 referrer 错误拼写成了 referer ,但现在用的都是错误的拼写
    secondwtq
        15
    secondwtq  
       7 天前
    这些语言的行为在它们自己的体系里是自洽的——比如 C 的浮点数转整数会直接把浮点部分切掉,而 C 的除法,商也是把浮点部分切掉,然后根据此算出余数。如果用传统香烟,啊不传统余数,那同时算出的商和余数会不满足 商*除数+余数=被除数 这一基本原则,这个问题显然更严重。
    注意这个行为是 C99 之后才有的,之前没有定义,不过 C99 之前标准库里定义了 div() 函数,可以同时算出商和余数,是一直遵循这个行为的。主流实现比如 x86 的 idiv 指令应该一直都是这样。

    C 标准库对浮点数还定义了 fmod() 和 remainder() 两个函数,两个采取了不同的定义,remainder() 函数对应的是 IEEE 754 标准定义的 remainder 操作。fmod() 函数我没有在标准里找到对应。

    Python 虽然浮点强转整数也是切,但是貌似实际用得不多,默认的 / 不能整除时直接给浮点,// 和 % 也是一致的。

    至于拿计算机语言强行追求贴合数学定义我觉得大可不必,光浮点数就很头疼。等下个 IEEE 754 标准更新之后,可能会有很多符合该标准的实现,但是可能大多数人不会用。
    coderluan
        16
    coderluan  
       7 天前
    作者说只有 python 是对的,其他语言是错的,从数学的角度我并不反对。

    但是作者说其他编程语言是因为 C 语言这么做,所以才跟着这么做的。我感觉作者有点太不看不起其他编程语言了吧,那其他语言和 C 语言不一致情况怎么解释,其他语言这会又不怕了吗?这就是明显的拉踩行为啊。
    cooltechbs
        17
    cooltechbs  
       7 天前
    谈数学怎么能不提 Fortran ,Fortran 是怎么处理的(我真的不懂,真心发问)?
    而其他语言“错”的根源肯定也不是 C ,而是汇编/机器码。这方面 ARM 、MIPS 又是怎么处理的?
    vvhy
        18
    vvhy  
       7 天前
    两种定义在数学上都是自洽的
    secondwtq
        19
    secondwtq  
       7 天前   ❤️ 2
    我记得这个问题我很久之前折腾过,不过具体怎样忘了(当时也没搞 Numerics ),我翻了一下记录,有这么一篇论文:
    dl.acm.org/doi/pdf/10.1145/128861.128862 The Euclidean Definition of the Functions div and mod
    刚才搜到了这个
    github.com/WebAssembly/design/issues/250 Semantics of signed integer divide and remainder · Issue #250 · WebAssembly/design · GitHub
    根据这个 thread ,最早用 truncating division 的是 Fortran ,原因是早期机器上多不使用 2's complement 表示,truncating division 更好实现,C 出于和 Fortran 兼容的考虑,最后也用了 truncating division 。但是现在的 2's complement 表示上,Euclidean division 可能更好实现(见上面论文,另外两个都引用了 Guy Steele 的 Arithmetic Shifting Considered Harmful ,不过这个我还没看)。但是 truncating division 作为前 2's complement 时代的习惯保留下来了。

    所以可能还真不是 C 带的头。至于是不是真的 Fortran 先干的我也不确定( Fortran 66 标准里面我没找到,77 里面倒是有,不过那时候已经有原始的 C 了),但是考古只考到 C 大概是不合格的,就算暴论也没上面那个 thread 有活。
    另外上面的“好实现”指得是用 ASR 操作来模拟,硬件除法器有自己的算法,我还没看过。
    geelaw
        20
    geelaw  
       7 天前   ❤️ 3
    C 语言规定 a / b 的值 q 是 a 除以 b 向零取整,而 a % b 是满足 a = qb + r (带余除法恒等式)惟一的 r 。
    数论中常见的定义是 0 <= r < |b|,此时 q 的数值并不是 a 除以 b 向零取整,而是向下取整,比如

    C 语言:
    -1 = 0*3 + (-1)
    1 = 0*(-3) + 1

    数论:
    -1 = (-1)*3 + 2
    1 = (-1)*(-3) + 2

    带余除法恒等式相当重要且自然,如果丧失它则扩展欧几里得算法 [给定 a, b 计算 x, y 使 ax+by=(a,b)] 会很难写对。以下三者不可兼得:

    1. 带余除法恒等式
    2. 对一切 a 不是 int 最小值且 b 不是 0 ,成立 -(a / b) == (-a) / b 且 -a / b == 0 - a / b ,即“向零取整”
    3. a % b 永远是非负数

    值得注意的是 Python 也没有完全采用数论中常见的定义,因为 Python 里 a % b 的符号是 0 或者和 b 相同(整数的情况),而不是永远非负。

    C 和 Python 都不是“常见数论教材”纯粹的。数学上对余数的选择没有某种必然的对错,通常选 (-b, b) 里的任何数都不会导致常见的算法(如欧几里得算法)无法继续。

    C 语言选择向零取整、保持带余除法恒等式,虽然 a % b 可能有负数,但是保证了

    -a/b
    (-a)/b
    (0-a)/b

    -(a/b)
    0-(a/b)
    0-a/b

    的计算结果都相同(假设 a 不是 int 最小值且 b 不是 0 )。而在 Python 里面,对于整数 a,b ,表达式

    -a//b
    (-a)//b
    (0-a)//b



    -(a//b)
    0-(a//b)
    0-a//b

    的两组结果分别相同,但组间可以不同,不同当且仅当 a/b 是负非整数。
    favourstreet
        21
    favourstreet  
       7 天前 via Android
    兄弟们,还是看一看实部或者虚部有一个是浮点数∞的时候都复数乘法该怎么算吧,我支持单点紧化
    NessajCN
        22
    NessajCN  
       7 天前
    定义问题
    数学上你 7%3 == -2 也是对的,也就是个向左取还是向右取的选择
    FishBear
        23
    FishBear  
       7 天前
    @liprais #9 冒犯了哦.
    laikick
        24
    laikick  
       7 天前
    无所谓 PHP 会出手
    edwardzcn98
        25
    edwardzcn98  
       7 天前   ❤️ 1
    应该只是定义不同,无关对错,哪里来的 python 精神可敬。。以下是 Lean 中求余的表达,官方也解释早期用 truncation-rounding 定义,后来用的 euclidean 定义。表达数学能力有差别,所以才改。

    这篇文章解释了几种定义下的除法和求余
    https://dl.acm.org/doi/pdf/10.1145/128861.128862

    ```lean4
    -- default (guess using emod as default)
    #eval (-1: Int) % (3: Int) -- 2
    #eval (1: Int) % (-3: Int) -- 1

    -- using emod (euclidean division)
    #eval (-1: Int).emod (3 : Int) -- 2
    #eval (1: Int).emod (-3 : Int) -- 1

    -- using tmod (truncating division)
    #eval (-1 : Int).tmod (3 : Int) -- -1
    #eval (-1 : Int).tmod (-3 : Int) -- -1
    ```
    edwardzcn98
        26
    edwardzcn98  
       7 天前
    这个算是标答了。以及#19 提到了同样一篇文章
    edwardzcn98
        27
    edwardzcn98  
       7 天前
    edwardzcn98
        28
    edwardzcn98  
       7 天前
    指#20 @geelaw
    paopjian
        29
    paopjian  
       7 天前
    这种拉一捧一的不是来秀优越性的么,计算机领域尊重数学某一学派就叫对,不遵守就叫错? 那看来编程语言有精度问题就可以说不配存在了
    mengdodo
        30
    mengdodo  
       7 天前
    @laikick 你真是个天才
    geelaw
        31
    geelaw  
       7 天前
    @geelaw #20 修正,数论常见的带余除法应该是 1 = 0*(-3) + 1
    cybort
        32
    cybort  
       7 天前 via Android
    这个是和取整方法有关的,C 语言取的是向 0 取整的结果,你给出来的是向下取整的结果。如果-1/3+1/3 不等于 0 ,其实更反直觉。运算系统本来就是人为定义的,欧氏空间也不比其他空间跟高贵,关键是哪一种好用。
    Maboroshii
        33
    Maboroshii  
       7 天前
    说起来可能有点可笑,我长这么大还没用过负数取模...
    xuld
        34
    xuld  
       6 天前
    并不是其他语言是错的,而是其他语言管 % 叫取模运算,这些语言规范中从没说 % 是取余运算。只不过取模运算在正数的时候,结果和取余是相同的。
    xuanbg
        35
    xuanbg  
       6 天前
    我个人不太认可数学洁癖的说法,我认为除法向零取整才是符合直觉的。所以 C 的做法没错,Python 反倒是有点矫情了
    InkStone
        37
    InkStone  
       6 天前
    欧几里得除法是什么玩意儿,你是想说辗转相除法么?这只是一个算法而已,不是什么取模的定义。

    事实上你在正经的数学文献里几乎不会看到取模运算这种东西,只有同余恒等式,没有取模运算。这跟编程里的概念是不一样的。

    什么是同余恒等式? 7 ≡ 17 ( mod 10 ),这才是数学的东西。
    NoOneNoBody
        38
    NoOneNoBody  
       6 天前
    一个是整除后,跟整除结果的距离。这里还有整除定义的问题,是除法结果的整数部分,还是除法结果向较小方向取整
    一个是分段区间跟较小端的距离 # 这个才叫“余下”,其实在负数情况下,人类语义基本就没有“余下”概念了,而是叫“尚缺”,就是和分段区间较大端的距离
    数学是脱离文字语言,对数字计算的归一处理,即使负数,也按相同的准则定义和计算。其中欧氏除法统一和较小端比较,或者说整除是除法结果取不大于该结果的最大整数

    编程是定义整除为“除法结果的整数部分”,取模为“跟整除结果倍数的距离”,其中余数符号的意义是方向
    它未必要向人类语义看齐,例如计数器下标从 0 开始,是不吻合人类理解的,就像公元一世纪,就是 01-100 年,没有公元零年或公元零世纪,想当年 1999~2000 跨年夜,一堆人庆祝“进入新世纪”就很好笑

    所以,计算机求“余”的计算,要按实际需求重写算法,而不是单纯用某个表达式替代
    GuuJiang
        39
    GuuJiang  
       6 天前 via iPhone
    @InkStone 不了解的东西可以先去检索而不是直接断言,欧几里得除法是个专有概念,维基百科都能查到,另外 rust 语言里的各种数值类型都提供了内置的 div_euclid 和 rem_euclid 方法
    moxuze
        40
    moxuze  
       6 天前
    数组这个下标,只有 Lua 是对的。当初 Python 这个老师教错了,那么一大票学生也就只敢跟着老师错。只有 Lua 敢于站出来坚持正确答案。
    ccpp132
        41
    ccpp132  
       6 天前
    @moxuze 我记得以前 basic 下标就是 1 开始了。当然还得是 pascal ,你爱从几开始自己定义
    cnbatch
        42
    cnbatch  
    OP
       6 天前
    @ccpp132 结合你的这段回忆,看得出其实 @moxuze 是在讽刺原图的“楓梓”啦
    InkStone
        43
    InkStone  
       6 天前
    @GuuJiang 这不就是欧几里得辗转相除法么?这是一个计算带余除法的算法,而不是一种除法的定义。你都查了,怎么连基本概念都没搞清楚
    FalconD
        44
    FalconD  
       6 天前 via Android
    InkStone
        45
    InkStone  
       6 天前
    @FalconD 好吧。欧几里得环。确实没往这方面想,是我搞错了。
    zeromake
        46
    zeromake  
       6 天前
    @moxuze lua 下标就是 1 开始,实际上没啥问题,问题在于写 lua 几乎不可能不使用 c 做扩展工作,然后就爽了一会在 c 里用下标 0 ,一会在 lua 里下标 1……
    tabc2tgacd
        47
    tabc2tgacd  
       6 天前
    感觉无需纠结这种问题,用什么语言就按什么语言的规矩来就行了。
    bluesenzhu
        48
    bluesenzhu  
       6 天前
    @FalconD 确实维基百科写的很全面很详细
    namonai
        49
    namonai  
       5 天前
    `%` 在 C 里面也叫取模运算,没人说过这是取余数
    Izual_Yang
        50
    Izual_Yang  
       5 天前
    经典老番,数学也有自己的“负小数的整数部分”(高斯取整),但是很少有能解释清楚这样定义有何优点的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3633 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:22 · PVG 12:22 · LAX 20:22 · JFK 23:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.