Skip to content

Instantly share code, notes, and snippets.

# antimatter15/README.md

Created August 16, 2021 06:21
Show Gist options
• Save antimatter15/2bf0fcf5b924b4387174d5f84f35277c to your computer and use it in GitHub Desktop.
Arbitrary Base Conversion Algorithm (Javascript)

# Arbitrary Base Conversion Algorithm

This is a function that can convert between arbitrary bases implemented in both Javascript and Python.

Many existing implementations, such as https://rot47.net/base.html or https://gist.github.com/inflammable/2929362 use a number as the internal representation, and thus can't safely encode/decode more than 8 letters of Base64 encoded text, or 9 letters of Base58 text (which isn't enough for parsing a Bitcoin address).

Other implementations rely on complicated third party libraries for bignum (e.g. https://rosettacode.org/wiki/Non-decimal_radices/Convert#JavaScript).

Several implementations required converting to Uint8Arrays (Base 256) as an intermediate. Others were essentially ports of complicated C implementations (see https://github.com/cryptocoinjs/base-x/blob/master/src/index.js).

This implementation works for arbitrary base conversions, such as Binary to Hexadecimal, Octal to Decimal, Binary to Octal, Octal to Hexadecimal, Hexadecimal to Base 36, Ternary to Binary, Ternary to Quadranary, Base 26, Base 32, Base 64, Base 58, Base 57, Base 62, Base 256, Base 512, etc. I believe it should work up until Base 94906265, which should even be enough to encode data into an alphabet consisting of all 1,112,064 valid UTF-8 code points.

Keep in mind that this algorithm is approximately `O(n^2*log(srcb)/log(destb))`. In practice this isn't noticable until you're processing tens of thousands of digits.

There's additionally an implementation here that uses native ES2020 BigInt, which is still ultimately O(n^2) but for larger strings a bit faster than the standard JS implementation.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // arbitrary base conversion function // By Kevin Kwok (antimatter15@gmail.com) // Released under MIT License in 2021 // This implementation only works on JS engines that have // native support for BigInt. Consult https://caniuse.com/bigint // for more up-to-date information. // Requires Edge 2020, Firefox 2019, Chrome 2018, Safari 2021 // or later. function baseConvertBigInt(digits, srcb, destb){ let val = 0n srcb = BigInt(srcb) destb = BigInt(destb) for(let i = 0; i < digits.length; i++){ val = val * srcb + BigInt(digits[i]) } let res = [] while(val !== 0n){ res.unshift(Number(val % destb)) val = val / destb } return res }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // arbitrary base conversion function // By Kevin Kwok (antimatter15@gmail.com) // Released under MIT License in 2021 function baseConvert(digits, srcb, destb) { let start = 0, result = [] while (true) { let carry = 0, done = true for (let i = start; i < digits.length; i++) { let p = srcb * carry + digits[i] digits[i] = Math.floor(p / destb) carry = p % destb if (done) { if (!digits[i]) start = i else done = false } } result.unshift(carry) if (done) return result } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # arbitrary base conversion function # By Kevin Kwok (antimatter15@gmail.com) # Released under MIT License in 2021 def baseConvert(digits, srcb, destb): start = 0 result = [] while True: carry = 0 started = False for i in range(start, len(digits)): pre = srcb * carry + digits[i] divide = pre // destb carry = pre % destb digits[i] = divide if not started: if divide == 0: start = i else: started = True result = [carry] + result if not started: break return result
to join this conversation on GitHub. Already have an account? Sign in to comment