Author lschoe
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-19.17:24:32
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550597072.4.0.852159328905.issue36027@roundup.psfhosted.org>
In-reply-to
Content
> Is there a clear reason for your expectation that the xgcd-based algorithm should be faster?

Yeah, good question. Maybe I'm assuming too much, like assuming that it should be faster;) It may depend a lot on the constants indeed, but ultimately the xgcd style should prevail.

So the pow-based algorithm needs to do log(p) full-size muls, plus log(p) modular reductions. Karatsuba helps a bit to speed up the muls, but as far as I know it only kicks in for quite sizeable inputs. I forgot how Python is dealing with the modular reductions, but presumably that's done without divisions.

The xgcd-based algorithm needs to do a division per iteration, but the numbers are getting smaller over the course of the algorithm. And, the worst-case behavior occurs for things involving Fibonacci numbers only. In any case, the overall bit complexity is quadratic, even if division is quadratic. There may be a few expensive divisions along the way, but these also reduce the numbers a lot in size, which leads to good amortized complexity for each iteration.
History
Date User Action Args
2019-02-19 17:24:32lschoesetrecipients: + lschoe, tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal
2019-02-19 17:24:32lschoesetmessageid: <1550597072.4.0.852159328905.issue36027@roundup.psfhosted.org>
2019-02-19 17:24:32lschoelinkissue36027 messages
2019-02-19 17:24:32lschoecreate