# 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 each arithetic operation (sum/multiplication/division/remainder/exponentation) has the running time of the fastest known algorithm, independent of the implementation that is actually used (This includes methods that you wrote yourself).
   * Addition can be done in linear time
   * Multiplcation/division/remainder run in \$ O(n \cdot \log(n))\$ where \$n\$ is the sum of the numbers of bits of the inputs <sup>*</sup>.
   * Exponentiation \$N^X\$ runs in \$O((n \log x)(\log(n)+\log(\log x)))\$ where \$n\$ and \$x\$ are the numbers of bits in \$N\$ and \$X\$ respectively.
   * If you know faster algorithms please link them in your challenge
* 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]

---

<sup>*</sup>
The \$O(n log (n)) \$ multiplication algorithm assumes that both arguments have the approximately same size, for simplicity you may assume that the same complexity can be archived for arbitrary argument sizes (this may not be true in practice).

---

# Meta

* Is this a duplicate?
* Is there interest in a challenge of this form?
* Is my explanation clear?