Arbitrary Precision BigInt class (In Development)

README.md

BigInt 1.0.0

The BigInt class is an Electric Imp agent or device side library aimed at managing arbitrarily large integers, including the addition and subtraction of BigInt's and the conversion to and from various other formats.

To add this library to your project, add #require "BigInt.class.nut:1.0.0" to the top of your agent/device code.

NOTE: If you need the cmp(), add() or sub functions, you will also need include the add #require "BigIntLib.class.nut:1.0.0" to the top of your agent/device code.

You can view the library's source code on GitHub.

Class Usage

Constructor: BigInt(initial_value, [sign])

A BigInt object must be instantiated with an initial value. The initial value can be an integer (e.g. 12), a float (e.g. 12.34, will be truncated), a hex string ("-0x1234") or another BigInt.

#require "BigInt.class.nut:0.0.1"

// Instantiate a new BigInt with an initial value of 100
local val1 = BigInt(100);

// Instantiate a new BigInt with an initial value of 123.45 which will be truncated to 123 internally
local val2 = BigInt(123.45);

// Instantiate a new BigInt with an initial value of -100 billion
local val3 = BigInt("-0x174876E800");

// Instantiate a new BigInt with another BigInt
local val4 = BigInt(val3);

Class Methods

tostring()

Returns a hex string of the BigInt value. Positive integers will look like "0x01AB" and negative integers will looks like "-0x01AB". There will be a maximum of one leading zero to ensure the number of hex digits is always even.

server.log( BigInt(-12345678).tostring() ); // Should output "-0xBC614E"

toblob()

Returns a blob of the BigInt value. The first byte is the sign, with 0x00 being positive and 0xFF being negative. The remaining bytes are LSB first. This is mostly used internally but can also be useful for streaming to a storage media, like SPIFlash.

// Write a BigInt to spi flash prefixed by the length
local data = BigInt("-0x123456").toblob(); 
spiflash.write(data.len());
spiflash.write(data);

abs()

Returns another BigInt holding the absolute value of the current BigInt (the sign set to positive).

// Instantiate a new BigInt with an initial negative value and then retrieve the absolute value
val1 <- BigInt("-0x123456").abs(); // Should be equal to BigInt("0x123456")

add(op)

A helper function for the BigIntLib.add() function. Returns a new BigInt with the value of the operand added to the current value.

// Instantiate a new BigInt and add a value to it
val2 <- BigInt(-10).add(20); // Should be equal to BigInt("0x0A")

sub(op)

A helper function for the BigIntLib.sub() function. Returns a new BigInt with the value of the operand subtracted from the current value.

// Instantiate a new BigInt and subtract a value from it
val3 <- BigInt(10).sub(BigInt(20)); // Should be equal to BigInt("-0x0A")

cmp(op)

A helper function for the BigIntLib.cmp() function. Returns -1 when the current value is less than the operand's value, 0 when the they are equal and +1 when the current value is greater than the operand's value.

// Compare two BigInt's
local cmp = BigInt(-10).cmp( BigInt(20) ); // Should be equal to -1 as -10 < 20

License

The BigInt class is licensed under the MIT License.

BigInt.class.nut

// Copyright (c) 2015 Electric Imp
// This file is licensed under the MIT License
// http://opensource.org/licenses/MIT

//==============================================================================
class BigInt {

    static version = [1,0,0];
    
    magnitude = null; // Blob with LSByte at index 0
    sign      = null; // 1 = positive, -1 = negative
    valid     = null; // Tells if an error condition happened such as unsupported operation

