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
  • Exponentiation \$n^x\$ runs in \$O((n \log x)(\log(n)+\log(\log x)))\$
  • 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)

code-golf restricted-complexity

Meta

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

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 ^*.
  • 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)

code-golf restricted-complexity

^* 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?

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 runs in \$ O(n \cdot \log(n))\$ where \$n\$ is the sum of the numbers of bits of the inputs (This includes methods that you wrote yourself)
• 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)

code-golf restricted-complexity

Meta

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

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
  • Exponentiation \$n^x\$ runs in \$O((n \log x)(\log(n)+\log(\log x)))\$
  • 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)

code-golf restricted-complexity

Meta

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

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)

code-golf restricted-complexity

Meta

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

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 runs in \$ O(n \cdot \log(n))\$ where \$n\$ is the sum of the numbers of bits of the inputs (This includes methods that you wrote yourself)
• 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)

code-golf restricted-complexity

Meta

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