Chris De Corte on Fri, 20 Feb 2015 04:21:23 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: moebius function


Hi,

I am doing tests on the moebius.
It went well for a few days until tonight when It gave an error.
A printscreen is attached.
What is the problem?
Is the m on the screen reliable?

By the way: when I want to make a list. how do I send my output to a file in pari/gp?

Thanks for your answer,
Chris


From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
To: Chris De Corte <chrisdecorte@yahoo.com>
Cc: pari-dev@pari.math.u-bordeaux.fr
Sent: Tuesday, February 17, 2015 8:42 AM
Subject: Re: moebius function

* Chris De Corte [2015-02-17 04:34]:
> Your moebius function seems to do calculations for very high
> figures.But your prime function seems to only go for low figures.

prime(n) uses a naive O~(n) algorithm (see ??prime), whereas moebius() calls
factor / factorint which use subexponential algorithms in exp O~(log n)^(1/2).




> Is your moebius then reliable?


It is to the extent factor() is: there is a remote possibility  that a
composite > 2^64 is incorrectly considered as prime (??factor).
[No example is known at present]

Use

  default(factor_proven, 1)

to get rid of this possibility (or set factor_proven = 1 in your gprc).
This will slow down a little the arithmetic kernel, but it may be
tolerable, or even negligible, in your application ( at worst
O(log n)^logloglog(n) extra cost when needing to factor the integer n )

In any case, moebius() will remain much faster than prime() :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux        Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)      http://pari.math.u-bordeaux.fr/ [PARI/GP]

`


Attachment: paricalc6.jpg
Description: JPEG image