Message board for the users of flat assembler.
> Macroinstructions > 8) Square root macro for numerical constants
Here is another brainchild of mine!
I have a nice square root macro that works on Flat Assembler integer
numerical constants at COMPILE TIME :]. (For beginners: if you want to
calculate square roots at runtime, use something like "fsqrt" instruction.)
It uses a sophisticated Heron method, thus only 7 iterative steps are
required in a worst case scenario to give the full 63bit Fasm precision.
Note that this macro works only on integer values (see Fasm documentation),
thus the returned square roots are rounded.
Furthermore and unfortunately, Fasm allows only complicated and slow early
out loops because the "repeat"-directive doesn't allow quit conditions, but
I think that this won't hurt too much.
Here is an usage example:
;The DispDec macro displays numerical constants in decimal macro DispDec Val if Val <> 0 Acc= Val Divider= 1000000000000000000 Highest0= 0 if Acc < 0 display "-" end if repeat 19 Digit= Acc/Divider Acc= Acc mod Divider Divider= Divider/10 if Digit <> 0 Highest0= 1 end if if Highest0 = 1 display Digit+"0" end if end repeat else display "0" end if SomeVar= 6432168469798324165;Any positive value up to 2^63 - 1 goes SqRt SomeVar;This is where the magic happens! DispDec SomeVar
Watch out: unfortunately SqRt cannot take immediates! so this code generates
Last edited by MCD on 06 Jan 2005, 19:09; edited 3 times in total
|05 Jan 2005, 20:30||
Here goes the actual SqRt macro:
macro SqRt Val if Val <> 0 if Val >= 0;These lines serve to guess a good and fast starting value Acc= 11 if Val >= 100h Acc= 171 if Val >= 10000h Acc= 2740 if Val >= 1000000h Acc= 43838 if Val >= 100000000h Acc= 701416 if Val >= 10000000000h Acc= 11222655 if Val >= 1000000000000h Acc= 179562481 if Val >= 100000000000000h Acc= 2038618457 end if end if end if end if end if end if end if Val= Val-1;This is just a rounding stuff repeat 7 Acc= Val/Acc + Acc +1 shr 1 end repeat Val= Acc else Acc= 1/0;This will intentionally cause an "value out of range" error! end if end if
MCD - the inevitable return of the Mad Computer Doggy
|05 Jan 2005, 20:31||
If you need a faster SqRt macro and you can sacrify some precision, then you
could use less iterative starting value steps or unroll the loop a bit
(not sure if this speeds it up?) or decrease the repeat number below 7. But
in any case, more than 7 repeats only slow it down.
The starting value stuff is difficult to optimize. If you use less steps, you
will have to use more repeats. Thus, both too much/less steps slow down the
iterative process. I tried out many different step numbers from 1 to 16, and
8 seem to be the gold middle. I tested it with the following code (this may
take some time on older machines):
repeat 40000h X= % - 1 SqRt X end repeat repeat 40000h X= % shl 45 - 1 SqRt X end repeat
Does anyone know a faster square root algorythm than Heron(except the Taylor
based stuff)? I would also know a way to optimize the starting value guess by
using a "bsr" operator, but I don't think it is worth beeing implemented. It
would give something like...
;... Acc= 1 shl bsr Val shr 1 ;Small, but very effective