Skip to main content
Actually implement my own suggestions. Doh.
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated assembleras­sembler to see how many instructions a certain part of your code will take.

…
a = 1, b = 1, c = 463000, time = 0.031000s
a = 1, b = 1, c = 464000, time = 0.031000s
a = 1, b = 1, c = 465000, time = 0.031000s
a = 1, b = 1, c = 466000, time = 0.031000s
a = 1, b = 1, c = 467000, time = 0.031000s
a = 1, b = 1, c = 468000, time = 0.031000s
a = 1, b = 1, c = 469000, time = 0.031000s
a = 1, b = 1, c = 470000, time = 0.031000s
a = 1, b = 1, c = 471000, time = 0.031000s
a = 1, b = 1, c = 472000, time = 0.031000s
a = 1, b = 1, c = 473000, time = 0.031000s
a = 1, b = 1, c = 474000, time = 0.031000s
a = 1, b = 1, c = 475000, time = 0.031000s
a = 1, b = 1, c = 476000, time = 0.031000s
a = 1, b = 1, c = 477000, time = 0.031000s
a = 1, b = 1, c = 478000, time = 0.031000s
a = 1, b = 1, c = 479000, time = 0.031000s
a = 1, b = 1, c = 480000, time = 0.031000s
a = 1, b = 1, c = 481000, time = 0.031000s
a = 1, b = 1, c = 482000, time = 0.031000s
a = 1, b = 1, c = 483000, time = 0.031000s
a = 1, b = 1, c = 484000, time = 0.031000s
a = 1, b = 1, c = 485000, time = 0.031000s
a = 1, b = 1, c = 486000, time = 0.031000s
a = 1, b = 1, c = 487000, time = 0.031000s
a = 1, b = 1, c = 488000, time = 0.031000s
a = 1, b = 1, c = 489000, time = 0.031000s
a = 1, b = 1, c = 490000, time = 0.031000s
a = 1, b = 1, c = 491000, time = 0.031000s
a = 1, b = 1, c = 492000, time = 0.031000s
a = 1, b = 1, c = 493000, time = 0.031000s
a = 1, b = 1, c = 494000, time = 0.031000s
a = 1, b = 1, c = 495000, time = 0.031000s
a = 1, b = 1, c = 496000, time = 0.031000s
a = 1, b = 1, c = 497000, time = 0.031000s
a = 1, b = 1, c = 498000, time = 0.031000s
a = 1, b = 1, c = 499000, time = 0.031000s
a = 1, b = 1, time = 0.031000s

Types

Given that all values should be strictly greater than zero, long int is not the appropriate type, as it can be negative. We should accommodate that. However, instead of using long unsigned int through­out our code, let's use a type synonym in case we want to change it later to a type with a greater range:

 typedef long unsigned int Number;

You can probably come up with a better name.

Remember how I said that nicely written, modular code isn't often optimal? This is one of those unfortunateun­fortunate examples where you have to help the compiler (unless you know exactly what optimization flags you have to use or your compiler is overly aggressive). The prop is gone, the calls to pow4 are now in your loop.

That being said, we should apply the other suggestions like the type synonym and the late declaration:

typedef long unsigned int Number;

