Extremely large numbers in javascript

javascript types numbers integer biginteger

40,726

Solution 1

You are going to need a javascript based BigInteger library. There are many to choose from. Here is one https://github.com/peterolson/BigInteger.js

You can use it like this

var n = bigInt("91942213363574161572522430563301811072406154908250")
    .plus("91942213363574161572522430563301811072406154908250");

Solution 2

Javascript recently got a new primitive data type BigInt (stage 4 proposal as of January 2020). https://github.com/tc39/proposal-bigint

Chrome, Firefox and few other browsers have started supporting this in newer versions (check compatibility here), while other browsers are still implementing it.

https://developers.google.com/web/updates/2018/05/bigint

Basically it can be declared using either literals like

var a = 1n;

var b = BigInt('22222222222222222222222222222222');

Math operators don't do auto conversion between BigInt and Number, so

1 + 1n

will throw an error.

40,726

Author by

JEJoll

Multimedia/Game Developer

Updated on March 25, 2020

Comments

JEJoll about 4 years
I'm working on the Project Euler problems (currently question 13).

For this question I have to find the first 10 digits of the sum of 100 numbers all of a size similar to this:
```
91,942,213,363,574,161,572,522,430,563,301,811,072,406,154,908,250
```
I think I could use something like Java's BigInteger, but I started solving the problems in JavaScript (I'm trying to boost my js abilities for work), and I would like to continue using it, even to solve this problem.

I'd like to stick to pure JS if possible.
bhspencer almost 9 years

You are not going to get accurate answers by doing this.
zerkms almost 9 years

@bhspencer actually if you take first significant 15 digits (which IEEE754 double precision number guarantees to be accurate) and summarize 100 of then then the extra gap of 5 digits will save you from inaccuracy. At least I cannot think of the case when the error might propagate further.
bhspencer almost 9 years

What if your integer is more than 15 digits long?
zerkms almost 9 years

@bhspencer as per the question you need to get the first 10 digits of the result. So it does not matter how long the initial numbers are.
Alex McMillan almost 9 years

Yeah using a biginteger library is probably the best bet, but this is a quick shortcut that doesn't have any external dependencies, and the accuracy won't be an issue with only the first 10 digits being required
zerkms almost 9 years

@AlexMcMillan how about you take 15 not 10 digits and use parseInt in your solution? :-)
zerkms almost 9 years

"and the accuracy won't be an issue with only the first 10 digits being required" --- it definitely might be an issue. Imagine 19 + 19 and taking one digit to get one digit of result. 1 + 1 == 2 whereas the correct answer would be 3
Alex McMillan almost 9 years

Yeah, but we're not dealing with 2 digit numbers... the inaccuracy you point to would be lost in the 5 digit "buffer" between the first 10 and the exponent
zerkms almost 9 years

@AlexMcMillan var firstTen = sum.substr(0, 10); - you're taking exactly 10 digits. To add 100 numbers precisely you need to have a safety "buffer" of at least 3 more digits.
SpiderPig almost 9 years

Imagine you add 89999999999999999999 and 10000000000000000001. In some cases the first digit of the result is affected by the last digits of the two numbers even if they are very long.
Alex McMillan almost 9 years

@zerkms We're not doing any math here - it's assumed that would have been done to produce the sum variable (hence the name "sum"). And the OP just wants the first 10 digits of the sum, so returning 13 or 15 digits is just... wrong. :)
zerkms almost 9 years

@AlexMcMillan you're not getting it. To get the 10 digits of the sum precisely the operands must be at least 13 digits long. Then you truncate it down to 10 significant digits. jsfiddle.net/xdzb2t5o --- here is when your solution returns the wrong result. It wouldn't be the case if you've taken 15 digits.
SpiderPig almost 9 years

No, you always need all the digits. Doing 13 digits will not guarantee a correct result.
zerkms almost 9 years

@SpiderPig 13 digits would guarantee a correct result if you need 10 significant digits of the result and if you add 100 numbers.
SpiderPig almost 9 years

So if you add 89999999999999999999 and 10000000000000000001 and you only add the first 13 digits you would have the guarantee that the first 10 digits of the result are correct? I don't think so.
zerkms almost 9 years

@SpiderPig oh, what was I thinking. Apologies, you're absolutely right.
Alex McMillan almost 9 years

I think you guys haven't understood the problem... The OP is not trying to add the first 10 digits of each number, he is trying to add ALL digits of each number, and get the first 10 digits of the final SUM. Tell me how this fiddle fails to do that.
Alex McMillan almost 9 years

I created an account at the site and submitted the answer generated by my fiddle. It was correct.
zerkms almost 9 years

@AlexMcMillan jsfiddle.net/mszgu7no/1 here is how it can fail. First ten digits must be 9999999999
Alex McMillan almost 9 years

Aaaaah I see... comments are being retroactively deleted ;-)
zerkms almost 9 years

Only the wrong ones are deleted. See the proof above.
Alex McMillan almost 9 years

@zerkms That's not a problem with my code... that's a problem with Javascript math. You'll note your sum is 100000000000000000000, of which my code successfully pulls the first 10 digits: 1000000000.
zerkms almost 9 years

@AlexMcMillan it's a problem with the solution - your solution produces the wrong result. It must have been 9999999999. Just because you've chosen the wrong tool does not qualify the solution as correct. The question was to add arbitrary length numbers and return the correct first 10 digits of the result. Your solution fails to do so, sorry.
Alex McMillan almost 9 years

@zerkms The creation of the large number (via summation) will potentially trigger overflow issues within Javascript, which is why my first comment says "using a biginteger library is probably the best bet". My solution successfully pulls the first 10 digits from a large number, using Javascript, as per the OPs question. I never claimed this handled the Javascript number issues.. it explicitly begins with an already-calculated sum variable. That being said, it still produces the correct answer for the project euler problem
zerkms almost 9 years

"My solution successfully pulls the first 10 digits from a large number, using Javascript, as per the OPs question." --- no it does not, I have provided you the case when your solution returns the wrong result. It produces the correct result for a particular project euler just by accident (just because they didn't intend to provide a combination that would produce a error significant enough to make IEEE754 computations crazy). In general the solution is wrong.
Alex McMillan almost 9 years

@zerkms your example provides the "large number" 100000000000000000000, of which my code successfully pulls the first 10 digits 1000000000. This was good debate but now it's going nowhere. I understand your point regarding integer overflow, but that is outside the domain of my solution. My solution BEGINS with the sum and ENDS with the first 10 digits of the sum. End of story, have a nice day.
zerkms almost 9 years

@AlexMcMillan nope, the sum of those 2 numbers IS NOT 100000000000000000000 (it's your broken solution thinks so - just take a calculator and check it's not correct). And it's not an integer overflow, there is no integer data type in ES at all.
JEJoll almost 9 years

I was actually able to come up with the correct answer just by adding all the values together directly. I must have had a typo in my code before. But I've accepted this answer because it seems the most reliable, and I doubt my simple solution would work in all cases--probably just a fluke.
Jessica B over 5 years

Project Euler explicitly states (every single time you solve a problem) that you should not post your solution publicly.