## I wanted to see square roots without decimals

## I wanted to see square roots without decimals

(OP)

I wanted to see square roots without decimals (=all decimals are zero) in a range of 1 to 2000

as I did not find a routine I coded this

It works, but perhaps that can be done shorter/easier....

Regards

Klaus

Peace worldwide - it starts here...

as I did not find a routine I coded this

#### CODE -->

*Calcmem.prg *Calculate and show square numbers within range 1 to 2000 Clea Set Decimals To 0 ? "Number............SQRT" For i = 1 To 2000 _Calcmem = i If Sqrt(_Calcmem)=Int(Sqrt(_Calcmem)) ?_Calcmem, Sqrt(_Calcmem) Endif Endfor

It works, but perhaps that can be done shorter/easier....

Regards

Klaus

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

You may want to try this

## CODE -->

hth

MarK

## RE: I wanted to see square roots without decimals

that's better.

because your code = one line shorter, and when I spread the scope to 20,000,000 the result about 2 seconds faster than mine.

Klaus

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

The faster speed is not the result of the absence of that one line - it is the result of the value of i NOT being stored to _Calcmem at each step through the loop

## CODE -->

hth

MarK

## RE: I wanted to see square roots without decimals

I did see it, but did not explain it that way exactly in my answer

I played at first only with _calcmem and then continued because I wanted to use it in a code.

Now I can not imagine for what this system-variable could be good for.

Any idea?

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

First thing I ask myself: Why even use _Calcmem? Its not a specially accelarated variable, it only plays a role as the "memory" of the calculator window.

I also saw you using _diarydate in a previous post. Why? Who has told you to use these system variables? Do you think because they already exist and don't need to be declared, that's giving you a performance advantage? They are bound to system windows of VFP, the calculator and the calendar, and used there. That rather means exra work for these windows to update, if you change the variable values, even if the windows are not visible, you trigger controlsource behavior of invisble windows, which takes extra time for nothing.

Just use normal variables, Klaus, the only use of _Calcmem or _Diarydate is for usage with those windows, if those windows are made visible. If the windows they are defined for are not visible they have a disadvantage barely used as memory variables.

But maybe what you wanted to learn has nothing to do with optimal performance at all, regarding the performance, the bigger sin is to check all the non-squares. Why? Simply turn the problem around: If you want to calculate squares up to 2000, then don't iterate all numbers and test whether they are perfect squares, just go the other way around. Compute squares until a square becomes larger than 2000.

## CODE

Notice perfect square is just a fancy term for square number, which points out it's a square of an integer, so its square root also is an integer. See https://en.wikipedia.org/wiki/Square_number

That the squares of an integer by definition have that integer as square root, and that square root has no decimals, means you don't need to check that, you already know it as you put it in a the outset.

All numbers between these perfect squares are not even checked and you save a lot of processing time and iterations. It's even cheaper to once compute the too high square number instead of computing the sqrt(2000) as the upper limit of a for loop. Because sqrt() is a complexer calculation than multiplying. Also, your code won't be optimized by some intelligent optimization algorithms of compilers, that notice the sqrt calculaton could stop at the momemt it encounters the first decimal place<>0. That's something you may expect when programming in C/C++ or also .net languages, perhaps, but I doubt even those compilers are that advanced to discover context of the overall code and make conclusions. Even if you had a function at hand, that would calculate a whole square and a rest, that won't be faster than simply computing the squares.

It's not measurable by seconds(), or simpler said your original code also produces its output faster than you can read it, but take the limits up and you get into territory where it really matters.

The major learning from performance point of view is, that it often pays to think of the inverse problem.

I don't know if you know about the Sieve of Erathostenes. It's a very iconic example of this inversion. Instead of testing whether a number isn't prime by finding a factor of it, you compute the primes by eleminating all multiples of them and exclude them from further investigtion thereby. For the simmple use case to check just one number to be prime, it is over the top to compute all primes lower than it including that prime, but when you want to generate all primes below some upper limit, that's the perfect way to do it.

So as last final conclusion, if you wanted to write a function that checks whether a number is a perfect square, then I'd test whether the square of the rounded square root is the original number. That a result has no decimals may only be a cause of approximation, if you go into the range of very hight numbers.

For example:

## CODE

Your check will tell 100000001 is a perfect square, because the non rounded result sqrt(100000001) is the same as the rounded Int(Sqrt(100000001)), but that's just luck, bad luck or good luck depends on your point of view. And this already happens far from the end of the range of numbers supported by integer. 10 million is far less than a few billion.

It is best to check whether the Int(sqrt(X)) squared actually results in X again.

So a good square root check function would be

## CODE -->

It can also report wrong results, once the precision of x in floating point is 2 or higher. If you want a function to only return verifiable truth, then it would also need to check whether its own calculations are within the number range that allow perfect results, i.e. such a function should know the limit of numbers it can verify, which would be at about 2^53.

You can see it this way:

## CODE -->

