Fastest way to convert a number to radix 64 in JavaScript?
JavascriptJavascript Problem Overview
In JavaScript you can convert a number to a string representation with a specific radix as follows:
(12345).toString(36) // "9ix"
...and you can convert it back to a regular number like this:
parseInt("9ix", 36) // 12345
36 is the highest radix you can specify. It apparently uses the characters 0-9 and a-z for the digits (36 total).
My question: what's the fastest way to convert a number to a base 64 representation (for example, using A-Z, and - and _ for the extra 28 digits)?
Update: Four people have posted responses saying this question is duplicated, or that I'm looking for Base64. I'm not.
"Base64" is a way of encoding binary data in a simple ASCII character set, to make it safe for transfer over networks etc. (so that text-only systems won't garble the binary).
That's not what I'm asking about. I'm asking about converting numbers to a radix 64 string representation. (JavaScript's toString(radix) does this automatically for any radix up to 36; I need a custom function to get radix 64.)
Update 2: Here are some input & output examples...
0 → "0"
1 → "1"
9 → "9"
10 → "a"
35 → "z"
61 → "Z"
62 → "-"
63 → "_"
64 → "10"
65 → "11"
128 → "20"
etc.
Javascript Solutions
Solution 1 - Javascript
Here is a sketch for a solution for NUMBERS (not arrays of bytes :)
only for positive numbers, ignores fractional parts, and not really tested -- just a sketch!
Base64 = {
_Rixits :
// 0 8 16 24 32 40 48 56 63
// v v v v v v v v v
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/",
// You have the freedom, here, to choose the glyphs you want for
// representing your base-64 numbers. The ASCII encoding guys usually
// choose a set of glyphs beginning with ABCD..., but, looking at
// your update #2, I deduce that you want glyphs beginning with
// 0123..., which is a fine choice and aligns the first ten numbers
// in base 64 with the first ten numbers in decimal.
// This cannot handle negative numbers and only works on the
// integer part, discarding the fractional part.
// Doing better means deciding on whether you're just representing
// the subset of javascript numbers of twos-complement 32-bit integers
// or going with base-64 representations for the bit pattern of the
// underlying IEEE floating-point number, or representing the mantissae
// and exponents separately, or some other possibility. For now, bail
fromNumber : function(number) {
if (isNaN(Number(number)) || number === null ||
number === Number.POSITIVE_INFINITY)
throw "The input is not valid";
if (number < 0)
throw "Can't represent negative numbers now";
var rixit; // like 'digit', only in some non-decimal radix
var residual = Math.floor(number);
var result = '';
while (true) {
rixit = residual % 64
// console.log("rixit : " + rixit);
// console.log("result before : " + result);
result = this._Rixits.charAt(rixit) + result;
// console.log("result after : " + result);
// console.log("residual before : " + residual);
residual = Math.floor(residual / 64);
// console.log("residual after : " + residual);
if (residual == 0)
break;
}
return result;
},
toNumber : function(rixits) {
var result = 0;
// console.log("rixits : " + rixits);
// console.log("rixits.split('') : " + rixits.split(''));
rixits = rixits.split('');
for (var e = 0; e < rixits.length; e++) {
// console.log("_Rixits.indexOf(" + rixits[e] + ") : " +
// this._Rixits.indexOf(rixits[e]));
// console.log("result before : " + result);
result = (result * 64) + this._Rixits.indexOf(rixits[e]);
// console.log("result after : " + result);
}
return result;
}
}
UPDATE: Here's some (very lightweight) testing of the above, for running in NodeJs where you have console.log.
function testBase64(x) {
console.log("My number is " + x);
var g = Base64.fromNumber(x);
console.log("My base-64 representation is " + g);
var h = Base64.toNumber(g);
console.log("Returning from base-64, I get " + h);
if (h !== Math.floor(x))
throw "TEST FAILED";
}
testBase64(0);
try {
testBase64(-1);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
try {
testBase64(undefined);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
try {
testBase64(null);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
try {
testBase64(Number.NaN);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
try {
testBase64(Number.POSITIVE_INFINITY);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
try {
testBase64(Number.NEGATIVE_INFINITY);
}
catch (err) {
console.log("caught >>>>>> " + err);
}
for(i=0; i<100; i++)
testBase64(Math.random()*1e14);
Solution 2 - Javascript
Here's a version just for 32 bit ints, that is, any number between -2147483648 and 2147483647 (inclusive).
I modified the version in the top answer by Reb Cabin. This should be quite a bit faster because it uses bit operations and lookup tables.
Base64 = (function () {
var digitsStr =
// 0 8 16 24 32 40 48 56 63
// v v v v v v v v v
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+-";
var digits = digitsStr.split('');
var digitsMap = {};
for (var i = 0; i < digits.length; i++) {
digitsMap[digits[i]] = i;
}
return {
fromInt: function(int32) {
var result = '';
while (true) {
result = digits[int32 & 0x3f] + result;
int32 >>>= 6;
if (int32 === 0)
break;
}
return result;
},
toInt: function(digitsStr) {
var result = 0;
var digits = digitsStr.split('');
for (var i = 0; i < digits.length; i++) {
result = (result << 6) + digitsMap[digits[i]];
}
return result;
}
};
})();
For example,
Base64.fromInt(-2147483648); // gives "200000"
Base64.toInt("200000"); // gives -2147483648
Solution 3 - Javascript
I think this question is missing a short solution.
const digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";
toB64 = x=>x.toString(2).split(/(?=(?:.{6})+(?!.))/g).map(v=>digit[parseInt(v,2)]).join("")
fromB64 = x=>x.split("").reduce((s,v,i)=>s=s*64+digit.indexOf(v),0)
Works for all integers between 0 and Number.MAX_SAFE_INTEGER.
Solution 4 - Javascript
Extremely fast implementation for all values of javascript safe integers range (from -9007199254740991 to 9007199254740991):
const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
// binary to string lookup table
const b2s = alphabet.split('');
// string to binary lookup table
// 123 == 'z'.charCodeAt(0) + 1
const s2b = new Array(123);
for (let i = 0; i < alphabet.length; i++) {
s2b[alphabet.charCodeAt(i)] = i;
}
// number to base64
const ntob = (number) => {
if (number < 0) return `-${ntob(-number)}`;
let lo = number >>> 0;
let hi = (number / 4294967296) >>> 0;
let right = '';
while (hi > 0) {
right = b2s[0x3f & lo] + right;
lo >>>= 6;
lo |= (0x3f & hi) << 26;
hi >>>= 6;
}
let left = '';
do {
left = b2s[0x3f & lo] + left;
lo >>>= 6;
} while (lo > 0);
return left + right;
};
// base64 to number
const bton = (base64) => {
let number = 0;
const sign = base64.charAt(0) === '-' ? 1 : 0;
for (let i = sign; i < base64.length; i++) {
number = number * 64 + s2b[base64.charCodeAt(i)];
}
return sign ? -number : number;
};
npm: number-to-base64
Perfomance comparison: https://jsperf.com/number-to-base64-encoding
Solution 5 - Javascript
Here's a different take
function base64(value) {
if (typeof(value) === 'number') {
return base64.getChars(value, '');
}
if (typeof(value) === 'string') {
if (value === '') { return NaN; }
return value.split('').reverse().reduce(function(prev, cur, i) {
return prev + base64.chars.indexOf(cur) * Math.pow(64, i);
}, 0);
}
}
base64.chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";
base64.getChars = function(num, res) {
var mod = num % 64,
remaining = Math.floor(num / 64),
chars = base64.chars.charAt(mod) + res;
if (remaining <= 0) { return chars; }
return base64.getChars(remaining, chars);
};
Solution 6 - Javascript
I was looking for a solution to the same problem, but for ActionScript (AS3), and it was evident that many persons confuse Base64 encode with 'numbers in base 64' (radix 64).
The vast majority of sites offer solutions for 'computational cryptography' and not mathematics. As solutions, this are not useful for the conversion that we needed.
Prior to this consultation, and knew the methods toString (radix) and parseInt (radix), I was worked with Hex numbers (radix 16) in both colors, and other features.
However, neither in AS3 or JS there exists a numerical method for transformations to and from radix 64.
Before coming to this site I found:
- In various online calculators, radix 64 not starting from scratch, but A.
Eg: convertix.com & alfredo4570.net - In radix 64 is formed by the following sets of ordered characters: AZ, az, 0-9, + and / (these I have defined a constant: STR64)
To avoid confusion with cryptographic methods, the methods to be used are based on well-known names:
- toString / to64String
- parseInt / to64Parse
The code was be wrote in AS3, but is very clear (common with JS).
> NOTE: Recommended use with number under: 1 * 1016
At the end, an example and results of operations are included.
const STR64:Array = ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/').split( '' );
// TRANSFORM NUMBERS BETWEEN radix 10 AND radix 64
/** Methods based on answers shared in:
* @url http://stackoverflow.com/questions/6213227/fastest-way-to-convert-a-number-to-radix-64-in-javascript
*/
// METHODS
/** to64String: Method to transform a radix 10 number to radix 64 number (as string)
* @param input Number for transform to radix 64 (as String)
* @param current String data (don't needed in request)
* @return String Number in radix 64 as String;
*
* @based http://stackoverflow.com/users/383780/monocle
* @based base64( Method for number to string - NOT string part )
*/
function to64String( input:Number, current:String = '' ):String
{
if ( input < 0 && current.length == 0 ){
input = input * - 1;
}
var modify:Number = input % 64;
var remain:Number = Math.floor( input / 64 );
var result:String = STR64[ modify ] + current;
return ( remain <= 0 ) ? result : to64String( remain, result );
}
/** to64Parse: Method for transform a number in radix 64 (as string) in radix 10 number
* @param input Number in radix 64 (as String) to transform in radix 10
* @return Number in radix 10
*
* @based http://stackoverflow.com/users/520997/reb-cabin
* @based Base64.toNumber( Method for string to number )
*/
function to64Parse ( input:String ):Number
{
var result:Number = 0;
var toProc:Array = input.split( '' );
var e:String;
for ( e in toProc ){
result = ( result * 64 ) + STR64.indexOf( toProc[ e ] );
}
return result;
}
// TEST
var i:int = 0;
var max:Number = 1000000000000;
var min:Number = 0;
for ( i == 0; i < 20; i++ ){
var num:Number = ( Math.ceil( Math.random() * ( max - min + 1 ) ) + min );
var s64:String = to64String( num );
var ret:Number = to64Parse ( s64 );
trace( i + '\t# ' + num + '\t' + s64 + '\t' + ret + '\t' + ( ret == num ) )
}
// TEST RESULT
/*
0 # 808936734685 LxYYv/d 808936734685 true
1 # 931332556532 NjXvwb0 931332556532 true
2 # 336368837395 E5RJSMT 336368837395 true
3 # 862123347820 Mi6jk9s 862123347820 true
4 # 174279278611 CiT2sAT 174279278611 true
5 # 279361353722 EELO/f6 279361353722 true
6 # 435602995568 GVr9jlw 435602995568 true
7 # 547163526063 H9lfNOv 547163526063 true
8 # 188017380425 CvGtYxJ 188017380425 true
9 # 720098771622 KepO0Km 720098771622 true
10 # 408089106903 F8EAZnX 408089106903 true
11 # 293941423763 ERwRi6T 293941423763 true
12 # 383302396164 Fk+mmkE 383302396164 true
13 # 695998940618 KIMxQXK 695998940618 true
14 # 584515331314 IgX1CTy 584515331314 true
15 # 528965753970 Hso0Nxy 528965753970 true
16 # 5324317143 E9WqHX 5324317143 true
17 # 772389841267 LPWBalz 772389841267 true
18 # 954212692102 N4rgjCG 954212692102 true
19 # 867031893694 MnfIMa+ 867031893694 true
*/
Solution 7 - Javascript
I wrote an npm module for this type of operation, [power-radix][1], that will help you. You can convert any number from any radix to any radix in a user-defined character encoding.
For example:
var base = ['Q', 'W', 'E', 'R', 'T', 'Y', 'I', 'O', 'U'];
new PowerRadix([1, 0], 10).toArray(base); // ['W', 'Q']
new PowerRadix('10', 10).toArray(base); // ['W', 'Q']
new PowerRadix(10, 10).toArray(base); // ['W', 'Q']
new PowerRadix([1, 0], 10).toString(base); // "WQ"
new PowerRadix('10', 10).toString(base); // "WQ"
new PowerRadix(10, 10).toString(base); // "WQ"
The module also supports custom source radix encodings.
new PowerRadix('ba', ['a', 'b']); // base 2 source radix, uses 'a' = 0 & 'b' = 1 character set.
new PowerRadix('ba', ['a', 'b']).toString(10); // returns "2"
[1]: https://www.npmjs.com/package/power-radix "power-radix"
Solution 8 - Javascript
The following implementation converts positive, negative and non-integer numbers to an arbitrary base. The conversion back to decimal is easily implemented in a similar fashion:
function toAnyBase(num, base) {
if (!Number.isInteger(base) || base < 2) throw new RangeError("toAnyBase() base argument must be an integer >= 2");
if (!Number.isFinite(num)) return num.toString();
if (num < 0) return "-" + toAnyBase(-num, base);
const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ#_",
inv_base = 1 / base;
var result = "",
residual;
// Integer part:
residual = Math.trunc(num);
do {
result = digits.charAt(residual % base) + result;
residual = Math.trunc(residual * inv_base);
} while (residual != 0);
// Fractional part:
residual = num % 1;
if (residual != 0) {
result += ".";
var max = 1000;
do {
residual *= base;
result += digits.charAt(Math.trunc(residual));
residual %= 1;
} while (residual != 0 && --max != 0);
}
return result;
}
console.log(toAnyBase( 64, 64)); // "10"
console.log(toAnyBase(-1.5, 64)); // "-1.w"
Solution 9 - Javascript
I was after the same solution and I think I've generalized what this person is after with as few lines as possible in basic Javascript. Should work for any positive integer, and endex can be whatever length you want for whatever base you want as long as all the characters are unique.
var endex = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";
function encode(intcode){
if(intcode < endex.length){
return endex[intcode];
}else{
return encode(Math.floor(intcode/endex.length)) + endex[intcode%endex.length];
}
}
function decode(charcode){
if(charcode.length < 2){
return endex.indexOf(charcode);
}else{
return (decode(charcode.slice(0, -1)) * endex.length) + endex.indexOf(charcode.slice(-1));
}
}
Solution 10 - Javascript
If you are using NodeJS, you can use the following code:
var base64 = Buffer.from([i>>24,i>>16,i>>8,i]).toString('base64').substr(0,6);
Solution 11 - Javascript
Well, you could just use any Javascript Base64 library: perhaps this question answers it?
EDIT: Binary data is essentially just a sequence of bytes. If you assume the bytes represent a single number you can represent the sequence of bytes as a base 64 string. Decode them and do some trivial math on the bytes to get a number. Convert the number to a sequence of bytes and encode to get a string. Seems quite reasonable, unless you are somehow invested in the specific characters used in the String.
Solution 12 - Javascript
I know the question is Java Script, but here is a solution in java, you probably can easily convert it.
private String toShortString(BigInteger value, String language) {
StringBuilder stringBuilder = new StringBuilder();
BigInteger length = BigInteger.valueOf(language.length());
while (value.compareTo(BigInteger.ZERO) > 0){
int index = value.mod(length).intValue();
stringBuilder.append(language.charAt(index));
value = value.divide(length);
}
return stringBuilder.reverse().toString();
}
Usage
BigInteger value = BigInteger.valueOf(2).pow(128);
System.out.println(value);
System.out.println(value.toString(16));
System.out.println(toShortString(value, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()-=_+"));
Output
> 340282366920938463463374607431768211456
> 100000000000000000000000000000000
> 8hS#phQaCO3849pE+^El4
If you convert this to Java Script please edit this question and add it below.
Solution 13 - Javascript
I've made some enhancements in @jahooma and @Reb.Cabin
1- BigInt: The reason is simple, when you are using radix64 the numbers will grow too fast and will overflow javascript primitive int capacity.
2- Better alphabet: I took liberty to change the radix64 alphabet to URL friendly one, also I sorted it lexicographically, this way if you sort alphabetically a list of strings representing radix64 numbers, the result will be the same as if you had converted the radix64 to decimal then sorted then converted back (might sound obvious but the current accepted answer wont work with)
Base64 = (function () {
const alphabet = '-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz';
const base64Values = { '0': 1n, '1': 2n, '2': 3n, '3': 4n, '4': 5n, '5': 6n, '6': 7n, '7': 8n, '8': 9n, '9': 10n, '-': 0n, 'A': 11n, 'B': 12n, 'C': 13n, 'D': 14n, 'E': 15n, 'F': 16n, 'G': 17n, 'H': 18n, 'I': 19n, 'J': 20n, 'K': 21n, 'L': 22n, 'M': 23n, 'N': 24n, 'O': 25n, 'P': 26n, 'Q': 27n, 'R': 28n, 'S': 29n, 'T': 30n, 'U': 31n, 'V': 32n, 'W': 33n, 'X': 34n, 'Y': 35n, 'Z': 36n, '_': 37n, 'a': 38n, 'b': 39n, 'c': 40n, 'd': 41n, 'e': 42n, 'f': 43n, 'g': 44n, 'h': 45n, 'i': 46n, 'j': 47n, 'k': 48n, 'l': 49n, 'm': 50n, 'n': 51n, 'o': 52n, 'p': 53n, 'q': 54n, 'r': 55n, 's': 56n, 't': 57n, 'u': 58n, 'v': 59n, 'w': 60n, 'x': 61n, 'y': 62n, 'z': 63n};
return {
fromInt: function(bigNum) {
if(typeof bigNum != 'bigint')
bigNum = BigInt(bigNum);
let len = 1+bigNum.toString().length/2|0;
const result = Array(len); //to calculate the exact size of the output some //to calculate the exact size of the output some complex log calcs are needed, I use this to get an approximation
do {
result[--len] = alphabet[(bigNum & 0x3fn)];
bigNum >>= 6n;
} while (bigNum>0)
return result.join('');
},
toInt: function(input) {
if(!input)
return 0;
var result = 0n;
for (var i = 0n; i < input.length; i++)
result = (result << 6n) + base64Values[input[i]];
return result;
}
};
})();
Solution 14 - Javascript
I translated Ilya Gazman's Java code to JavaScript:
function toShortString(value, language) {
var string = "";
var length = language.length;
while (value > 0) {
var index = value % length;
string += language.charAt(index);
value = value / length;
}
return string.split("").reverse().join("").replace(/^0+/g, "");
}
var base64Language = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";
console.log(toShortString(138, base64Language)); //> 2a
Solution 15 - Javascript
In a mozilla or webkit browser you can use btoa() and atob() to encode and decode base64.