    //--------------------------------------------------------------------------
    constructor(ivalue = 0, isign = null) {
        
        local imagnitude = null;
        switch (typeof ivalue) {
            
            case "string":
                ivalue = _fromHexString(ivalue);
                // Fall through to BigInt handler

            case "BigInt":
                // Fiddle with the input pointers
                if (isign == null) isign = 1;
                if (ivalue.sign == null) ivalue.sign = 1;
                isign = isign * ivalue.sign;
                imagnitude = ivalue.magnitude;
                break;
                
            case "blob":
                if (isign == null) {
                    // No sign means we have an exported blob (with a sign at [0])
                    if (ivalue.len() > 1) {
                        // Take the first byte for the sign
                        ivalue.seek(0);
                        isign = ivalue.readn('b') == 0x00 ? 1 : -1;
                        imagnitude = ivalue.readblob( ivalue.len() - 1 );
                    }
                } else {
                    // We have a sign which means the blob doesn't include one
                    imagnitude = ivalue;
                }
                break;
                
            case "float":
                // Trim the float to an integer
                ivalue = ivalue.tointeger();
                // Fall through to the integer handler
                
            case "integer":
                // Capture the sign (ignore the sign parameter)
                isign = (typeof isign == "integer" && isign != 0) ? isign : 1;
                isign = (ivalue >= 0 ? 1 : -1) * isign;
                
                // Convert the integer into a four-byte blob
                ivalue = math.abs(ivalue);
                
                imagnitude = blob(4);
                imagnitude[0] = (ivalue      ) & 0xFF;
                imagnitude[1] = (ivalue >>  8) & 0xFF;
                imagnitude[2] = (ivalue >> 16) & 0xFF;
                imagnitude[3] = (ivalue >> 24) & 0xFF;
                break;
            
            default:
                // throw format("Can't convert '%s' to BigInt", typeof magnitude);

        }
        
        if (imagnitude) {
            magnitude = clone imagnitude;
            sign      = (isign >= 0) ? 1 : -1;
            valid     = true;
            _trim();
        } else {
            valid     = false;
        }
            

    }

    //--------------------------------------------------------------------------    
    //  Public Methods
    //--------------------------------------------------------------------------    

    //--------------------------------------------------------------------------
    function tostring() {
        if (!valid) return "";
        local s = (sign == -1) ? "-0x" : "0x";
        for (local i = magnitude.len()-1; i >= 0; i--) {
            s += format("%02X", magnitude[i]);
        }
        return s;
        
    }
    
    //--------------------------------------------------------------------------
    function toblob() {
        if (!valid) return null;
        local result = blob(1 + magnitude.len());
        result.writen(this.sign >= 0 ? 0x00 : 0xFF, 'b');
        result.writeblob(magnitude);
        return result;
    }
    
    
    //--------------------------------------------------------------------------
    function abs() {
        if (!valid) return null;
        return BigInt(magnitude, 1);
    }


    //--------------------------------------------------------------------------
    function add(op) {
        return BigIntLib.add(this, op);
    }
    

    //--------------------------------------------------------------------------
    function sub(op) {
        return BigIntLib.sub(this, op);
    }
    

    //--------------------------------------------------------------------------
    function cmp(op) {
        return BigIntLib.cmp(this, op);
    }
    
    //--------------------------------------------------------------------------    
    //  Private Methods
    //--------------------------------------------------------------------------    

    //--------------------------------------------------------------------------
    // Remove excess 0x00 bytes and make the blob as compact as possible
    function _trim() {
        // Local for speed
        local m = magnitude; 
        local l = m.len();
        local i;
        for (i = l-1; i > 0; i--) {
            if(m[i] != 0x00) {
                break;
            }
        }
        m.resize(i+1);
        
        // Don't allow a value of -0x00
        if (m.len() == 1 && m[0] == 0x00){
            sign = 1;
        }
    }
 
     //--------------------------------------------------------------------------
    static function _hexByteToInt(str){
        local hex = 0;
        local str = str.tolower();
        foreach (ch in str) {
            local nibble;
            if (ch >= '0' && ch <= '9') {
                nibble = (ch - '0');
            } else {
                nibble = (ch - 'a' + 10);
            }
            hex = (hex << 4) + nibble;
        }
        return hex;
    }
    
    //--------------------------------------------------------------------------
    static function _fromHexString(str) {

        // Create an empty blob to hold our data        
        local result = blob();

        // Let's only deal with lower case letters
        str = str.tolower();
        
        // Remove the leading sign if present
        if (str.len() >= 1 && str.slice(0, 1) == "-") {
            str = str.slice(1);
            result.writen(0xFF, 'b');
        } else {
            result.writen(0x00, 'b');
        }
        
        // Remove leading "0x" if present
        if (str.len() >= 2 && str.slice(0, 2) == "0x") {
            str = str.slice(2);
        }
        
        // start scanning from the right
        local hex, int;
        for (local i = str.len() - 2; i >= -1; i -= 2) {
            if (i < 0) { 
                hex = str.slice(0, 1)
            } else {
                hex = str.slice(i, i+2)
            }
            int = _hexByteToInt(hex);
            result.writen(int, 'b');
        }

        return BigInt(result);
    }
    

