Reply to post: Re: On speed

Rust marks five years since its 1.0 release: The long and winding road actually works

GrumpenKraut Silver badge

Re: On speed

> long division algorithm

Long division is O(n^2), Newton iteration with FFT-multiplication is roughly O(n*log(n)). Contrary to folklore the overhead for the latter is not anymore big. With 10k-digit numbers just forget about any O(n^2) algorithms!

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2021