Re: SquareFreeQ vs. MoebiusMu
- To: mathgroup at smc.vnet.net
- Subject: [mg30164] Re: [mg30144] SquareFreeQ vs. MoebiusMu
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Wed, 1 Aug 2001 02:19:19 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
But the whole point of my reply was that your numbers are far too
small! SquareFreeQ uses elliptic curves so it performs well only for
huge numbers. I do not really know whether it is established which of
these methods is faster "in the long run", but for very large numbers
sometimes one and sometimes the other function appears to be faster,
with MoebiusMu generally having a slight edge. In any case, MoebiusMu
is certainly not (for very large numbers!) thousands, or even tens of
times faster. Here is, for example, a case where SquareFreeQ is slightly
faster ( on my machine anyway):
In[43]:=
SquareFreeQ[2^201-1]//Timing
Out[43]=
{1.22 Second,True}
In[44]:=
MoebiusMu[2^201-1]//Timing
Out[44]=
{1.25 Second,1}
I believe that it is included mainly for theoretical reasons (because of
the method it uses) and perhaps because there may be cases where it is
significantly faster than MoebiusMu and it may be useful to have a
choice.
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
On Tuesday, July 31, 2001, at 10:38 PM, Harvey P. Dale wrote:
> Andrzej:
> Try to use the functions across a list. Here's what I got (Pentium
> 3 at 733 mHz under Windows 2000):
> Select[Range[1000], SquareFreeQ]; // Timing
> {8.442 Second, Null}
> Select[Range[1000], MoebiusMu[#] != 0 &]; // Timing
> {0.01 Second, Null}
> Best,
> Harvey
>
> -----Original Message-----
> From: Andrzej Kozlowski [mailto:andrzej at tuins.ac.jp]
To: mathgroup at smc.vnet.net
> Sent: Tuesday, July 31, 2001 5:35 AM
> To: Harvey P. Dale
> Cc: mathgroup at smc.vnet.net
> Subject: Re: [mg30144] SquareFreeQ vs. MoebiusMu
>
> Several thousand times as fast???
> Not on my computer:
>
> In[1]:=
> <<NumberTheory`NumberTheoryFunctions`
>
> In[4]:=
> SquareFreeQ[2^101-1]//Timing
>
> Out[4]=
> {19.98 Second,True}
>
> In[5]:=
> MoebiusMu[2^101-1]//Timing
>
> Out[5]=
> {19.65 Second,1}
>
> On Tuesday, July 31, 2001, at 05:27 PM, Harvey P. Dale wrote:
>
>> The function SquareFreeQ[n], in NumberTheory`NumberTheoryFunctions`,
>> appears
>> to do the same thing as testing for MoebiusMu[n] being unequal to
>> zero. The
>> latter, however, is several thousand times as fast. Is there ever any
>> reason for using SquareFreeQ? If not, why is it included in the
>> standard
>> Add-On package?
>> I should add that at page 317 of the Mathematica 4 Standard Add-On
>> Packages volume, SquareFreeQ is erroneously described. It says the
>> function will give True if n contains a squared factor, False
>> otherwise.
>> That is exactly backwards.
>> Best,
>> Harvey
>>
>>
>> _____________________________________________________________________
>> This message has been checked for all known viruses by the
>> MessageLabs Virus Scanning Service. For further information visit
>> http://www.messagelabs.com/stats.asp
>>
>>
>>
>
> _____________________________________________________________________
> This message has been checked for all known viruses by the
> MessageLabs Virus Scanning Service. For further information visit
> http://www.messagelabs.com/stats.asp
>
>