    //--------------------------------------------------------------------------
    //  Meta-Methods
    //--------------------------------------------------------------------------
    
    //--------------------------------------------------------------------------
    function _typeof() {
        return "BigInt";
    }
    
}

BigIntLib.class.nut

//==============================================================================
class BigIntLib {

    static version = [1,0,0];
    
    //--------------------------------------------------------------------------    
    //  Public Methods
    //--------------------------------------------------------------------------    

    //--------------------------------------------------------------------------
    static function add(op1, op2) {

        if (typeof op1 != "BigInt") op1 = BigInt(op1);
        if (typeof op2 != "BigInt") op2 = BigInt(op2);

        local newMag, newSign;
        if (op1.sign == op2.sign) {
            //  3 +  2 =  5, if both positive then add magnitudes and sign is positive
            // -3 + -2 = -5, if both negative then add magnitudes and sign is negative
            // Simplifies to |this| + |op|, sign
            // 3 + 2 = 5  and -3 + -2 = -5
            newMag  = addMagnitudes(op1.magnitude, op2.magnitude);
            newSign = op1.sign;
        } else {
            //  3 + -3 =  0, if opposite signs and same magnitude then 0
            //  3 + -2 =  1, if opposite signs and |this| > |op| then |this| - |op| and this.sign
            // -3 +  2 = -1, same as above
            //  2 + -3 = -1, if opposite signs and |this| > |op| then |op| - |this| and -this.sign
            // -2 +  3 =  1, same as above
            local cmp = cmpMagnitudes(op1.magnitude, op2.magnitude);
            
            if (cmp == 0) {
                // Always zero
                // -3 + 3 = 0
                newMag  = blob(1);
                newSign = 1;
            } else if (cmp == 1) {
                // Take the sign from the first operand
                // 3 + -2 = 1 or -5 + 3 = -2
                newMag  = subMagnitudes(op1.magnitude, op2.magnitude);
                newSign = op1.sign;
            } else {
                // Take the sign from the second operand
                // 2 + -3 = -1 or -3 + 5 = 2
                newMag  = subMagnitudes(op2.magnitude, op1.magnitude);
                newSign = -op1.sign;
            }
        }

        return BigInt(newMag, newSign);
    }        

    //--------------------------------------------------------------------------
    // Invert the sign of the second operand and make it into addition
    static function sub(op1, op2) {
        
        if (typeof op1 != "BigInt") op1 = BigInt(op1);
        if (typeof op2 == "BigInt") {
            op2 = BigInt(op2.magnitude, -op2.sign)
        } else {
            op2 = BigInt(op2, -1);
        }
        
        return add(op1, op2);
        
    }

    //--------------------------------------------------------------------------
    static function cmp(op1, op2) {
        
        if (typeof op1 != "BigInt") op1 = BigInt(op1);
        if (typeof op2 != "BigInt") op2 = BigInt(op2);
        
        // If signs mismatch then return sign (1 if positive, -1 if negative)
        if (op1.sign != op2.sign) return op1.sign;

        // If the signs are the same, then check the magnitudes
        //  3 <=>  3 them cmp =  0, return  0
        // -3 <=> -3 them cmp =  0, return  0
        //  5 <=>  3 then cmp =  1, return  1
        // -5 <=> -3 then cmp =  1, return -1
        //  3 <=>  5 then cmp = -1, return -1
        // -3 <=> -5 then cmp = -1, return  1
        // Simplifies to sign * cmp
        
        local cmp = cmpMagnitudes(op1.magnitude, op2.magnitude);
        return op1.sign * cmp;
        
    }
    
    

    //--------------------------------------------------------------------------    
    //  Private Methods
    //--------------------------------------------------------------------------    
    