int main() {
    clock_t t;
    t = clock();

    for (Number a = 1; a < 100000; a++) {
        const Number a4 = pow4(a);                         // remember
        for (Number b = a; b < 300000; b++) {
            const Number b4 = pow4(b);                     // remember
            for (Number c = b; c < 500000; c++) {
                const Number c4 = pow4(c);                 // the fourth power
                for (Number d = c; d < 500000; d++) {
                    const Number d4 = pow4(d);             // of this member
                    if (a4 + b4 + c4 == d4)
                        printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);
…

While const isn't necessary here, it will make sure that we don't change our cached results accidentally.

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated assembler to see how many instructions a certain part of your code will take.

…
a = 1, b = 1, c = 463000, time = 0.031000s
a = 1, b = 1, c = 464000, time = 0.031000s
a = 1, b = 1, c = 465000, time = 0.031000s
a = 1, b = 1, c = 466000, time = 0.031000s
a = 1, b = 1, c = 467000, time = 0.031000s
a = 1, b = 1, c = 468000, time = 0.031000s
a = 1, b = 1, c = 469000, time = 0.031000s
a = 1, b = 1, c = 470000, time = 0.031000s
a = 1, b = 1, c = 471000, time = 0.031000s
a = 1, b = 1, c = 472000, time = 0.031000s
a = 1, b = 1, c = 473000, time = 0.031000s
a = 1, b = 1, c = 474000, time = 0.031000s
a = 1, b = 1, c = 475000, time = 0.031000s
a = 1, b = 1, c = 476000, time = 0.031000s
a = 1, b = 1, c = 477000, time = 0.031000s
a = 1, b = 1, c = 478000, time = 0.031000s
a = 1, b = 1, c = 479000, time = 0.031000s
a = 1, b = 1, c = 480000, time = 0.031000s
a = 1, b = 1, c = 481000, time = 0.031000s
a = 1, b = 1, c = 482000, time = 0.031000s
a = 1, b = 1, c = 483000, time = 0.031000s
a = 1, b = 1, c = 484000, time = 0.031000s
a = 1, b = 1, c = 485000, time = 0.031000s
a = 1, b = 1, c = 486000, time = 0.031000s
a = 1, b = 1, c = 487000, time = 0.031000s
a = 1, b = 1, c = 488000, time = 0.031000s
a = 1, b = 1, c = 489000, time = 0.031000s
a = 1, b = 1, c = 490000, time = 0.031000s
a = 1, b = 1, c = 491000, time = 0.031000s
a = 1, b = 1, c = 492000, time = 0.031000s
a = 1, b = 1, c = 493000, time = 0.031000s
a = 1, b = 1, c = 494000, time = 0.031000s
a = 1, b = 1, c = 495000, time = 0.031000s
a = 1, b = 1, c = 496000, time = 0.031000s
a = 1, b = 1, c = 497000, time = 0.031000s
a = 1, b = 1, c = 498000, time = 0.031000s
a = 1, b = 1, c = 499000, time = 0.031000s
a = 1, b = 1, time = 0.031000s

Remember how I said that nicely written, modular code isn't often optimal? This is one of those unfortunate examples where you have to help the compiler (unless you know exactly what optimization flags you have to use or your compiler is overly aggressive). The prop is gone, the calls to pow4 are now in your loop.

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated as­sembler to see how many instructions a certain part of your code will take.

…
a = 1, b = 1, c = 481000, time = 0.031000s
a = 1, b = 1, c = 482000, time = 0.031000s
a = 1, b = 1, c = 483000, time = 0.031000s
a = 1, b = 1, c = 484000, time = 0.031000s
a = 1, b = 1, c = 485000, time = 0.031000s
a = 1, b = 1, c = 486000, time = 0.031000s
a = 1, b = 1, c = 487000, time = 0.031000s
a = 1, b = 1, c = 488000, time = 0.031000s
a = 1, b = 1, c = 489000, time = 0.031000s
a = 1, b = 1, c = 490000, time = 0.031000s
a = 1, b = 1, c = 491000, time = 0.031000s
a = 1, b = 1, c = 492000, time = 0.031000s
a = 1, b = 1, c = 493000, time = 0.031000s
a = 1, b = 1, c = 494000, time = 0.031000s
a = 1, b = 1, c = 495000, time = 0.031000s
a = 1, b = 1, c = 496000, time = 0.031000s
a = 1, b = 1, c = 497000, time = 0.031000s
a = 1, b = 1, c = 498000, time = 0.031000s
a = 1, b = 1, c = 499000, time = 0.031000s
a = 1, b = 1, time = 0.031000s

Types

Given that all values should be strictly greater than zero, long int is not the appropriate type, as it can be negative. We should accommodate that. However, instead of using long unsigned int through­out our code, let's use a type synonym in case we want to change it later to a type with a greater range:

 typedef long unsigned int Number;

You can probably come up with a better name.

Remember how I said that nicely written, modular code isn't often optimal? This is one of those un­fortunate examples where you have to help the compiler (unless you know exactly what optimization flags you have to use or your compiler is overly aggressive). The prop is gone, the calls to pow4 are now in your loop.

That being said, we should apply the other suggestions like the type synonym and the late declaration:

typedef long unsigned int Number;

int main() {
    clock_t t;
    t = clock();

    for (Number a = 1; a < 100000; a++) {
        const Number a4 = pow4(a);                         // remember
        for (Number b = a; b < 300000; b++) {
            const Number b4 = pow4(b);                     // remember
            for (Number c = b; c < 500000; c++) {
                const Number c4 = pow4(c);                 // the fourth power
                for (Number d = c; d < 500000; d++) {
                    const Number d4 = pow4(d);             // of this member
                    if (a4 + b4 + c4 == d4)
                        printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);
…

While const isn't necessary here, it will make sure that we don't change our cached results accidentally.

add a link to godbolt, so that interested can read the assembler without using gcc on their own machine
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89

Lets have a look at your code. Well, not yours, but the assembler the compiler generates. You can use gcc -S -O3. On my platform, this results in the following "hot" section in mainOn my platform, this results in the following "hot" section in main:

.L6:
    movapd  %xmm6  add     rbx, %xmm11
    movapd  %xmm10  cmp     rbx, %xmm0500000
        je      .L18
.L8:
        mov     rax, QWORD PTR .LC0[rip]
        movsd   xmm0, QWORD PTR [rsp+40]
        movq    xmm1, rax
        call    pow                        ; (1)
    movapd  %xmm6  mov     rax, %xmm1QWORD PTR .LC0[rip]
    movapd  %xmm0  movsd   QWORD PTR [rsp+8], %xmm13xmm0
    movapd  %xmm11  movsd   xmm0, %xmm0QWORD PTR [rsp+48]
        movq    xmm1, rax
        call    pow                        ; (2)
    movapd  %xmm6  mov     rax, %xmm1QWORD PTR .LC0[rip]
    movapd  %xmm0  movsd   QWORD PTR [rsp+16], %xmm8xmm0
    movapd  %xmm9  movsd   xmm0, %xmm0QWORD PTR [rsp+32]
        movq    xmm1, rax
        call    pow                        ; (3)
    movapd  %xmm0  mov     rax, %xmm7QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+24], xmm0
        pxor    %xmm0xmm0, %xmm0xmm0
    movapd  %xmm6  cvtsi2sd        xmm0, %xmm1rbx
    cvtsi2sdq   %rbx movq    xmm1, %xmm0rax
        call    pow                        ; (4)
        movsd   xmm2, QWORD PTR [rsp+8]
        addsd   %xmm13xmm2, %xmm8QWORD PTR [rsp+16]
        movapd  xmm1, xmm0
        movsd   xmm0, QWORD PTR [rsp+24]
        addsd   %xmm8xmm0, %xmm7xmm2
        ucomisd %xmm0xmm0, %xmm7xmm1
        jp      .L6
        jne     .L6

Even though you might not know assembler, but you can see those four calls to pow. The first thing you need to know is that call is slow compared to those other operations. Those four calls happen in the innermost loop. The compiler removed the call to prop and instead replaced it by its code (that's faster).

See the next section how to get multiplications down.

Lets have a look at your code. Well, not yours, but the assembler the compiler generates. You can use gcc -S -O3. On my platform, this results in the following "hot" section in main:

.L6:
    movapd  %xmm6, %xmm1
    movapd  %xmm10, %xmm0
    call    pow
    movapd  %xmm6, %xmm1
    movapd  %xmm0, %xmm13
    movapd  %xmm11, %xmm0
    call    pow
    movapd  %xmm6, %xmm1
    movapd  %xmm0, %xmm8
    movapd  %xmm9, %xmm0
    call    pow
    movapd  %xmm0, %xmm7
    pxor    %xmm0, %xmm0
    movapd  %xmm6, %xmm1
    cvtsi2sdq   %rbx, %xmm0
    call    pow
    addsd   %xmm13, %xmm8
    addsd   %xmm8, %xmm7
    ucomisd %xmm0, %xmm7

Even though you might not know assembler, but you can see those four calls to pow. The first thing you need to know is that call is slow compared to those other operations. Those four calls happen in the innermost loop. The compiler removed the call to prop and instead replaced it by its code (that's faster).

See the next section how to get multiplications down

Lets have a look at your code. Well, not yours, but the assembler the compiler generates. You can use gcc -S -O3. On my platform, this results in the following "hot" section in main:

.L6:
        add     rbx, 1
        cmp     rbx, 500000
        je      .L18
.L8:
        mov     rax, QWORD PTR .LC0[rip]
        movsd   xmm0, QWORD PTR [rsp+40]
        movq    xmm1, rax
        call    pow                        ; (1)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+8], xmm0
        movsd   xmm0, QWORD PTR [rsp+48]
        movq    xmm1, rax
        call    pow                        ; (2)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+16], xmm0
        movsd   xmm0, QWORD PTR [rsp+32]
        movq    xmm1, rax
        call    pow                        ; (3)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+24], xmm0
        pxor    xmm0, xmm0
        cvtsi2sd        xmm0, rbx
        movq    xmm1, rax
        call    pow                        ; (4)
        movsd   xmm2, QWORD PTR [rsp+8]
        addsd   xmm2, QWORD PTR [rsp+16]
        movapd  xmm1, xmm0
        movsd   xmm0, QWORD PTR [rsp+24]
        addsd   xmm0, xmm2
        ucomisd xmm0, xmm1
        jp      .L6
        jne     .L6

Even though you might not know assembler, you can see those four calls to pow. The first thing you need to know is that call is slow compared to those other operations. Those four calls happen in the innermost loop. The compiler removed the call to prop and instead replaced it by its code (that's faster).

See the next section how to get multiplications down.

better introduction
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89

Note: At some point, this review drifted into the realm of assembler and GMP. An actual review is at the end of this post, whereas the first section discusses the runtime-problems concerning pow, wrong data types and arbitrary large integers.

A study in assemblyNo life time for run time

Would there be any way (on my current machine) to get this to run in my lifetime?

There's a great saying in carpentry: measure twice, cut once. It concerns cutting wood or other material, where you have to throw away your resources if you accidentally cut at the wrong place.

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated assembler to see how many instructions a certain part of your code will take.

Here, we will take the latter route, start with the assembler, take considerations step by step and see where we end up.

A study in assembly

Double trouble

Double trouble

Using proper functions

Using proper functions

Proper bounds and parameter estimation

Proper bounds and parameter estimation

Exercise

Exercise

Remark

Important remark about integer sizes

A study in assembly

Double trouble

Using proper functions

Proper bounds and parameter estimation

Exercise

Remark

Note: At some point, this review drifted into the realm of assembler and GMP. An actual review is at the end of this post, whereas the first section discusses the runtime-problems concerning pow, wrong data types and arbitrary large integers.

No life time for run time

Would there be any way (on my current machine) to get this to run in my lifetime?

There's a great saying in carpentry: measure twice, cut once. It concerns cutting wood or other material, where you have to throw away your resources if you accidentally cut at the wrong place.

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated assembler to see how many instructions a certain part of your code will take.

Here, we will take the latter route, start with the assembler, take considerations step by step and see where we end up.

A study in assembly

Double trouble

Using proper functions

Proper bounds and parameter estimation

Exercise

Important remark about integer sizes

proper bounds for d
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89
Loading
added 5467 characters in body
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89
Loading
remarks on pow4
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89
Loading
added 2149 characters in body
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89
Loading
Source Link
Zeta
  • 19.3k
  • 2
  • 55
  • 89
Loading