Long Doubles Aren't Long Enough
Teaching myself C++ by doing various exercises from around the 'Net, and I came across Project Euler. Awesome site, but I'm stumped on even where to begin on a couple of the problems.
I'm absolutely NOT looking for actual code, just a general idea of if my idea will even work.
The problem is to find the first ten digits of the sum of an arbitraily large number of 50 digit numbers.
Mind, if it was a simple matter of rounding, then fine, whatever, run with a bunch of long ints, or long doubles, but this site, they want exact values.
I THINK, but only think mind, that I can maybe do this as a form of string arrays, but that's where my brain breaks down. I know a string can be any length I want to make it, so long as my PC has enough memory to hold it all, so that fixes the length of the number problem, but then how in the world do I do math with string literals?
Is this even a valid line of thought, or am I barking up the wrong tree entire?
I'm absolutely NOT looking for actual code, just a general idea of if my idea will even work.
The problem is to find the first ten digits of the sum of an arbitraily large number of 50 digit numbers.
Mind, if it was a simple matter of rounding, then fine, whatever, run with a bunch of long ints, or long doubles, but this site, they want exact values.
I THINK, but only think mind, that I can maybe do this as a form of string arrays, but that's where my brain breaks down. I know a string can be any length I want to make it, so long as my PC has enough memory to hold it all, so that fixes the length of the number problem, but then how in the world do I do math with string literals?
Is this even a valid line of thought, or am I barking up the wrong tree entire?
A lot of Project Euler problems expect you to be able to work with big integers. Since C++ doesn't support them natively, it would be worth your time to learn how to use GNU MP (through its C++ interface: http://gmplib.org/manual/C_002b_002b-Class-Interface.html ) or some other similar library.
Last edited on
| then how in the world do I do math with string literals? |
| A lot of Project Euler problems expect you to be able to work with big integers |
@Cubbi Not the most... open structures in the world. If I was a bit more versed, I might be able to use it easily, and then love it. As it is, I have NO idea what to do with it.
@IceThatJaw unsigned long long is maxed out at 18,446,744,073,709,551,615, or 20 digits, less than half the needed resolution. Really, only about 19 digits, since the top digit is effectively binary.
Might work for the second idea I have, split the long-@*%$ number up into five groups of numbers of 10 digits, add the right most group together, take the newly generated however long digit number, cut the last ten digits off the back (since they are no longer needed, after all), add the front end numbers into the next group, repeat until I have the final front ten digits.
@ne555 I know I can do some "math" with strings, say by coding, "Hello " + "world!", and end up with a single string "Hello world!". By that logic, "222" + "333" isn't going to be "555", it'll be "222333". Am I wrong? If I'm right, then I can't actually do real math with the string literals, I have to convert them back into integers, floats, whatever. See above for that possible idea chain.
@IceThatJaw unsigned long long is maxed out at 18,446,744,073,709,551,615, or 20 digits, less than half the needed resolution. Really, only about 19 digits, since the top digit is effectively binary.
Might work for the second idea I have, split the long-@*%$ number up into five groups of numbers of 10 digits, add the right most group together, take the newly generated however long digit number, cut the last ten digits off the back (since they are no longer needed, after all), add the front end numbers into the next group, repeat until I have the final front ten digits.
@ne555 I know I can do some "math" with strings, say by coding, "Hello " + "world!", and end up with a single string "Hello world!". By that logic, "222" + "333" isn't going to be "555", it'll be "222333". Am I wrong? If I'm right, then I can't actually do real math with the string literals, I have to convert them back into integers, floats, whatever. See above for that possible idea chain.
Last edited on
Yep, to do math with strings you will have to convert them to doubles using atof or a stringstream. Sounds like a nightmare to me.
I am familiar with Euler himself but not these problems. It seems like they are suited for 128-bit machines. lol
I am familiar with Euler himself but not these problems. It seems like they are suited for 128-bit machines. lol
If you want to work with digits only, why don't you use an array? I like working with cstrings because you can input a string into a variable easily, and you can easily convert a character to an integer...
For instance, if you want to practice the addition algorithm we learned in school and never told it was called an algorithm until university, then you could use arrays for simplicity...
For instance, if you want to practice the addition algorithm we learned in school and never told it was called an algorithm until university, then you could use arrays for simplicity...
Last edited on
@ToniAz I had thought about that, maybe a multi-dimensional array, then I realized it wouldn't work the way I would want after the 1's digit. There are 100 numbers to process through, so theoretically even if I had an array like int myArray[100][50] (100 elements for the hundred numbers, 50 elements for the digits) by the time I finished adding up just the 1's column I could easily have a tens displacement of 99. Then the 10's added up could easily be over a 1000 hundreds, and it only gets bigger as I run each additional digit.
I thank you all for the assist, and I'f I have any further issues, I know where to ask. Thanks again!
I thank you all for the assist, and I'f I have any further issues, I know where to ask. Thanks again!
Topic archived. No new replies allowed.