4 ms·
Why is base 10 string -> int a quadratic algorithm? Are there no faster ones that could be implemented?
by ridiculous_fish 4y ago
Why is base 10 string -> int a quadratic algorithm? Are there no faster ones that could be implemented?
- blahedo 4y agoNo, because 10 is not a power of 2, so any digit in the source (base 10) can affect any digit in the result (base 2). Converting from e.g. base 16 to base 2 is linear, because 16 is a power of 2.
- krick 4y agoThis simply isn't true. Faster algorithm is even linked in comments to this particular issue: https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf (p.38)
- blahedo 4y agoMy mistake! I knew it couldn't be linear and got sloppy. (For those checking that link, see p38, section 1.7.2)
- adgjlsfhk1 4y agoThe best algorithm isn't quadratic. It's M(n)log(n) where M(n) is the cost of your integer multiply (M(n) theoretically be as low as nlog(n), but in practice the best algorithms used are nlog(n)log(log(n))). Python just didn't bother to implement them.