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

Postby Styhn » 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!

dark_dragon
Posts: 1
Joined: Mon Mar 29, 2010 3:57 pm UTC

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

Postby dark_dragon » 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

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

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

Postby Styhn » 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 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?

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

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

Postby joeframbach » 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)

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

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

Postby Dason » 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.
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++

Postby Styhn » 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?

User avatar
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++

Postby phlip » 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).

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

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

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

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

Postby Styhn » 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?

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

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

Postby troyp » 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.

User avatar
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++

Postby phlip » 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.

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

Postby Tirian » 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.

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

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

Postby Rubys » 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 :P no more "Find fibonacci number bigger than a million", heh
We could change the world, if we had the source code.

User avatar
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++

Postby Berengal » 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.
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 13 guests