Incorrect multiplication result

[astiob]

Unfortunately I don’t have a smaller example, but raising this number (represented in base 36 for compactness) to the 4th power and then squaring it gives a mathematically incorrect result: https://gist.github.com/astiob/091b8dbadf0698affb7a469e93450a0b

x = new BN("...", 36)

x.sqr().sqr()        // is correct
x.sqr().sqr().sqr()  // is incorrect
x.pow(new BN(8))     // is incorrect (equivalent to previous line)

x.sqr().sqr().maskn(256).toString()                            // 9076919990156733995225002098329760000 (correct)
x.sqr().sqr().maskn(256).sqr().maskn(256).toString()           // 82390476507706923968765337733501879292364638168635194987781701657600000000 (correct)
x.sqr().sqr().mul(x.sqr()).mul(x.sqr()).maskn(256).toString()  // 82390476507706923968765337733501879292364638168635194987781701657600000000 (correct)
x.sqr().sqr().sqr().maskn(256).toString()                      // 308574507784727280410577156852044557420092381404603103173567945519950528512 (incorrect)

Tested using Git master in Firefox 48 on Mac OS X 10.6, Firefox 62 and 64 on Windows 7 and Chrome 71 on Windows Server 2016.

I should note that this number isn’t unique. I’m seeing this with plenty of numbers that I produce as a Kronecker substitution of some probability distribution convolutions, but all affected numbers that I’ve seen so far are similarly large or larger.

[astiob]

Could this be caused by the fact an actual Fourier transform with floating-point maths is used? As far as I understand (which may be wrong), it can introduce errors by virtue of being floating-point, and ideally a number-theoretic transform should be used instead.

[fanatid]

Can you paste what number used as input, what result received and what expected? Is there any difference between pass number in base36 or in base10 on creating BN number? (maybe problem in parser?)

[astiob]

I’ve already pasted the full number (in the linked gist). It’s only in base 36 to make it shorter than it would be in base 10. (I couldn’t even get it out in base 10 as Firefox complained the string was too long for the Developer Console.) In fact, I must admit I haven’t actually tested new BN("...", 36) as I conducted my tests with the original number that this is an export of, so the parser isn’t involved in this.

I’ve already shown several operations and their results, including several mathematically equivalent ways of computing the 8th power that produce different results in bn.js including both correct and incorrect ones. What other details would you like?

[fanatid]

If you paste JS example with BN and code which do same on python (bignumber native support) which demonstrate that result incorrect -- this will be great.

[astiob]

To be honest I still don’t understand what this gives you that I haven’t already provided, but here:

xhr = new XMLHttpRequest()
xhr.open('GET', 'https://gist.githubusercontent.com/astiob/091b8dbadf0698affb7a469e93450a0b/raw/2f13cc26872fd0d60787f23a2614bdd21156b730/base.base36')
xhr.onload = function () {
	console.log(new BN(this.responseText, 36).pow(new BN(8)).maskn(256).toString())
}
xhr.send()

import urllib.request
with urllib.request.urlopen('https://gist.githubusercontent.com/astiob/091b8dbadf0698affb7a469e93450a0b/raw/2f13cc26872fd0d60787f23a2614bdd21156b730/base.base36') as response:
	print(int(response.read(), 36) ** 8 & (1 << 256) - 1)

If you want to see the entire number, remove the masks, but the output will be huge.

[fanatid]

@astiob my request was related with easiest reproducing problem, it's hard dive into 3rd problem.

Can confirm bug in library, ping @indutny

I found that problem related with jumboMulTo (function was introduced by @alexeykudinkin in #27)

File for code: bnjs-issue211-sample.txt

const BN = require('bn.js')

// with jumboMulTo
new BN(require('fs').readFileSync('./bnjs-issue211-sample.txt', 'utf8'), 'hex').sqr().maskn(256).toString('hex')
// aea1a09f48cbf79860cfde07055249390b91e238605a5e79cddd4744610000

// with bigMulTo (jumboMulTo replaced to bigMulTo)
new BN(require('fs').readFileSync('./bnjs-issue211-sample.txt', 'utf8'), 'hex').sqr().maskn(256).toString('hex')
// 2ea1a09f48cbf79860cfde07055249390b91e238605a5e79cddd4744610000

bigMulTo result is correct...

[fanatid]

I think that multiplication with FFT should be disabled while problem is not solved. As @chjj done ^^^