Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
math-buffer
Advanced tools
math-buffer - npm Package Compare versions
Comparing version 0.0.0 to 0.1.0
275
index.js
@@ -6,6 +6,31 @@ //add two buffers, | ||
| exports.add = function (a, b, c) { | ||
| var fromInt = exports.fromInt = function (int, length) { | ||
| var b = new Buffer(Math.max(length || 0, 4)) | ||
| b.fill() | ||
| b.writeInt32LE(int, 0) | ||
| return b | ||
| } | ||
| var isZero = exports.isZero = function (v) { | ||
| var l = v.length | ||
| while(l--) if(v[l]) return false | ||
| return true | ||
| } | ||
| var isOne = exports.isOne = function (v) { | ||
| var l = v.length | ||
| while(l--) { | ||
| if(l === 0) return v[0] === 1 | ||
| else if(v[l]) return false | ||
| } | ||
| return true | ||
| } | ||
| //okay, need addShift(a, b, n) | ||
| //a + (b<<n) | ||
| var add = exports.add = function (a, b, c) { | ||
| var l = Math.max(a.length, b.length) | ||
| if(!c) c = new Buffer(l); | ||
| c.fill() | ||
| if(!c) { c = new Buffer(l); c.fill() } | ||
| var carry = 0 | ||
@@ -27,4 +52,3 @@ for(var i = 0; i < l; i++) { | ||
| var l = Math.max(a.length, b.length) | ||
| if(!c) c = new Buffer(l) | ||
| c.fill() | ||
| if(!c) { c = new Buffer(l); c.fill() } | ||
| var carry = 0 | ||
@@ -34,4 +58,3 @@ for(var i = 0; i < l; i++) { | ||
| if(A < B) { | ||
| A += 256 | ||
| carry = 1 | ||
| A += 256; carry = 1 | ||
| } else | ||
@@ -44,42 +67,16 @@ carry = 0 | ||
| //mulitply. | ||
| //multiply each pair of places and accumulate results in a new buffer. | ||
| exports.mul = | ||
| exports.multiply = function (a, b, c) { | ||
| var l = Math.max(a.length, b.length) | ||
| if(!c) c = new Buffer(l) | ||
| c.fill() | ||
| //for each place in A, multiply each place in B, | ||
| //and add it to the running total. | ||
| for(var i = 0; i < b.length; i++) { | ||
| for(var j = 0; j < a.length; j++) { | ||
| var value = b[i] * a[j] | ||
| var current = (c[i + j]||0) + ((c[i + j + 1]<<8) || 0) | ||
| var v = current + value | ||
| c[i + j] = v & 0xff | ||
| c[1 + i + j] = v >> 8 | ||
| } | ||
| } | ||
| return c | ||
| } | ||
| function readInt(b, n) { | ||
| return b[n] | (b[n + 1]||0)<<8 | (b[n + 2]||0)<<16 | (b[n + 2]||0)<<24 | ||
| } | ||
| // a % n (where n is < 2^31) | ||
| // this uses Buffer#readInt32LE | ||
| // so, buffers length must be multiple of 4. | ||
| exports.modInt = function (a, n, c) { | ||
| var l = a.length | ||
| if(!c) c = new Buffer(l) | ||
| a.copy(c) | ||
| l = l - 4 | ||
| do { | ||
| c.writeInt32LE(c.readInt32LE(l) % n, l) | ||
| } while(l--) | ||
| return c | ||
| // should also be able to adapt this to divide by int, | ||
| // which would be useful for converting to different bases (like base 10, or 58) | ||
| exports.modInt = function (a, n) { | ||
| var l = a.length, w = 0 | ||
| while(l--) w = (w << 8 | a[l]) % n | ||
| return w | ||
| } | ||
| //return -1, 0, or 1 if a < b, a == b, a > b | ||
| var compare = exports.compare = function (a, b) { | ||
@@ -105,4 +102,2 @@ var l = Math.max(a.length, b.length) | ||
| for(var i = a.length - 1; i >= -bytes; i--) { | ||
| // console.log(bytes, bits) | ||
| // console.log(c, i) | ||
| var v = a[i] << bits | ||
@@ -112,3 +107,2 @@ c[i + bytes + 1] = carry | v >> 8 | ||
| } | ||
| } else { | ||
@@ -120,11 +114,4 @@ var bits = -1*bits | ||
| var v = (a[i] << 8) >> bits | ||
| // console.log('shifted->', new Buffer([v & 0xff, v >> 8])) | ||
| // console.log('c-byte', a[i], a[i] >> bits) | ||
| // console.log('t-byte', v >> 8) | ||
| // console.log('b-byte', v & 0xff) | ||
| // console.log(c) | ||
| c[i + bytes - 1] = v & 0xff | carry | ||
| carry = c[i + bytes] = v >> 8 | ||
| // carry = v >> 8 | ||
| } | ||
@@ -135,2 +122,23 @@ } | ||
| //multiply, using shift + add | ||
| var multiply = | ||
| exports.mul = | ||
| exports.multiply = function (a, b, m) { | ||
| var w = new Buffer(b) | ||
| var l = a.length * 8, prev = 0 | ||
| if(!m) m = new Buffer(a.length) | ||
| m.fill() //m must be zeros, or it will affect stuff. | ||
| for(var i = 0; i < l; i++) { | ||
| if(getBit(a, i)) { | ||
| shift(w, i - prev, w) | ||
| prev = i | ||
| add(m, w, m) | ||
| } | ||
| } | ||
| return m | ||
| } | ||
| function _msb (x) { | ||
@@ -144,4 +152,4 @@ return ( | ||
| var msb = | ||
| exports.msb = | ||
| var mostSignificantBit | ||
| var msb = mostSignificantBit = exports.msb = | ||
| exports.mostSignificantBit = function (a) { | ||
@@ -153,3 +161,7 @@ var l = a.length | ||
| } | ||
| var getBit = | ||
| exports.getBit = function (q, bit) { | ||
| return q[bit>>3] & 1<<(bit%8) | ||
| } | ||
| var divide = | ||
| exports.divide = function (a, b, q, r) { | ||
@@ -176,21 +188,152 @@ if(!q) q = new Buffer(a.length) | ||
| // console.log('*** shifted! ******************') | ||
| // console.log(mA, mB, mA - mB) | ||
| // console.log(a) | ||
| // console.log('->', b , '>>', mA - mB, '=', _b) | ||
| while(compare(_b, b) >= 0) { | ||
| // instead of shifting this along 1 bit at a time | ||
| // it would probably be more performant to find the | ||
| // next most significant bit and move that far. | ||
| // at least in sparse numbers. | ||
| var bit = mA - mB | ||
| while(bit >= 0) { | ||
| if(compare(_b, r) <= 0) { | ||
| subtract(r, _b, _r) | ||
| // console.log('div', _b, '-', r, '=', _r) | ||
| var t = r; r = _r; _r = t | ||
| //set bit of quotent! | ||
| //set 1 bit of quotent! | ||
| q[bit>>3] |= 1<<(bit%8) | ||
| } | ||
| // else | ||
| // console.log('keep', r) | ||
| shift(_b, -1, _b) | ||
| // var t = _b2; _b2 = _b; _b = t | ||
| bit-- | ||
| } | ||
| return {remainder: r} | ||
| return {remainder: r, quotient: q} | ||
| } | ||
| // to base: | ||
| // b.unshift(_a = (a % 10)); a = (a - _a) / 10; b | ||
| var square = exports.square = function (a, m) { | ||
| return multiply(a, a, m) | ||
| } | ||
| //exports.exponent | ||
| //http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method | ||
| var pow = | ||
| exports.pow = | ||
| exports.power = function (base, exp, mod) { | ||
| var result = new Buffer(exp.length) | ||
| result.fill() | ||
| result[0] = 1 | ||
| var modulus = mod ? function (v) { | ||
| return divide(v, mod).remainder | ||
| } : function (id) { return id } | ||
| var msb = mostSignificantBit(exp) | ||
| for(var i = 0; i < msb; i++) { | ||
| if(getBit(exp, i)) | ||
| result = modulus(multiply(result, base)) | ||
| base = modulus(square(base)) | ||
| } | ||
| return result | ||
| } | ||
| // greatest common divisor | ||
| // http://en.wikipedia.org/wiki/Binary_GCD_algorithm | ||
| exports.gcd = function (u, v, mutate) { | ||
| if(!mutate) { | ||
| u = new Buffer(u) | ||
| v = new Buffer(v) | ||
| } | ||
| var shifts = 0; | ||
| //GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 | ||
| if (isZero(u)) return v; | ||
| if (isZero(v)) return u; | ||
| // if u and v are divisible by 2, then gcd must be 2*something. | ||
| // gcd(v, u) == gcd(v/2, u/2)*2 | ||
| // shift out a factor of two, and we'll add it back at the end. | ||
| for (shifts = 0; ((u[0] | v[0]) & 1) == 0; ++shifts) { | ||
| shift(u, -1, u) | ||
| shift(v, -1, v) | ||
| } | ||
| //NOTE: v & 1 == isEven | ||
| // ~v & 1 == isOdd (~ flips the last 0 into 1, then ands it with 1) | ||
| //while u is even, divide by two. | ||
| while (~u[0] & 1) | ||
| shift(u, -1, u) | ||
| //From here on, u is always odd. | ||
| do { | ||
| //if v is even, 2 cannot be a divisor. | ||
| while (~v[0] & 1) { | ||
| shift(v, -1, v); | ||
| } | ||
| // Now u and v are both odd. | ||
| // swap so that v is larger, so that we can safely subtract v - u | ||
| if (compare(u, v) > 0) { | ||
| var t = v; v = u; u = t; | ||
| } | ||
| subtract(v, u, v) | ||
| } while (!isZero(v)); | ||
| //multiply by the factors of 2 we removed at line 240 | ||
| return shift(u, shifts, u) | ||
| } | ||
| var isOdd = exports.isOdd = function (p) { | ||
| return !!(p[0] & 1) | ||
| } | ||
| var isEven = exports.isEven = function (p) { | ||
| return !(p[0] & 1) | ||
| } | ||
| exports.inverse = function (n, p) { | ||
| var a = fromInt(1, n.length), b = fromInt(0, n.length) | ||
| var x = new Buffer(n), y = new Buffer(p) | ||
| var tmp, i, nz=1; | ||
| if(isEven(p)) | ||
| throw new Error("inverse: p must be odd"+p); | ||
| // invariant: y is odd | ||
| do { | ||
| if (isOdd(x)) { | ||
| if (compare(x, y) < 0) { | ||
| // x < y; swap everything | ||
| tmp = x; x = y; y = tmp; | ||
| tmp = a; a = b; b = tmp; | ||
| } | ||
| subtract(x, y, x) | ||
| if(compare(a, b) < 0) add(a, p, a) | ||
| subtract(a, b, a) | ||
| } | ||
| // cut everything in half | ||
| shift(x, -1, x) | ||
| if (isOdd(a)) add(a, p, a) | ||
| shift(a, -1, a) | ||
| } while(!isZero(x)) | ||
| if (!isOne(y)) throw new Error("inverseMod: p and x must be relatively prime") | ||
| return b; | ||
| } | ||
| function _lsb (x) { | ||
| if(x == 0) return -1 | ||
| return ( | ||
| x & 0x0F | ||
| ? x & 0x03 ? x & 0x01 ? 0 : 1 : x & 0x04 ? 2 : 3 | ||
| : x & 0x30 ? x & 0x10 ? 4 : 5 : x & 0x20 ? 6 : 7 | ||
| ) | ||
| } | ||
| var lowestSetBit = exports.lowestSetBit = function (n) { | ||
| for(var i = 0; i < n.length; i++) | ||
| if(n[i]) return i + _lsb(n[i]) | ||
| return -1 | ||
| } | ||
114
mod.js
@@ -9,5 +9,5 @@ | ||
| //shift B right until it it's just smaller than A. | ||
| //shift B right until it it's most significant bit lines up with A's | ||
| while(B < A) { | ||
| B<<=1; C<<=1 | ||
| B<<=1; C<<=1 //C is just a single bit that points to current position. | ||
| } | ||
@@ -18,9 +18,11 @@ //now, shift B back, while subtracting. | ||
| //mark the bits where you could subtract. | ||
| //this becomes the quotent! | ||
| if(B < A) { | ||
| D |= C; A = A - B | ||
| A = A - B | ||
| //mark the bits where you could subtract. | ||
| //this becomes the quotent! | ||
| D |= C | ||
| } | ||
| console.log('=', D.toString(2)) | ||
| } while(B > _B) | ||
| //when you get back to your origin position, stop. | ||
| } while(B > _B) | ||
| console.log(D, D.toString(2)) | ||
@@ -48,1 +50,101 @@ return A | ||
| module.exports = mod | ||
| function _lsb (x) { | ||
| if(x == 0) return -1 | ||
| return ( | ||
| x & 0x0F | ||
| ? x & 0x03 ? x & 0x01 ? 0 : 1 : x & 0x04 ? 2 : 3 | ||
| : x & 0x30 ? x & 0x10 ? 4 : 5 : x & 0x20 ? 6 : 7 | ||
| ) | ||
| } | ||
| //var a = [] | ||
| //for(var i = 0; i < 0x100; i++) | ||
| // console.log(i.toString(2), _lsb(i)) | ||
| // | ||
| //function inverse(a, n) | ||
| // t := 0; newt := 1; | ||
| // r := n; newr := a; | ||
| // while newr ≠ 0 | ||
| // quotient := r div newr | ||
| // (t, newt) := (newt, t - quotient * newt) | ||
| // (r, newr) := (newr, r - quotient * newr) | ||
| // if r > 1 then return "a is not invertible" | ||
| // if t < 0 then t := t + n | ||
| // return t | ||
| // | ||
| // modular inverse. | ||
| // inverse(a, n) => solve for X: a * X % n == 1 | ||
| var inverse = module.exports = function (a, n) { | ||
| var t = 0, _t = 1 | ||
| var r = n, _r = a | ||
| // var r = n, _r = A | ||
| while(_r != 0) { | ||
| var q = (r / _r) | 0 | ||
| console.log(r, _r, t, _t) | ||
| // var m = x % _r | ||
| var $ | ||
| $ = _r; _r = r % _r; r = $ | ||
| // $ = _t; _t = t - q * _t; t = $ | ||
| $ = _t; _t = t - q * _t; t = $ | ||
| } | ||
| if(r > 1) throw new Error('a is not invertable') | ||
| if(t < 0) return t + n | ||
| return t | ||
| } | ||
| //inverse, without going negative. | ||
| function inverse2(n, p) { | ||
| var a = 1, b = 0 | ||
| var x = n, y = p | ||
| var tmp, i, nz=1; | ||
| if (!(p & 1)) //is even | ||
| throw new Error("inverse: p must be odd"); | ||
| // invariant: y is odd | ||
| do { | ||
| console.log(x, y, a, b) | ||
| if (x & 1) { | ||
| if (x < y) { | ||
| console.log('SWAP') | ||
| // x < y; swap everything | ||
| tmp = x; x = y; y = tmp; | ||
| tmp = a; a = b; b = tmp; | ||
| console.log('swapped', x, y, a, b) | ||
| } | ||
| console.log('x -= y', x, y) | ||
| x -= y | ||
| console.log('===', x) | ||
| console.log('compare', a < b, a, b) | ||
| if(a < b) | ||
| a += p; | ||
| a -= b; | ||
| // console.log('neg?', x, y, a, b) | ||
| } | ||
| // cut everything in half | ||
| // console.log('half', x, a, p) | ||
| x >>= 1 | ||
| if (a & 1) a += p | ||
| a >>= 1 | ||
| } while(x) | ||
| if (y != 1) throw new Error("inverseMod: p and x must be relatively prime") | ||
| console.log(x, y, a, b) | ||
| return b; | ||
| } | ||
| var a = parseInt(process.argv[2]), n = parseInt(process.argv[3]) | ||
| console.log('inverse=', inverse(a, n), 'inverse2=',inverse2(a, n)) | ||
| { | ||
| "name": "math-buffer", | ||
| "description": "big integer math operations implemented on top of node buffers", | ||
| "version": "0.0.0", | ||
| "version": "0.1.0", | ||
| "homepage": "https://github.com/dominictarr/math-buffer", | ||
@@ -6,0 +6,0 @@ "repository": { |
116
README.md
| # math-buffer | ||
| use node buffers as big integers. | ||
| ## byte order & base | ||
| Buffers and interpreted as base 256 numbers, | ||
| where each place is 256 times larger than the previous one, | ||
| instead of 10 times larger. `value = Math.pow(256, i)`. | ||
| Also note that this means bytes in a buffer are interpreted in little endian order. | ||
| This means that a number such as `0x12345678` is represented in a buffer | ||
| as `new Buffer([0x78, 0x56, 0x34, 0x12])`. | ||
| This greatly simplifies the implementation because the least significant byte (digit) | ||
| also has the lowest index. | ||
| ## api | ||
| in general, all methods follow this pattern: | ||
| `result = op(a, b, m?)` | ||
| where `m` is an optional buffer that the result will be stored into. | ||
| If `m` is not provided, then it will be allocated. | ||
| ### bool = isZero(x) | ||
| return true if this buffer represents zero. | ||
| ### fromInt: `result = fromInt(int_n, length?)` | ||
| convert `int_n` into a buffer, that is at least 4 bytes, | ||
| but if you supply a longer `length` value, | ||
| then it will be zero filled to that length. | ||
| ### add: `result = add(a, b, m?)` | ||
| add `a` to `b` and store the result in `m` | ||
| (if m is not provided a new buffer will be allocated, and returned) | ||
| in some cases, `a` may === `m`, in other cases, it must be a different buffer. | ||
| `m` *may* be `a, b` | ||
| ### subtract: `result = subtract(a, b, m?)` | ||
| subtract `b` from `a` and store the result in `m` | ||
| (if m is not provided a new buffer will be allocated, and returned) | ||
| only positive integers are supported (currently) so `a` must be larger than `b`. | ||
| `m` *may* be `a, b` | ||
| ### multiply: `result = multiply (a, b, m?)` | ||
| multiply `a` by `b`. | ||
| `m` *must not* be `a, b` | ||
| ### modInt: `int_result = modInt(a, int_n)` | ||
| get the modulus of dividing a big number with a 32 bit int. | ||
| ### compare: `order = compare(a, b)` | ||
| Compare whether `a` is smaller than (-1), equal (0), or greater than `b` (1) | ||
| this the same signature as is expected by `Array.sort(comparator)` | ||
| ### shift: `result = shift(a, bits, m?)` | ||
| move a big number across by `bits`. `bits` can be both positive or negative. | ||
| a positive number of bits is the same as `Math.pow(a, bits)` | ||
| This is an essential part of `divide` | ||
| `m` *may* be `a` | ||
| ### mostSignificantBit: `bits = mostSignificantBit (a)` | ||
| Find the position of the largest valued bit in the number. | ||
| (since the buffer may have trailing zeros, it's not necessaryily in the last byte) | ||
| ### divide: `{quotient, remainder} = divide (a, b, q?, r?)` | ||
| Divide `a` by `b`, updating the `q` (quotient) and `r` (remainder) buffers. | ||
| `a`,`b`,`q`, and `r` *must* all be different buffers. | ||
| ### square: `result = square (a, m?)` | ||
| multiply `a` by itself. | ||
| `m` *must not* be `a`. | ||
| ### power: `result = power (e, x, mod?)` | ||
| Raise `e` to the power of `x`, | ||
| If `mod` is provided, the result will be `e^x % mod`. | ||
| ### gcd: `result = gcd(u, v, mutate=false)` | ||
| Calculate the greatest common divisor using the | ||
| [binary gcd algorithm](http://en.wikipedia.org/wiki/Binary_GCD_algorithm) | ||
| If `mutate` is true, the inputs will be mutated, | ||
| by default, new buffers will be allocated. | ||
| ### gcd: `x = inverse(a, m)` | ||
| Calculate the [modular multiplicative inverse](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse) | ||
| This is the inverse of `a*x % m = 1`. | ||
| My implementation is based on | ||
| [sjcl's implementation](https://github.com/bitwiseshiftleft/sjcl/blob/master/core/bn.js#L182-L226) | ||
| Unfortunately I was unable to find any reference explaining this particular algorithm, | ||
| (the benefit this algorithm is that it doesn't require negative numbers, which I havn't implemented) | ||
| ## TODO | ||
| * isProbablyPrime (needed for RSA) | ||
| ## License | ||
| MIT |
@@ -10,5 +10,6 @@ var big = require('./') | ||
| shift(new Buffer([8, 1]), -3, new Buffer([0x21, 0])) | ||
| //shift(new Buffer([8, 1]), -3, new Buffer([0x21, 0])) | ||
| shift(new Buffer([7, 0]), 10, new Buffer([0x0, 0x1c])) | ||
| //shift(new Buffer([7, 0]), 10, new Buffer([0x0, 0x1c])) | ||
| console.log(big.multiply2(new Buffer([7, 7]), new Buffer([7, 7]), new Buffer(2))) |
@@ -8,6 +8,56 @@ var big = require('../') | ||
| function equal(t, a, b) { | ||
| t.deepEqual(a.toJSON(), b.toJSON()) | ||
| function clone (a) { | ||
| return JSON.parse(JSON.stringify(a)) | ||
| } | ||
| function equal(t, a, b, message) { | ||
| //clone to turn Buffers into arrays which makes deepEquals work better. | ||
| t.deepEqual(clone(a), clone(b), message) | ||
| } | ||
| function createTest(t, forward, reverse, mutate) { | ||
| return function (a, b, c) { | ||
| var r, r2 | ||
| equal(t, r = big[forward](a, b), c, | ||
| r.inspect() + ' == ' + forward + '('+a.inspect()+', ' + b.inspect()+')') | ||
| if(reverse) | ||
| equal(t, r2 = big[reverse](r, b), a, | ||
| r2.inspect() + ' == ' + reverse + '('+a.inspect()+', ' + b.inspect()+')') | ||
| if(mutate) { | ||
| var _a = new Buffer(a) | ||
| equal(t, r = big[forward](_a, b, _a), c, | ||
| _a.inspect() + ' == ' + forward + '('+a.inspect()+', ' + b.inspect()+', m)') | ||
| if(reverse) | ||
| equal(t, big[reverse](r, b, r), a, | ||
| _a.inspect() + ' == ' + forward + '('+r.inspect()+', ' + b.inspect()+')') | ||
| } | ||
| } | ||
| } | ||
| tape('add/sub with mutate', function (t) { | ||
| var test = createTest(t, 'add', 'sub', true) | ||
| //simple | ||
| test(B(0, 1), B(1, 0), B(1, 1)) | ||
| //carry | ||
| test(B(0x80, 0), B(0x80, 0), B(0, 1)) | ||
| //carry | ||
| test(B(0x80, 0), B(0x80, 0), B(0, 1)) | ||
| //two carries | ||
| test(B(0x80, 0xff, 0), B(0x80, 0, 0), B(0, 0, 1)) | ||
| //xfffff + 0xffff == 0x1fffe | ||
| test(B(0xff, 0xff, 0), B(0xff, 0xff, 0), B(0xfe, 0xff, 0x01)) | ||
| t.end() | ||
| }) | ||
| tape('ADD - add two buffers', function (t) { | ||
@@ -66,6 +116,7 @@ var a = new Buffer([0x01, 0x02, 0x03]) | ||
| tape('multiply - carry2', function (t) { | ||
| var a = new Buffer([0x00, 0x10]) | ||
| var b = new Buffer([0x00, 0x10]) | ||
| var a = new Buffer([0x00, 0x10, 0x00, 0x00]) | ||
| var b = new Buffer([0x00, 0x10, 0x00, 0x00]) | ||
| var c = new Buffer([0x00, 0x00, 0x00, 0x01]) | ||
| equal(t, big.mul(a, b, new Buffer(4)), c) | ||
| var m = new Buffer(4); m.fill() | ||
| equal(t, big.mul(a, b, m), c) | ||
| t.end() | ||
@@ -75,21 +126,23 @@ }) | ||
| tape('multiply - carry3', function (t) { | ||
| var a = new Buffer([0x10, 0x10]) | ||
| var b = new Buffer([0x10, 0x10]) | ||
| var a = new Buffer([0x10, 0x10, 0, 0]) | ||
| var b = new Buffer([0x10, 0x10, 0, 0]) | ||
| var c = new Buffer([0x00, 0x01, 0x02, 0x01]) | ||
| equal(t, big.mul(a, b, new Buffer(4)), c) | ||
| var m = new Buffer(4); m.fill() | ||
| equal(t, big.mul(a, b, m), c) | ||
| t.end() | ||
| }) | ||
| tape('multiply - carry3', function (t) { | ||
| var a = new Buffer([0x12, 0x34]) | ||
| var b = new Buffer([0x56, 0x78]) | ||
| var a = new Buffer([0x12, 0x34, 0, 0]) | ||
| var b = new Buffer([0x56, 0x78, 0, 0]) | ||
| var c = new Buffer([0x0c, 0xee, 0x79, 0x18]) | ||
| equal(t, big.mul(a, b, new Buffer(4)), c) | ||
| var m = new Buffer(4); m.fill() | ||
| equal(t, big.mul(a, b, m), c) | ||
| t.end() | ||
| }) | ||
| tape('modInt', function (t) { | ||
| var a = new Buffer([0, 0, 0x12, 0x34]) | ||
| equal(t, big.modInt(a, 0x13), new Buffer([0x11, 0, 0, 0])) | ||
| t.equal(big.modInt(a, 0x13), 0x11) | ||
| t.end() | ||
@@ -100,3 +153,3 @@ }) | ||
| var a = new Buffer([0, 0, 0, 0, 0x12, 0x34]) | ||
| equal(t, big.modInt(a, 0x130000), new Buffer([0, 0, 0x11, 0, 0, 0])) | ||
| t.equal(big.modInt(a, 0x130000), 0x110000) | ||
| t.end() | ||
@@ -107,3 +160,3 @@ }) | ||
| var a = new Buffer([0x12, 0x34, 0x56, 0x78, 0x9a, 0, 0, 0]) | ||
| equal(t, big.modInt(a, 0x123456), new Buffer([0xea, 0x47, 0x08, 0, 0, 0, 0, 0])) | ||
| t.equal(big.modInt(a, 0x123456), 0x0847ea) | ||
| t.end() | ||
@@ -114,3 +167,3 @@ }) | ||
| var a = B(0xab, 0x33, 0, 0) | ||
| equal(t, big.modInt(a, 28), new Buffer([11, 0, 0, 0])) | ||
| t.equal(big.modInt(a, 28), 11) | ||
| t.end() | ||
@@ -200,8 +253,81 @@ }) | ||
| // var r = .r | ||
| equal(t, big.divide(B(0x80), B(8)).remainder, B(0)) | ||
| equal(t, big.divide(B(0x80), B(7)).remainder, B(2)) | ||
| equal(t, big.divide(B(0, 0x80), B(7, 0)).remainder, B(1, 0)) | ||
| equal(t, big.divide(B(0x34, 0x12), B(0, 7)).remainder, B(0x34, 4)) | ||
| equal(t, big.divide(B(0x34, 0x12), B(7, 0)).remainder, B(5, 0)) | ||
| equal(t, big.divide(B(0x80), B(8)), {remainder: B(0), quotient: B(0x10)}) | ||
| equal(t, big.divide(B(0x80), B(7)), {remainder: B(2), quotient: B(0x12)}) | ||
| equal(t, big.divide(B(0, 0x80), B(7, 0)), {remainder: B(1, 0), quotient: B(0x49, 0x12)}) | ||
| equal(t, big.divide(B(0x34, 0x12), B(0, 7)), {remainder: B(0x34, 4), quotient: B(0x02, 0)}) | ||
| equal(t, big.divide(B(0x34, 0x12), B(7, 0)), {remainder: B(5, 0), quotient: B(0x99, 0x02)}) | ||
| t.end() | ||
| }) | ||
| tape('square', function (t) { | ||
| equal(t, big.square(B(1)), B(1)) | ||
| equal(t, big.square(B(2)), B(4)) | ||
| equal(t, big.square(B(0x80, 0)), B(0, 0x40)) | ||
| equal(t, big.square(B(0xff, 0)), B(0x01, 0xfe)) | ||
| equal(t, big.square(B(0xff, 0xff, 0, 0)), B(0x01, 0, 0xfe, 0xff)) | ||
| equal(t, big.square(B(0xff, 0xff, 0xff, 0, 0, 0)), B(0x01, 0, 0, 0xfe,0xff, 0xff)) | ||
| t.end() | ||
| }) | ||
| function testIntExp(t, base, exponent, mod) { | ||
| var result = Math.pow(base, exponent) | ||
| if(mod) result = result % mod | ||
| //only test if we didn't overflow | ||
| var exp = base+'^'+exponent+(mod ? '%'+mod : '')+'==='+result | ||
| if(result > 0xffffffff) | ||
| throw new Error('cant calculate with int:'+exp) | ||
| console.log('**********************') | ||
| console.log(exp) | ||
| var b = big.fromInt(base, 8) | ||
| var e = big.fromInt(exponent, 8) | ||
| var m = mod && big.fromInt(mod, 8) | ||
| var r = big.fromInt(result, 8) | ||
| equal(t, r, big.power(b, e, m)) | ||
| } | ||
| tape('power', function (t) { | ||
| equal(t, big.power(B(2), B(4)), B(0x10)) | ||
| equal(t, big.power(B(0x3, 0, 0, 0, 0), B(0x17, 0, 0, 0, 0)), B(0x4b, 0xe8, 0x5e, 0xeb, 0x15)) | ||
| //test with some random numbers | ||
| testIntExp(t, 2, 27) | ||
| testIntExp(t, 3, 17) | ||
| testIntExp(t, 5, 13) | ||
| testIntExp(t, 5, 11) | ||
| testIntExp(t, 7, 7) | ||
| testIntExp(t, 2, 27, 5234) | ||
| testIntExp(t, 3, 27, 79234) | ||
| testIntExp(t, 5, 13, 3412) | ||
| testIntExp(t, 5, 11, 333453) | ||
| testIntExp(t, 7, 7, 13131) | ||
| t.end() | ||
| }) | ||
| tape('power modulus', function (t) { | ||
| equal(t, big.power(B(0x3, 0, 0), B(0x17, 0, 0), B(0x19)), B(2, 0, 0)) | ||
| t.end() | ||
| }) | ||
| tape('gcd', function (t) { | ||
| equal(t, big.gcd(B(45, 0), B(95, 0)), B(5, 0)) | ||
| equal(t, big.gcd(B(46, 200), B(193, 200)), B(3, 0)) | ||
| equal(t, big.gcd(B(0x9f, 0xf4, 0xb8, 0x57, 0x37, 0xdf, 0x02), | ||
| B(0x89, 0x41, 0xe5, 0x1b, 0xda, 0x9a, 0x01)), | ||
| B(0x39, 0xbe, 0x23, 0, 0, 0, 0)) | ||
| t.end() | ||
| }) | ||
| tape('inverse', function (t) { | ||
| equal(t, big.inverse(big.fromInt(23), big.fromInt(7)), big.fromInt(4)) | ||
| equal(t, big.inverse(big.fromInt(23), big.fromInt(17)), big.fromInt(3)) | ||
| equal(t, big.inverse(big.fromInt(235), big.fromInt(171)), big.fromInt(163)) | ||
| equal(t, big.inverse(big.fromInt(235123), big.fromInt(112341347)), big.fromInt(11542649)) | ||
| t.end() | ||
| }) |
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by126.51%
29580
- Number of package files
- increased by25%
10
- Lines of code
- increased by81.3%
698
- Number of lines in readme file
- increased by1657.14%
123
No dependency changes