Smart ways to solve an equation in C++
Moderators: phlip, Moderators General, Prelates
Smart ways to solve an equation in C++
I've decided to learn C++ a couple of days ago. To help me learn the language I've started to do a couple of Project Euler problems in C++. At the moment I'm working at problem 44 (http://projecteuler.net/index.php?section=problems&id=44).
As part of the solution I have to write a function that, given a positive integer m, finds an integer n such that the equation m = n(3n1)/2 holds.
Since I'm not very good at programming and computerassisted problem solving I was wondering if you guys could give me tips as to how efficient I could do this. Ofcourse, the most naive way of doing this is using a for loop where n starts at 1 and increments by one every iteration. However I have the nagging feeling that this could be done a lot quicker. Thanks in advance for any hints you guys could give me!
As part of the solution I have to write a function that, given a positive integer m, finds an integer n such that the equation m = n(3n1)/2 holds.
Since I'm not very good at programming and computerassisted problem solving I was wondering if you guys could give me tips as to how efficient I could do this. Ofcourse, the most naive way of doing this is using a for loop where n starts at 1 and increments by one every iteration. However I have the nagging feeling that this could be done a lot quicker. Thanks in advance for any hints you guys could give me!

 Posts: 1
 Joined: Mon Mar 29, 2010 3:57 pm UTC
Re: Smart ways to solve an equation in C++
isn't that the quadratic equation?
m=n(3n1)/2
or 0 = (3/2)n^2 + (1/2)n  m
whcih can be solved using http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula
m=n(3n1)/2
or 0 = (3/2)n^2 + (1/2)n  m
whcih can be solved using http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula
Re: Smart ways to solve an equation in C++
.. I can't believe I didn't realize that. This is my problem with programming; most of the time I'm so concerned with how I am going to design my program that I fail to see the most obvious solutions (programming courses at my university used to give me nightmares). Thanks for the hint!
But now I am presented with a new problem. I've created some pseudocode for my isPentagonal function:
But I have no idea how to check of what type the variables n1 and n2 are. Furthermore, how should I store them when I calculate the roots?
But now I am presented with a new problem. I've created some pseudocode for my isPentagonal function:
Code: Select all
//check if m is of the form n(3n1)/2 for some positive integer n
bool isPentagonal(int m) {
calculate n1 = 1/6 + 1/2*sqrt(24*m+1);
calculate n2 = 1/6  1/2*sqrt(24*m+1); //these are the roots of the equation 3/2n^2  1/2n  m = 0
if((n1 is of type int and n1 > 0) OR (n2 is of type int and n2 > 0)) {
return true;
} else {
return false;
}
But I have no idea how to check of what type the variables n1 and n2 are. Furthermore, how should I store them when I calculate the roots?

 Posts: 1478
 Joined: Sun Nov 05, 2006 12:49 am UTC
Re: Smart ways to solve an equation in C++
Be careful when comparing floatingpoints.
So, suppose n1=5.0000001, which might happen.
You would want to test but that won't work!
Depending on how much precision you expect from your calculations, your "Is x zero" test can be coded like this:
Code: Select all
#include <stdio.h>
void main() {
double d = ((1.0/3.0)(1.0/2.01.0/6.0));
if (d>0) printf("gt\n");
if (d==0) printf("eq\n");
if (d<0) printf("lt\n");
}
$ ./test
lt
So, suppose n1=5.0000001, which might happen.
You would want to test
Code: Select all
if((int)n1n1==0)
Depending on how much precision you expect from your calculations, your "Is x zero" test can be coded like this:
Code: Select all
if (fabs(x)<0.0001)
Re: Smart ways to solve an equation in C++
Styhn wrote:.. I can't believe I didn't realize that. This is my problem with programming; most of the time I'm so concerned with how I am going to design my program that I fail to see the most obvious solutions (programming courses at my university used to give me nightmares). Thanks for the hint!
One of the great things about project euler is that in a lot of the cases you should be more concerned with getting a nice clean solution to the problem than trying to brute force your way through it. After working on a problem for a while if you can't find a nice fast way to do the problem then chances are you're doing it wrong. Take a step back and try to find an obvious/unique way to look at things and it could make your life easier.
double epsilon = .0000001;
Re: Smart ways to solve an equation in C++
Dason wrote:Styhn wrote:.. I can't believe I didn't realize that. This is my problem with programming; most of the time I'm so concerned with how I am going to design my program that I fail to see the most obvious solutions (programming courses at my university used to give me nightmares). Thanks for the hint!
One of the great things about project euler is that in a lot of the cases you should be more concerned with getting a nice clean solution to the problem than trying to brute force your way through it. After working on a problem for a while if you can't find a nice fast way to do the problem then chances are you're doing it wrong. Take a step back and try to find an obvious/unique way to look at things and it could make your life easier.
You're very right about that, and it's something I have to learn when I code (I'm not a novicelevel programmer and don't have a lot of experience).
But I think the problem that I have now is not math related but rather codebased. The problem that I now have is that I want to store a store the value of a root in a variable (which will have to be a float or double I guess) but then I want to look of it's actually an integer. I have no idea how to do that, I think it requires knowledge of certain specific functions, right?
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Smart ways to solve an equation in C++
For pretty much all number theory, you want to avoid floats like the plague... stick to integer types.
Which means you need to be a little bit cleverer with how you do "is f(x) an integer" tests  you can't just calculate f(x) and check if it's integeral, because floats can be inaccurate. For instance, to check if a is divisible by b, you don't want to check whether a/b is an integer... but you can check whether a%b is 0, since that stays with integers (and you thus don't lose any precision).
So, what does it take for "1/6 + 1/2*sqrt(24*m+1)" to be an integer? Say you had a "bool isPerfectSquare (int n);" function; how would you code that check? And how would you code an isPerfectSquare function?
Also: I'd doublecheck that "1/6 + 1/2*sqrt(24*m+1)" equation, it doesn't seem to be correct (for instance, m=35 should give n=5, but it doesn't).
Which means you need to be a little bit cleverer with how you do "is f(x) an integer" tests  you can't just calculate f(x) and check if it's integeral, because floats can be inaccurate. For instance, to check if a is divisible by b, you don't want to check whether a/b is an integer... but you can check whether a%b is 0, since that stays with integers (and you thus don't lose any precision).
So, what does it take for "1/6 + 1/2*sqrt(24*m+1)" to be an integer? Say you had a "bool isPerfectSquare (int n);" function; how would you code that check? And how would you code an isPerfectSquare function?
Also: I'd doublecheck that "1/6 + 1/2*sqrt(24*m+1)" equation, it doesn't seem to be correct (for instance, m=35 should give n=5, but it doesn't).
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}

 Posts: 167
 Joined: Tue Jan 20, 2009 12:02 pm UTC
 Location: trapped in a profile factory please send help
