squareRoot() produces incorrect result

[guidovranken]

BigNumber.config({ EXPONENTIAL_AT: 10000, ROUNDING_MODE: 1 })
console.log(new BigNumber(new BigNumber("1900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001").squareRoot().toFixed(0)).toString());

This prints:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

but it should print:

52838058721772159177448907333242226474676273722824546318056365201184268980770050127260547419911003155460331597669032975718351095515936750613608507339331776175023257016677603122334856843636331424934221702706434483795689452927254977366615861404912014153171265016178675912153501046651190150158175216157592434074951993530283151051720611396029746176714002726368104372467558168233383940353698361967551818352819655853644037240032773557290413186403950050146284773147068223203417558998005563506178922228538616483233197658941088135584621960807585123307716639270625934232487732806807737724428406573039023236495491805666652184446483881693612746271634261577344708465537701138496743142136570782775020124483839410770840606946051907927184703188078364708992678248074102814112105806298450223418232068897786551226364110895291587250241802870684197672922365551263705633361655940536021198306288686568278664270461385527150021134760542207000000000000000000000000000000000000000000000000

[MikeMcl]

No, it shouldn't print that.

It should print

43588989435406735522369819838596156591370039252324449368903441381595573282031580856561591558519445269056586212982742136295839927838261170121565608364174699009777529188794058900619967156631207402231024023243567359810484091999315007271878765

What software are you using to check the result?

There are limits to sqrt, but I am not sure where they are exactly.

I'll look into into it at some point. Thanks for the report.

[guidovranken]

I'm sorry, you're right, I copied the wrong number.

I'm using a fuzzer to verify cryptographic operations (including bignum calculations) across many different libraries. This particular bug was found while running Cryptofuzz on OSS-Fuzz.

https://i.imgur.com/c65WCzW.png

[MikeMcl]

Fixed in v9.0.1.

Do you have any further details or perhaps code to share regarding the tests that you have performed here?

Regardless, thanks again for the report, as this bug also affects my other library decimal.js.

Notes:
This bug was fixed by just changing a single character. It only appeared when taking the square root of a number with more than 308 integer digits when the digits were 19 followed by zeros for at least half the number of the remaining digits. The bug was caused by a difficult-to-foresee problem with the initial square root estimate, which for smaller numbers is instead performed with Math.sqrt.

[guidovranken]

@MikeMcl thanks for fixing it!

My project Cryptofuzz generates random numbers and performs the same calculation on those numbers in different libraries. Currently about 30 different libraries are supported: https://github.com/guidovranken/cryptofuzz/tree/master/modules

The harness code for bignumber.js is here: https://github.com/guidovranken/cryptofuzz/blob/master/modules/bignumber.js/harness.js

• It receives data in JSON (FuzzerInput)
• Parses the JSON
• Performs the calculation based on the specified operation
• Stores the result in FuzzerOutput

Cryptofuzz then compares the result to that of eg. OpenSSL, and alerts you if it finds a discrepancy.

What else would you like to know? If you would like to run it yourself, I can make a build script for you.

[MikeMcl]

Great project!

Thanks for the info. I'll take a good look when time permits.