Python anyone?

[jack]

raymond
what algorithm did you use for the square root?

[daydreamer]

My main interest was to find out if there is a significantly different way of extracting a square root compared to all those I have learned in the past.

The most promising one for speed would have to be using logarithms. But then, are there means to convert those rapidly back and forth with sufficient precision? Or is it something totally different? A self-contained working program would certainly be useful to run under ollydbg and get some of the details.

I don't know if Taylor series has sufficient precision for log and exp functions?
I have SIMD trigo functions that calculate 4*sincos fast
y0 = exp(log(x0)/2)*exp(2.302585092994046*ex/2) ;possibility for SIMT or SIMD calculates *0.5 and exp functions in parallel?

[jack]

y0 = exp(log(x0)/2)*exp(2.302585092994046*ex/2)

I wrote it that way at the time because I was playing with nth roots, but for the square root it's simpler to use sqrt(x0)*exp(2.302585092994046*ex/2), the reason for splitting the number is so that you can deal with huge numbers beyond the range of double or even extended
so for example if x=17, then x0=1.7 and ex=1
but suppose x=5e10000 then x0=5 and ex=10000 so exp(2.302585092994046*ex/2) = 1.00000000000158e5000 so you need to use MPexp to evaluate that expression
I tried the inverse square root Newton-Rapson method but with my very simple multiplication algorithm it was slower.

[raymond]

raymond
what algorithm did you use for the square root?

When I first learned about this algo in the early 1960s, I dubbed it the "abacus" algo because it seemed as if it could have been developed in ancient times when the abacus was the prime instrument to perform calculations.

In those days, IBM was marketing mechanical calculators to perform primarily the usual math functions: add, subtract, multiply, divide. The user's manual also described a procedure to extract square roots without using any mult/div operations except for one single preliminary multiplication. That is the procedure which I adapted in the late 1980's for a TRS80 to achieve 10,000 decimal precision of square roots with only 64kb total memory (using what was named at the time as "machine language" )!

Here's a brief description of that algo.

Code Select Expand

Let's use the square root of 2 for example
;1st step is to multiply the source by 5
 2.0000....*5 = 10.0000.....
;2nd step subdivide the result into chunks of 2 digits from the decimal delimiter, pad front with a 0 if necessary
10 00 00 00 ...........
;start by subtracting 05 from the first double digits
05
__
05 00 00 00 ......
;continue incrementing the '05' by 10 for the subsequent subtractions until the result would be negative
15
__
;would be negative for this example
;remove the terminating 5 and replace it with a 05, then shift by 1 digit right and repeat subtractions
05 00 00 00 ..........
01 05
______________
03 95 00 00 ....
01 15
______________
02 80 00 00 ....
01 25
______________
01 55 00 00 .........
01 35
______________
00 20 00 00 ......
01 45
;would become negative for this next digit
;remove the terminating 5 and replace it with a 05, then shift by 1 digit right and repeat subtractions
00 20 00 00 ...........
00 14 05
_____________
00 05 95 00 ..........
00 14 15
;would become negative for this next digit
;remove the terminating 5 and replace it with a 05, then shift by 1 digit right and repeat subtractions
00 05 95 00 ..........
00 01 41 05
_____________
00 04 53 95 ..........
00 01 41 15
_____________
00 03 12 80 ..........
00 01 41 25
_____________
00 01 71 55 ..........
00 01 41 35
_____________
00 00 30 20
00 01 41 45
;would become negative for this next digit
;remove the terminating 5 and replace it with a 05, then shift by 1 digit right and repeat subtractions
00 00 30 20 00 00 ........
00 00 14 14 05
________________
00 00 16 05 95 00 .......
00 00 14 14 15
________________
00 00 01 91 80 00 .........
00 00 14 14 25
;would become negative for this next digit
;remove the terminating 5 and replace it with a 05, then shift by 1 digit right and repeat subtractions
00 00 01 91 80 00 .........
00 00 01 41 42 05

;and you can continue to repeat this ad infinitum......... limited to the amount of available memory.

You also have to keep track of where the decimal delimiter would be in the result.

This somehow makes me feel old.

[jack]

 
interesting algorithm

[daydreamer]

SSE rcpsqrt low-res LUT I use in make circles very fast in ddraw, documentation suggest use newton- raphson to perform better precision
my dos. Com file is inspired by pixelshader way of make circles per pixel checking every pixel if inside or outside circle radius r= sqrt(x*x+Y*y)
Fastest I use in dos. Com is reduce the slow fsqrt every pixel vs 100 radius, with
R=x*x+Y*y
.If R < 10000 ; check vs 100*100
Mov color,circle color
.else
Mov color,background color
.endif