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