标签: integer-division

我正在研究一个6502 cpu的汇编语言程序,我发现我需要一个快速尽可能快的七分程序,特别是一个可以获得16位分红的程序.

我熟悉这里发现的例程,但是对七分法例程进行了概括,发现它非常复杂,粗略地检查了一般算法(使用整数除法)

x/7~ =(x + x/8 + x/64 ...)/ 8

表示要处理16位范围,由于6502的单个累加器寄存器和6502上各个存储器位移的相对慢速,可能需要100多个周期才能完成.

我认为查找表可能会有所帮助,但在6502上,我当然只限于256字节或更少的查找表.为此,可以假设存在两个256字节的查找表xdiv7和xmod7,当使用无符号的单字节值作为表的索引时,可以快速获得字节除以7或模数的结果分别为7.但是,我不确定如何利用它们来查找完整16位范围的值.

与此同时,我还需要一个模7算法,尽管理想情况下,可以通过除法得到的解决方案也会产生mod7结果.如果需要额外的预计算表,只要所有表的总内存需求不超过约3k,我就可以添加这些表.

虽然我最终需要一个带符号的除法算法,但是一个无符号算法就足够了,因为我可以根据需要将它推广到一个有符号的例程.

任何帮助将不胜感激.

避免转换为浮点是必要的。

我有以下功能：

pub fn s_v1(n: &u64) -> u64 {
    let mut x: u64 = 1;

    for i in 1..=*n  {
        x = x * (*n + i) / i;
    }

    x
}

这段代码给出了正确的答案s_v1(&20) == 137846528820

但是，如果我将 for 循环中的行更改为x *= (*n + i) / i;

答案改为s_v1(&20) == 16094453760

为什么结果不同？不是x = x * y一样吗x *= y？

在C中,整数除法a/b与floor(a/b)之间是否存在差异,其中a和b都是整数？更具体地说,在两个过程中发生了什

这是我不理解的代码的一部分:

byte b1 = (byte)(64 / 0.8f); // b1 is 79
int b2 = (int)(64 / 0.8f); // b2 is 79
float fl = (64 / 0.8f); // fl is 80

为什么前两个计算一个一个？我应该如何执行此操作,所以它快速而正确？

编辑:我需要字节结果

我正在尝试计算iPhone应用程序中的一些数字.

int i = 12;
int o = (60 / (i * 50)) * 1000;

我希望在这个例子中o为100(即毫秒),但它等于0,由NSLog(@"%d",o)显示.

这也等于0.

int o = 60 / (i * 50) * 1000;

这等于250,000,这是从左到右的直接数学.

int o = 60 / i * 50 * 1000;

什么在我头顶飞过？

谢谢,
尼克

我想知道在Visual C++中是否真的没有128位除法内部函数？

有一个名为_umul128()的64x64 = 128位乘法内部函数,它很好地匹配MUL x64汇编程序指令.

当然,我假设也会有一个128/64 = 64位内部分区(对DIV指令进行建模),但令我惊讶的是,Visual C++和英特尔C++似乎都没有它,至少它没有在intrin.h中列出.

有人可以证实吗？我尝试grep'ing在编译器可执行文件中的函数名称,但首先找不到_umul128,所以我想我看错了.

更新:至少我现在在Visual C++ 2010的c1.dll中找到了模式"umul128"(没有前导下划线).所有其他内在函数都列在它周围,但不幸的是没有"udiv128"之类的东西:(所以它似乎他们真的"忘记"实施它.

澄清一下:我不只是在寻找128位数据类型,而是在C++中将128位标量int除以64位int的方法.无论是一个内在的功能或本地 128位整数的支持会解决我的问题.

编辑:答案是否定的,Visual Studio 2010或2012中没有_udiv128内在函数.

据我所知,大多数编译器会通过乘法然后向右移位进行快速除法.例如,如果你检查这个SO线程,它会说当你要求Microsoft编译器除以10时,它会将被除数乘以0x1999999A(即2 ^ 32/10),然后将结果除以2 ^ 32(使用32向右移动).

到现在为止还挺好.

但是,一旦我使用GCC在ARM上测试了相同的除法,但编译器做了一些略微不同的事情.首先,它将被除数乘以0x66666667(2 ^ 34/10),然后将结果除以2 ^ 34.到目前为止,除了使用更高的乘数之外,它与Microsoft相同.然而,在那之后,它从结果中减去(被除数/ 2 ^ 31).

我的问题:为什么在ARM版本上有额外的减法？你能给我一个数字例子,如果没有减法,结果会出错吗？

如果你想检查生成的代码,它在下面(带我的评论):

        ldr     r2, [r7, #4] @--this loads the dividend from memory into r2
        movw    r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant 
        movt    r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant
        smull   r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3
        asr     r1, r3, #2 @--r3>>2, then store in r1 (effectively …

给出下面的代码,其中两个a和b是Number表示符号的32位带符号整数的范围内的值S:

var quotient = ((a|0) / (b|0))|0;

并且假设运行时完全符合ECMAScript 6规范,那么值是否quotient 始终是正确的有符号整数除a以及b整数？换句话说,这是一种在JavaScript中实现真正有符号整数除法的正确方法,它等同于机器指令吗？

我遇到了代码语法d //= 2,其中d是一个变量.这不是任何循环的一部分,我不太明白.
有人可以开导我吗？