indutny/bn.js

BigNum in pure javascript

bn.js's Issues

modn API inconsistency

All mod/div methods return a BN instance, except modn which returns a JS Number.

I think it would make sense making the current modn internal (prefixing it with _) so that toString can keep using it the fastest way, and creating a new modn which returns a BN instance.

divmod already encapsulates a modn result as a BN instance so it should use the new method.

Comments?

RFC: parseBase/toString for radixes outside 2/10/16 (maybe even 8)

Does any other base than 2/10/16 (and maybe even 8) make any sense in day to day usage? Is there any use case for them today? The current implementation forces a single hardcoded alphabet consisting of 0-9,a-z,A-Z cut off at the radix.

Wouldn't it make more sense for those to support a user-supplied alphabet, similarly to the way base-x does it?

mod.neg in divmod

bn.js/lib/bn.js

Line 2294 in c9d5ab8

if (positive && mod.neg) {

if (mode !== 'div') {
  mod = res.mod.neg();
  if (positive && mod.neg) {
    mod = mod.add(num);
  }
}

neg? Will be always true, because neg is function.

make cmp easy to work with

what do you think about added eq, gte, lte, gt, lt to the API? Each of these method would return a bool. Code get messy fast if you have a bunch of cmps

regression in 4.1.0

specifically in dsa calculations, will try to make a test case, but basically browserify-sign dsa doesn't work with 4.1.0 but does with 4.0.0

handling zero on sub bug

This is not what I expected
new BN(0).divn(100000).subn(2)
<BN: 3fffffe>

I would think it would just be -2

All inputs are valid?

var bn = require('bn.js')
var z = new bn('asd')
console.log(z instanceof bn) // true
console.log(z) // <BN: 50d>
var x = new bn(')*(&^(*&^')
console.log(x) // <BN: 3ffffffd62fcf5b>
console.log(x.toString(10)) // '-70undefined-1509797'

This isn't really an issue, I am just trying to understand what is happening here.
Especially the undefined in the toString(10) output seems to be interesting.

to string can cause freezing

This causes my computer to lock up

var a = new BN([]);
a.toString();

new BN("100000001").toString() !== "100000001"

mod not working correctly on some numbers

var a = new BN('945304eb96065b2a98b57a48a06ae28d285a71b5', 'hex');
var b = new BN('fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe', 'hex');

a.mul(b).mod(a) ///gives 945304eb96065b2a98b57a48a06ae28d285a71b5 should be '0'

mod should be zero in this case but it is not

new BN("1").divide(new BN("-2")).toString() === "-"

modular exponentiation?

does the library support this?

Benchmark results

I have run the benchmarks (including #88) and it could be better. Not sure whether it is representative at all in terms of commonly used methods.

Where bn.js failed:

• toString(10)
• toString(16)
• mul 35% slower
• mul-jumbo 96% slower (this might be a broken test, but two others were at least twice as fast as bn.js)
• sqr 26% slower
• div 63% slower
• mod 57% slower
• pow 80% slower
• gcd 27% slower

Regarding toString(10): a dedicated case might speed things up.

Re: toString(16): the fact that 26 bits are stored in a word makes it a lengthier process. Storing 24 or 32 bits would make this significantly faster. What is the actual reason behind going for 26 bits?

The full output:

bash-3.2$ node index.js 
Benchmarking: create-10
bn.js#create-10 x 917,636 ops/sec ±2.74% (8 runs sampled)
bignum#create-10 x 224,568 ops/sec ±2.60% (9 runs sampled)
bigi#create-10 x 571,307 ops/sec ±11.43% (8 runs sampled)
yaffle#create-10 x 912,360 ops/sec ±4.76% (9 runs sampled)
silentmatt-biginteger#create-10 x 73,199 ops/sec ±1.61% (8 runs sampled)
bignumber#create-10 x 479,789 ops/sec ±1.88% (9 runs sampled)
------------------------
Fastest is bn.js#create-10,yaffle#create-10
========================
Benchmarking: create-hex
bn.js#create-hex x 1,178,547 ops/sec ±11.80% (9 runs sampled)
bignum#create-hex x 189,415 ops/sec ±13.69% (8 runs sampled)
bigi#create-hex x 548,509 ops/sec ±6.54% (9 runs sampled)
sjcl#create-hex x 743,918 ops/sec ±3.52% (8 runs sampled)
yaffle#create-hex x 874,148 ops/sec ±5.63% (9 runs sampled)
silentmatt-biginteger#create-hex x 19,237 ops/sec ±4.85% (8 runs sampled)
bignumber#create-hex x 17,456 ops/sec ±1.67% (8 runs sampled)
------------------------
Fastest is bn.js#create-hex
========================
Benchmarking: toString-10
bn.js#toString-10 x 493,331 ops/sec ±2.14% (9 runs sampled)
bignum#toString-10 x 377,052 ops/sec ±3.66% (9 runs sampled)
bigi#toString-10 x 56,522 ops/sec ±1.85% (8 runs sampled)
yaffle#toString-10 x 1,160,115 ops/sec ±5.15% (9 runs sampled)
silentmatt-biginteger#toString-10 x 3,089,024 ops/sec ±4.15% (9 runs sampled)
bignumber#toString-10 x 22,371 ops/sec ±4.83% (9 runs sampled)
------------------------
Fastest is silentmatt-biginteger#toString-10
========================
Benchmarking: toString-hex
bn.js#toString-hex x 373,833 ops/sec ±7.83% (9 runs sampled)
bignum#toString-hex x 2,053,779 ops/sec ±3.73% (9 runs sampled)
bigi#toString-hex x 597,184 ops/sec ±2.52% (9 runs sampled)
sjcl#toString-hex x 380,253 ops/sec ±6.30% (9 runs sampled)
yaffle#toString-hex x 336,258 ops/sec ±4.74% (9 runs sampled)
silentmatt-biginteger#toString-hex x 9,564 ops/sec ±5.16% (9 runs sampled)
bignumber#toString-hex x 24,026 ops/sec ±5.71% (9 runs sampled)
------------------------
Fastest is bignum#toString-hex
========================
Benchmarking: add
bn.js#add x 7,486,633 ops/sec ±2.01% (8 runs sampled)
bignum#add x 113,935 ops/sec ±2.02% (8 runs sampled)
bigi#add x 1,994,830 ops/sec ±7.26% (9 runs sampled)
sjcl#add x 3,863,970 ops/sec ±4.71% (9 runs sampled)
yaffle#add x 5,122,197 ops/sec ±2.97% (9 runs sampled)
silentmatt-biginteger#add x 1,328,770 ops/sec ±5.26% (9 runs sampled)
bignumber#add x 1,475,561 ops/sec ±5.36% (8 runs sampled)
------------------------
Fastest is bn.js#add
========================
Benchmarking: sub
bn.js#sub x 5,438,894 ops/sec ±4.31% (9 runs sampled)
bignum#sub x 112,649 ops/sec ±4.04% (9 runs sampled)
bigi#sub x 1,612,451 ops/sec ±16.89% (8 runs sampled)
sjcl#sub x 3,326,135 ops/sec ±17.04% (8 runs sampled)
yaffle#sub x 4,654,711 ops/sec ±4.51% (8 runs sampled)
silentmatt-biginteger#sub x 3,256,610 ops/sec ±6.52% (9 runs sampled)
bignumber#sub: 
------------------------
Fastest is bn.js#sub
========================
Benchmarking: mul
bn.js#mul x 1,492,842 ops/sec ±3.50% (9 runs sampled)
bn.js[FFT]#mul x 114,362 ops/sec ±4.76% (9 runs sampled)
bignum#mul x 58,624 ops/sec ±26.16% (7 runs sampled)
bigi#mul x 390,251 ops/sec ±7.24% (8 runs sampled)
sjcl#mul x 2,287,125 ops/sec ±3.93% (9 runs sampled)
yaffle#mul x 1,409,295 ops/sec ±6.91% (9 runs sampled)
silentmatt-biginteger#mul x 514,773 ops/sec ±4.03% (8 runs sampled)
bignumber#mul x 556,803 ops/sec ±1.41% (9 runs sampled)
------------------------
Fastest is sjcl#mul
========================
Benchmarking: mul-jumbo
bn.js#mul-jumbo x 1,190 ops/sec ±4.87% (9 runs sampled)
bn.js[FFT]#mul-jumbo x 3,026 ops/sec ±3.93% (9 runs sampled)
bignum#mul-jumbo x 28,532 ops/sec ±7.91% (9 runs sampled)
bigi#mul-jumbo x 1,157 ops/sec ±5.46% (8 runs sampled)
sjcl#mul-jumbo x 2,841 ops/sec ±3.68% (9 runs sampled)
yaffle#mul-jumbo x 1,552 ops/sec ±2.28% (9 runs sampled)
silentmatt-biginteger#mul-jumbo x 599 ops/sec ±6.48% (9 runs sampled)
bignumber#mul-jumbo x 593 ops/sec ±7.00% (8 runs sampled)
------------------------
Fastest is bignum#mul-jumbo
========================
Benchmarking: sqr
bn.js#sqr x 1,328,815 ops/sec ±5.63% (8 runs sampled)
bignum#sqr x 59,338 ops/sec ±28.25% (7 runs sampled)
bigi#sqr x 249,727 ops/sec ±11.39% (8 runs sampled)
sjcl#sqr x 1,810,258 ops/sec ±3.90% (8 runs sampled)
yaffle#sqr x 1,364,301 ops/sec ±5.63% (8 runs sampled)
silentmatt-biginteger#sqr x 318,959 ops/sec ±5.51% (9 runs sampled)
bignumber#sqr x 522,413 ops/sec ±3.23% (8 runs sampled)
------------------------
Fastest is sjcl#sqr
========================
Benchmarking: div
bn.js#div x 253,720 ops/sec ±6.84% (8 runs sampled)
bignum#div x 35,872 ops/sec ±64.38% (6 runs sampled)
bigi#div x 121,087 ops/sec ±6.19% (7 runs sampled)
yaffle#div x 677,293 ops/sec ±3.85% (9 runs sampled)
silentmatt-biginteger#div x 23,874 ops/sec ±3.83% (9 runs sampled)
bignumber#div x 38,726 ops/sec ±3.88% (8 runs sampled)
------------------------
Fastest is yaffle#div
========================
Benchmarking: mod
bn.js#mod x 213,368 ops/sec ±18.17% (9 runs sampled)
bignum#mod x 52,249 ops/sec ±22.77% (7 runs sampled)
bigi#mod x 97,774 ops/sec ±6.44% (9 runs sampled)
yaffle#mod x 500,369 ops/sec ±6.86% (8 runs sampled)
silentmatt-biginteger#mod x 17,479 ops/sec ±6.18% (8 runs sampled)
------------------------
Fastest is yaffle#mod
========================
Benchmarking: mul-mod k256
bn.js#mul-mod k256 x 821,985 ops/sec ±3.56% (8 runs sampled)
sjcl#mul-mod k256 x 349,720 ops/sec ±5.63% (7 runs sampled)
------------------------
Fastest is bn.js#mul-mod k256
========================
Benchmarking: pow k256
bn.js#pow k256 x 3,235 ops/sec ±9.99% (9 runs sampled)
bignum#pow k256 x 15,680 ops/sec ±39.71% (9 runs sampled)
------------------------
Fastest is bignum#pow k256
========================
Benchmarking: invm k256
bn.js#invm k256 x 5,544 ops/sec ±3.72% (8 runs sampled)
sjcl#invm k256 x 3,930 ops/sec ±7.69% (8 runs sampled)
------------------------
Fastest is bn.js#invm k256
========================
Benchmarking: gcd
bn.js#gcd x 21,713 ops/sec ±5.84% (9 runs sampled)
bigi#gcd x 29,660 ops/sec ±4.42% (8 runs sampled)
------------------------
Fastest is bigi#gcd
========================
Benchmarking: egcd
bn.js#egcd x 5,435 ops/sec ±23.47% (8 runs sampled)
------------------------
Fastest is bn.js#egcd
========================
Benchmarking: bitLength
bn.js#bitLength x 19,521,537 ops/sec ±44.08% (8 runs sampled)
------------------------
Fastest is bn.js#bitLength
========================

toArray could benefit from endian and width parameters

endian arg not honoured by constructor when array is passed

For compatibility, please pad HEX strings to an even number of characters in length...

Would you please check new bn(...).toString(16) always returns an even number of HEX digits. For compatibility with other libraries it is sometimes necessary to prefix the HEX string with '0'.

I will be happy to expand this to a full example if it is not obvious. I encountered this when I used the library to calculate a shared secret and then tried to use the shared secret in a buffer. The Buffer complains when the zero is not added. With the zero the shared secret decrypts the message so I have good confidence that we are simply needing a conditional zero prefix.

    sh0 = s0.derive(s1.getPublic())
    sh1 = s1.derive(s0.getPublic())    
    assert.equal sh0.toString(16), sh1.toString(16), "shared secret did not match"

    shared_secret = "0"+sh0.toString(16) #### only works for this shared secret (bn.js::toString)
    console.log "elliptic shared_secret\t",shared_secret
    ss_buffer = new Buffer(shared_secret, "hex")

Feature request: bitwise negation

It would be nice to have a method for doing bitwise negation.

no muln method

there is no muln method.

1 / (new BN("-1").cmp(new BN("-1"))) !== Infinity

-3 >> 8 == 0

in JavaScript -3 >> 8 === -1, in bn.js it is 0.
I think, x >> n should be equal to floor(x / 2**n) for compatibility with JavaScript and some other libraries

GCD of negative number + zero

In the tests we have assert.equal(new BN(-18).gcd(new BN(12)).toString(16), '6'); thus allowing negative numbers as an input.

For new BN(-18).gcd(new BN(0)) we get -18, where GCD should be a positive number?

The same applies to new BN(0).gcd(new BN(-18)).

If allowing gcd over a negative number is desired, the simple fix is to call iabs() here:

  BN.prototype.gcd = function gcd (num) {
    if (this.isZero()) return num.clone();
    if (num.isZero()) return this.clone();
  ...

bitwise operators on negative numbers

seems, https://github.com/justmoon/node-bignum throws an error if any a or b is a negative integer for a ^ b, a & b, a | b

The behaviour of this operators for negative integers in other libraries and in JavaScript is as if twos complement arithmetic were used. ( http://www-cs-students.stanford.edu/~tjw/jsbn/ )

I think, you might throw an error while this behaviour is not implemented

Extra hands

@dcousens @calvinmetcalf

I just wanted to ask you guys if you would be interested in becoming maintainers for this library? Not that I'm not going to review PRs, but it looks like you have lots of feedback that is driven by your needs, and usually provide very relevant suggestions.

If it works for you - I will give you permissions here and on npm.

(@axic don't be offended, you are next on this queue! Just give it some time :) I want to make sure that we synchronize our view on this library)

Improve smallMulTo?

smallMulTo
If I understand all correctly,

      var r = a * b;

      var lo = r & 0x3ffffff;
      ncarry = (ncarry + ((r / 0x4000000) | 0)) | 0;
      lo = (lo + rword) | 0;
      rword = lo & 0x3ffffff;
      ncarry = (ncarry + (lo >>> 26)) | 0;

can be represented as

      var r = a * b + rword;
      ncarry += (r / 0x4000000) | 0;
      rword = r & 0x3ffffff;

2add + 1div + 1round + 1and
instead
3add + 1div + 1 round + 2and + 1shift

Feature request: two's complement

It would be nice to support two's complement representation for toArray() and perhaps a new way of loading a two's complement representation into BN.

the benchmark is incorrect for browserify-bignum

This lib is for decimal computation, so division will result in non-integer value.
It is possible to configure this:

BigNumber.config({DECIMAL_PLACES : 0, ROUNDING_MODE : 1, EXPONENTIAL_AT: 1048576});

Make the `negative` property public.

Is there any particular reason why the negative property is not a public field?

In my use case, I keep numbers of variable sizes in BN and have them dumped as binary. I would like to know if they are negative, because of two's complements padding I need to add differs.

So far I was using one of three horrible shortcuts to check:

return bn.toString().startsWith('-');
or
return BN.min(bn, new BN(0)) === bn;
or
return bn.abs() !== bn;

I am probably doing it wrong, and there's a simpler way or negative can be made public.

carry in _iaddn, _isubn

._iaddn add num to words[0], but num can be more than 0x03FFFFFF (26 bits), as result:

var BN = require('bn.js')
new BN(0).addn(0x90000000).muln(2) // <BN: fffffffffffff20000000>

_isubn also affected to this bug...

redSqrt error

On testing cryptocoinjs/secp256k1-node#57 Martin Becze found that elliptic and secp256k1-node embedded pure js implementation have error on recover operation.

• Message: f75c6b18a72fabc0f0b888c3da58e004f0af1fe14f7ca5d8c897fe164925d5e9
• Signature: fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd03641408887321be575c8095f789dd4c743dfe42c1820f9231f98a962b210e3ac2452a3
• Recovery ID: 0

But the real problem with redSqrt:

var BN = require('bn.js')
var n = new BN('16e5f9d306371e9b876f04025fb8c8ed10f8b8864119a149803357e77bcdd3b1', 'hex').toRed(BN.red('k256'))
console.log(n.redSqr().redSqr().cmp(n))

give 1 instead 0

It's can be easily solving in bn.js by comparing result with redSqr and throwing error... but how resolve it in elliptic context?
@indutny any ideas?

cc: @wanderer

Feature request: divRound should be able to round up

I need a way to round up the remained in division. Would that be a good option for divRound?

Use semistandard for enforcing style

https://github.com/Flet/semistandard/

-178 = 10 * (-17) + 2, -178 = -10 * 17 + 8

Your mod result is always positive and division is a truncated division, so the quotient q and the remainder r of a divided by n do not satisfy a = nq + r.
see http://en.wikipedia.org/wiki/Modulo_operation#Remainder_calculation_for_the_modulo_operation

I think, https://github.com/justmoon/node-bignum is correct here.

can you please check division?

new BN("6582018229284824168619876730229320890292528855852623664389292032").div(new BN("730750818665451459101842416358132502628711530497")).toString()

result of truncated divison should be equal to "9007199254740991"

We need a Logo.

@indutny I'm not all that great in making logos, just gave it try, not that good.

Maybe @stoeffel can help...

This is awesome!

It's now being used by bittorrent-tracker. Rock on!

BN() without `new` stopped working

Using new works:

> new BN(5)

And omitting new used to work too. But not since upgrading to 0.4:

<BN: 5>
> BN(5)
TypeError: Object #<Object> has no method '_init'
    at BN (/Users/feross/code/bittorrent-tracker/node_modules/bn.js/lib/bn.js:27:10)
    at repl:1:2
    at REPLServer.self.eval (repl.js:110:21)
    at Interface.<anonymous> (repl.js:239:12)
    at Interface.EventEmitter.emit (events.js:95:17)
    at Interface._onLine (readline.js:202:10)
    at Interface._line (readline.js:531:8)
    at Interface._ttyWrite (readline.js:760:14)
    at ReadStream.onkeypress (readline.js:99:10)
    at ReadStream.EventEmitter.emit (events.js:98:17)

pow(baseNumber, 0) gives invalid results

Here is my test;

const BN = require('bn.js');
const base = new BN(256).toRed( BN.red('k256'));
const exponent = new BN(0);

const result = base.redPow(exponent)
console.log(result.toString());

the result is 256, when it should be 1

Bug in toArray?

var tmp = new BN(0)
tmp.toString() // -> ‘0’
tmp.toNumber() // -> 0
tmp.toArray() // -> []

I think toArray() should return [0]. Zero should still mean zero and not nil.

.cmp() can return -0

new BN(-42).cmp(new BN(-42)) // -0

This line is the cause: https://github.com/indutny/bn.js/blob/master/lib/bn.js#L2768

It is not a major issue per se, as -0 == 0 in Javascript, thus comparing the output with 0 will return true.

new BN("-100000000000").mul(new BN("3").div(new BN("4"))).toString(16) === "-0000000"

Missing documentation

When I try using bn, just by intuition (no doc is available). I get just errors:

var BigNum = require('bn.js');

var num = new BigNum(9772.13);

num.mod(0.001); // Crash: TypeError: Object 0.001 has no method 'cmpn'

num.mod(new BigNum(0.001)); // Crash: Error: Assertion failed

// hmm.. maybe we should use strings:
num = new BigNum('9772.13');
String(num.mod(new BigNum('0.1'))); // 0  (wrong, should be 0.03)

Breaking changes for the next major release

(Taking the discussion from #112 to here)

Proposed changes:

• Make .modn() return a BN (#112)
• Renaming .strip() to ._strip() is a breaking change too (#105)
• Maybe reviewing the constructor method(s) could lead to such a change (see #90 & #91)
• Rename .andln() to .andn() (see the README). Perhaps fold the functionality into toArrayLike and make .andn() safe in terms of working up to 53 bits
• Maybe at that stage two's complement could be made more internal (part of constructor and toString) (see #73)
• Split out the extended functions (saving destroyed bits) off iusrhn() into a specific shift right version, because it is only used in MPrime.split() and is complex.
• Remove internal functions from the BN context (good candidates are: _countBits, _zeroBits, etc. Others could be moved too with passing a self variable instead of using this, however that might have a speed penalty or increase?)
• Perhaps rethink naming/functionality of the following bitwise methods: setn (should be renamed isetn as it is in-place), testn, maskn, bincn

Bug in parseBase for numbers containing a dot ('0.0079')

new BN('0.0079', 10) // <BN: ffffb22f>
new BN('0.02', 10) // <BN: ffffff3a>

_init, parseBase or _parseBase will not care if a dot is included in a base-10 input, will process it as ('.' - 48) & 0xf.

I think it should just reject such input?

new BigInteger("-0").toString(16) === "-0"

Sign Change, Positive Numbers Tests

These tests are failing:

    iaddn
      1) should allow a sign change
    isubn
      2) should work for positive numbers
      3) should not allow a sign change

Latest commit hash: 0bf5d7d

power mod

How can I do a powm ?

can benchmarks be runnable without node?

1. I have "0.00" ops/sec for all libs. Seems, "benchmark.js" does not work well under node.js for me.
2. I have no "python", so i cannot install some libs for benchmark.

It is still interesting to compare performance under web browsers.
Can the benchmark be rewritten, so it will be possible to run it under Chrome or Firefox or ... AND this will still be same benchmark?

Why are big numbers from a Number limited to 2^26 - 1 ?

If you create a bn from a Number, e.g. new bn(50), it creates a new bn as expected. But if you plug in a Number greater than 2^26 - 1, it returns 0, which is not expected. However, if you first convert the Number to a String, it does work. Example:

> (new bn(Math.pow(2, 26))).toString();
'0'
> (new bn(Math.pow(2, 26)-1)).toString();
'67108863'
> (new bn(Math.pow(2, 26).toString())).toString();
'67108864'
> (new bn(Math.pow(2, 26).toString(16), 16)).toString()
'67108864'

Is this expected behavior?

lib/bn.js is too big

With a SLOC count of over 2000 for a single file.
Perhaps its time to break out parts of it?

Really big JS numbers don't work in the Constuctor

The Constructor doesn't work with really big JS Numbers.

var a = new BN(8.834235323891922e+71)
a.toString(); // '0'