# Sub-quadratic base conversion Write a program that converts a positive integer given in base 10 to its base 2 representation. Your algorithm must run in a complexity lower that \$O(n^2)\$ ## Rules * You can assume that multiplication/division/remainder of two integers run in \$ O(n \cdot \log(n))\$ where \$n\$ is the sum of the numbers of bits of the inputs * All built-in base-conversion/library methods for base-conversion are assumed to run in quadratic time in the input, even if the actual implementation is faster * _(... more rules will follow)_ [tag:code-golf] [tag:restricted-complexity] --- # Meta * Is this a duplicate? * Is there interest in a challenge of this form? * Is my explanation clear?