Hello, I am new to this forum. I am hoping to have some feedback I am having problems in checking whether a number,X is a X=pow(j,2) of some number. I have written codes that can do such a thing but it consumes a lot of time/resources in calculating large number. So it lags there. It works fine for small numbers, but the problem occured when finding square root for 6 digits numbers. The structure of the program is actually;

1) User input the digits number. eg: Input: 4, then the program will check one by one all 4 digit number from 1000 - 9999 whether it is a sqrt or not.
2) When a sqrt number is found, print the number.

My codes runs like this;


Can anybody suggest me a better solution? Thanx

I'll give you my thoughts specifically about using this method for finding which 6-digit decimal integers are perfect squares. If you find this useful, then it will be your job to generalize it for other ranges of numbers.

First of all, why don't we get a feel for what is the smallest number whose square is a 6-digit number and what is the largest number whose square is a 6-digit number?

Well, 100000 is the smallest 6-digit number and 999999 is the largest 6-digit number.

Let's look at a few facts that don't require (much) calculation:

10 squared = 100, which is the smallest three-digit number.
100 squared = 10000, which is the smallest five-digit number.
1000 squared = 1000000, which is the smallest seven-digit number.

What can we say about numbers whose squares are 6-digit numbers?

From the above short list, isn't it clear that they must be larger than 100 and smaller than 1000? (The only programmatically interesting problem is how to generalize this, but for now, let's just make a program based on this knowledge).


Therefore, for the inner loop (where you are iterating j and testing to see if j*j is exactly equal to x):

You never need to start with j less than 100, and you never need to go to j larger than 999.

Furthermore, if you find that a number, x, has j as its square root, you know that numbers larger than this value of x will have numbers larger than this value of j as their square roots. (So after finding a number that is a perfect square, the next test loop(s) can start with a value of j that is equal to one more than this value of j)

Furthermore, if you are in the test loop and you find that j*j == x, you can break out of the loop as soon as you print the value, since it's silly to continue testing any more values of j after you get the answer for that value of x.

So the algorithm for 6-digit numbers could look something like this:


Try it. See if you get all 682 numbers whose square is a six-digit number. Now, maybe the loop limits can be refined somewhat (to reduce the total number of iterations), but I think the limits that I used can be derived from the input data without much programming effort. Use whatever you think is appropriate. You may be able to make it more elegant, more efficient, just plain prettier, but the first goal, in my opinion should be to see if it works (and to understand how it works).

Now, go back and see if you can come up with a way (first manually, then in a program) to do the following:

Given n, the number of digits in the numbers you are testing, determine xmin and xmax for your program. Determine reasonable values for jmin and jmax (without any complicated mathematical calculations). Do it with pencil and paper. Be specific about what the loop limits will be for 2-digit numbers, 3-digit numbers, 4-digit numbers, etc. (but don't use a calculator).

Regards,

Dave

Wow! I am really getting a very good reply for this thread. Dave, your elaborations are precise, thoughtful and well understood. Yeah, I did my first mistake for not breaking the loop when I already got the answer. And programmer's worst enemy, the sillyness of codes really kills... It didnt occured to me that I can actually reduce the count enormously by reducing the sqrt range of a given digit. sqrt(start) ---> sqrt(end)... Duhh~~ Now, it seems to me that this shall work more quicker than mine. Okay Dave, keep up the great effort helping helpless ppl, like me.... Thanx a bunch!

Another thing you can do to reduce the loop is only loop until
j*j > X no matter what j is.

__________________

Age is unimportant -- except in cheese

I agree. That's a good point, and it makes a real difference when you get to the 6837 8-digit and 21623 9-digit perfect squares. My point was to refine the Original Poster's plan by reducing the ranges of the loop limits, but it wasn't the ultimate (obviously).

So, what I learned here is, just because someone points out some good stuff, don't stop looking; there may be more, even better, stuff.

Regards,

Dave

Yes Dave, I will always ponder upon that. After refining my codes, it then able to compute for 6 digits number increasingly faster. Phew!! It will always be a challenge to find a faster solution for a problem, but its always intriguing. The refine codes are;



Am I doing it correctly? Thanx!

Does it work?

Here's the way I might have done it, after applying Walt's suggested improvement:


(Note that you don't need a separate calculation for jmin. Note that you don't even need jmax,as I indicated in my first post. I just put that in there to try to give you a feeling of why your program was doing way too much work.)

This is just a suggestion. There are, obviously other ways. Some ways of implementing this are more efficient than others. This is just a suggested blueprint for one approach to the problem. Even if you like it, you shouldn't try to implement it line-by-line as it is shown. The loops can be for(){} loops, while() {} loops or do{}while(); loops. Use whatever seems "natural" to you.

If you understand how and why such a thing can work, then take a shot. If you see a way that is more clear to you, then do that first and worry about optimization later.

Regards,

Dave

Hey Dave! Hahaha...at last I did it using only one for loop. it goes like this;



But still I dont know what's the consequences, yet for the moment it runs okay...Phew! Anyway, I am still open for any suggestions or comments.

__________________

Age is unimportant -- except in cheese

I guess the joke is on me alright.

By the way, the code that you posted certainly doesn't "run OK."


The variable i doesn't change in the loop, and you don't show where j is initialized (but that's irrelevant, since j is not used in the loop).

As far as the methodology, I somehow thought you were given the integer trial-and-test method of your first post, and I was trying to get us to look a little at the quantities involved to see what could be done to improve the efficiency. That "insight" thing.

As I look again at the problem statement from your first post:

It really doesn't make sense, since all non-negative integers are the square root of some integer. (I guarantee 1000 is the square root of something and I don't need a computer to tell me that; I guarantee that 1001 is the square root of something; etc.)

Next time, maybe I will read the problem more carefully before jumping on a proposed solution.

As far as using floating point arithmetic and expecting exact values, well sometimes it works and sometimes not. Your "rounding" step, of course doesn't "round" anything; It truncates any fractional part.

So, I wish you well in completing your assignment, but I guess I wasted a lot of board bandwidth trying see how to refine your effort when the solution was something quite different.

Regards,

Dave

P.S.
Note that code tags consist of [code] before the first line and [/code] after the last line. (Not [\code].) With C code, the syntax is nicely highlighted if you use [c] and [/c] instead of "code" and "/code"