Jump to content
  • Advertisement
Sign in to follow this  
L. Spiro

Extracting Raw Bits from Doubles

This topic is 2666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How do I convert a double to string without accounting for the decimal position? I just want to extract the raw mantissa bits in decimal form.

Basically exactly what the _fltout2() function does in Microsoft’s implementation of the standard C library.

If I pass 23.365354 to _gcvt_s(), it will call _fltout2() internally.
_fltout2() fills out a structure containing the following:
{
sign = 0x20
decpt = 0x02
flag = 0x01
mantissa = "23365354"
}


I am specifically interested in how it got "23365354".
Does anyone have an algorithm for this? You can assume I have extracted the mantissa bits into an unsigned __int64 type.


Thank you,
Yogurt Emperor

Share this post


Link to post
Share on other sites
Advertisement
Thank you but I am looking for a way to directly convert the mantissa/significant to a string, as [color=#1C2837][size=2]_fltout2() does.
[color="#1C2837"]I know the floating-point format. I have already separated it into bit components and made a function that prints the number correctly.
[color="#1C2837"]But I wish to print it another way, more accurately, and more quickly. To do that I need to use whatever algorithm _fltout2() is using.
[color="#1C2837"]_fltout2() works by converting 23.365354 to the string “23365354”, and storing the decimal place separately. This allows other functions to reconstruct the string with the decimal place in the correct spot.
[color="#1C2837"]This is my goal exactly, and all I need is a way to extract the actual mantissa/significant bits into a string buffer.

[color=#1C2837][size=2]

[color=#1C2837][size=2]

[color=#1C2837][size=2]Yogurt Emperor

Share this post


Link to post
Share on other sites
[color="#1c2837"]This is my goal exactly, and all I need is a way to extract the actual mantissa/significant bits into a string buffer.

It's a binary fraction, so you'll have to convert it to decimal. It's a hassle to do with integer math, and pretty easier with floating point math. If you only want to use integers, you can set up a lookup table with large integer representations of the decimal fractions the various bits in the mantissa converts to (the first could be "10000000000", the second "5000000000", third "2500000000" etc., but you'll want more zeroes for double precision). Then you go through all the bits and add up the set fractions, to get an integer representation of the whole mantissa. THEN you will have to account for the exponent, which is in base-2, so you'll have to divide or multiply the result by 2 (depending on whether it's positive or negative) in a loop for however large the exponent it. Then you can print as an integer (which you hopefully know how to do).

Using floating point math, you can just multiply the absolute of the value by
10^( x - floor( log10(|value|) ) )
where x is the number of significant figures you want. Then just convert it to an integer, using a cast or whatever. It basically removes the exponent to automatically get a correct fraction, so then it's just a matter of scaling the result with a power of 10, which is what x does.

Share this post


Link to post
Share on other sites

I once used the code found here to write my own conversion routines.

That appears to be exactly what I have been trying to find for the last 8 months!
I implemented my own “painfully accurate” method which is several times slower than sprintf(), and lossy when it comes to saving data to a file and later retrieving it.
And, like that author, I have reasons not to use cstdio.

I am just guessing this is what I need based on the front page but we will see.
Thank you for the find.


[font=arial, verdana, tahoma, sans-serif][size=2]

[quote name='YogurtEmperor' timestamp='1299410055' post='4782373'][size=2][color="#1c2837"]This is my goal exactly, and all I need is a way to extract the actual mantissa/significant bits into a string buffer.

It's a binary fraction, so you'll have to convert it to decimal. It's pretty easy to do with integer math, and even easier with floating point math. If you only want to use integers, you can set up a lookup table with large integer representations of the decimal fractions the various bits in the mantissa converts to (the first could be "10000000000", the second "5000000000", third "2500000000" etc., but you'll want more zeroes for double precision). Then you go through all the bits and add up the set fractions, to get an integer representation of the whole mantissa, which you then can print as an integer (which you hopefully know how to do).

Using floating point math, you can just multiply the absolute of the value by
10^( x - floor( log10(|value|) ) )
where x is the number of significant figures you want. Then just convert it to an integer, using a cast or whatever. It basically removes the exponent to automatically get a correct fraction, so then it's just a matter of scaling the result with a power of 10, which is what x does.You can also do that sort of conversion using only integer math, but it's a hassle and will frankly probably be slower on processors with FPUs.
[/quote]
I certainly do know how to print integers. I will toy around with this method also.[/font]

Yogurt Emperor

Share this post


Link to post
Share on other sites
[font="arial, verdana, tahoma, sans-serif"]I certainly do know how to print integers. I will toy around with this method also.[/font]


Good, but if you try the first method, note that I forgot an important part: You'll have account for the exponent too. I've edited my post to reflect this.

Share this post


Link to post
Share on other sites

[quote name='haegarr' timestamp='1299411121' post='4782375']
I once used the code found here to write my own conversion routines.

That appears to be exactly what I have been trying to find for the last 8 months!
I implemented my own “painfully accurate” method which is several times slower than sprintf(), and lossy when it comes to saving data to a file and later retrieving it.
[/quote]
For what it is worth, the comments on my implementation state that


// Timings (relative) of conversion routines compared to sprintf:
//
// sprintf( float ) : 41
// preset( float, ... ) : 8.5
//
// sprintf( double ) : 41
// preset( double, ... ) : 10.5

but I don't remember whether I've implemented the fast or accurate method. And further, I've done some changes:


// The computation of exp10 (in case x is not 0) was originally:
// exp10 = int( ceil( log10( x ) ) ) = int( ceil( log10( s * 2^exp2 ) ) )
// This can be transformed to:
// = int( ceil( log10( s ) + log10( 2^exp2 ) ) )
// = int( ceil( log10( s ) + ld( 2^exp2 ) / ld( 10 ) ) )
// = int( ceil( log10( s ) + exp2 * inv( ld( 10 ) ) )
//
// Because normalized significand s is 1 <= s < 2, one gets an maximum error < log10( 2 ) ~= 0.3 if logarithm is totally
// avoided. So approx. every 3rd case will run into the correction with the "while" due to this neglection (that
// correction code was included in the original anyway).
//
// Additionally, only in very few cases will int( ceil( x ) ) differ from int( x ) + 1. Hence we use:
// exp10 = int( exp2 * inv( log( 10 ) ) ) + 1
// as fast approximation.

Share this post


Link to post
Share on other sites

[quote name='YogurtEmperor' timestamp='1299413362' post='4782382']
[quote name='haegarr' timestamp='1299411121' post='4782375']
I once used the code found here to write my own conversion routines.

That appears to be exactly what I have been trying to find for the last 8 months!
I implemented my own “painfully accurate” method which is several times slower than sprintf(), and lossy when it comes to saving data to a file and later retrieving it.
[/quote]
For what it is worth, the comments on my implementation state that


// Timings (relative) of conversion routines compared to sprintf:
//
// sprintf( float ) : 41
// preset( float, ... ) : 8.5
//
// sprintf( double ) : 41
// preset( double, ... ) : 10.5

but I don't remember whether I've implemented the fast or accurate method. And further, I've done some changes:


// The computation of exp10 (in case x is not 0) was originally:
// exp10 = int( ceil( log10( x ) ) ) = int( ceil( log10( s * 2^exp2 ) ) )
// This can be transformed to:
// = int( ceil( log10( s ) + log10( 2^exp2 ) ) )
// = int( ceil( log10( s ) + ld( 2^exp2 ) / ld( 10 ) ) )
// = int( ceil( log10( s ) + exp2 * inv( ld( 10 ) ) )
//
// Because normalized significand s is 1 <= s < 2, one gets an maximum error < log10( 2 ) ~= 0.3 if logarithm is totally
// avoided. So approx. every 3rd case will run into the correction with the "while" due to this neglection (that
// correction code was included in the original anyway).
//
// Additionally, only in very few cases will int( ceil( x ) ) differ from int( x ) + 1. Hence we use:
// exp10 = int( exp2 * inv( log( 10 ) ) ) + 1
// as fast approximation.

[/quote]
Those timings are way better than my existing method.
I’ve rewritten many of the standard C functions, and all of my methods are at least 150% faster than the original methods except for my routine to print doubles. This is my crux.
On x64 my routines are literally 20 times faster (minimum).

I will look into all of these and pick the fastest one that is lossless (can convert to string and back without any change to the value).


Yogurt Emperor

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!