MikeMcl / bignumber.js

A JavaScript library for arbitrary-precision decimal and non-decimal arithmetic
http://mikemcl.github.io/bignumber.js
MIT License
6.68k stars 742 forks source link

squareRoot() produces incorrect result #276

Closed guidovranken closed 4 years ago

guidovranken commented 4 years ago
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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

@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

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 commented 4 years ago

Great project!

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