Message 335976 - Python tracker

Message335976

Author	mark.dickinson
Recipients	lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date	2019-02-19.16:49:13
SpamBayes Score	-1.0
Marked as misclassified	Yes
Message-id	<1550594953.7.0.118041009846.issue36027@roundup.psfhosted.org>
In-reply-to

Content
> Then, it should be considerably faster Why would you expect that? Both algorithms involve a number of (bigint) operations that's proportional to log(p), so it's going to be down to the constants involved and the running times of the individual operations. Is there a clear reason for your expectation that the xgcd-based algorithm should be faster? Remember that Python has a subquadratic multiplication (via Karatsuba), but its division algorithm has quadratic running time.

Content

> Then, it should be considerably faster

Why would you expect that? Both algorithms involve a number of (bigint) operations that's proportional to log(p), so it's going to be down to the constants involved and the running times of the individual operations. Is there a clear reason for your expectation that the xgcd-based algorithm should be faster?

Remember that Python has a subquadratic multiplication (via Karatsuba), but its division algorithm has quadratic running time.

History
Date	User	Action	Args
2019-02-19 16:49:13	mark.dickinson	set	recipients: + mark.dickinson, tim.peters, rhettinger, steven.daprano, skrah, pablogsal, lschoe
2019-02-19 16:49:13	mark.dickinson	set	messageid: <1550594953.7.0.118041009846.issue36027@roundup.psfhosted.org>
2019-02-19 16:49:13	mark.dickinson	link	issue36027 messages
2019-02-19 16:49:13	mark.dickinson	create