Tony Tribelli and I have been working on some optimized algorithms that convert a numeric value to a string of hexadecimal digits. The original work for for a new book I'm working on, "The Art of ARM Assembly." However, Tony has graciously converted the ARM code to x86 code. You can find the results of his work here:
https://randallhyde.com/Forum/viewtopic.php?t=694 (https://randallhyde.com/Forum/viewtopic.php?t=694)
and
https://github.com/atribelli/hexstr (https://github.com/atribelli/hexstr)
Spoiler alert: as was the case for the 64-bit ARM CPU, the 256-entry (512-byte) lookup table was the fastest version, even beating (IIRC) the SIMD version.
Cheers,
Randy Hyde
thanks hyder :smiley:
I would love an algorithm for fast conversion of a multi-precision binary floating-point number to decimal string and vice-versa
my current method involves multiplying and dividing by a power of 10 which gets very slow at high precision, especially the string to float conversion
Quote from: jack on November 17, 2023, 07:56:17 AMmulti-precision binary floating-point number
Something official, like REAL16? If not, how many bits of mantissa, how many for the exponent?
jj, the mantissa is limited to 4294967295 bits and the exponent to 2147483647 bits but with my kindergarten arithmetic algorithms the operations become impossibly slow above 100000 decimal digits, 50000 digits not so bad
I hate to throw shade on your programming efforts, but how is this something we should care about? If you're converting binary to hex, I would assume that the purpose is to display those numbers, either on a screen or perhaps in a text file. What difference could it possibly make how fast the conversion routine is, unless you're somehow logging a bazillion different numbers? Wouldn't your efforts be better spent optimizing something that could really use it?
Quote from: jack on November 17, 2023, 08:56:06 AMthe mantissa is limited to 4294967295 bits and the exponent to 2147483647 bits
With simple QuadMath (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1449), you can arrive at pretty high precision - 33 digits:
digits 1.23456789012345678901234567890123
Big 1.23456789012345678901234567890123 Real16 precision
PI 3.14159265358979323846264338327950 (as text)
MyPI 3.14159265358979323846264338327950 Real16 precision
FpuPI 3.141592653589793238That is more than enough precision to shoot Voyager 3 to Andromeda's black hole, where it would arrive in a trillion years. So what is the practical (or theoretical?) relevance of 4294967295 bits of mantissa, when 112 bits are more than sufficient?
Btw there are some threads about REAL16 precision:
8/2017: GCC QuadMath library - REAL16 math (https://masm32.com/board/index.php?topic=6477.0)
6/2018: REAL16 for statistics and Gamma function (https://masm32.com/board/index.php?topic=7224.0)
Both have been vandalised by our dear former member nidud, but you can still get useful information from other members' posts.
:thumbsup:
I'd really like to see how one can express pi in hexadecimal ...
include \masm32\include\masm32rt.inc
.data?
PI REAL8 ?
.code
start:
cls
fldpi
fstp PI
print hex$(dword ptr PI[4])
inkey hex$(dword ptr PI), "h"
exit
end start
Output: 400921FB54442D18h (more (https://float.exposed/0x400921fb54442d18))
Brilliant. That works but it's totally meaningless.
Quote from: NoCforMe on November 17, 2023, 11:46:47 AMbut how is this something we should care about?
It's for a book, for people learning assembly and SIMD. Converting binary to hex string is something that just screams for parallelism and is a quite graspable example of converting an algorithm to SSE or NEON. It's literally the same algorithm as one of the regular assembly implementation.
Quote from: NoCforMe on November 17, 2023, 11:46:47 AMAssembly language programming should be fun. That's why I do it.
You don't find converting an 8-byte hex values into a 17-byte zero terminated strings in about 16 assembly instructions to be fun? :-)
Quote from: ttribelli on November 17, 2023, 04:24:44 PMQuote from: NoCforMe on November 17, 2023, 11:46:47 AMAssembly language programming should be fun. That's why I do it.
You don't find converting an 8-byte hex values into a 17-byte zero terminated strings in about 16 assembly instructions to be fun? :-)
OK, well, you got me there. Never tried any of that fancy-schmancy SIMD, etc., stuff, but 16 instructions is definitely impressive.
Quote from: jack on November 17, 2023, 08:56:06 AMjj, the mantissa is limited to 4294967295 bits and the exponent to 2147483647 bits but with my kindergarten arithmetic algorithms the operations become impossibly slow above 100000 decimal digits, 50000 digits not so bad
try optimization inspired by SSE RCPPS/MULPS replacing division?
FMUL 0.1 instead of fdiv 10
Quote from: ttribelli on November 17, 2023, 04:24:44 PMIt's for a book, for people learning assembly and SIMD. Converting binary to hex string is something that just screams for parallelism and is a quite graspable example of converting an algorithm to SSE or NEON. It's literally the same algorithm as one of the regular assembly implementation.
I found SSE parallelise taylor series more useful as alternative to most fpu functions
fsinx4,fcosx4,even fsincosx4
there's this old computer virus that converts itself (asm code) to hexadecimal debugscript to infect batch files and i remember that converting from whatever data/numtype it begins to hexadecimal string is not that complicated..
Quote from: jack on November 17, 2023, 07:56:17 AMthanks hyder :smiley:
I would love an algorithm for fast conversion of a multi-precision binary floating-point number to decimal string and vice-versa
my current method involves multiplying and dividing by a power of 10 which gets very slow at high precision, especially the string to float conversion
The trick I use (for double-precision conversion) is to create a table of power of 10:
10**256
10**128
10**64
10**32
10**16
10**8
10**2
10**1
10**0
.
.
.
10**-256
At that point I take the binary exponent and use the set bits to multiply the value by an entry in the table (alternately, I compare the floating-point value against each entry and divide the number by an entry in the table when it's greater than the table entry). So, at most, about nine FP multiplications (or divisions) are required. You can see the algorithm in "The Art of 64-bit Assembly" and you can download the code from my website: https://www.randallhyde.com (https://www.randallhyde.com).
For string-to-float I use the decimal exponent as an index into this same able to multiply the converted mantissa by various powers of 10. Algorithm is also in Ao64A and in my on-line code.
I suppose if you wanted the fastest possible algorithm, it *might* be possible to create a lookup table indexed by the exponent and you could get it down to 2-3 multiplications or divisions. I never followed through on that idea, however, because the table would be quite large (several thousand 8-byte entries, IIRC), so I've never proven that idea would work.
Cheers,
Randy Hyde
Quote from: hyder on December 18, 2023, 03:13:43 PM(several thousand 8-byte entries, IIRC)
Hmm, that's what, somewhere in the neighborhood of 16-32K? Not all that big. Why don't you code that up? Would be interesting. I'm assuming you can generate that table programmatically somehow (would be a bitch to have to create it by hand!).
Quote from: NoCforMe on December 18, 2023, 05:01:12 PMyou can generate that table programmatically
FastMath (https://www.jj2007.eu/MasmBasicQuickReference.htm#Mb1520):
include \masm32\MasmBasic\MasmBasic.inc
SetGlobals fct:REAL10
Init
FastMath FastLog10 ; define a math function
For_ fct=0.0 To 10.0 Step 0.5 ; max 10,000 iterations
fld fct ; X
fstp REAL10 ptr [edi]
void Log10(fct) ; Y (built-in MasmBasic function)
fstp REAL10 ptr [edi+REAL10]
add edi, 2*REAL10
Next
FastMath
Print Str$("Log(5.0)=%Jf", FastLog10(5)v)
EndOfCodeRoughly 3.3 times faster then the FPU. You waste a millisecond or so at program start, you allocate a whopping 300kBytes for the table but no bloat for the exe. And then you get the same precision as The Real Thing
TM but three times faster.
The speed gain is bigger for more complex function. For example, FastMath beats the GSL Bessel function (https://masm32.com/board/index.php?msg=95835) by a factor 55, at the same precision.
(https://masm32.com/board/index.php?action=dlattach;attach=10959;image)
Hi jj2007
I am interested in the algorithm, would you post it in pseudo code?
what kind and degree of interpolation do you use?
how do you determine what subset of the table to use?
That's a very long story, Jack - sorry, I don't have the time to rewrite several hundred lines in pseudocode, from weird macros that I coded 10 years ago. Besides, it's all public in \Masm32\MasmBasic\MasmBasic.inc ...
Check this post to get some ideas (https://masm32.com/board/index.php?topic=1668.msg16947#msg16947).
Quote from: jack on November 17, 2023, 07:56:17 AMthanks hyder :smiley:
I would love an algorithm for fast conversion of a multi-precision binary floating-point number to decimal string and vice-versa
my current method involves multiplying and dividing by a power of 10 which gets very slow at high precision, especially the string to float conversion
FWIW, I just added a fast double-precision to string conversion to this very forum (https://masm32.com/board/index.php?topic=11931.0 (https://masm32.com/board/index.php?topic=11931.0)).
Cheers,
Randy Hyde