Simpe Loop squaring Integer Values is slower in C than in PHP

Question

Yesterday I watched a nice (short) video about a mathematics problem with the number '33'. Link: https://www.youtube.com/watch?v=wymmCdLdPvM

In short: Many numbers can be calculated by: a³ + b³ + c³

For example: 29 = 3³ + 1³ + 1³

(should be mentioned: a, b, c can be negative!)

So, I though I give the problem a short bruteforce try. Nothing sophisticated, just to see how fast I can compute those values.

I built 3 Programs (PHP, Pyhton and C, let's concentrate on PHP and C here), and thats what I've got...

PHP-Program:

#!/usr/bin/php5
<?php

$total = 0;
$aktstamp = time();

for ($a = -100000000000; $a <= 100000000000; $a++) {
    for ($b = -100000000000; $b <= 100000000000; $b++) {
        for ($c = -100000000000; $c <= 100000000000; $c++) {
            $total++;

            if ($a**3+$b**3+$c**3 == 33) {
                echo "FOUND IT! a**3+$b**3+$c**3 a: " . $a . " b: " . $b + " c: " . $c;
            }
            if ((-$a)**3+$b**3+$c**3 == 33) {
                echo "FOUND IT! (-a)**3+$b**3+$c**3 a: " . $a . " b: " . $b + " c: " . $c;
            }                   
            if ($a**3+(-$b)**3+$c**3 == 33) {
                echo "FOUND IT! a**3+(-$b)**3+$c**3 a: " . $a . " b: " . $b + " c: " . $c;
            }                   
            if ($a**3+$b**3+(-$c)**3 == 33) {
                echo "FOUND IT! a**3+$b**3+(-$c)**3 a: " . $a . " b: " . $b + " c: " . $c;
            }                   
            if ((-$a)**3+(-$b)**3+$c**3 == 33) {
                echo "FOUND IT! (-a)**3+(-$b)**3+$c**3 a: " . $a . " b: " . $b + " c: " . $c;
            }                   
            if ((-$a)**3+$b**3+(-$c)**3 == 33) {
                echo "FOUND IT! (-a)**3+$b**3+(-$c)**3 a: " . $a . " b: " . $b + " c: " . $c;
            }                   
            if ($a**3+(-$b)**3+(-$c)**3 == 33) {
                echo "FOUND IT! a**3+(-$b)**3+(-$c)**3 a: " . $a . " b: " . $b + " c: " . $c;  
            }

            if ($total % 10000000 == 0) {
                $timetaken = time() - $aktstamp;
                $calcspersec = 10000000 / $timetaken;

                $date = date("d.m.Y", time());
                $time = date("H:i:s", time());
                echo $date . " " . $time . ": " . $a . "\n";
                echo "(Calcs per sec: " . $calcspersec . ")\n";

                $aktstamp = time();         
            }
        }
    }
}
?>

And a C Program:

/* 
Compile with: 
gcc ./33.c -o 33 -lm -O1
*/

#include <stdio.h>
#include <math.h>
#include <sys/time.h>

long long main(long long argc, char *argv[])
{
    long long total = 0, a = 0, b = 0, c = 0;
    int timetaken, calcspersec;
    int aktstamp = (int)time(NULL);

    for (a = -100000000000; a <= 100000000000; a++) {
        for (b = -100000000000; b <= 100000000000; b++) {
            for (c = -100000000000; c <= 100000000000; c++) {
                total++;

                if (pow(a, 3)+pow(b, 3)+pow(c, 3) == 33) {
                    printf("FOUND IT! pow(a, 3)+pow(b, 3)+pow(c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }
                if (pow(-a, 3)+pow(b, 3)+pow(c, 3) == 33) {
                    printf("FOUND IT! pow(-a, 3)+pow(b, 3)+pow(c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }                   
                if (pow(a, 3)+pow(-b, 3)+pow(c, 3) == 33) {
                    printf("FOUND IT! pow(a, 3)+pow(-b, 3)+pow(c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }                   
                if (pow(a, 3)+pow(b, 3)+pow(-c, 3) == 33) {
                    printf("FOUND IT! pow(a, 3)+pow(b, 3)+pow(-c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }                   
                if (pow(-a, 3)+pow(-b, 3)+pow(c, 3) == 33) {
                    printf("FOUND IT! pow(-a, 3)+pow(-b, 3)+pow(c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }                   
                if (pow(-a, 3)+pow(b, 3)+pow(-c, 3) == 33) {
                    printf("FOUND IT! pow(-a, 3)+pow(b, 3)+pow(-c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }                   
                if (pow(a, 3)+pow(-b, 3)+pow(-c, 3) == 33) {
                    printf("FOUND IT! pow(a, 3)+pow(-b, 3)+pow(-c, 3) a: %lld b: %lld c: %lld\n", a, b, c);
                }

                if (total % 10000000 == 0) {
                    timetaken = (int)time(NULL) - aktstamp;
                    calcspersec = 10000000 / timetaken;

                    printf("%lld\n", a);
                    printf("(Calcs per sec: %u)\n", calcspersec);

                    aktstamp = time(NULL);          
                }
            }
        }
    }
}

Here are the Speeds:

PHP: (Calcs per sec: 2000000)
Python: (Calcs per sec: 1186440)
C: (Calcs per sec: 833333)

It was no suprise to me that PHP was faster than Python. But why on earth is C so much slower than PHP?

Even Python is faster than C...

Do I have a stupid error, or is the C-pow() Function so much slower than PHPs ** ?

So, does anyone see a obvious reason for why C is half as fast as PHP?

An excerpt from http://stackoverflow.com/questions/2940367/what-is-more-efficient-using-pow-to-square-or-just-multiply-it-with-itself `So in C, yes x*x*x will be faster than pow(x, 3), because there is no pow(double, int) overload. ` There is also some benchmark code in the answer you can run yourself to confirm. — Christian Witts, Nov 10 '15 at 09:01
You can also optimise both versions by storing `pow(a,3)` or `$a**3`,etc... in a local variable rather than recalculating them each time. — Alex, Nov 10 '15 at 09:04

score 4 · Accepted Answer · answered Nov 10 '15 at 09:04

4

Probably because with the pow() function you are converting your long long's to double, then calling a function, then converting the resulting double back to long long, which are all unnecessary if you would have written a*a*a.

answered Nov 10 '15 at 09:04

Paul Ogilvie

25,048
4
23
41

score 1 · Answer 2 · answered Nov 10 '15 at 10:35

That was the solution! Using a*a*a instead of pow(a, 3) made the program much faster. I also computed the variables at the beginning of the Loop in all three Program Versions (that was one low hanging fruit, I should have thougth about it, thanks Jaco!).

Here are the speeds now:

PHP: (Calcs per sec: 27.343.750)
Python: (Calcs per sec: 5.636.070)
C: (Calcs per sec: 250.000.000)

Thanks a lot for your help!

Thomas

PS: I will mention all of you if I am solving this mathematics riddle ;-)

Simpe Loop squaring Integer Values is slower in C than in PHP

2 Answers2