D slower ~1s from C ?!
Minas
minas_mina1990 at hotmail.co.uk
Thu Apr 5 10:22:37 PDT 2012
Many of you should know the website "projecteuler.net", where
there are mathematical problems to solve with computers.
I am doing those in D, and after I finished one today, I decided
to compile it in C as well to compare the results.
The problem was:
"The number 3797 has an interesting property. Being prime itself,
it is possible to continuously remove digits from left to right,
and remain prime at each stage: 3797, 797, 97, and 7. Similarly
we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable
from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes."
My solution in D:
[source]
import std.stdio;
import std.math;
import std.conv;
void main()
{
int count, i = 10, sum;
while( count < 11 )
{
if( isPrime(i) && isPrimeRightToLeft(i) &&
isPrimeLeftToRight(i) )
{
//writeln(i);
++count;
sum += i;
}
++i;
}
writeln(sum);
}
/// returns true if n is a prime number
bool isPrime(ulong n)
{
n = abs(n);
// 0 and 1 aren't primes
if( n < 2 ) return false;
if( n % 2 == 0 && n != 2)
return false; // an even number can't be a prime (except 2)
// check only if it's odd
for(ulong i = 2; i <= cast (ulong)sqrt(cast(double)n+1); ++i)
if( n % i == 0 )
return false;
return true;
}
/**
* returns true if n is a prime* truncatable from right to left.
* Note: n must have been tested to be prime with a separate
function
*/
bool isPrimeRightToLeft(ulong n)
{
if( n < 10 )
return false;
n /= 10; // assuming that n has already been tested to be prime,
we can skip checking it
while( n > 0 )
{
if( !isPrime(n) )
return false;
n /= 10;
}
return true;
}
/**
* returns true if n is a prime* truncatable from left to right.
* Note: n must have been tested to be prime with a separate
function
*/
bool isPrimeLeftToRight(ulong n)
{
if( n < 10 )
return false;
ulong power = cast(ulong)pow(10, cast(ulong)log10(n));
ulong firstDigit = n / power;
n -= firstDigit * power;
while( n > 0 )
{
if( !isPrime(n) )
return false;
power = cast(ulong)pow(10, cast(ulong)log10(n));
firstDigit = n / power;
n -= firstDigit * power;
}
return true;
}
[/source]
In C:
[source]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef unsigned long ulong;
int isPrime(ulong n);
int isPrimeRightToLeft(ulong n);
int isPrimeLeftToRight(ulong n);
int main()
{
int count = 0, i = 10, sum = 0;
while( count < 11 )
{
if( isPrime(i) && isPrimeRightToLeft(i) &&
isPrimeLeftToRight(i) )
{
//writeln(i);
++count;
sum += i;
}
++i;
}
printf("%d\n", sum);
return 0;
}
/// returns true if n is a prime number
int isPrime(ulong n)
{
n = abs(n);
// 0 and 1 aren't primes
if( n < 2 ) return 0;
if( n % 2 == 0 && n != 2)
return 0; // an even number can't be a prime (except 2)
// check only if it's odd
for(ulong i = 2; i <= (ulong)sqrt((double)n+1); ++i)
if( n % i == 0 )
return 0;
return 1;
}
/**
* returns 1 if n is a prime* truncatable from right to left.
* Note: n must have been tested to be prime with a separate
function
*/
int isPrimeRightToLeft(ulong n)
{
if( n < 10 )
return 0;
n /= 10; // assuming that n has already been tested to be prime,
we can skip checking it
while( n > 0 )
{
if( !isPrime(n) )
return 0;
n /= 10;
}
return 1;
}
/**
* returns 1 if n is a prime* truncatable from left to right.
* Note: n must have been tested to be prime with a separate
function
*/
int isPrimeLeftToRight(ulong n)
{
if( n < 10 )
return 0;
ulong power = (ulong)pow(10, (ulong)log10(n));
ulong firstDigit = n / power;
n -= firstDigit * power;
while( n > 0 )
{
if( !isPrime(n) )
return 0;
power = (ulong)pow(10, (ulong)log10(n));
firstDigit = n / power;
n -= firstDigit * power;
}
return 1;
}
[/source]
And this is the time execution of the programs:
In D:
real 0m1.648s
user 0m1.644s
sys 0m0.000s
In C:
real 0m0.766s
user 0m0.760s
sys 0m0.000s
There's quite a big difference here. Is that normal or is there
something wrong? (Maybe a bug?)
* C source file was compiled as "gcc euler37.c -o euler37 -lm
-std=c99 -O5
D source file was compiled as "dmd euler37.d -O -release"
** In gcc as well in dmd sizeof(ulong) == 8
More information about the Digitalmars-d-learn
mailing list