相关疑难解决方法(0)

我在GNU的C++编译器上尝试这个代码,我无法理解它的行为:

#include <stdio.h>;

int main()
{
    int  num1 = 1000000000;
    long num2 = 1000000000;
    long long num3;
    //num3 = 100000000000;
    long long num4 = ~0;

    printf("%u %u %u", sizeof(num1), sizeof(num2), sizeof(num3));
    printf("%d %ld %lld %llu", num1, num2, num3, num4);
    return 0;
}

当我取消注释注释行时,代码不会编译并给出错误:

错误:对于long类型,整数常量太大

但是,如果代码按原样编译并执行,则会产生远大于10000000000的值.

为什么？

在C++中表示128位数的最佳方法是什么？它应该尽可能地与内置数值类型一致(即支持所有算术运算符等).

我正在考虑构建一个具有2个64位或4个32位数的类.或者可能只是创建一个128位的内存块并自己完成所有操作.

是否有一些更容易/更标准的方式,或者我自己实施它时不太可能搞砸的东西？:)

如果它可以扩展到256位,512位等等也会很好...

我的程序经常需要执行以下计算：

鉴于：

• N是32位整数
• D是32位整数
• abs（N）<= abs（D）
• D！= 0
• X是任意值的32位整数

找：

• X * N / D为四舍五入的整数，X缩放为N / D（即10 * 2/3 = 7）

显然我可以直接使用r=x*n/d，但经常会从中溢出x*n。如果我改为这样做，r=x*(n/d)则由于整数除法会除去小数部分，因此我只会得到0或x。然后有，r=x*(float(n)/d)但在这种情况下我不能使用浮点数。

精度会很高，但并不像速度和决定性功能那么关键（总是在给定相同输入的情况下返回相同的值）。

N和D当前已签名，但如果有帮助，我可以解决它们始终未签名的问题。

可以使用任何X值（以及N和D，只要N <= D）的泛型函数是理想的，因为此操作以各种不同的方式使用，但是我也有一个特殊的情况，其中X的值是已知的保持2的幂（准确地说是2048），并且加快特定的调用速度将是一个很大的帮助。

目前，我正在使用64位乘法和除法来完成此操作，以避免溢出（本质上是，int multByProperFraction(int x, int n, int d) { return (__int64)x * n / d; }但是有一些断言和多余的位数摆弄而不是舍入）。

不幸的是，我的探查器报告64位除法函数占用了过多的CPU（这是一个32位应用程序）。我尝试减少执行此计算的频率，但用尽了很多方法，因此，即使有可能，我也在尝试找出一种更快的方法。在X的常数为2048的特定情况下，我使用了移位而不是乘法，但这并没有太大帮助。

我想知道在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内在函数.

我需要做以下算术:

long a,b,c;
long result = a*b/c;

虽然结果保证适合long,但乘法不是,所以它可以溢出.

我试图一步一步地进行(首先乘法再划分),同时通过将中间结果拆分a*b为最大4的大小的int数组来处理溢出(就像BigInteger使用其int[] mag变量一样).

在这里,我被这个部门困住了.我无法理解进行精确划分所需的按位变换.我需要的只是商(不需要余数).

假设的方法是:

public static long divide(int[] dividend, long divisor)

此外,我不考虑使用,BigInteger因为代码的这部分需要快速(我想坚持使用原语和原始数组).

任何帮助将非常感激!

编辑:我不是要BigInteger自己实现整个.我想要做的是比使用泛型更快地解决特定问题(a*b/c哪里a*b可以溢出)BigInteger.

编辑2:如果它可以以一种聪明的方式完成,完全没有溢出,注释中出现了一些提示,那将是理想的,但我仍在寻找一个正确的方法.

更新: 我尝试将BigInteger代码移植到我的特定需求,没有创建对象,并且在第一次迭代中,与使用BigInteger(在我的开发PC上)相比,我的速度提高了约46%.

然后我尝试了一下修改@大卫Eisenstat的解决方案,这给了我〜56%(我跑100_000_000_000随机输入来自Long.MIN_VALUE于Long.MAX_VALUE减少)运行的时间(超过2倍)比较的BigInteger(即〜18%相比,我的适应BigInteger的算法中) .