Clearly n+1 is not n, but at about 2^53 you reach the precision of double floating point to be higher than 1, so that 2^53+1 is converted to the same floating point representation as 2^53 and so VFP tells they are the same, as the comparison isn't comparing the expression 2^53+1 and 2^53, which clearly differ, but it compares the results, which are the floating point representations of these expressions after the expressions are compiled and operations are executed. You can't even trust when r*r=x that it exactly hits x and not x+1 or x-1, if r is beyond that limit. So numbers above 2^53 would need more precise data types to be able to verify them.

Chriss

## RE: I wanted to see square roots without decimals

thanks for your comments.

That's what I indeed thought. I had never used this variable before. to find out, what happens I used it in a loop.

That is correct - I always thought that the use of system-variables could increase the speed within VFP. Now I now it better....

.

Again you were right. I tested a loop for a scope from 1 to 20,000,000 and the speed is much more higher than before.

Consumed time including listing of the results

My prog:

31,8secwithout storing always in _calcmem30,7 sec(Mark adjusted it)your prog.

6,3 sec.very educational!that shows indeed when you said

***

Yes, and I am sad that my name is not

Andrew Wiles.Fermat's Great Theorem was formulated by Pierre de Fermat in the 17th century, but was not proven until 1994 by Andrew Wiles.

(I have a book about that).

In our language is that theorem known as "Fermat'sche Vermutung"

Your comments about the limits in precise calculation were also very good explained by your examples.

If possible your comment would be more worth than one star....

Regards

Klaus

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

You seem to have a rather slow machine - 25 000 000 iterations - 10 sec my code - 8 sec Chris's code

## CODE -->

Enjoy

MarK

## RE: I wanted to see square roots without decimals

My fault was, that I tested all 3 programs as one, obviously I confused one seconds()-statement there.

And ...no I have a fast computer (Intel 7, 64 GB) and your program shows a result in 8,6 seconds for a 25 mio-range.

Forgive me, please

Klaus

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

Almost no number is a square, but there is the simple formula of i*i to compute them. It can even be done faster, when you know each square is the sum of all odd integers. Most of the time really goes into output of the numbers. If you really want to see what time difference is in the actual computation, only do that part.

Here's using both i*i and adding odd numbers in the first two loops, then Klaus or your amended code to do the same with SQRT(i) = INT(SQRT(i)) verification.

## CODE

To spare the time waiting for Klaus or your amended code to finish, I defined f3 to let you see how large i is and what percentage of UPPERLIMT that covers. So after it takes a few seconds and seemed to have got stuck, just press F3 to see how large i currently is. Make sure you can break the code with ESC.

Is it really that hard to see how much more sqrt() computations you have to do when going through every integer? Alone between 16 and 25, all the numbers 17 to 24 are not square and you compute 9 sqrt() twice just to see they don't result in an integer. The percentage of unnecessary computations rises drastically, it becomes almost 100% of what the code does, therefore it also can only crunch a very small percentage of that range.

One thing you can clearly say: You computed a lot of square roots within the same time my code takes to compute all squares in the given range, and that processing power used within the same time is quite the same, just what the CPU can do within that time. But the results of finding perfect square numbers are deminishing, as the effectivness is exteremely low.

Chriss

## RE: I wanted to see square roots without decimals

_{Only 4,472 integer square numbers can be found in the first 20,000,000 integers.}I.e. only

0.022%For the first

40,000,000integers there are 6324 integer square numbers to be foundI.e. only

0.00016%Klaus

Peace worldwide - it starts here...

## RE: I wanted to see square roots without decimals

## CODE -->

You're of course right. I should have revisited my algebra classes.

Not quite right: The square of N is the sum of the N first odd integers starting with 1

e.g.

2*2 = 1 + 3

3*3 = 1 + 3 + 5

4*4 = 1 + 3 + 5 + 7

5*5 = 1 + 3 + 5 + 7 + 9

6*6 = 1 + 3 + 5 + 7 + 9 + 11

...

MarK

## RE: I wanted to see square roots without decimals

It doesn't need all the induction steps, as you can see it simply from the binomial formula for (a+b)^2 = a^2+2ab+b^2 used with a=n and b=1: (n+1)^2=n^2+2n+1, so the difference between n^2 and (n+1)^2 is 2n+1, which is the formula for an odd number. Then it's only a matter to start at n=0 so you see that for n=1 you need to add 2*0+1=1, then 2*1+1=3, 2*2+1=5, etc. And so n^2 is the sum of the first n odd numbers.

Chriss

## RE: I wanted to see square roots without decimals

Well, for square numbers it is easy to see how many there are in a range, because we know n^2 is the nth square number, in a range from 1 to N=n^2 you have n squares, in general, sqrt(N) tells you the number of squares, even if N isn't a square itself, when you round that down down, i.e. floor(sqrt(N)) is the number of squares you find in 1..N, even when N is not a square itself, this functions just increments by 1 whenever N reaches the next perfect square number.

In the big picture, you don't need to round down for the estimation, and then the percentage of squares from 1 to N simply is the number of squares sqrt(N) divided by the size of the range N, that is sqrt(N)/N and that rapidly decreases, as N grows stronger than sqrt(N), actually you can simplify this to 1/Sqrt(n), which clearly shrinks down with n getting larger.

Chriss