首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >浮标和双倍(C/C++)的快速乘法/除法2

问浮标和双倍(C/C++)的快速乘法/除法2
EN

Stack Overflow用户
提问于 2011-10-11 02:02:18
回答 9查看 20.8K关注 0票数 29

在我正在编写的软件中,我用我的值的2(或2的幂)做了数以百万计的乘法或除法。我真的希望这些值是int,这样我就可以访问位移位运算符了。

代码语言:javascript
复制
int a = 1;
int b = a<<24

但是,我不能,我必须坚持双打。

我的问题是:作为双数的标准表示形式(符号、指数、尾数),是否有一种方法可以用指数来以2的幂获得快速乘法/除法?

我甚至可以假设比特数是固定的(该软件将在机器上工作,而机器总是有64位长的双倍)。

是的,算法大多只做这些操作。这是瓶颈(它已经是多线程的)。

编辑:还是我完全错了,聪明的编译器已经为我优化了东西?

临时结果(用Qt来测量时间、过度消耗,但我不在乎):

代码语言:javascript
复制
#include <QtCore/QCoreApplication>
#include <QtCore/QElapsedTimer>
#include <QtCore/QDebug>

#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);

while(true)
{
    QElapsedTimer timer;
    timer.start();

    int n=100000000;
    volatile double d=12.4;
    volatile double D;
    for(unsigned int i=0; i<n; ++i)
    {
        //D = d*32;      // 200 ms
        //D = d*(1<<5);  // 200 ms
        D = ldexp (d,5); // 6000 ms
    }

    qDebug() << "The operation took" << timer.elapsed() << "milliseconds";
}

return a.exec();
}

运行表明D = d*(1<<5);和D = d*32;在同一时间运行(200 ms),而D = ldexp (d,5);运行速度慢得多(6000 ms)。我知道这是一个微基准,而我的内存突然爆炸了,因为每当我运行ldexp()时,Chrome突然要求在我的背上计算Pi,所以这个基准没有任何价值。不过,我还是会留着的。

另一方面,我在执行reinterpret_cast<uint64_t *>时遇到了困难,因为const违规(似乎volatile关键字会干扰)

EN

回答 9

Stack Overflow用户

回答已采纳

发布于 2011-10-11 02:19:02

您可以非常安全地采用IEEE754格式,其细节可以非常精确(尤指p)。当你进入异常状态时)。然而,在普通情况下,这一做法应能奏效:

代码语言:javascript
复制
const int DOUBLE_EXP_SHIFT = 52;
const unsigned long long DOUBLE_MANT_MASK = (1ull << DOUBLE_EXP_SHIFT) - 1ull;
const unsigned long long DOUBLE_EXP_MASK = ((1ull << 63) - 1) & ~DOUBLE_MANT_MASK; 
void unsafe_shl(double* d, int shift) { 
    unsigned long long* i = (unsigned long long*)d; 
    if ((*i & DOUBLE_EXP_MASK) && ((*i & DOUBLE_EXP_MASK) != DOUBLE_EXP_MASK)) { 
        *i += (unsigned long long)shift << DOUBLE_EXP_SHIFT; 
    } else if (*i) {
        *d *= (1 << shift);
    }
} 

编辑:在做了一些计时之后,这个方法比我的编译器和机器上的double方法慢得多,甚至被简化到了执行的最小代码:

代码语言:javascript
复制
    double ds[0x1000];
    for (int i = 0; i != 0x1000; i++)
        ds[i] = 1.2;

    clock_t t = clock();

    for (int j = 0; j != 1000000; j++)
        for (int i = 0; i != 0x1000; i++)
#if DOUBLE_SHIFT
            ds[i] *= 1 << 4;
#else
            ((unsigned int*)&ds[i])[1] += 4 << 20;
#endif

    clock_t e = clock();

    printf("%g\n", (float)(e - t) / CLOCKS_PER_SEC);

在DOUBLE_SHIFT中,在1.6秒内完成,内循环为