优化和测试会有更多的迭代,但在这一点上,我认为我必须接受这个答案是最好的.

假设这uint是我的定点平台上最大的整数类型，我有：

uint func(uint a, uint b, uint c);

这需要返回一个很好的近似值a * b / c。

的值c大于 的值a和 的值b。

所以我们肯定知道 的值a * b / c将适合 a uint。

但是，a * b本身的值会溢出 a 的大小uint。

因此，计算 的值的一种方法a * b / c是：

return a / c * b;

甚至：

if (a > b)
    return a / c * b;
return b / c * a;

但是， 的值c …

请考虑以下内容作为参考实现:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint64_t x = a;
    x = x * b;
    x = x / c;
    return x;
}

我感兴趣的是一个不需要64位整数类型的实现(在C或伪代码中).

我开始草拟一个如下概述的实现:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint32_t d1, d2, d1d2;
    d1 = (1 << 10);
    d2 = (1 << 10);
    d1d2 = (1 << 20); /* d1 * d2 */
    return ((a / d1) …

鉴于三个整数,a,b并c与a,b <= c < INT_MAX我需要计算(a * b) % c,但a * b可以溢出,如果值太大,这给错误的结果.

有没有办法通过bithacks直接计算它,即不使用不会溢出的值的类型？

我的问题仅限于 256 位无符号整数。

我有一个值x，我需要按比率对其进行除垢n / d，其中n < d。

简单的解决方案当然是x * n / d，但问题是x * n可能会溢出。

我正在寻找任何可能有助于获得尽可能准确的结果的算术技巧。

在计算之前将每个 和 除以n并d不能保证成功。gcd(n, d)x * n / d

我可以使用任何流程（迭代或其他）来解决这个问题吗？

请注意，我愿意选择不准确的解决方案，但我需要能够估计错误。

在x86上实现bignums时,显然数字大小的最有效选择是32位.但是,您需要算术最多两倍的数字大小(即32 + 32 = 33,32*32 = 64,64/32 = 32).幸运的是,x86不仅提供了这一功能,而且还可以从便携式C(uint64_t)访问它.

类似地,在x64上,希望使用64位数字.这将需要128位算术(即64 + 64 = 65,64*64 = 128,128/64 = 64).幸运的是,x64提供了这个功能.不幸的是,它无法通过便携式C接入,但很明显可以进入组装.

所以我的问题是它是否可从非便携式C访问.X64上的任何C编译器是否提供对此的访问,如果是,那么语法是什么？

(注意,我不是在谈论128位向量,它们被严格地视为32或64位字的集合,它们之间没有进位传播,但是关于实际的128位整数运算.)

我有一个C函数:

int64_t fn(int64_t a, int32_t b, int32_t c, int32_t d)
{
    /* should return (a * b * c)/d */   
}

a可能接近INT64_MAX,但最终结果不会溢出,例如,如果b = 1,c = d = 40.但是,我无法弄清楚如何计算这个以便我永远不会丢失数据舍入(通过先进行除法)或中间结果溢出.

如果我可以访问足够大的数据类型以适应a,b和c的整个产品,我只会在该类型中进行数学计算然后截断,但有没有一些方法可以在没有大整数的情况下执行此操作？

我正在寻找一个快速的方法来有效地计算(a⋅ b)模n  (在该数学意义上)的a,b,n类型的uint64_t.我可以忍受诸如n!=0甚至是前提条件a<n && b<n.

请注意,C表达式(a*b)%n不会删除它,因为产品被截断为64位.我正在寻找,(uint64_t)(((uint128_t)a*b)%n)除了我没有uint128_t(我知道,在Visual C++中).

我正在使用Visual C++(最好)或GCC/clang内部,充分利用x86-64平台上可用的底层硬件; 或者如果便携式inline功能无法做到这一点.

是否有可能创建一个双倍的函数并将其提升到纯C中另一个双倍的幂？如(3.5 ^2.7).我被告知这只有在使用汇编来编写函数时才有可能.