C++ Prime Testing: Find & Fix Errors

In summary: This way you'll never lose precision due to overflow (inexact results).In summary, this function is not efficient because it's trying to compare a double to an integer which is not an exact value.
  • #1
Whovian
652
3
Alright. I know how incredibly inefficient this algorithm is, but I felt like giving this a whirl.

#include <iostream>
#include <cmath>
using namespace std;

bool prime(int x)
{
bool j = true;
for (double i = 2;i == x;i++)
{
if (x/i == floor(x/i))
{
j = false;
}
}
return j;
}

int main()
{
cout << prime(4) << endl;
return 0;
}

It returns "1" (true.) Why is this? Obviously, an error on my part.
 
Last edited:
Technology news on Phys.org
  • #2
This is one of the times I wish I could delete my own threads. I used = instead of ==. Still not working. Edited the original post.
 
  • #3
Whovian said:
This is one of the times I wish I could delete my own threads. I used = instead of ==.

Don't worry about it. It's a classic mistake. :wink:
 
  • #4
I managed to figure the new problem out, I used == when I should've used !=. These =, ==, and != are killing me! :)
 
  • #5
You can write it like this if you want.

Code:
for (double i = 2;i != x;i++)
    if (x/i == floor(x/i))
        j = false;

And you could do do it this way instead also

Code:
for (int i = 2; i != x; i++)
    if ((x % i)==0)  
        j = false;
 
  • #6
Now, for fun, I decided to see if I could make a perfect number tester. What's wrong with this function?

Code:
bool perfect (int x)
{
	int y = 0;
	for (double i = 2;i != x;i++)
	{
		if (x/i == floor(x/i))
		{
			y = y + i;
			}
		}
	return (y == x);
	}

Whatever I input, it returns 0.

EDIT: Figured it out. *bashes head against wall* I started counting factors at 2, not 1.

EDIT: And it's still looking for 33550336.
 
Last edited:
  • #7
Whovian said:
EDIT: And it's still looking for 33550336.

I don't know the specifics, maybe someone else can help me out about this, but I would think that a comparison between a double and an integer as a loop condition might be problematic.

Integers are exact values while doubles are approximate values.

It seams possible that as you add up i's as doubles, you might end up with a loss of precision enough that i != x when you would expect it to and you will get stuck in an infinite loop.

I just did a test and found that

2.0000000000000001==2 , but
2.000000000000001 !=2
 
  • #8
I just ran a test and found this out.
Code:
int x=2;
double y=2;

for ( int i=0; i < 29; ++i){
    y+=y;  //equivalent to y=y+y;
    x+=x;
}

if (x==y) 
    cout << "yes";

Turns out that after 29 additions
Code:
x==y
, but after 30,
Code:
x!=y

If you use the modulus operator then you will have no problems

Code:
(x % i) == //The integer remainder of x/i, which is zero if i is a factor of x.
 
  • #9
a/b == floor(a/b) is ugly to begin with. Those modulus operators don't exist for no reason. :wink:
 
  • #10
jreelawg said:
I just ran a test and found this out.
Code:
int x=2;
double y=2;

for ( int i=0; i < 29; ++i){
    y+=y;  //equivalent to y=y+y;
    x+=x;
}

if (x==y) 
    cout << "yes";

Turns out that after 29 additions
Code:
x==y
, but after 30,
Code:
x!=y
If you print out the value of x and y at each iteration, you mgiht be surprised as to which of x and y is accurate and which is not...
... but you shouldn't really be surprised that if x is a 32-bit signed integer, it can't hold a number bigger than 231.

On the other hand a double can hold integers up to about 252 exactly, so sometimes storing integer values in doubles wins over storing them in integers.

Try the same code with "long x = 2" (if your implementation uses 64-bit long integers) to see when that falls over. Actually, it might work beyond 52 iterations, because a double can hold integer powers of 2 exactly right up to the maximum value for a double, which is bigger than 10300. But C++ it won't necessarily print those values accurately to 300 digits precision, of course.
 
  • #11
"long long" is always at least 64 bits wide on any x86 arch, if not 128. Use long long if you need more range, but stay away from floating point numbers.

Use % to check for remainder. For example, if i % p == 0, then p divides i and i isn't prime if p is any number but i or 1.

Also, if you need guaranteed width, look at cstdint.
 
  • #12
TylerH said:
"long long" is always at least 64 bits wide on any x86 arch, if not 128. Use long long if you need more range, but stay away from floating point numbers.

In my experience, it's 64 bits on most compilers: http://gcc.gnu.org/ml/gcc/2004-03/msg01251.html.

"64 bits ought to be anything for anyone." - Me. :biggrin:
 
  • #13
When comparing doubles (floating point numbers in general), you should compare to within an error bound to account for small variances in precision.

Example:

Code:
double x, y;
epsilon = 0.000000005 // error bound

// some code assigning values to x and y

if(abs(x - y) < epsilon) // absolute value keeps the result of x - y positive for comparison with the error bound
{
  // they are 'equal', or close enough
}
else
{
  // they are not equal
}
 
  • #14
Hobin said:
a/b == floor(a/b) is ugly to begin with. Those modulus operators don't exist for no reason. :wink:

Oh! Modulus! Why didn't I think of that?
 

What is C++ Prime Testing?

C++ Prime Testing is a process of identifying and correcting errors in a C++ program. It involves running various tests on the code to find any bugs or issues that may cause the program to malfunction.

Why is C++ Prime Testing important?

C++ Prime Testing is important because it ensures the reliability and functionality of a C++ program. By finding and fixing errors, it helps to prevent crashes, unexpected behavior, and other issues that may arise during the execution of the program.

What are some common errors that C++ Prime Testing can detect?

C++ Prime Testing can detect a variety of errors, such as syntax errors, logic errors, runtime errors, and memory leaks. It can also identify issues with data types, variable declarations, and function calls.

How is C++ Prime Testing performed?

C++ Prime Testing is typically performed by using a combination of debugging tools, such as a debugger, compiler, and code analyzer. These tools help to identify errors and provide suggestions for fixing them.

Can C++ Prime Testing guarantee a bug-free program?

No, C++ Prime Testing cannot guarantee a bug-free program. It can help to identify and fix errors, but there may still be unforeseen issues that arise during the execution of the program. It is important to continuously test and refine the code to improve its reliability and functionality.

Similar threads

  • Programming and Computer Science
Replies
15
Views
1K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
22
Views
2K
  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
3
Views
701
  • Programming and Computer Science
Replies
13
Views
1K
  • Programming and Computer Science
Replies
6
Views
8K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
2
Replies
39
Views
3K
Back
Top