Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>
>



  • Prev by Date: Re: Lists and speed
  • Next by Date: RE: Lost Line Directives in 3D Graphics
  • Previous by thread: RE: SquareFreeQ vs. MoebiusMu
  • Next by thread: Re: ListCorrelate[] ??