I'm new to Mathematica and it was suggested to me to go through the Project Euler problems in order to learn it. However, I can't quite figure out why my solution to #5 is so slow.
The problem:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
My Mathematica solution:
n = 1;
max = Fold[Times, 1, Range[20]];
While[Fold[Plus, 0, Table[Mod[n, x], {x, 20} ]] != 0 And n < max,
Null;
n++
];
Print[n]
This works but takes a long time to finish (to give you an idea I had time to eat supper and it still wasn't done).
For comparison I wrote a close analogue of the above code in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
int main(int argc, char* argv[])
{
std::array<int, 20> divisors;
std::iota(std::begin(divisors), std::end(divisors), 1);
auto isMultipleOf = [&](unsigned long long x)
{
return std::all_of(std::begin(divisors), std::end(divisors), [=](int i) { return (x % i) == 0; });
};
unsigned long long n = 1;
while (!isMultipleOf(n)) { n++; }
std::cout << n << std::endl;
std::cin.get();
return 0;
}
It follows the same structure, a while loop that stops when Modulo returns 0 for each divisor from 1 to 20.
To give you an idea of how much faster this is, I've benchmarked it using nonius with the following setup:
#define NONIUS_RUNNER
#include "Nonius.h++"
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
NONIUS_BENCHMARK("Project Euler #5", [](nonius::chronometer meter)
{
std::vector<unsigned long long> results(meter.runs());
std::array<int, 20> divisors;
std::iota(std::begin(divisors), std::end(divisors), 1);
auto isMultipleOf = [&](unsigned long long x)
{
return std::all_of(std::begin(divisors), std::end(divisors), [=](int i) { return (x % i) == 0; });
};
std::vector<int> storage(meter.runs());
meter.measure([&](int i)
{
unsigned long long n = 1;
while (!isMultipleOf(n)) { n++; }
results[i] = n;
});
})
And these are the results (and in HTML for here):
As you can see, the average is about 5.2s seconds per run. In fact the whole benchmark took less time than one run in Mathematica and I'm really curious as to why.
max
is around 2*10^18, you start withn=1
and increment once per iteration untilmax
is exceeded? If that's what's happening then yes, it will be slow. $\endgroup$