News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Numeric to hex string

Started by hyder, November 17, 2023, 02:19:33 AM

Previous topic - Next topic

hyder

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.

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

NoCforMe

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!).
Assembly language programming should be fun. That's why I do it.

jj2007

Quote from: NoCforMe on December 18, 2023, 05:01:12 PMyou can generate that table programmatically

FastMath:
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)
EndOfCode

Roughly 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 ThingTM but three times faster.

The speed gain is bigger for more complex function. For example, FastMath beats the GSL Bessel function by a factor 55, at the same precision.

jack

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?

jj2007

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.

hyder

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).
Cheers,
Randy Hyde