    //--------------------------------------------------------------------------
    // If both operands are the same sign we can add the magnitudes and keep the same sign
    // if operands have opposite signs, but we need to do a subtraction then this is equivalent
    // to a sameSignAdd. (Math!)
    static function addMagnitudes(aMag, bMag) {
        
        local aLen = aMag.len();
        local bLen = bMag.len();
        local maxLen = (aLen > bLen) ? aLen : bLen;
        
        // Grow by 1 byte over longest integer to allow overflow
        maxLen++;
        
        // Create a blob to hold the result
        local newMag = blob(maxLen);
        
        local val, carry = 0;
        for (local i = 0; i < maxLen; i++) {
            val  = carry;
            val += (i < aLen) ? aMag[i] : 0;
            val += (i < bLen) ? bMag[i] : 0;

            carry = (val >> 8);
            newMag[i] = val & 0xFF;
        }
        
        return newMag;
    }

    //--------------------------------------------------------------------------
    // This is an ordered a minus b operation. a must be larger than b otherwise
    // the result will be invalid.
    static function subMagnitudes(aMag, bMag) {
        
        local aLen  = aMag.len();
        local bLen  = bMag.len();
        
        // Result will be no longer than aMag
        local newMag = blob(aLen);
        
        local minuend, subtrahend, borrow = 0;
        for (local i = 0; i < aLen; i++) {
            minuend    = aMag[i];
            subtrahend = borrow  + (i < bLen ? bMag[i] : 0);
            
            if (minuend >= subtrahend) {
                newMag[i] = minuend - subtrahend;
                borrow = 0;
            } else {
                newMag[i] = 0x100 + minuend - subtrahend;
                borrow = 1;
            }
            // server.log(format("sub[%d] => 0x%02x - 0x%02x = 0x%02x", i, aMag[i], bMag[i], newMag[i]))
        }

        return newMag;
    }
    
    //--------------------------------------------------------------------------
    static function cmpMagnitudes(aMag, bMag) {
        
        // If lengths are different then the values must be different
        local lc = aMag.len() <=> bMag.len();
        if (lc != 0) return lc;

        for (local i = aMag.len()-1; i >= 0; i--) {
            local c = (aMag[i] <=> bMag[i]); 
            // server.log(format("cmp[%d] 0x%02x <=> 0x%02x = %d", i, aMag[i], bMag[i], c))
            if (c != 0) return c;
        }
        
        return 0;
    }
    
}

BigIntTests.nut

//==============================================================================
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;
    }
}

