20

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.

Improve this question
2
  • maybe it's just me, but I'd solve this in Python which has native bignums and is much easier to use than Java; and then I'd pick a challenge which is much more "Javascripty" than this one, maybe something like drawing using HTML5 canvas elements. Commented Jun 6, 2015 at 2:24
  • 3
    You can keep your numbers as an array of digits and then just write functions to do math this way (the old fashioned way you learned to do math in elementary school). Commented Jun 6, 2015 at 2:26

5 Answers 5

Reset to default
21

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;

or

var b = BigInt('22222222222222222222222222222222');

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

1 + 1n

will throw an error.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

17

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");
Improve this answer

1 Comment

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.
1

Surprisingly, sticking all the values in an array and adding them all together and just taking the first 10 digits worked. I must have had a typo somewhere in my code when it didn't work before.

I'm sure that doing something this simple wouldn't work in all cases (like those @AlexMcmillan and @zerkms have been debating about). I think the safest bet is the BigInteger library mentioned by @bhspencer, but it seems like adding the first x significant digits with y digits as a buffer might also be worth a shot in some cases.

Improve this answer

1 Comment

This works nearly all of the time. All common implementations of JS use 64-bit floats to represent numbers, which gives you about 15 significant digits. So your top 10 digits will be correct when the top 10 digits of the exact sum aren't followed by enough consecutive '9' digits so that the computed result rounds the trailing nines up to make your result off by 1 in the tenth digit.
1

I did this using an array and updating all entries with a function.

function f(a) {
  for (let i = 0; i < a.length - 1; i++) {
      a[i + 1] = a[i + 1] + parseInt(a[i] / 10);
      a[i] = a[i] % 10;
  }
  return a;
}
// remember to init the array with enough elements for all digits
var a = Array(200);
a.fill(0);
a[0] = 1;

Here is a JSFiddle with the code for problem 20.

Improve this answer

1 Comment

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

You could always convert your sum to a string, rip out the . and grab the result - something like this:

var sum = 2384762348723648237462348;
sum = sum.toString(); // "2.3847623487236483e+24"

// Rip out the "."
sum = sum.substr(0, 1) + sum.substr(2);

// Grab the first 10 characters
var firstTen = sum.substr(0, 10);
Improve this answer

27 Comments

You are not going to get accurate answers by doing this.
@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 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.
@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.
@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. :)
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.