PARI/GP Bug report logs - #1305
gp core() function: could do better?

Full log

🔗 View this message in rfc822 format

X-Loop: allomber@math.u-bordeaux.fr
From: allomber@math.u-bordeaux.fr (PARI/GP Bug Tracking System)
To: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Cc: Karim.Belabas@math.u-bordeaux.fr
Subject: Bug#1305: marked as done (gp core() function: could do better?)
Message-ID: <handler.1305.D1305.133711604014023.ackdone@pari.math.u-bordeaux.fr>
In-Reply-To: <20120515210713.GA13972@math.u-bordeaux1.fr>
References: <20120515210713.GA13972@math.u-bordeaux1.fr> <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
Precedence: bulk
X-PARI/GP-PR-Message: closed 1305
X-PARI/GP-PR-Package: pari-stable
X-PARI/GP-PR-Keywords: 

Your message dated Tue, 15 May 2012 23:07:13 +0200
with message-id <20120515210713.GA13972@math.u-bordeaux1.fr>
and subject line Bug#1305: gp core() function: could do better?
has caused the attached Bug report to be marked as done.

This means that you claim that the problem has been dealt with.
If this is not the case it is now your responsibility to reopen the
Bug report if necessary, and/or fix the problem forthwith.

(NB: If you are a system administrator and have no idea what I am
talking about this indicates a serious mail system misconfiguration
somewhere.  Please contact me immediately.)

Bill Allombert
(administrator, PARI/GP bugs database)

--------------------------------------
Received: (at submit) by pari.math.u-bordeaux.fr; 19 Mar 2012 11:08:31 +0000
From k.buzzard@imperial.ac.uk Mon Mar 19 12:08:31 2012
Received: from smtp2.cc.ic.ac.uk ([155.198.5.156])
	by pari.math.u-bordeaux1.fr with esmtp (Exim 4.72)
	(envelope-from <k.buzzard@imperial.ac.uk>)
	id 1S9aRz-0001HY-39
	for submit@pari.math.u-bordeaux.fr; Mon, 19 Mar 2012 12:08:31 +0100
Received: from crackerjack.ma.ic.ac.uk ([155.198.192.80])
	by smtp2.cc.ic.ac.uk with esmtpsa (TLSv1:AES256-SHA:256)
	(Exim 4.77)
	(envelope-from <k.buzzard@imperial.ac.uk>)
	id 1S9aRt-0000Wn-KL
	for submit@pari.math.u-bordeaux.fr; Mon, 19 Mar 2012 11:08:25 +0000
Date: Mon, 19 Mar 2012 11:08:16 +0000 (GMT)
From: Kevin Buzzard <k.buzzard@imperial.ac.uk>
X-X-Sender: buzzard@crackerjack.ma.ic.ac.uk
Reply-To: Kevin Buzzard <k.buzzard@imperial.ac.uk>
To: submit@pari.math.u-bordeaux.fr
Subject: gp core() function: could do better?
Message-ID: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-IC-MsgID: 1S9aRt-0000Wn-KL

Package: pari-stable
Version: 2.5.0

[Sorry -- I should upgrade to 2.5.1, but I didn't yet, and I don't see 
core mentioned in the changelog 2.5.0->2.5.1 so let me gamble that this 
is still an issue]

What do you think of this?

(11:00) gp > isprime(10^1000+1)
%1 = 0
(11:00) gp > core(5*(10^1000+1)^2)
[gp now goes into a very long loop, presumably because it's trying to 
factor (10^1000+1)^2?]

I am not C++-savvy enough to know what the "core" function was doing in 
2.5.0, but in this particular case I can see a relatively simple way of spotting the 
answer: if we use trial division or ECM or whatever to find a few small 
factors, then could it be worth checking to see if what we have left is a 
square?? If it is then we're done. Presumably core() is not currently 
doing this...

Kevin

