Message335987
> 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. |
|
Date |
User |
Action |
Args |
2019-02-19 17:24:32 | lschoe | set | recipients:
+ lschoe, tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal |
2019-02-19 17:24:32 | lschoe | set | messageid: <1550597072.4.0.852159328905.issue36027@roundup.psfhosted.org> |
2019-02-19 17:24:32 | lschoe | link | issue36027 messages |
2019-02-19 17:24:32 | lschoe | create | |
|