Geek Answers Handbook

Support x * x in C ++

I have the following while-loop

uint32_t x = 0;
while(x*x < STOP_CONDITION) {
    if(CHECK_CONDITION) x++
    // Do other stuff that modifies CHECK_CONDITION
}

STOP_CONDITIONis constant at runtime, but not at compile time. Is there a more efficient way to support it, x*xor do I really need to compromise it every time?

+4
source share
5 answers

Note. According to the standard below, this code works about 1-2% slower than this parameter . Please read the disclaimer below!

Tamas Ionut, STOP_CONDITION ,

(x + 1)² = x² + 2x + 1

, x:

uint32_t x = 0;
unit32_t xSquare = 0;
while(xSquare < STOP_CONDITION) {
    if(CHECK_CONDITION) {
      xSquare += 2 * x + 1;
      x++;
    }
    // Do other stuff that modifies CHECK_CONDITION
}

2*x + 1 - , .

:. " ", . + , . , . , , . , , , , (, , x*x ).

+9

:

uint32_t x = 0;
double bound= sqrt(STOP_CONDITION);
while(x < bound) {
    if(CHECK_CONDITION) x++
    // Do other stuff that modifies CHECK_CONDITION
}

, .

+4

CompuChip :

: 19.7068

:

uint32_t x = 0;
double bound= sqrt(STOP_CONDITION);
while(x < bound) {
    if(CHECK_CONDITION) x++
    // Do other stuff that modifies CHECK_CONDITION
}

CompuChip: 20.2056

:

uint32_t x = 0;
unit32_t xSquare = 0;
while(xSquare < STOP_CONDITION) {
    if(CHECK_CONDITION) {
      xSquare += 2 * x + 1;
      x++;
    }
    // Do other stuff that modifies CHECK_CONDITION
}

STOP_CONDITION = 1000000 1000000

:

  • : MSVC 2013
  • : Windows 8.1 - X64
  • : Core i7-4510U @2.00 GHZ
  • - (/O2)
+4

, readibility , ,

,

0

, Tamas Ionut , CompuChip, for x ++. uint32_t double . uint32_t double. , x 2 ^ 16 = 65536, x ^ 2.

, , , , Tamas Ionut .

, clang 3.8.0 -O3. , .

using T = size_t;

void test1(const T stopCondition, bool checkCondition) {
    T x = 0;
    while (x < stopCondition) {
        if (checkCondition) {
            x++;
        }
        // Do something heavy here
    }
}

void test2(const T stopCondition, bool checkCondition) {
    T x = 0;
    T xSquare = 0;
    const T threshold = stopCondition * stopCondition;
    while (xSquare < threshold) {
        if (checkCondition) {
            xSquare += 2 * x + 1;
            x++;
        }
        // Do something heavy here
    }
}

(gdb) disassemble test1
Dump of assembler code for function _Z5test1mb:
   0x0000000000400be0 <+0>: movzbl %sil,%eax
   0x0000000000400be4 <+4>: mov    %rax,%rcx
   0x0000000000400be7 <+7>: neg    %rcx
   0x0000000000400bea <+10>:    nopw   0x0(%rax,%rax,1)
   0x0000000000400bf0 <+16>:    add    %rax,%rcx
   0x0000000000400bf3 <+19>:    cmp    %rdi,%rcx
   0x0000000000400bf6 <+22>:    jb     0x400bf0 <_Z5test1mb+16>
   0x0000000000400bf8 <+24>:    retq   
End of assembler dump.
(gdb) disassemble test2
Dump of assembler code for function _Z5test2mb:
   0x0000000000400c00 <+0>: imul   %rdi,%rdi
   0x0000000000400c04 <+4>: test   %sil,%sil
   0x0000000000400c07 <+7>: je     0x400c2e <_Z5test2mb+46>
   0x0000000000400c09 <+9>: xor    %eax,%eax
   0x0000000000400c0b <+11>:    mov    $0x1,%ecx
   0x0000000000400c10 <+16>:    test   %rdi,%rdi
   0x0000000000400c13 <+19>:    je     0x400c42 <_Z5test2mb+66>
   0x0000000000400c15 <+21>:    data32 nopw %cs:0x0(%rax,%rax,1)
   0x0000000000400c20 <+32>:    add    %rcx,%rax
   0x0000000000400c23 <+35>:    add    $0x2,%rcx
   0x0000000000400c27 <+39>:    cmp    %rdi,%rax
   0x0000000000400c2a <+42>:    jb     0x400c20 <_Z5test2mb+32>
   0x0000000000400c2c <+44>:    jmp    0x400c42 <_Z5test2mb+66>
   0x0000000000400c2e <+46>:    test   %rdi,%rdi
   0x0000000000400c31 <+49>:    je     0x400c42 <_Z5test2mb+66>
   0x0000000000400c33 <+51>:    data32 data32 data32 nopw %cs:0x0(%rax,%rax,1)
   0x0000000000400c40 <+64>:    jmp    0x400c40 <_Z5test2mb+64>
   0x0000000000400c42 <+66>:    retq   
End of assembler dump.
0
source

More articles:


All Articles