Simplifying Radicals with a Simple Program

In summary: R == int(fR): print str(iRad) + " is a cube"else: print str(iRad) + " is not a cube"...the program printsIn summary, the program helps simplify radicals by breaking down cubes. However, for some inputs, the program fails to recognize a perfect cube. The problem is that I cannot seem to find a reliable way to check for the cube root, so the program fails for some inputs.
  • #1
computerex
68
0
Hello. I wrote a simple program that helps me simplify radicals:

Code:
#include <iostream>
#include <math.h>

typedef struct 
{
	unsigned int x, y;
}pair;

bool breakcube(unsigned int radi, unsigned short inx, pair& pr)
{
	unsigned int cb = 0;
	for (unsigned int i = 2; i < radi; i++)
	{
		cb=i;
		for (unsigned short j = 1; j < inx; j++)
		     cb*=i;
		for (unsigned int j = 1; j < radi; j++)
		{
			if (cb*j==radi)
			{
				pr.x = cb;
				pr.y = j;
				return true; 
				
			}
		}
	}
	return false;
}
int main()
{
	unsigned int   radi = 0;
	unsigned int   cb   = 0;
	unsigned short inx  = 0;
	char     buff[64];
	while(true)
	{
		std::cout << "\nEnter radicand ('quit' to terminate): ";
		std::cin >> buff;
		if (!strcmp(buff, "quit"))
		    return 0;
		radi=(unsigned int)atof(buff);  
		std::cout << "\nEnter index: ";
		std::cin >> inx;
		cb = (unsigned int)pow(radi, 1.0/inx);
		if ((double)pow(radi, 1.0/inx) == cb) // force the comparison
		{
			std::cout << "\nPerfect " << inx << " : "; 
			for (unsigned short i = 0; i < inx; i++)
			{
				std::cout << cb;
				if (i!=inx-1)
				    std::cout << " * ";
		    }
		    std::cout << " = " << pow(cb, inx);
			continue;
		}
		pair pr;
		if (breakcube(radi, inx, pr))
		   std::cout << "\n" << radi << " can be broken by: " << pr.x << " * " << pr.y;
		else
		   std::cout << "\n" << radi << " cannot be broken";
	}
	return 0;
}

The problem happens when you try to break a perfect cube. The funny bit is that it works for some cases, and it doesn't work for others. For example, if you input 8 with an index of 3, the program works as expected, and says that it has found a perfect square. However if you enter 64 (4*4*4) it fails to recognize the perfect cube. I have ran this through the debugger, everything should work as expected...
 
Technology news on Phys.org
  • #2
I'm having a bit of trouble following the code, but you can check if a number is a cube with

Code:
bool isCube(int n, int& root) {
  root = (int)(0.5 + pow(n, 1.0/3)); // Nearest integer to the cube root
  return root * root * root == n;
}

and you can check for divisibility by perfect squares with

Code:
void simplify (int radicand, int& factor) {
  factor = 1;

  // Check for factors of 2; replace operations with shifts for better speed.
  while (radicand%4 == 0) {
    radicand /= 4;
    factor *= 2;
  }

  // Check for odd factors
  int limit = (int)(sqrt(radicand) + .0001); // Add small constant to avoid rounding the wrong way on perfect squares
  for (int n = 3; n <= limit; n += 2) {
    if (radicand % (n*n) == 0) {
      radicand /= n * n;
      factor *= n;
      limit = (int)(sqrt(radicand) + .0001);
    }
  }
}

Of course directly factoring the number would probably be faster, because then you could stop work on 33812897387 when you hit 18,670 = isqrt(348586571) instead of 183,882 = isqrt(33812897387). A quick change to the above code could make that improvement.

Of course using a list of primes could speed things along as well.
 
Last edited:
  • #3
A quick look over it makes me think you're having rounding/casting issues.

Code:
cb = (unsigned int)pow(radi, 1.0/inx);
		if ((double)pow(radi, 1.0/inx) == cb) // force the comparison

If you cast a floating point value to an int, it doesn't round to the nearest number, it simply throws away everything after the decimal. This, coupled with the tendency for floating point values to be "close" (say, 3.99999999999 or 4.000000001 instead of 4.0), you're going to run into issues when doing the comparison the way that you are.

Try looking at the round() function, or maybe rethink how you're doing your check.

Hope that helps.
 
  • #4
Thanks for the replies guys. CRGreathouse, the program helps break down radicals of any index, so explicitly checking for a cube root is not going to work here. The problem is, I have tried stepping through the code using a debugger, string outputs, rounding, pretty much everything I can think off, everything should work as expected, but it doesn't. Bill_B, if it was some rounding problem, wouldn't it present itself for other indexes too? For simplicity's sakes, here's the problem demonstrated in python:

Code:
#! /usr/bin/python

iRad = int(raw_input("Enter cube: "))
fR = pow(iRad, 1.0/3)

if fR == int(fR):
   print str(iRad) + " is a cube"
else:
   print str(iRad) + " is not a cube"
 
  • #5
if it was some rounding problem, wouldn't it present itself for other indexes too?

It does. Try 4^6, for example. I'm sure there are others.

When I execute the program with an input of 64,3 - after this line -

Code:
 		cb = (unsigned int)pow(radi, 1.0/inx);

cb equals 3, not 4. (due to the truncation by the cast to int)

So when this line is executed -

Code:
  	if ((double)pow(radi, 1.0/inx) == cb) // force the comparison

you're comparing 4 == 3, so it doesn't see it as a cube.

I still stand by my original answer.
 
  • #6
computerex said:
Thanks for the replies guys. CRGreathouse, the program helps break down radicals of any index, so explicitly checking for a cube root is not going to work here.

That's what the rest of my post was for. The natural translation for nth roots instead of square roots:

