Am Thu, 05 Apr 2012 19:22:37 +0200
schrieb "Minas" <[email protected]>:
> 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 first rule or PE: You don't talk about PE in the public. You accidentally
posted a solution to a problem in the public. Now people can solve the task,
using a search engine. And after solving the problem, get access to other
language implementations. Some employers even use problems from there to assess
new programmers. And believe me, you wouldn't want a co-worker that cheated on
PE to get the job ;).
Anyway like others suggested, I use GDC to get the most out of D and I actually
like the challenge of staying under 50ms for every problem I solve. (My Friend
Key is 58749952297599_fa95cc8e61e8df1206f1144436ac050f)
Admittedly my first solutions aren't always fast. Often I just solve the
problem and then look into the forum for how to make it _fast_. After a while I
think, I should have a nice library of very fast helper functions.
My personal favorite is a small struct that can be used to iterate along rows
or diagonals of Pascal's triangle:
---------------------
alias size_t ℕ;
/**
* The ultimate tool to move around in Pascal's triangle. Pascal(0, 0) is the
* top of the triangle with the value of 1.
*/
struct Pascal
{
this(ℕ n, ℕ k) {
// internally we offset these by +1, to simplify the math
++n; ++k;
_n = n;
if (k > n / 2) {
_k = _n;
left(_n - k);
} else {
right(k - 1);
}
}
ℕ left(ℕ amount) {
while (amount--) {
_value *= --_k;
_value /= _n - _k;
}
return _value;
}
ℕ right(ℕ amount) {
while (amount--) {
_value *= _n - _k;
_value /= _k++;
}
return _value;
}
ℕ rightDown(ℕ amount) {
while (amount--) {
_value *= _n++;
_value /= _k++;
}
return _value;
}
ℕ leftDown(ℕ amount) {
while (amount--) {
_value *= _n++;
_value /= _n - _k;
}
return _value;
}
ℕ leftUp(ℕ amount) {
while (amount--) {
_value *= --_k;
_value /= --_n;
}
return _value;
}
ℕ rightUp(ℕ amount) {
while (amount--) {
_value *= _n - _k;
_value /= --_n;
}
return _value;
}
@property
ℕ value() { return _value; }
alias value this;
private:
ℕ _n = 1, _k = 1;
ℕ _value = 1;
}
-------------------------
I use it like this for combinatorics calculations (n over k), where a naive
approach would recalculate that Pascal's triangle value at the required
position over and over again:
ℕ[] permut_per_variation = new ℕ[variations];
Pascal pascal = Pascal(_2 + _3, _3);
foreach (v; 0..variations)
{
permut += permut_per_variation[v] = pascal;
pascal.leftDown(1);
pascal.left(2);
}
Still some functional programmers keep mocking me for my lines of code count.
And I tend to agree now and then (some FP solutions are _really_ short). With
these fun tasks it is more a matter of personality though. I prefer fast over
concise code. Some participants even use ASM... maybe they like it really close
to the metal. In any case it is good to know how C/D code maps to machine code,
e.g. what is efficient and what not, so you don't misuse real instead of int.
Looking at your code I noticed the following:
*) writeln() is ok, but doesn't flush (e.g. missing output when a program
is halted in a debugger or crashes)
You can use stdout.writeln() when you need the output on the screen as
soon as the line is executed
*) n = abs(n); // <- don't need this, you already declared n as unsigned
*) if( n % 2 ...)
Just in case someone wonders, GCC/GDC replaces the modulo with faster
code. There is no need to write n & 1, which is a bit more cryptic.
*) for(ulong i = 2; i <= cast (ulong)sqrt(cast(double)n+1); ++i)
can be written as:
foreach (i; 2 .. cast(ulong)sqrt(n)+1)
Foreach only computes start and end once and 'i' will be ulong thanks
to the cast!
*) ulong power = cast(ulong)pow(10, cast(ulong)log10(n));
can alternatively be written as:
ulong power = 10 ^^ cast(ulong)log10(n);
*) In the following while loop, you can replace
power = cast(ulong)pow(10, cast(ulong)log10(n));
with
power /= 10;
But really, only the isPrime() function is taking up time in this code. This is
a short and fast version with GDC 64bit, but a different algorithm would help
more:
bool isPrime(ulong n)
{
// 0 and 1 aren't primes
if( n < 2 ) return false;
for( ulong i = 2; n / i >= i; ++i )
if( n % i == 0 )
return false;
return true;
}
When / and % are used close to each other, they are handled in one CPU
instruction. So you can avoid floating point math altogether.
--
Marco