---------------------------------------
Received: (at 1305-close) by pari.math.u-bordeaux.fr; 15 May 2012 21:07:20 +0000
From Karim.Belabas@math.u-bordeaux1.fr Tue May 15 23:07:20 2012
Received: from smail.math.u-bordeaux1.fr ([147.210.16.22])
	by pari.math.u-bordeaux1.fr with esmtp (Exim 4.72)
	(envelope-from <Karim.Belabas@math.u-bordeaux1.fr>)
	id 1SUOxk-0003e8-Ci
	for 1305-close@pari.math.u-bordeaux.fr; Tue, 15 May 2012 23:07:20 +0200
Received: from localhost (localhost.localdomain [127.0.0.1])
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id 5D1D370C7E
	for <1305-close@pari.math.u-bordeaux.fr>; Tue, 15 May 2012 23:07:15 +0200 (CEST)
X-Virus-Scanned: amavisd-new at math.u-bordeaux1.fr
X-Spam-Flag: NO
X-Spam-Score: 0.811
X-Spam-Level: 
X-Spam-Status: No, score=0.811 required=6 tests=[BAYES_50=0.8,
	RCVD_IN_SORBS_DUL=0.001, RDNS_DYNAMIC=0.01] autolearn=disabled
Received: from smail.math.u-bordeaux1.fr ([127.0.0.1])
	by localhost (smail.math.u-bordeaux1.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id 4PtRHOZdcyvA; Tue, 15 May 2012 23:07:14 +0200 (CEST)
Received: from colibri.math.u-bordeaux1.fr (tal33-1-82-226-197-154.fbx.proxad.net [82.226.197.154])
	(using TLSv1 with cipher AES256-SHA (256/256 bits))
	(No client certificate requested)
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id 7F7407079D;
	Tue, 15 May 2012 23:07:14 +0200 (CEST)
Received: from kb by colibri.math.u-bordeaux1.fr with local (Exim 4.77)
	(envelope-from <Karim.Belabas@math.u-bordeaux1.fr>)
	id 1SUOxd-0003do-El; Tue, 15 May 2012 23:07:13 +0200
Date: Tue, 15 May 2012 23:07:13 +0200
From: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
To: Kevin Buzzard <k.buzzard@imperial.ac.uk>,
	1305-close@pari.math.u-bordeaux.fr
Subject: Re: Bug#1305: gp core() function: could do better?
Message-ID: <20120515210713.GA13972@math.u-bordeaux1.fr>
References: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
 <20120319121716.GA18235@math.u-bordeaux1.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
In-Reply-To: <20120319121716.GA18235@math.u-bordeaux1.fr>
User-Agent: Mutt/1.5.21 (2010-09-15)
Content-Transfer-Encoding: quoted-printable

* Karim Belabas [2012-03-19 13:17]:
> Hi Kevin,
>=20
> * Kevin Buzzard [2012-03-19 12:37]:
> > [Sorry -- I should upgrade to 2.5.1, but I didn't yet, and I don't
> > see core mentioned in the changelog 2.5.0->2.5.1 so let me gamble
> > that this is still an issue]
> >=20
> > What do you think of this?
>=20
> No good :-)
>=20
> > (11:00) gp > isprime(10^1000+1)
> > %1 =3D 0
> > (11:00) gp > core(5*(10^1000+1)^2)
> > [gp now goes into a very long loop, presumably because it's trying
> > to factor (10^1000+1)^2?]
>=20
> Trying to factor 10^1000 + 1, rather.
>=20
> > I am not C++-savvy enough to know what the "core" function was doing
> > in 2.5.0, but in this particular case I can see a relatively simple
> > way of spotting the answer: if we use trial division or ECM or
> > whatever to find a few small factors, then could it be worth
> > checking to see if what we have left is a square?? If it is then
> > we're done. Presumably core() is not currently doing this...
>=20
> Currently core(n) is implemented via=20
>=20
>   F =3D factor(n);
>   weed_out_stuff_from(F);
>=20
> which is sub=ADoptimal for your example, even if factor() is trying to =
be
> clever.
>=20
> I'll try to come up with a nice generic implementation (as opposed to a
> quick hack starting from a full copy of the factoring engine + minor
> tweakings to hunt for square factors).

Done in master (testing branch 2.6.*)

(23:06) gp > core(5*(10^1000+1)^2)
time =3D 36 ms.
%1 =3D 5

Thanks for your feedback !


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

Send a report that this bug log contains spam.