Skip to content

Instantly share code, notes, and snippets.

@blindman2k

blindman2k/BigInt.class.nut Secret

Forked from bbharris/BigNum.class.nut
Last active October 14, 2015 10:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save blindman2k/8a2d62f337f011171980 to your computer and use it in GitHub Desktop.
Save blindman2k/8a2d62f337f011171980 to your computer and use it in GitHub Desktop.
Download ZIP
Arbitrary Precision BigInt class (In Development). Replaced by https://gist.github.com/blindman2k/91edac399f4e6a920dad
Raw
BigInt.class.nut
// Copyright (c) 2014 Electric Imp
// This file is licensed under the MIT License
// http://opensource.org/licenses/MIT
//==============================================================================
class BigInt {
_data = null; // Blob with LSB at index 0
_sign = null; // 1 = positive, -1 = negative
_valid = true;
//--------------------------------------------------------------------------
constructor(value = 0, sign = 1) {
if (sign != -1) sign = 1;
_convert(value, sign);
}
//--------------------------------------------------------------------------
function _typeof() {
return "BigInt";
}
//--------------------------------------------------------------------------
function _convert(value = 0, sign = 1) {
_sign = sign;
switch (typeof value) {
case "array":
case "blob":
_data = blob(value.len());
for (local i = 0; i < value.len(); i++) {
if (typeof value[i] == "integer") {
// Store LSB at 0
_data[i] = value[i] & 0xFF;
} else {
server.error("Not yet implemented: " + typeof value[i] + " in initial " + typeof value);
}
}
break;
case "string":
// This should be a hex or decimal string
value = strip(value);
if (value.len() == 0) {
_data = blob(); _data.writen(0, 'b');
_sign = 1;
} else {
// Do we have a negative sign?
if (value[0] == '-') {
value = value.slice(1);
_sign = -sign;
} else {
_sign = sign;
}
// What type of integer is this
if (value.len() >= 2 && value.slice(0, 2).tolower() == "0x") {
// It's hex
value = value.slice(2).toupper();
if (value.len() == 0) {
_data = blob(); _data.writen(0, 'b');
_sign = 1;
} else {
// make sure we have an even number of digits
if (value.len() % 2 == 1) value = "0" + value;
// start scanning from the right
_data = blob();
for (local i = value.len() - 2; i >= 0; i -= 2) {
local hex = value.slice(i, i+2)
local int = _hex2int(hex);
_data.writen(int, 'b');
}
}
} else {
// It's a decimal
server.error("Decimal strings not implemented");
// Some concepts to review
// http://www.statman.info/conversions/hexadecimal.php
// http://www.mobilefish.com/scripts/bigint.js
_data = blob(); _data.writen(0, 'b');
_sign = 1;
_valid = false;
}
}
break;
case "null":
value = 0;
case "float":
value = value.tointeger();
case "integer":
// This is a 32 bit signed number
if (value < 0) {
_sign = -sign;
value = -value;
} else {
_sign = sign;
}
// Now it's a 31 bit unsigned number
_data = blob(4);
for (local i = 0; i < 4; i++) {
// Store LSB at 0
_data[i] = (value >> i*8) & 0xFF;
}
break;
default:
server.error("Unsupported value type: " + typeof value);
_data = blob(); _data.writen(0, 'b');
_sign = 1;
_valid = false;
}
_trim();
}
//--------------------------------------------------------------------------
function _trim() {
local l = _data.len();
local i;
for (i = l-1; i > 0; i--) {
if (_data[i] != 0x00) {
break;
}
}
_data.resize(i+1);
// Don't allow a value of -0x00
if (_data.len() == 1 && _data[0] == 0x00 && _sign == -1) _sign = 1;
}
//--------------------------------------------------------------------------
// Convert hex string to an integer
function _hex2int(hex) {
local result = 0;
local shift = hex.len() * 4;
// For each digit..
for (local d=0; d<hex.len(); d++) {
// Convert from ASCII Hex to integer
local digit;
if (hex[d] >= 0x61) {
digit = hex[d] - 0x57;
} else if(hex[d] >= 0x41) {
digit = hex[d] - 0x37;
} else {
digit = hex[d] - 0x30;
}
// Accumulate digit
shift -= 4;
result += digit << shift;
}
return result;
}
//--------------------------------------------------------------------------
static function _sameSignAdd(a, b) {
local aData = a._data;
local bData = b._data;
local aLen = aData.len();
local bLen = bData.len();
local maxLen = (aLen > bLen) ? aLen : bLen;
// Grow by 1 byte over longest integer to allow overflow
local result = array(maxLen+1);
local val;
for (local i = 0; i < maxLen + 1; i++) {
val = (i < aLen) ? aData[i] : 0;
val += (i < bLen) ? bData[i] : 0;
val += (i > 0) ? (result[i-1] >> 8) : 0; // No carry for first value
result[i] = val;
}
return BigInt(result, a._sign);
}
//--------------------------------------------------------------------------
static function _orderedSub(a, b){
// assert: |a| > |b|
local aData = clone a._data; // aData is changed below. Need a copy.
local bData = b._data;
local aLen = aData.len();
local bLen = bData.len();
// Result will be no larger than larger number
local result = array(aLen);
for (local i = 0; i < aLen; i++) {
if (i >= bLen) {
result[i] = aData[i];
} else if (aData[i] >= bData[i]) {
result[i] = aData[i] - bData[i];
} else {
aData[i+1]--; // i+1 is guranteed to exist by design
result[i] = (aData[i] + 0x100) - bData[i];
}
}
return BigInt(result, a._sign);
}
//--------------------------------------------------------------------------
function _cmp(op) {
if (typeof op != "BigInt") op = BigInt(op);
local myd = this._data;
local opd = op._data;
// If I am negative then I am always smaller
if (this._sign != op._sign) return this._sign;
// If lengths are different then the values must be different
// Short positive numbers are smaller than long positive numbers
// Long negative numbers are smaller than short negative numbers
if (myd.len() > opd.len()) {
return this._sign;
} else if ( myd.len() < opd.len() ) {
return -this._sign;
}
// server.log(format("cmp %s <=> %s", this.tostring(), op.tostring()))
for (local i = myd.len()-1; i >= 0; i--) {
// -1 if I am |smaller|, 1 if I am |bigger|
local c = (myd[i] <=> opd[i]);
// server.log(format("cmp[%d] %d <=> %d = %d", i, myd[i], opd[i], c))
if (c != 0) return this._sign ? c : 0-c;
}
return 0;
}
//--------------------------------------------------------------------------
function _sub(op) {
if (typeof op != "BigInt") op = BigInt(op);
// server.log(this + " - " + op + " => " + this + " + " + op.negate());
return this + op.negate();
}
//--------------------------------------------------------------------------
function _add(op) {
if (typeof op != "BigInt") op = BigInt(op);
if (this._sign == op._sign) {
// 3 + 2 = 5 and -3 + -2 = -5
return BigInt._sameSignAdd(this, op);
} else {
// 1 == this is bigger, 0 == equal, -1 == op is bigger
local cmp = this.abs() <=> op.abs();
// server.log(this.abs() + " <=> " + op.abs() + " == " + cmp);
if (cmp == 0) {
// -3 + 3 = 0
return BigInt();
} else if (cmp > 0 && this._sign == 1) {
// 3 + -2 = 1
return BigInt._orderedSub(this, op.abs());
} else if (cmp > 0 && this._sign == -1) {
// -3 + 2 = -1
return BigInt._orderedSub(this.abs(), op).negate();
} else if (cmp < 0 && this._sign == 1) {
// 3 + -4 = -1
return BigInt._orderedSub(op.abs(), this).negate();
} else if (cmp < 0 && this._sign == -1) {
// -3 + 4 = 1
return BigInt._orderedSub(op, this.abs());
}
}
}
//--------------------------------------------------------------------------
function _tostring() {
local s = (_sign == -1) ? "-0x" : "0x";
for (local i = _data.len()-1; i >= 0; i--) {
s += format("%02X", _data[i]);
}
return s;
}
//--------------------------------------------------------------------------
function tostring() {
return "" + this;
}
//--------------------------------------------------------------------------
function abs() {
return BigInt(_data);
}
//--------------------------------------------------------------------------
function negate() {
return BigInt(_data, -_sign);
}
//==============================================================================
static function myassert(num, expect) {
if (!("BigInt_checks" in getroottable())) {
::BigInt_checks <- 0;
::BigInt_failures <- 0;
}
++::BigInt_checks;
local result = num.tostring();
local expect = expect.tostring();
if (result != expect) {
::BigInt_failures++;
server.log(format("Test %d failed: %s != %s", ::BigInt_checks, result, expect));
return false;
} else {
return true;
}
}
//--------------------------------------------------------------------------
static function selftest() {
// Comparisons
myassert(BigInt(1) <=> BigInt(1), 0);
myassert(BigInt(-1) <=> BigInt(-1), 0);
myassert(BigInt(-1) <=> BigInt(1), -1);
myassert(BigInt(1) <=> BigInt(-1), 1);
myassert(BigInt(0x10) <=> BigInt(0x1000), -1);
myassert(BigInt(0x1000) <=> BigInt(0x10), 1);
myassert(BigInt(-0x10) <=> BigInt(0x1000), -1);
myassert(BigInt(-0x1000) <=> BigInt(0x10), -1);
myassert(BigInt(0x10) <=> BigInt(-0x1000), 1);
myassert(BigInt(0x1000) <=> BigInt(-0x10), 1);
myassert(BigInt(0x1000) <=> BigInt(0x1000), 0);
myassert(BigInt(-0x1000) <=> BigInt(-0x1000), 0);
myassert(BigInt(0x1001) <=> BigInt(0x1000), 1);
myassert(BigInt(0x1000) <=> BigInt(0x1001), -1);
myassert(BigInt(-0x1001) <=> BigInt(0x1000), -1);
myassert(BigInt(0x1000) <=> BigInt(-0x1001), 1);
// Zero values
myassert(BigInt(), "0x00");
myassert(BigInt(0), "0x00");
myassert(BigInt(0, -1), "0x00");
// Basics, positive values
myassert(BigInt(1), "0x01");
myassert(BigInt(1, 1), "0x01");
// Basics, negative values
myassert(BigInt(1, -1), "-0x01");
myassert(BigInt(-1, 1), "-0x01");
myassert(BigInt(-1, -1), "0x01");
myassert(BigInt(10, -1), "-0x0A");
myassert(BigInt(500, -1), "-0x01F4");
// Converted values
myassert(BigInt(null), "0x00");
myassert(BigInt(123.456, -1), "-0x7B");
myassert(BigInt(-11259375), "-0xABCDEF");
myassert(BigInt("-0xABCDEF", -1), "0xABCDEF");
myassert(BigInt("0xabcdef"), "0xABCDEF");
myassert(BigInt("0x0000001"), "0x01");
myassert(BigInt([0xEF, 0xCD, 0xAB], -1), "-0xABCDEF");
myassert(BigInt("0xABCDEF01234567890ABCDEF01234567890"), "0xABCDEF01234567890ABCDEF01234567890");
// Addition
myassert(BigInt(1) + BigInt(2), "0x03");
myassert(BigInt(-1) + BigInt(-2), "-0x03");
myassert(BigInt(-2) + BigInt(2), "0x00");
myassert(BigInt(-4) + BigInt(2), "-0x02");
myassert(BigInt(3) + BigInt(2), "0x05");
myassert(BigInt(3) + BigInt(-2), "0x01");
myassert(BigInt(3) + BigInt(-5), "-0x02");
myassert(BigInt(0) + BigInt(0), "0x00");
myassert(BigInt("0x11111111111111111") + BigInt("0x222222222"), "0x011111111333333333");
// Subtraction
myassert(BigInt(3) - BigInt(1), "0x02");
myassert(BigInt(3) - BigInt(4), "-0x01");
myassert(BigInt(3) - BigInt(0), "0x03");
myassert(BigInt(3) - BigInt(-4), "0x07");
myassert(BigInt(-5) - BigInt(-4), "-0x01");
myassert(BigInt(-4) - BigInt(-5), "0x01");
myassert(BigInt(0) - BigInt(-4), "0x04");
myassert(BigInt(0) - BigInt(4), "-0x04");
myassert(BigInt(0) - BigInt(0), "0x00");
myassert(BigInt(2345) - BigInt(2345), "0x00");
// Casting numbers automatically
myassert(BigInt(0xFF) - 0xFF, "0x00");
myassert(BigInt(0xFF) + 1, "0x0100");
myassert(BigInt(0x100) - 1, "0xFF");
myassert(BigInt(0x1) - 2, "-0x01");
myassert(BigInt(5) + 4, "0x09");
myassert(BigInt(5) + 4.99, "0x09");
myassert(BigInt("0x40") + 0x04, "0x44");
// Unary functions
myassert(BigInt(-123).abs(), "0x7B");
myassert(BigInt(123).abs(), "0x7B");
myassert(BigInt(123).negate(), "-0x7B");
myassert(BigInt(-123).negate(), "0x7B");
myassert(BigInt(-123).abs().negate(), "-0x7B");
myassert(BigInt(123).negate().abs(), "0x7B");
// Unsupported or unimplemented
// myassert(BigInt("11259375", -1), "0x00");
// myassert(BigInt({"A": "B"}, -1), "0x00");
// myassert(BigInt(["A", "B"]), "0x00");
// Finished
if (::BigInt_failures == 0) server.log(format("All %d tests passed", ::BigInt_checks));
else server.log(format("%d of %d tests failed", ::BigInt_failures, ::BigInt_checks))
delete ::BigInt_checks;
delete ::BigInt_failures;
}
}
//==============================================================================
server.log("BigInt started");
BigInt.selftest();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment