Quote:Original post by apatriarca I have solved that problem using haskell that support big integers. Others have done the same thing. You can probably do it yourself if you like but I think there are others more interesting problems and the use of a library like GMP is acceptable.
That would be a total cop-out. What's the point in even attempting the problem if you're just going to use an existing big-int library? Then all you have to do is find the first ten digits, and load the numbers from a file (if you wanted to make things neat)
Where is the challenge in that? I'm not so interested in project Euler for the mathematics side of things, more for the chance to flex my programming muscles.
My favorite way of implementing big integer type classes is to not implement them at all. Instead, implement a polynomial class. This has much wider ranging implications, and after all, an integer in base 10 is simply a polynomial in x, with x=10. For example, the number 32484 = 3*10^4 + 2*10^3 + 4*10^2 + 8*10^1 + 4*10^0. the beauty of this is that every operation is the same, except that with "numbers in base k" all the digits have to be mod k. But this is easily solved once you've implemented polynomial arithmetic.
For example, let's try to multiply the numbers 37 and 64 in, say, base 13.
37 x 64 = (3*13^1 + 7*13^0) x (6*13^1 + 4*13^0) = 18*13^2 + 30*13^1 + 28*13^0
Now we have digits that need to be normalized since they're too large. We can do this with modular arithmetic.
28 % 13 = 2, so
28*13^0 = 2*13^0 + 26*13^0 = 2*13^0 + 2*13^1
As you can see, you're essentially just "carrying the 2". Continuing in this way you end up with the number
1*13^3 + 7*13^2 + 6*13^1 + 2*13^0 = 1762
(I hope I didn't make any stupid mistakes).
So basically you write a polynomial class, implement addition, subtraction, multiplication, and division (division is a little harder admittedly), and decide how to implement normalization (perhaps as a separate member function such as 'void normalize(int base)' is the most appropriate since this is, after all, a generic integer class.
One side-benefit of this approach is that if you store your coefficients in an std::vector or otherwise contiguous array of memory, you are set up perfectly to use the SIMD integer instructions such as PMULHUW etc.
I don't know that this is necessarily the -fastest- approach, but it's the coolest (IMO)
BTW, since this is for Project Euler, I can tell you that should you get further along in the problem set, a lot of the problems there will benefit from having a generic polynomial class handy. It's good to build up a project_euler library while you work on the problems, and you'll find that as you progress you'll use lots of the stuff you're previously written time and time again.
Quote:Original post by _Sauce_ Where is the challenge in that? I'm not so interested in project Euler for the mathematics side of things, more for the chance to flex my programming muscles.
I started project euler to learn haskell better and in that case there was no challenge at all with that language. A lot of other languages have similar built-in data type. I think it's important to learn to use the right tools in programming and in that case C++ isn't probably the best language to use. I think you should try to solve quickly the first few problems and start solving the harder and more interesting ones.
Quote:Original post by _Sauce_ Where is the challenge in that? I'm not so interested in project Euler for the mathematics side of things, more for the chance to flex my programming muscles.
I started project euler to learn haskell better and in that case there was no challenge at all with that language. A lot of other languages have similar built-in data type. I think it's important to learn to use the right tools in programming and in that case C++ isn't probably the best language to use. I think you should try to solve quickly the first few problems and start solving the harder and more interesting ones.
Well I figured I would do them in order of ID (I know they aren't necessarily arranged in order of difficulty) and I have completed the first 12 problems. It's just this one that has me stuck.
Thanks for the tip on the polynomial stuff, cache_hit. I'll analyse your post in a bit greater detail when I haven't had anything to drink ;)
Quote:Original post by cache_hit My favorite way of implementing big integer type classes is to not implement them at all. Instead, implement a polynomial class. [...] I don't know that this is necessarily the -fastest- approach, but it's the coolest (IMO)
...and since multiplication of polynomials is convolution of their coefficients, then by the convolution theorem you can do it in O(n log n) time using the FFT. :-)
(I should add that although this is super-cool, I think I've read that in practice the Karatsuba algorithm is faster.)
It seems to me that the "error" from the smaller bits is limited in how much effect it can have. If you add up only the first 13 digits, then the worst-case scenario is if the other 47 digits are all 9. ie:
3710728753 390 2102... (first number in the sequence for reference) 0000000000 000 9999...*100 is less than 0000000000 100 0000...
The only way for this effect to propagate into the first 10 digits is if the 3-digit sum of the middle column has a 9 in the hundreds decimal place, so that 9 will add with the 100 000 and flip a higher decimal place. In other words, check if
390 + 749 + 952 + ... = xx9xx.
Now this is unlikely (1/9 chance), but it could still happen. In that case, instead of summing the first 13 digits you could sum the first 14, then the same argument applies, except shifted over by 1, so you would need to do another 3 digit sum to check that
902 + 490 + 524 + ... =/= xx9xx
If that fails, just keep moving over by 1 digit until you find a block of 3 whose sum doesn't have a 9 in the hundreds place.
So you consider it cheating to use the big num class to solve this problem, but don't consider it cheating to go online and ask a bunch of people how to solve the problem?
Not sure if you realize it, but being able to assimilate a large software tool like GMP bigint into your project and effectively use it to solve a real-world problem (or even a BS one like the one on Project Euler), is not cheating. Its called software engineering and its a career.
Nobody writes all their computer code in a vacuum. Being able to integrate other people's software libraries/classes/tools into your projects and reach your own goals is the mark of a true professional. I vote that you take this opportunity to integrate GMP's bignum classes into your code as a learning experience, not as cheating.
I'm not at all asking for a solution, Steve_Segrato. I'm looking for tips.
Quote:Original post by Steve_Segreto
Not sure if you realize it, but being able to assimilate a large software tool like GMP bigint into your project and effectively use it to solve a real-world problem (or even a BS one like the one on Project Euler), is not cheating. Its called software engineering and its a career.
I'm aware of this, however I don't believe doing such a thing is in the spirit of the problem presented on Project Euler. In the real world I would happily go ahead and use an existing bigInt library (unless of course, I already had my own one which was better suited to the task at hand - unlikely), but for a learning exercise, I think it's perfectly acceptable to want to attempt to replicate the functionality of such a class. I know you don't have to know how a class works in order to use it well, but it's certainly nice to know how it works.
I've actually been working on some uni stuff, so I haven't had time to come back to this yet. I'll resurrect the thread when I've had another go at it. Feel free to continue discussing :)