//--------------------------------------------------------------------------    
function selftest() {
    
    // Comparisons
    myassert(BigIntLib.cmp(BigInt(1),       BigInt(1)),        0);
    myassert(BigIntLib.cmp(BigInt(-1),      BigInt(-1)),       0);
    myassert(BigIntLib.cmp(BigInt(-1),      BigInt(1)),       -1);
    myassert(BigIntLib.cmp(BigInt(1),       BigInt(-1)),       1);
    myassert(BigIntLib.cmp(BigInt(0x10),    BigInt(0x1000)),  -1);
    myassert(BigIntLib.cmp(BigInt(0x1000),  BigInt(0x10)),     1);
    myassert(BigIntLib.cmp(BigInt(-0x10),   BigInt(0x1000)),  -1);
    myassert(BigIntLib.cmp(BigInt(-0x1000), BigInt(0x10)),    -1);
    myassert(BigIntLib.cmp(BigInt(0x10),    BigInt(-0x1000)),  1);
    myassert(BigIntLib.cmp(BigInt(0x1000),  BigInt(-0x10)),    1);
    myassert(BigIntLib.cmp(BigInt(0x1000),  BigInt(0x1000)),   0);
    myassert(BigIntLib.cmp(BigInt(-0x1000), BigInt(-0x1000)),  0);
    myassert(BigIntLib.cmp(BigInt(0x1001),  BigInt(0x1000)),   1);
    myassert(BigIntLib.cmp(BigInt(0x1000),  BigInt(0x1001)),  -1);
    myassert(BigIntLib.cmp(BigInt(-0x1001), BigInt(0x1000)),  -1);
    myassert(BigIntLib.cmp(BigInt(0x1000),  BigInt(-0x1001)),  1);
    
    // Basic values
    myassert(BigInt(0),   "0x00");
    myassert(BigInt(1),   "0x01");
    myassert(BigInt(-1), "-0x01");

    // Converted values
    myassert(BigInt(-123.456),      "-0x7B"); 
    myassert(BigInt(-11259375),     "-0xABCDEF"); 
    myassert(BigInt("0x63"),        "0x63");
    myassert(BigInt("-0x63"),       "-0x63");
    myassert(BigInt("0x123456"),    "0x123456");
    myassert(BigInt("0x1234567"),   "0x01234567");
    myassert(BigInt("0x00000001"),  "0x01");
    myassert(BigInt("0000000001"),  "0x01");
    myassert(BigInt("0x123456789ABCDEF0").add("0x01"),  "0x123456789ABCDEF1");

    // Addition
    myassert(BigIntLib.add(BigInt(1),  BigInt(2)),   "0x03");
    myassert(BigIntLib.add(BigInt(-1), BigInt(-2)), "-0x03");
    myassert(BigIntLib.add(BigInt(-2), BigInt(2)),   "0x00");
    myassert(BigIntLib.add(BigInt(-4), BigInt(2)),  "-0x02");
    myassert(BigIntLib.add(BigInt(3),  BigInt(2)),   "0x05");
    myassert(BigIntLib.add(BigInt(3),  BigInt(-2)),  "0x01");
    myassert(BigIntLib.add(BigInt(3),  BigInt(-5)), "-0x02");
    myassert(BigIntLib.add(BigInt(0),  BigInt(0)),   "0x00");
    
    // Subtraction
    myassert(BigIntLib.sub(BigInt(3),    BigInt(1)),    "0x02");
    myassert(BigIntLib.sub(BigInt(3),    BigInt(4)),   "-0x01");
    myassert(BigIntLib.sub(BigInt(3),    BigInt(0)),    "0x03");
    myassert(BigIntLib.sub(BigInt(3),    BigInt(-4)),   "0x07");
    myassert(BigIntLib.sub(BigInt(-5),   BigInt(-4)),  "-0x01");
    myassert(BigIntLib.sub(BigInt(-4),   BigInt(-5)),   "0x01");
    myassert(BigIntLib.sub(BigInt(0),    BigInt(-4)),   "0x04");
    myassert(BigIntLib.sub(BigInt(0),    BigInt(4)),   "-0x04");
    myassert(BigIntLib.sub(BigInt(0),    BigInt(0)),    "0x00");
    myassert(BigIntLib.sub(BigInt(2345), BigInt(2345)), "0x00");

    // Casting numbers automatically
    myassert(BigIntLib.sub(BigInt(0xFF),  0xFF),   "0x00");
    myassert(BigIntLib.add(BigInt(0xFF),  1),    "0x0100");
    myassert(BigIntLib.sub(BigInt(0x100), 1),      "0xFF");
    myassert(BigIntLib.sub(BigInt(0x1),   2),     "-0x01");
    myassert(BigIntLib.add(BigInt(5),     4),      "0x09");
    myassert(BigIntLib.add(BigInt(5),     4.99),   "0x09");

    // Unary functions
    myassert(BigInt(-123).abs(),       "0x7B");
    myassert(BigInt(123).abs(),        "0x7B");
    myassert(BigInt(0).abs(),          "0x00");
    
    myassert(BigInt(100).add(24),      "0x7C");
    myassert(BigInt(100).add(-24),     "0x4C");
    myassert(BigInt(100).add(-124),   "-0x18");
    myassert(BigInt(100).add(-124),   "-0x18");

    myassert(BigInt(100).sub(99),      "0x01");
    myassert(BigInt(100).sub(200),    "-0x64");
    myassert(BigInt(100).sub(0),       "0x64");
    myassert(BigInt(100).sub(-100),    "0xC8");
    
    // Blobs
    myassert(BigInt(BigInt(0).toblob()),     "0x00");
    myassert(BigInt(BigInt(123).toblob()),   "0x7B");
    myassert(BigInt(BigInt(-123).toblob()), "-0x7B");

    // 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");
selftest();

LICENSE.txt

The MIT License (MIT)

Copyright (c) 2015 Electric Imp

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.