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.

Soviut
  • 88,194
  • 49
  • 192
  • 260
JEJoll
  • 547
  • 1
  • 6
  • 20
  • 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. – Jason S Jun 06 '15 at 02: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). – jfriend00 Jun 06 '15 at 02:26

5 Answers5

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.

Sunil Chaudhary
  • 4,481
  • 3
  • 22
  • 41
Qi Fan
  • 809
  • 1
  • 10
  • 27
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");
bhspencer
  • 13,086
  • 5
  • 35
  • 44
  • 1
    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. – JEJoll Jun 07 '15 at 15:52
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.

JEJoll
  • 547
  • 1
  • 6
  • 20
  • 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. – Mike Housky Aug 20 '22 at 01:16
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.

cheesehead
  • 29
  • 2
  • 2
    Project Euler explicitly states (every single time you solve a problem) that you should not post your solution publicly. – Jessica B Sep 15 '18 at 21:48
-1

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);
Alex McMillan
  • 17,096
  • 12
  • 55
  • 88
  • 12
    You are not going to get accurate answers by doing this. – bhspencer Jun 06 '15 at 02:29
  • 1
    @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. – zerkms Jun 06 '15 at 02:34
  • What if your integer is more than 15 digits long? – bhspencer Jun 06 '15 at 02:35
  • 1
    @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. – zerkms Jun 06 '15 at 02:35
  • 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 – Alex McMillan Jun 06 '15 at 02:35
  • @AlexMcMillan how about you take 15 not 10 digits and use `parseInt` in your solution? :-) – zerkms Jun 06 '15 at 02:39
  • "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` – zerkms Jun 06 '15 at 02:39
  • 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 – Alex McMillan Jun 06 '15 at 02:41
  • 1
    @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 Jun 06 '15 at 02:42
  • 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. – Tesseract Jun 06 '15 at 02:44
  • 1
    @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. :) – Alex McMillan Jun 06 '15 at 02:44
  • @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. http://jsfiddle.net/xdzb2t5o/ --- here is when your solution returns the wrong result. It wouldn't be the case if you've taken 15 digits. – zerkms Jun 06 '15 at 02:46
  • 1
    No, you always need all the digits. Doing 13 digits will not guarantee a correct result. – Tesseract Jun 06 '15 at 02:47
  • @SpiderPig 13 digits **would guarantee** a correct result if you need 10 significant digits of the result and if you add 100 numbers. – zerkms Jun 06 '15 at 02:48
  • 1
    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. – Tesseract Jun 06 '15 at 02:49
  • 1
    @SpiderPig oh, what was I thinking. Apologies, you're absolutely right. – zerkms Jun 06 '15 at 02:50
  • 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](http://jsfiddle.net/mszgu7no/) fails to do that. – Alex McMillan Jun 06 '15 at 02:52
  • I created an account at [the site](https://projecteuler.net/problem=13) and submitted the answer generated by my fiddle. It was correct. – Alex McMillan Jun 06 '15 at 02:56
  • @AlexMcMillan http://jsfiddle.net/mszgu7no/1/ here is how it can fail. First ten digits must be `9999999999` – zerkms Jun 06 '15 at 03:03
  • Aaaaah I see... comments are being retroactively deleted ;-) – Alex McMillan Jun 06 '15 at 03:03
  • Only the wrong ones are deleted. See the proof above. – zerkms Jun 06 '15 at 03:04
  • @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`. – Alex McMillan Jun 06 '15 at 03:06
  • @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. – zerkms Jun 06 '15 at 03:07
  • @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](https://projecteuler.net/problem=13) – Alex McMillan Jun 06 '15 at 03:14
  • "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. – zerkms Jun 06 '15 at 03:15
  • @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. – Alex McMillan Jun 06 '15 at 03:18
  • @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. – zerkms Jun 06 '15 at 03:18