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.
History
Date User Action Args
2019-02-19 16:49:13mark.dickinsonsetrecipients: + mark.dickinson, tim.peters, rhettinger, steven.daprano, skrah, pablogsal, lschoe
2019-02-19 16:49:13mark.dickinsonsetmessageid: <1550594953.7.0.118041009846.issue36027@roundup.psfhosted.org>
2019-02-19 16:49:13mark.dickinsonlinkissue36027 messages
2019-02-19 16:49:13mark.dickinsoncreate