D slower ~1s from C ?!

q66 quaker66 at gmail.com
Thu Apr 5 10:24:33 PDT 2012


On Thursday, 5 April 2012 at 17:22:38 UTC, Minas wrote:
> 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

My guess would be still worse optimization capabilities of dmd. 
Try with gdc and see.


More information about the Digitalmars-d-learn mailing list