Code:
int simplify (int radicand, int idx) {
  int factor = 1;

  // Check for factors of 2; replace operations with shifts for better speed.
  while (radicand%pow(2, idx) == 0) {
    radicand /= pow(2, idx);
    factor *= 2;
  }

  // Check for odd factors
  int limit = (int)(pow(radicand, 1.0/idx) + .0001); // Add small constant to avoid rounding the wrong way on perfect powers
  for (int n = 3; n <= limit; n += 2) {
    while (radicand % pow(n, idx) == 0) {
      radicand /= pow(n, idx);
      factor *= n;
      limit = (int)(pow(radicand, 1.0/idx) + .0001);
    }
  }
  return factor;
}

This assumes you have an integer power function. If not, code it:
Code:
int pow(int a, int b) {
  int c = 1;
  while (b > 1) {
    if (b&1)
      c *= a;
    a *= a;
    b >>= 1;
  }
  return c * a;
}

It's probably worthwhile, as before, to pull out any factors you find rather than looking only for divisibility by prime powers of large enough exponent. This way you stop the computation sooner and don't compute as many idx-th powers.
 
  • #7
Thanks for that. I am not accomplished at mathematical algorithms, so don't expect any good code coming from me. :)
 
  • #8
Here's the final program, in working condition. It might not be the fastest, but it helps nonetheless. CRGreathouse, your suggestions were great, but a bit over my head buddy. Bill_B, thank you as well.

EDIT:

Nope, false alarm. :( It certainly is better, it now recognizes 64 as a perfect cube, but it doesn't recognize 125...I am gloomy now.

Code:
#include <iostream>
#include <math.h>

typedef struct 
{
	unsigned int x, y;
}pair;

bool breakcube(unsigned int radi, unsigned short inx, pair& pr)
{
	unsigned int cb = 0;
	for (unsigned int i = 2; i < radi; i++)
	{
		cb=i;
		for (unsigned short j = 1; j < inx; j++)
		     cb*=i;
		for (unsigned int j = 1; j < radi; j++)
		{
			if (cb*j==radi)
			{
				pr.x = cb;
				pr.y = j;
				return true; 
				
			}
		}
	}
	return false;
}
bool isPerfect(int rad, int idx)
{
     double rt = pow(rad, 1.0/idx);
     rt = round(rt);
     if (pow(rt, idx)==rad)
         return true;
     return false;
}
int main()
{
	unsigned int   radi = 0;
	double   cb   = 0;
	unsigned short inx  = 0;
	char     buff[64];
	while(true)
	{
		std::cout << "\nEnter radicand ('quit' to terminate): ";
		std::cin >> buff;
		if (!strcmp(buff, "quit"))
		    return 0;
		radi=(unsigned int)atof(buff);  
		std::cout << "\nEnter index: ";
		std::cin >> inx;
		cb = pow(radi, 1.0/inx);
		if (isPerfect(radi, inx))
		{
			std::cout << "\nPerfect " << inx << " : "; 
			for (unsigned short i = 0; i < inx; i++)
			{
				std::cout << cb;
				if (i!=inx-1)
				    std::cout << " * ";
		    }
		    std::cout << " = " << pow(cb, inx);
			continue;
		}
		pair pr;
		if (breakcube(radi, inx, pr))
		   std::cout << "\n" << radi << " can be broken by: " << pr.x << " * " << pr.y;
		else
		   std::cout << "\n" << radi << " cannot be broken";
	}
	return 0;
}
 
Last edited:
  • #9
computerex said:
Here's the final program, in working condition. It might not be the fastest, but it helps nonetheless. CRGreathouse, your suggestions were great, but a bit over my head buddy.

Your problem is almost certainly with rounding. At this point

Code:
bool isPerfect(int rad, int idx)
{
     double rt = pow(rad, 1.0/idx);
     rt = round(rt);
     if (pow(rt, idx)==rad)
         return true;
     return false;
}

output rad, rt, and pow(rt, idx) and see how they look. My best guess is that pow(rad, idx) is wrong since it's a floating-point number which may not match rad exactly; my second guess is that rt is rounded wrong.
 
  • #10
Ah!
pycb.png

This seems to fix the problem!
Code:
bool isPerfect(int rad, int idx)
{
     double rt = pow(rad, 1.0/idx);
     rt = round(rt);
     if (round(pow(rt, idx))==rad)
         return true;
     return false;
}

Thanks! Can someone confirm to make sure?
 
  • #11
computerex said:
Thanks! Can someone confirm to make sure?

It looks good, and tests good for all 32-bit values with index up to 10 million.
 

What does it mean to simplify radicals?

Simplifying radicals means finding the simplest form of a radical expression, where the radical is no longer present in the denominator or under another radical.

Why is it important to simplify radicals?

Simplifying radicals can make expressions easier to understand and work with. It also allows for easier comparison and manipulation of expressions.

How does a simple program help with simplifying radicals?

A simple program can provide step-by-step instructions and automate the process of simplifying radicals, making it faster and more accurate.

What are the basic steps for simplifying radicals using a simple program?

The basic steps for simplifying radicals using a simple program include: identifying the index and radicand, factoring the radicand, simplifying any perfect squares, and rewriting the radical in its simplest form.

Can a simple program simplify all types of radicals?

Yes, a simple program can simplify all types of radicals, including square roots, cube roots, and higher index radicals. However, the program may require some manual input for more complex radicals.

Similar threads

  • Programming and Computer Science
Replies
6
Views
8K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
3
Replies
75
Views
4K
  • Programming and Computer Science
2
Replies
39
Views
3K
  • Programming and Computer Science
Replies
14
Views
4K
  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
30
Views
2K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
3
Replies
73
Views
4K
Back
Top