Timeline for Alternate algorithms for Chinese remainder theorem
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2022 at 17:28 | comment | added | coolpapa | I suppose if we were in a position to choose the mods ahead of time and just hardcode the inverses, we get to skip all those steps at run-time. But even just comparing addition and multiplication steps, I think it's 2n vs 3n calculations. Fairly insignificant savings at the best of times. Thanks for the help! | |
| Dec 8, 2022 at 21:21 | comment | added | Dror Speiser | @Aurel Once 3 goes to infinity you can't dismiss the subsequent multiplications of the mod a/b/c inverses over mod n as Timothy Chow has, and then you see the complexity is still only a constant away. Not to mention there's a quasi linear version of Euclid's algorithm which is better applied as 3 goes to infinity and used in the OP's idea | |
| Dec 8, 2022 at 16:42 | comment | added | Aurel | @DavidESpeyer It does when $3 \to \infty$, doesn't it? | |
| Dec 8, 2022 at 14:02 | comment | added | David E Speyer | That seems like a reasonable rule of thumb, but I'll point out that $(\log a + \log b + \log c)^2 \leq 3 ((\log a)^2 + (\log b)^2 + (\log c)^2)$, so it won't make a big difference. | |
| Dec 8, 2022 at 13:38 | history | answered | Timothy Chow | CC BY-SA 4.0 |