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

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### 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(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!

dark_dragon
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(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

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### 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:

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?

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

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

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)`

Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

### 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;

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### 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 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?

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 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).

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Axidos
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 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.

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### 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(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?

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

### 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(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.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### 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.

Rubys
Posts: 7
Joined: Thu Mar 11, 2010 2:42 pm UTC

### 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++

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.
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.

Return to “Coding”

### Who is online

Users browsing this forum: No registered users and 9 guests