What is the fastest possible square number test in Mathematica 7, both for machine size and big integers?
I presume in version 8 the fastest will be a dedicated C LibraryLink function.
I don't think there are any built-in functions for this but the following is probably fast enough for most purposes.
Does 1 million integers in under a second.
This is under 2 orders of magnitude faster than the un-compiled equivalent, by the way.
I am not sure how to speed up each comparison (as in, I spent half an hour trying different things and didn't manage to), but making the compiled function listable speeds things up quite a bit.
and then compare:
ie, it's 3-4 times faster.
What makes you say
Sorry for my ignorance not taking into account that the question specifically asked for a Mathematica 7 solution. I updated the complete post.
In Mathematica 7 we don't have the option the compile code into a C-library which includes the thread parallelization which can be turned on when using
This leaves the possibility to not compile the used function and make it a normal Mathematica function where you can set the attribute Listable. I tried this, but it was horrible slow.
After a bit of research I found a nice solution which uses some number-properties in base 16. Since (at least in V7) it seems somewhat hard to return lists of True|False, I use 0 and 1 where 0 means no square.
Comparing this with the almost one-liner of Sal gives
I leave it to you to decide whether such a C-like programming style is worth the small speed up.
The fastest way (using Mathematica only) I know is to compile a C-library and process all data in parallel. Since most computers these days have at least 2 cores, this gives a boost. In Mathematica 8 the compilation to a C-library does not copy the data when it is called.
To make the computation parallel you have to use the Parallization option and the compiled function must be Listable. If you are sure of your input-data, you can additionally switch off most of the data-checks by using RuntimeOptions set to "Speed".
Update I include here the parallelized version of the Mathematica 7 code above:
The results here come from my MacBook in battery-save mode which has 2 Intel cores. The disadvantage is that you need a C-compiler installed on your system which is most likely not true for the majority of Mathematica users.
|show 1 more comment|
I voted for all three previous answer because they all taught me something. However they, being
At least on my system, Sal Mangano's code appears reducible to this without loss of speed:
For big integers between about 2*10^9 and 2*10^11 I am currently using this code from Sasha:
For integers larger than that I am using code (modified) from Daniel Lichtblau:
|show 3 more comments|
More info as requested by @Mr.Wizard.
For $n$ below the $\approx 2*10^9$ limit, Compile gives the fastest solutions. For larger $n$, Sasha used