相关疑难解决方法(0)

我试图想出一个方法,它接受一个整数并返回一个布尔值来说明数字是否为素数,我不知道多少C; 有人会关心给我一些指示吗？

基本上,我会在C#中这样做:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

我正在尝试生成代码(目前使用clang ++ - 3.8),它添加了两个由多个机器字组成的数字.为了简化目前我只添加128位数字,但我希望能够概括这一点.

首先是一些typedef:

typedef unsigned long long unsigned_word;
typedef __uint128_t unsigned_128;

而"结果"类型:

struct Result
{
  unsigned_word lo;
  unsigned_word hi;
};

第一个函数f采用两对无符号字并返回结果,作为一个中间步骤,在添加它们之前将这两个64位字放入一个128位字中,如下所示:

Result f (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
  Result x;
  unsigned_128 n1 = lo1 + (static_cast<unsigned_128>(hi1) << 64);
  unsigned_128 n2 = lo2 + (static_cast<unsigned_128>(hi2) << 64);
  unsigned_128 r1 = n1 + n2;
  x.lo = r1 & ((static_cast<unsigned_128>(1) << 64) - 1);
  x.hi = r1 >> 64;
  return x;
}

这实际上非常好地内联:

movq    8(%rsp), …

我正在寻找另一个问题(这里),有人正在寻找一种方法来获得x86汇编中64位整数的平方根.

事实证明这很简单.解决方案是转换为浮点数,计算sqrt然后转换回来.

我需要在C中做一些非常相似的事情,但是当我看到等价物时,我会陷入困境.我只能找到一个接收双打的sqrt函数.双精度不具有存储大64位整数的精度而不会引入明显的舍入误差.

是否有一个我可以使用的具有long doublesqrt功能的通用数学库？

我有一个像这样的循环:

for(uint64_t i=0; i*i<n; i++) {

这需要每次迭代进行乘法运算.如果我可以在循环之前计算sqrt,那么我可以避免这种情况.

unsigned cut = sqrt(n)
for(uint64_t i=0; i<cut; i++) {

在我的情况下,如果sqrt函数向下舍入到下一个整数是没关系的,但如果它向下舍入则不行.

我的问题是:sqrt函数是否准确到足以在所有情况下执行此操作？

编辑:让我列出一些案例.如果n是一个完美的正方形,那么n = y^2我的问题就是 - cut=sqrt(n)>=y对于所有n？ 如果cut = y-1则存在问题.例如,如果n = 120且cut = 10则没关系,但是如果n = 121(11 ^ 2)并且cut仍然是10则那么它将不起作用.

我首先关心的是浮点数的小数部分只有23位和双52,因此它们不能存储某些32位或64位整数的所有数字.但是,我不认为这是一个问题.假设我们想要某个数字y的sqrt,但是我们不能存储y的所有数字.如果我们将y的分数存储为x,我们可以写y = x + dx,那么我们要确保无论我们选择什么dx都不会将我们移动到下一个整数.

sqrt(x+dx) < sqrt(x) + 1  //solve
dx < 2*sqrt(x) + 1 
// e.g for x = 100 dx < 21
// sqrt(100+20) < sqrt(100) + 1

Float可以存储23位,所以我们让y = 2 ^ 23 + 2 ^ 9.这已经足够了,因为2 ^ 9 <2*sqrt(2 …