Page 1 of 1

### Smart ways to solve an equation in C++

Posted: Mon Mar 29, 2010 3:41 pm UTC
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(3n-1)/2 holds.

Since I'm not very good at programming and computer-assisted 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!

### Re: Smart ways to solve an equation in C++

Posted: Mon Mar 29, 2010 4:01 pm UTC
isn't that the quadratic equation?

m=n(3n-1)/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++

Posted: Mon Mar 29, 2010 4:22 pm UTC
.. 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:

Code: Select all

`//check if m is of the form n(3n-1)/2 for some positive integer nbool 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?

### Re: Smart ways to solve an equation in C++

Posted: Mon Mar 29, 2010 5:14 pm UTC
Be careful when comparing floating-points.

Code: Select all

`#include <stdio.h>void main() {        double d = ((1.0/3.0)-(1.0/2.0-1.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)n1-n1==0)`
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

`if (fabs(x)<0.0001)`

### Re: Smart ways to solve an equation in C++

Posted: Mon Mar 29, 2010 6:16 pm UTC
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.

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 12:46 am UTC
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 novice-level programmer and don't have a lot of experience).

But I think the problem that I have now is not math related but rather code-based. 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?

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 1:07 am UTC
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 double-check 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).

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 3:36 pm UTC
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 double-check 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++

Posted: Tue Mar 30, 2010 4:47 pm UTC
No that's my fault. I made a typo; it should be 1/6 +- 1/3sqrt(24m-1) @ phlip: so what I could do is, if x = 1/6 +- 1/3sqrt(24m-1), check whether x(3x-1) % 2 == 0 right? But then my question remains; of what type should x be?

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 10:06 pm UTC
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.

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 10:33 pm UTC
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(24m-1) 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(24m-1), check whether x(3x-1) % 2 == 0 right?

Not really... what you want to figure out is that, if you were to calculate 1/6 + 1/3sqrt(24m-1) (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(24m-1) directly - you just want to figure out whether it'd be an integer or not.

As a hint: If (24m-1) isn't a perfect square, is it possible for 1/6 + 1/3sqrt(24m-1) to be an integer? If (24m-1) is a perfect square, is it possible for 1/6 + 1/3sqrt(24m-1) to be an integer? If so, when?

Remember, the square root of an integer is either another integer, or it's irrational.

### Re: Smart ways to solve an equation in C++

Posted: Tue Mar 30, 2010 10:46 pm UTC
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++

Posted: Tue Mar 30, 2010 11:11 pm UTC
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

### Re: Smart ways to solve an equation in C++

Posted: Wed Mar 31, 2010 12:43 am UTC
Rubys wrote:double (which has 64 bits)
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).

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.