Re: Smart ways to solve an equation in C++
phlip wrote:For pretty much all number theory, you want to avoid floats like the plague... stick to integer types.
What about decimal, e.g. C#'s implementation of it?
Also: I'd doublecheck that "1/6 + 1/2*sqrt(24*m+1)" equation, it doesn't seem to be correct (for instance, m=35 should give n=5, but it doesn't).
Maybe it's being interpreted incorrectly.
Re: Smart ways to solve an equation in C++
No that's my fault. I made a typo; it should be 1/6 + 1/3sqrt(24m1)
@ phlip: so what I could do is, if x = 1/6 + 1/3sqrt(24m1), check whether x(3x1) % 2 == 0 right? But then my question remains; of what type should x be?
@ phlip: so what I could do is, if x = 1/6 + 1/3sqrt(24m1), check whether x(3x1) % 2 == 0 right? But then my question remains; of what type should x be?
Re: Smart ways to solve an equation in C++
Axidos wrote:by Axidos » 31 Mar 2010, 01:36
phlip wrote:For pretty much all number theory, you want to avoid floats like the plague... stick to integer types.
What about decimal, e.g. C#'s implementation of it?
Is that like an exact version of floating point?
I think phlip was speaking in the context of mainstream languages. What you actually need is an exact type. For instance, some languages have exact rational types that would be suitable.
 phlip
 Restorer of Worlds
 Posts: 7573
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Smart ways to solve an equation in C++
Axidos wrote:What about decimal, e.g. C#'s implementation of it?
I'm unfamiliar with C#... would such a class be able to tell you that, say, a million is a perfect square, but a million and one is not? Without having to worry about potential rounding errors?
Styhn wrote:No that's my fault. I made a typo; it should be 1/6 + 1/3sqrt(24m1)
No, that's still not right (thanks, Axidos, I didn't know about that particular feature in Alpha).
Styhn wrote:@ phlip: so what I could do is, if x = 1/6 + 1/3sqrt(24m1), check whether x(3x1) % 2 == 0 right?
Not really... what you want to figure out is that, if you were to calculate 1/6 + 1/3sqrt(24m1) (or whatever the equation actually is), whether you'd get an integer answer. That doesn't mean you want to actually calculate 1/6 + 1/3sqrt(24m1) directly  you just want to figure out whether it'd be an integer or not.
As a hint: If (24m1) isn't a perfect square, is it possible for 1/6 + 1/3sqrt(24m1) to be an integer? If (24m1) is a perfect square, is it possible for 1/6 + 1/3sqrt(24m1) to be an integer? If so, when?
Remember, the square root of an integer is either another integer, or it's irrational.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Smart ways to solve an equation in C++
IME, if you're going to commit to PE, you should write yourself a fast isqrt function such that isqrt(n) is the largest integer whose square is less than or equal to an integer n. (Or probably a long integer or even whatever bigint solution you come up with.) You will be pulling that function out of your toolbox quite often.
Re: Smart ways to solve an equation in C++
Axidos wrote:phlip wrote:For pretty much all number theory, you want to avoid floats like the plague... stick to integer types.
What about decimal, e.g. C#'s implementation of it?
C#'s decimal is 128 bits, which means it's twice as accurate compared to double (which has 64 bits), you can still get rounding errors, but it's accurate enough. It should be enough for project euler.
I'm also going through euler, just started last week, solved 55 by now. And got stuck, cause things are hard now no more "Find fibonacci number bigger than a million", heh
We could change the world, if we had the source code.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Smart ways to solve an equation in C++
No, a double has 53 bits precision. If C#s decimal is an IEEE 754 quad then it has 113 bits precision, more than twice as much. Conversely, the range increase is relatively small, from 11 bits exponentials to 15 (which is again only three times more bits than a half, which is one eight the total bitsize).Rubys wrote:double (which has 64 bits)
Anyway, once you go floating point you generally lose all confidence in the exactness of numbers. Sure, their operations are exactly specified, but there are still rounding errors you can't track and numbers you can't represent exactly. This makes it very hard to do any kind of number theory where you need to be exact all the way.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Who is online
Users browsing this forum: No registered users and 7 guests