Algorithm for square root - GameCreators Forum

Author

Message

Aidan

User Banned

Posted: 6th Aug 2023 08:27

Will post here too as Studio is the main app these days, I don't think people go into classic thread much. I have worked out how square root works and I believe is simply

+ Code Snippet

// N#.= number we wish to square root 

Function mysqrt ( N# as float )

Local X# as float

X# = N#

For loops = 1 to 100 
        X# = 0.5 × ( X# + ( N# / X# ) ) 
Next loops

Print X# + " is the square root of " + N# + " approx"

Endfunction X#


//

Just something for you guys to replace the standard sqrt function. I haven't tested it. It's from memory, but by all means give it a try and see if it comes out correctly, not sure how fast it is and maybe faster than sqrt

I have tested small ones like 64, 81 etc and comes back correct.

Trying large ones like huge numbers then will have to increase that for loop to something like 100, 1000 or do a while loop to stop when it starts repeating the result

I hope you can utilise it somewhere in our developments. It's better then the long winded sqrt. Give it a try alongside sqrt to see results but I think and tested it to be exact and faster

Aidan

Back to top

Profile

hendron

8

Years of Service

User Offline

Joined: 20th Dec 2015

Location:

Posted: 6th Aug 2023 15:19

Link

Just tested it out of curiosity. The result was correct but the built in Sqrt() command is a lot faster even after reducing the for loop in the function to 10 iterations. Keep in mind that AppGameKit (Tier1) is an interpreted language. While your algorithm may or may not be faster (I have no idea), the built in Sqrt() is calling a compiled C++ function which can run hundreds of times faster than AGK's bytecode when it comes to loops and logical/mathematical operations. You'd need to test it in Tier 2 to see if your algorithm is actually faster.

Here's the code I used and my results.

+ Code Snippet

#constant ITERATIONS = 100000
#constant VALUE = 80.0

ms = GetMilliseconds()
for i = 1 to ITERATIONS
	result# = mysqrt(VALUE)
next i
mySqrtTime = GetMilliseconds() - ms
mySqrtResult# = result#

ms = GetMilliseconds()
for i = 1 to ITERATIONS
	result# = sqrt(VALUE)
next i
sqrtTime = GetMilliseconds() - ms
sqrtResult# = result#

while not GetRawKeyPressed(27)
	print("sqrt   :  result =  " + str(sqrtResult#) + " time = " + str(sqrtTime))
	print("mysqrt :  result =  " + str(mySqrtResult#) + " time = " + str(mySqrtTime))
	sync()
endwhile


Function mysqrt ( N# as float )

	X# = N#

	For loops = 1 to 10
	        X# = 0.5 * ( X# + ( N# / X# ) ) 
	Next loops

Endfunction X#

Both outputted a result of 8.944272
Sqrt() time = 6ms
mysqrt() time = 141ms

Back to top

Profile PM

Aidan

User Banned

Posted: 6th Aug 2023 15:32

Link

Thanks for testing, it was nice to work out how sqrt mathematically works with that simple

X = 0.5 * ( x + ( n / x ) )

And maybe one day I'll test it in c++ to check its timings to the normal sqrt then maybe the Devs can replace the normal or add an additional sqrt function using the above that is indeed noticeably faster.

C++ compiles straight to ASM which is at machine level so
No harm in trying it I suppose as a new agk built in function

Back to top

Profile

Aidan

User Banned

Posted: 6th Aug 2023 18:21 Edited at: 6th Aug 2023 19:02

Link

But then I've noticed that you have hard coded 10 steps into the for loop. Promise it will find the answer within 5:for small numbers.so your iterations is wasting time with 5/6 extra unnecessary steps

So will have to jig the code to do a while loop instead and stop or exit the while loop once it finds its first repeat.

Cause it will fail straight away if want to do higher / huge numbers
I will be back soon with that code

Promise This will be worth investigatin

+ Code Snippet




Function mysqrt ( N# as float )
    Oldx# = 0
    X# = N# / 2
 
    While (X# != Oldx#)
            oldx# = x#
            X# = 0.5 * ( X# + ( N# / X# ) ) 
    Endwhile
 
Endfunction X#

Forgive my coding, I don't have appgamekit. Doing it from memory

Back to top

Profile

PSY

Developer

7

Years of Service

User Offline

Joined: 3rd Jul 2016

Location: Laniakea Supercluster

Posted: 6th Aug 2023 23:59

Link

There are many ways to calculate the square root of X.
In general, the faster the calculation, the less accurate it is.
Quake III used a very fast inverse square root for normalization, which was about three times faster, with a margin of error of about 1%, which was negligible for this purpose.

PSY LABS Games
Coders don't die, they just gosub without return

Back to top

Profile PM Website

hendron

8

Years of Service

User Offline

Joined: 20th Dec 2015

Location:

Posted: 7th Aug 2023 01:58

Link

Tried it again with your new function (same code otherwise), still getting about 6ms for the built in sqrt() and 106ms for the custom one. But again, the interpreter is almost certainly a bottleneck for this kind of thing, especially inside of an interpreted function call. I did a quick test with a function that does nothing other than return 1.0, and the sqrt() call was still faster. Up to 2x faster over 100,000 iterations.

Back to top

Profile PM

Aidan

User Banned

Posted: 7th Aug 2023 07:43

Link

Thanks again guys.

I don't understand the concept of the magic number version involving

0x5f3759df

It didn't work for me either that one, came back as wrong results.

I'll leave this for now until get my hands on a laptop with c++

Thanks Hendron too for your bit of testing

Back to top

Profile

Aidan

User Banned

Posted: 8th Aug 2023 08:04 Edited at: 8th Aug 2023 09:11

Link

Ok cool. Did some digging and this fast root thing is (c#) but similarly in most

+ Code Snippet


using System;
 
class Gfg
{
  // function to find the inverse square root
  static float inverse_rsqrt(float number)
  {
    const float threehalfs = 1.5F;
 
    float x2 = number * 0.5F;
    float y = number;
 
    // evil floating point bit level hacking
    uint i = BitConverter.ToUInt32(BitConverter.GetBytes(y), 0);
 
    // value is pre-assumed
    i = 0x5f3759df - (i >> 1);
    y = BitConverter.ToSingle(BitConverter.GetBytes(i), 0);
 
    // 1st iteration
    y = y * (threehalfs - (x2 * y * y));
 
    // 2nd iteration, this can be removed
    // y = y * ( threehalfs - ( x2 * y * y ) );
 
    return y;
  }
 
  static void Main(string[] args)
  {
    int n = 256;
    float f = inverse_rsqrt(n);
    Console.WriteLine(f);
  }
}

Or

Converted to AGK. Forgive me if it's wrong. Doing it from memory

+ Code Snippet


  Function fastroot( number# as float)
    x2# = number# * 0.5
    y# = 0x5f3759df - (number# >> 1)
    // 1st iteration
    y# = y# * (1.5 - (x2# * y# * y#));
 
Endfunction y#

This results in

0.0623942

Which is from

https://www.google.com/amp/s/www.geeksforgeeks.org/fast-inverse-square-root/amp/

But the code suggests to find the root of 256. This by rights is not. The root of 256 is 16 or 16 x 16 not 0.0623942

My mind boggles with this FastRoot one, doesn't make no sense

Anyway

Aidan

Back to top

Profile

MadBit

VIP Member

Gold Codemaster

14

Years of Service

User Offline

Joined: 25th Jun 2009

Location: Germany

Posted: 8th Aug 2023 17:56

Link

As PSY has already pointed out, almost inverse square root is only an approximation of the real square root.
Which is perfectly fine for game development (most of the time).
If you multiply your 256 by 0.0623942 you get the approximate value. (15.9729152)

Share your knowledge. It\'s a way to achieve immortality. (Tenzin Gyatso)

Donations are always welcome.

Back to top

Profile PM Email

Aidan

User Banned

Posted: 9th Aug 2023 08:23 Edited at: 9th Aug 2023 08:26

Link

Thanks for that

256 x 0.0625 = 16

Which is definitely close to that approximation. Now understandable, I just couldn't wrap this idea in my mind. All good now.

Which will work for distance maths, cross vector maths, normalisations I suppose. Heavily useful all the same

Like

D# = sqrt ( (X2-X1)* (X2-X1)+(Y2-Y1)*(Y2-Y1) +(Z2-Z1) *(Z2-Z1))

Back to top

Profile

Raven

19

Years of Service

User Offline

Joined: 23rd Mar 2005

Location: Hertfordshire, England

Posted: 10th Aug 2023 08:02

Link

As a note: Fast Approximation for Square Roots while we're useful 20 years ago are no longer going to provide the same performance differential as when first proposed.

You have to keep on mind that all CPUs now have Mathematics Accelerators... i.e. Fixed Function accelerated processing for various common mathematics problems.
This will provide close to, if not the same performance as approx. approaches whole offering an accurate calculation... I mean a BIG performance issue with Sqrt was always the branching, but we now have intelligent branch prediction.

Figuring out the maths behind various common tasks is a good exercise to know /what/ is going on behind the scenes but in general it's simply an academic exercise rather than something you'd do for performance

Back to top

Profile PM Email Website

Arch-Ok

AGK Developer

4

Years of Service

User Offline

Joined: 11th Jul 2019

Location: Bursa/TÜRKIYE

Posted: 10th Aug 2023 19:07

Link

https://forum.thegamecreators.com/thread/227891#msg2667991

Back to top

Profile PM

Aidan

User Banned

Posted: 11th Nov 2023 13:30 Edited at: 11th Nov 2023 15:28

Link

Here is a math hack

Square root 25

Add ( 2 + 5) = 7 - 2 = 5

Square root 64

Add ( 6 + 4 ) = 10 - 2 = 8

Square root 196

Add ( 1 + 9 + 6 ) = 16 - 2 = 14

Square root 289

Add ( 2 + 8 + 9 ) = 19 - 2 = 17

Try it out

Edit... Ignore me

Square root 11

1 + 1 = 2 - 2 = 0

Instead of 3.3xxxxxxx something

I got my hopes up then lol

Don't believe any maths shorts on YouTube lol

On the other hand, it's fascinating why these particular numbers work so well.

Are they whole, perfect, Fibonacci, prime numbers or something

But 3 x 3 = 9, so

9 on its own using the above - 2 = 7 )wrong)

God knows why that you tuber is surviving giving me hope then destroying it at same time lol

Back to top

Profile

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 21st Nov 2023 18:01

Link

@Arch-Ok, I think your algorithm could be sped up by ditching the memblock. I think there's a bitwise method for changing that float to an int that should be faster. Whether or not its enough to make it as fast as the built-in sqrt I can't say.
I ran your program and got these results:

+ Code Snippet

agk sqrt: 78ms
inverse sqrt: 374ms

number: 3515
agk sqrt: 59.287434
inverse sqrt: 59.289505

As far as precision goes, I'd be perfectly happy with it up to the hundredths place. Anything more than that in most cases is negligible.

Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda
Pixel-Perfect Collision

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Back to top

Profile PM Email Website

Sorry your browser is not supported!

AppGameKit Studio Chat / Algorithm for square root