代码语言:javascript
复制
movupd xmm0,xmmword ptr [ecx]  
lea    ecx,[ecx+10h]  
mulpd  xmm0,xmm1  
movupd xmmword ptr [ecx-10h],xmm0

相对于2.4秒,否则,内部循环为:

代码语言:javascript
复制
add dword ptr [ecx],400000h
lea ecx, [ecx+8]  

真是出乎意料!

编辑2:谜团解开!VC11的一个变化是,它现在总是将浮点循环矢量化,从而有效地强制了/arch:SSE2,尽管VC10 (即使是/arch:SSE2 )在3.0秒内循环的情况下更糟:

代码语言:javascript
复制
movsd xmm1,mmword ptr [esp+eax*8+38h]  
mulsd xmm1,xmm0  
movsd mmword ptr [esp+eax*8+38h],xmm1  
inc   eax

没有VC10的/arch:SSE2 (即使是/arch:SSE)是5.3秒.具有1/100次迭代的!!,内循环:

代码语言:javascript
复制
fld         qword ptr [esp+eax*8+38h]  
inc         eax  
fmul        st,st(1)  
fstp        qword ptr [esp+eax*8+30h]

我知道x87的FP堆栈是令人敬畏的,但500倍的更糟糕是有点可笑。您可能不会看到这种加速转换,即矩阵操作到SSE或into,因为这是加载到FP堆栈、执行一个操作并从中存储的最坏情况,但是这是一个很好的例子,说明了为什么x87不是实现任何perf的方法。相关的。

票数 8
EN

Stack Overflow用户

发布于 2011-10-11 02:11:40

这是那些高度应用的特定事物之一。在某些情况下,它可能会有所帮助,而在另一些情况下则不然。(在绝大多数情况下,直截了当的乘法仍然是最好的。)

这样做的“直观”方法就是将比特提取成64位整数,并将移位值直接添加到指数中。(只要您不按NAN或INF,这就会起作用)

所以就像这样:

代码语言:javascript
复制
union{
    uint64 i;
    double f;
};

f = 123.;
i += 0x0010000000000000ull;

//  Check for zero. And if it matters, denormals as well.

注意到,这段代码在任何方面都不符合C标准,只是为了说明这个想法而已。任何实现这一功能的尝试都应该直接在程序集或SSE本质中完成。。

但是,在中,大多数情况下,将数据从FP单元移动到整数单元(和返回)的开销将远远超过直接执行乘法的开销。特别是在预SSE时代,需要将值从x87 FPU存储到内存中,然后再读入整数寄存器。

在SSE时代,Integer SSE和FP SSE使用相同的ISA寄存器(尽管它们仍然有单独的寄存器文件)。根据阿格纳雾,在Integer和FP执行单元之间移动数据有1到2个周期的代价。因此,成本比x87时代要好得多,但它仍然存在。

总之,这将取决于你在管道上还有什么。但在大多数情况下,乘积仍会更快。我以前也遇到过同样的问题,所以我是从第一手的经验中说出来的。

现在,256位AVX指令只支持FP指令,就更没有动机去玩这样的把戏了。

票数 19
EN

Stack Overflow用户

发布于 2011-10-11 02:28:20

ldexp怎么样?

任何半体面的编译器都会在您的平台上生成最佳代码。

但正如“克林顿”所指出的,简单地用“显而易见”的方式来写应该也是一样的。乘积和除法是现代编译器的儿戏。

直接咀嚼浮点表示,除了不可移植之外,几乎肯定不会更快(而且很可能更慢)。

当然,除非您的分析工具要求您考虑这个问题,否则您不应该浪费时间。但是听这个建议的人永远不需要它,那些需要它的人永远不会听。

更新

好的,我刚刚用g++ 4.5.2尝试了ldexp。cmath头将其内联为对__builtin_ldexp的调用,这反过来.

...emits调用libm ldexp函数。我本以为这个内置的优化是微不足道的,但我想GCC的开发人员从来没有考虑过这个问题。

因此,正如您所发现的那样,乘1 << p可能是您的最佳选择。

票数 9
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/7720668

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档