I wanted to see square roots without decimals 3

[german12]

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

*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...

 

[mjcmkrsr]

Hi Klaus,

You may want to try this

CLEAR

For i = 1 To 2000
	IF SQRT(i) = INT(SQRT(i))
		? i, INT(Sqrt(i))
	ENDIF 
Endfor 

RETURN

hth

MarK

 

[german12]

Thanks Mark,
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...

 

[mjcmkrsr]

Hi Klaus,

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

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

For i = 1 To 2000 && you have a variable i
	_Calcmem = i && why do you create a new variable and feed it with the value of i?
	If Sqrt(_Calcmem)=Int(Sqrt(_Calcmem))
		?_Calcmem, Sqrt(_Calcmem)
	Endif

Endfor

hth

MarK

 

[german12]

Yes, that is true.
I did see it, but did not explain it that way exactly in my answer

Calcmem_ = i && why do you create a new variable and feed it with the value of i?

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

 

[Chris Miller]

I don't know what you wanted to learn or test with this.

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.

Clear
? "Number............SQRT"
Local lnI
lnI = 0
Do While .T.
   lnI = m.lnI + 1 
   lnSquare = m.lnI*m.lnI
   If (lnSquare>2000)
      Exit 
   Else
      ? m.lnSquare, m.lnI
   Endif
Enddo

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

a square number or perfect square is an integer that is the square of an integer

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:

? sqrt(100000001),Int(Sqrt(100000001)), sqrt(100000001) = Int(Sqrt(100000001)), Int(Sqrt(100000001))*Int(Sqrt(100000001))=100000001

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

Function IsPerfectSquare(x)
r = floor(sqrt(x))
return (r*r=x)

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:

? 2^52+1 = 2^52 && prints .f.
? 2^53+1 = 2^53 && prints .t.

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

 

[german12]

Chriss,
thanks for your comments.

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.

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

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?

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

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

.

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,8 sec
without storing always in _calcmem 30,7 sec (Mark adjusted it)
your prog. 6,3 sec.

very educational!
that shows indeed when you said

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

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

 

[mjcmkrsr]

Hi Klaus

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

CLEAR

LOCAL lnS1, lnS2, lnI

lnS1 = SECONDS()

For i = 1 To 25000000
	IF SQRT(i) = INT(SQRT(i))
		? i, INT(Sqrt(i))
	ENDIF 
Endfor 

lnS1 = SECONDS() - lnS1

WAIT WINDOW " ... continues in 3 sec ..." TIMEOUT 3

CLEAR 

lnS2 = SECONDS()
lnI = 0

Do While .T.
   lnI = m.lnI + 1 
   lnSquare = m.lnI * m.lnI
   
   If (lnSquare > 25000000)
      Exit 
   Else
      ? m.lnSquare, m.lnI
   Endif

Enddo 

lnS2 = SECONDS() - lnS2

CLEAR

? lnS1, " - ", lnS2

RETURN

Enjoy

MarK

 

[german12]

Sorry Mark,
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...

 

[Chris Miller]

MarK try without outputting the numbers, then theres a much bigger time difference.

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.

#define UPPERLIMT 1e12

CLEAR

LOCAL i, lnS1, lnS2, lnS3, lnSquare, lnAdd

lnS1 = SECONDS()

lnSquare = 0
lnAdd = 1
Do While .T.
   lnSquare = m.lnSquare + m.lnAdd 
   If (m.lnSquare > UPPERLIMT )
      Exit 
   Else
      lnAdd = m.lnAdd+2
   Endif
Enddo
lnS1 = SECONDS() - lnS1
? 'adding odd numbers', lnS1
lnS2 = SECONDS()
lnI = 0

Do While .T.
   lnI = m.lnI + 1 
   lnSquare = m.lnI * m.lnI
   
   If (lnSquare > UPPERLIMT )
      Exit
   Endif

Enddo 
lnS2 = SECONDS() - lnS2
? 'squaring lnI', lnS2

lnS3 = SECONDS()

On key label f3 ? i , i/UPPERLIMT*100 && i and the percentage of the covered range
For i = 1 To UPPERLIMT 
	IF SQRT(i) = INT(SQRT(i))
	EndIf
Endfor 
lnS1 = SECONDS() - lnS1
? 'checking SQRT(i) = INT(SQRT(i))', lnS2

RETURN

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

 

[german12]

t's really amazing how small the number of squares in a list of 20 million integers is
[sub]Only 4,472 integer square numbers can be found in the first 20,000,000 integers.[/sub]
I.e. only 0.022%
For the first 40,000,000 integers there are 6324 integer square numbers to be found
I.e. only 0.00016%

Klaus

Peace worldwide - it starts here...

 

[mjcmkrsr]

Hi Chriss,

lnSquare = 0
lnAdd = 1
Do While .T.
   lnSquare = m.lnSquare + m.lnAdd 
   If (m.lnSquare > UPPERLIMT )
      Exit 
   Else
      lnAdd = m.lnAdd + 2
   Endif
Enddo

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

... when you know each square is the sum of all odd integers.

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

 

[Chris Miller]

Yes, at school they usually teach it the hard way with proof by induction. Not because they want to make it hard, but it is one of the easiest ways of using induction to prove something.

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

 

[Chris Miller]

Klaus, yes as the gaps grow with the 2n+1, linearly, the squares become scarcer, only a set of numbers that keep a constant distance in average would keep a constant percentage. For example all multiples of 10 are 10% of all numbers no matter how high you go, but anything with a growing distance between ordered members means a decreasing percentage.

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, which clearly shrinks down with n getting larger.

Chriss