Skip to content

Instantly share code, notes, and snippets.

@jjbubudi
Last active January 26, 2019 02:11
Show Gist options
  • Save jjbubudi/ad491ee25190fd8ada65f9bbfe378be0 to your computer and use it in GitHub Desktop.
Save jjbubudi/ad491ee25190fd8ada65f9bbfe378be0 to your computer and use it in GitHub Desktop.
const DIGITS = [
'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
];
const TWO_TO_32 = 0x100000000;
const MAX_SAFE_INTEGER = 0x1FFFFFFFFFFFFF;
export class UInt64 {
readonly low: number;
readonly high: number;
constructor(low: number, high: number) {
this.low = low;
this.high = high;
}
static fromNumber(value: number): UInt64 {
const low = value >>> 0;
const high = Math.floor((value - low) / TWO_TO_32) >>> 0;
return UInt64.fromBits(low, high);
}
static fromString(s: string): UInt64 {
// We can avoid very expensive multiply based code path for some common cases.
const numberValue = +s;
if (numberValue <= MAX_SAFE_INTEGER) {
return UInt64.fromNumber(numberValue);
}
// Do several (8) digits each time through the loop, so as to
// minimize the calls to the very expensive emulated multiply.
var result = UInt64.fromBits(0, 0);
for (let i = 0; i < s.length; i += 8) {
const size = Math.min(8, s.length - i);
const value = +s.substring(i, i + size);
if (size < 8) {
const power = UInt64.fromBits(Math.pow(10, size), 0);
result = result.multiply(power).add(UInt64.fromBits(value, 0));
} else {
result = result.multiply(UInt64.fromBits(100000000, 0)).add(UInt64.fromBits(value, 0));
}
}
return result;
}
static fromBits(low: number, high: number): UInt64 {
return new UInt64(low, high);
}
unsafeToNumber(): number {
return this.high * TWO_TO_32 + this.low;
}
add(other: UInt64): UInt64 {
const low = ((this.low + other.low) & 0xFFFFFFFF) >>> 0;
const high =
(((this.high + other.high) & 0xFFFFFFFF) >>> 0) +
(((this.low + other.low) >= 0x100000000) ? 1 : 0);
return new UInt64(low >>> 0, high >>> 0);
}
multiply(other: UInt64): UInt64 {
// Divide each long into 4 chunks of 16 bits, and then add up 4x4 products.
// We can skip products that would overflow.
const a48 = this.high >>> 16;
const a32 = this.high & 0xFFFF;
const a16 = this.low >>> 16;
const a00 = this.low & 0xFFFF;
const b48 = other.high >>> 16;
const b32 = other.high & 0xFFFF;
const b16 = other.low >>> 16;
const b00 = other.low & 0xFFFF;
let c48 = 0, c32 = 0, c16 = 0, c00 = 0;
c00 += a00 * b00;
c16 += c00 >>> 16;
c00 &= 0xFFFF;
c16 += a16 * b00;
c32 += c16 >>> 16;
c16 &= 0xFFFF;
c16 += a00 * b16;
c32 += c16 >>> 16;
c16 &= 0xFFFF;
c32 += a32 * b00;
c48 += c32 >>> 16;
c32 &= 0xFFFF;
c32 += a16 * b16;
c48 += c32 >>> 16;
c32 &= 0xFFFF;
c32 += a00 * b32;
c48 += c32 >>> 16;
c32 &= 0xFFFF;
c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48;
c48 &= 0xFFFF;
return new UInt64((c16 << 16) | c00, (c48 << 16) | c32);
}
subtract(other: UInt64): UInt64 {
const low = ((this.low - other.low) & 0xffffffff) >>> 0;
const high =
(((this.high - other.high) & 0xffffffff) >>> 0) -
(((this.low - other.low) < 0) ? 1 : 0);
return new UInt64(low >>> 0, high >>> 0);
};
toString(): string {
// Skip the expensive conversion if the number is small enough to use the
// built-in conversions.
if (this.high <= 0x1FFFFF) {
return '' + this.unsafeToNumber();
}
// What this code is doing is essentially converting the input number from
// base-2 to base-1e7, which allows us to represent the 64-bit range with
// only 3 (very large) digits. Those digits are then trivial to convert to
// a base-10 string.
// The magic numbers used here are -
// 2^24 = 16777216 = (1,6777216) in base-1e7.
// 2^48 = 281474976710656 = (2,8147497,6710656) in base-1e7.
// Split 32:32 representation into 16:24:24 representation so our
// intermediate digits don't overflow.
const low = this.low & 0xFFFFFF;
const mid = (((this.low >>> 24) | (this.high << 8)) >>> 0) & 0xFFFFFF;
const high = (this.high >> 16) & 0xFFFF;
// Assemble our three base-1e7 digits, ignoring carries. The maximum
// value in a digit at this step is representable as a 48-bit integer, which
// can be stored in a 64-bit floating point number.
let digitA = low + (mid * 6777216) + (high * 6710656);
let digitB = mid + (high * 8147497);
let digitC = (high * 2);
// Apply carries from A to B and from B to C.
const base = 10000000;
if (digitA >= base) {
digitB += Math.floor(digitA / base);
digitA %= base;
}
if (digitB >= base) {
digitC += Math.floor(digitB / base);
digitB %= base;
}
// Convert base-1e7 digits to base-10, omitting leading zeroes.
let start = false;
let result = '';
function emit(digit: number) {
let temp = base;
for (let i = 0; i < 7; i++) {
temp /= 10;
let decimalDigit = ((digit / temp) % 10) >>> 0;
if ((decimalDigit == 0) && !start) continue;
start = true;
result += DIGITS[decimalDigit];
}
}
if (digitC || start) emit(digitC);
if (digitB || start) emit(digitB);
if (digitA || start) emit(digitA);
return result;
}
}
export class Int64 {
readonly low: number;
readonly high: number;
constructor(low: number, high: number) {
this.low = low;
this.high = high;
}
static fromString(s: string): Int64 {
const hasNegative = (s.length > 0 && s[0] == '-');
const numberString = hasNegative ? s.substring(1) : s;
const unsigned = UInt64.fromString(numberString);
const signed = hasNegative ? UInt64.fromBits(0, 0).subtract(unsigned) : unsigned;
return new Int64(signed.low, signed.high);
}
toString(): string {
const negative = (this.high & 0x80000000);
const low = negative ? (~this.low + 1) >>> 0 : this.low;
const high = negative ? (~this.high + ((this.low == 0) ? 1 : 0)) >>> 0 : this.high;
const signed = UInt64.fromBits(low, high);
return (negative ? '-' : '') + signed.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment