You can implement a decimal equivalent of frexp yourself quite easily. The code you need looks something like this:
int exponent = (int)log10(fabs(d));
double mantissa = d / pow(10, exponent);
printf("%f X 10^%d\n", mantissa, exponent);
First we determine the exponent by taking the base-10 logarithm of the absolute value of your number. (We need fabs because log10 requires a positive argument.) The cast rounds towards zero, which is, conveniently, what we need. Then we normalize the mantissa by dividing.
This doesn't handle d==0 (or infinity or NaN), the division will introduce some error into the result, and I haven't tested it with small numbers or negative numbers, but this should give you something to start from.
Answer from pburka on Stack OverflowYou can implement a decimal equivalent of frexp yourself quite easily. The code you need looks something like this:
int exponent = (int)log10(fabs(d));
double mantissa = d / pow(10, exponent);
printf("%f X 10^%d\n", mantissa, exponent);
First we determine the exponent by taking the base-10 logarithm of the absolute value of your number. (We need fabs because log10 requires a positive argument.) The cast rounds towards zero, which is, conveniently, what we need. Then we normalize the mantissa by dividing.
This doesn't handle d==0 (or infinity or NaN), the division will introduce some error into the result, and I haven't tested it with small numbers or negative numbers, but this should give you something to start from.
I like the OP approach to let printf(), using the "%e" format, to do the heavy lifting.
There are many issues with double to string conversion that existing functions already handle nicely. (INF, Nan, -0, rounding, negatives). OP use of frexp(), power() typically have troubles near values a power of 10 do to rounding and and finite precision.
OP is fuzzy on how much precision given only 1 example. power(0.5, 100) would need 100 digits. Let's limit it to DBL_DIG, rather than use the %e default of 6. (which is really 7 digits, just 6 after the DP.)
char *Heyhey_Notation(char *dest, double x) {
static const char Times[] = " times 10 to the power ";
char buffer[3 + DBL_DIG + sizeof(Times) + 20 + 1];
sprintf(buffer, "%.*e", DBL_DIG, x);
char *e = strchr(buffer, 'e'); // find exponent position
if (e) {
char *zero = e;
while (zero[-1] == '0') zero--;
*zero = '\0'; // OP wants excess zeros trimmed.
int power = atoi(&e[1]); // trim excess zeros by converting to int
sprintf(dest, "%s%s%d", buffer, Times, power);
}
else {
strcpy(dest, buffer);
}
return dest;
}
int main() {
char buf[100];
puts(Heyhey_Notation(buf, 3349.25));
puts(Heyhey_Notation(buf, -0.0));
puts(Heyhey_Notation(buf, 123));
puts(Heyhey_Notation(buf, -1234567890.0/9999999999.0));
puts(Heyhey_Notation(buf, -1/0.0));
puts(Heyhey_Notation(buf, atof("nan")));
return 0;
}
3.34925 times 10 to the power 3
-0. times 10 to the power 0
1.23 times 10 to the power 2
-1.234567890123457 times 10 to the power -1
-inf
nan
Here is C++ code to convert a decimal string to a binary floating-point value. Although the question is tagged C, I presume the question is more about the algorithm and calculations than the programming language.
The DecimalToFloat class is constructed with a string that contains solely decimal digits and a decimal point (a period, most one). In its constructor, it shows how to use elementary school multiplication and long division to convert the number from decimal to binary. This demonstrates the fundamental concepts using elementary arithmetic. Real implementations of decimal-to-floating-point conversion in commercial software using algorithms that are faster and more complicated. They involve prepared tables, analysis, and proofs and are the subjects of academic papers. A significant problem of quality implementations of decimal-to-binary-floating-point conversion is getting the rounding correct. The disparate nature of powers of ten to powers of two (both positive and negative powers) makes it tricky to correctly determine when some values are above or below a point where rounding changes. Normally, when we are parsing something like 123e300, we want to figure out the binary floating-point result without actually calculating 10300. That is a much more extensive subject.
The GetValue routine finishes the preparation fo the number, taking the information prepared by the constructor and rounding it to the final floating-point form.
Negative numbers and exponential (scientific) notation are not handled. Handling negative numbers is of course easy. Exponential notation could be accommodated by shifting the input—moving the decimal point right for positive exponents or left for negative exponents. Again, this is not the fastest way to perform the conversion, but it demonstrates fundamental ideas.
/* This code demonstrates conversion of decimal numerals to binary
floating-point values using the round-to-nearest-ties-to-even rule.
Infinities and subnormal values are supported and assumed.
The basic idea is to convert the decimal numeral to binary using methods
taught in elementary school. The integer digits are repeatedly divided by
two to extract a string of bits in low-to-high position-value order. Then
sub-integer digits are repeatedly multiplied by two to continue extracting
a string of bits in high-to-low position-value order. Once we have enough
bits to determine the rounding direction or the processing exhausts the
input, the final value is computed.
This code is not (and will not be) designed to be efficient. It
demonstrates the fundamental mathematics and rounding decisions.
*/
#include <algorithm>
#include <limits>
#include <cmath>
#include <cstring>
template<typename Float> class DecimalToFloat
{
private:
static_assert(std::numeric_limits<Float>::radix == 2,
"This code requires the floatng-point radix to be two.");
// Abbreviations for parameters describing the floating-point format.
static const int Digits = std::numeric_limits<Float>::digits;
static const int MaximumExponent = std::numeric_limits<Float>::max_exponent;
static const int MinimumExponent = std::numeric_limits<Float>::min_exponent;
/* For any rounding rule supported by IEEE 754 for binary floating-point,
the direction in which a floating-point result should be rounded is
completely determined by the bit in the position of the least
significant bit (LSB) of the significand and whether the value of the
trailing bits are zero, between zero and 1/2 the value of the LSB,
exactly 1/2 the LSB, or between 1/2 the LSB and 1.
In particular, for round-to-nearest, ties-to-even, the decision is:
LSB Trailing Bits Direction
0 0 Down
0 In (0, 1/2) Down
0 1/2 Down
0 In (1/2, 1) Up
1 0 Down
1 In (0, 1/2) Down
1 1/2 Up
1 In (1/2, 1) Up
To determine whether the value of the trailing bits is 0, in (0, 1/2),
1/2, or in (1/2, 1), it suffices to know the first of the trailing bits
and whether the remaining bits are zeros or not:
First Remaining Value of Trailing Bits
0 All zeros 0
0 Not all zeros In (0, 1/2)
1 All zeros 1/2
1 Not all zeros In (1/2, 1)
To capture that information, we maintain two bits in addition to the
bits in the significand. The first is called the Round bit. It is the
first bit after the position of the least significand bit in the
significand. The second is called the Sticky bit. It is set if any
trailing bit after the first is set.
The bits for the significand are kept in an array along with the Round
bit and the Sticky bit. The constants below provide array indices for
locating the LSB, the Round Bit, and the Sticky bit in that array.
*/
static const int LowBit = Digits-1; // Array index for LSB in significand.
static const int Round = Digits; // Array index for rounding bit.
static const int Sticky = Digits+1; // Array index for sticky bit.
char *Decimal; // Work space for the incoming decimal numeral.
int N; // Number of bits incorporated so far.
char Bits[Digits+2]; // Bits for significand plus two for rounding.
int Exponent; // Exponent adjustment needed.
/* PushBitHigh inserts a new bit into the high end of the bits we are
accumulating for the significand of a floating-point number.
First, the Round bit shifted down by incorporating it into the Sticky
bit, using an OR so that the Sticky bit is set iff any bit pushed below
the Round bit is set.
Then all bits from the significand are shifted down one position,
which moves the least significant bit into the Round position and
frees up the most significant bit.
Then the new bit is put into the most significant bit.
*/
void PushBitHigh(char Bit)
{
Bits[Sticky] |= Bits[Round];
std::memmove(Bits+1, Bits, Digits * sizeof *Bits);
Bits[0] = Bit;
++N; // Count the number of bits we have put in the significand.
++Exponent; // Track the absolute position of the leading bit.
}
/* PushBitLow inserts a new bit into the low end of the bits we are
accumulating for the significand of a floating-point number.
If we have no previous bits and the new bit is zero, we are just
processing leading zeros in a number less than 1. These zeros are not
significant. They tell us the magnitude of the number. We use them
only to track the exponent that records the position of the leading
significant bit. (However, exponent is only allowed to get as small as
MinimumExponent, after which we must put further bits into the
significand, forming a subnormal value.)
If the bit is significant, we record it. If we have not yet filled the
regular significand and the Round bit, the new bit is recorded in the
next space. Otherwise, the new bit is incorporated into the Sticky bit
using an OR so that the Sticky bit is set iff any bit below the Round
bit is set.
*/
void PushBitLow(char Bit)
{
if (N == 0 && Bit == 0 && MinimumExponent < Exponent)
--Exponent;
else
if (N < Sticky)
Bits[N++] = Bit;
else
Bits[Sticky] |= Bit;
}
/* Determined tells us whether the final value to be produced can be
determined without any more low bits. This is true if and only if:
we have all the bits to fill the significand, and
we have at least one more bit to help determine the rounding, and
either we know we will round down because the Round bit is 0 or we
know we will round up because the Round bit is 1 and at least one
further bit is 1 or the least significant bit is 1.
*/
bool Determined() const
{
if (Digits < N)
if (Bits[Round])
return Bits[LowBit] || Bits[Sticky];
else
return 1;
else
return 0;
}
// Get the floating-point value that was parsed from the source numeral.
Float GetValue() const
{
// Decide whether to round up or not.
bool RoundUp = Bits[Round] && (Bits[LowBit] || Bits[Sticky]);
/* Now we prepare a floating-point number that contains a significand
with the bits we received plus, if we are rounding up, one added to
the least significant bit.
*/
// Start with the adjustment to the LSB for rounding.
Float x = RoundUp;
// Add the significand bits we received.
for (int i = Digits-1; 0 <= i; --i)
x = (x + Bits[i]) / 2;
/* If we rounded up, the addition may have carried out of the
initial significand. In this case, adjust the scale.
*/
int e = Exponent;
if (1 <= x)
{
x /= 2;
++e;
}
// Apply the exponent and return the value.
return MaximumExponent < e ? INFINITY : std::scalbn(x, e);
}
public:
/* Constructor.
Note that this constructor allocates work space. It is bad form to
allocate in a constructor, but this code is just to demonstrate the
mathematics, not to provide a conversion for use in production
software.
*/
DecimalToFloat(const char *Source) : N(), Bits(), Exponent()
{
// Skip leading sources.
while (*Source == '0')
++Source;
size_t s = std::strlen(Source);
/* Count the number of integer digits (digits before the decimal
point if it is present or before the end of the string otherwise)
and calculate the number of digits after the decimal point, if any.
*/
size_t DigitsBefore = 0;
while (Source[DigitsBefore] != '.' && Source[DigitsBefore] != 0)
++DigitsBefore;
size_t DigitsAfter = Source[DigitsBefore] == '.' ? s-DigitsBefore-1 : 0;
/* Allocate space for the integer digits or the sub-integer digits,
whichever is more numerous.
*/
Decimal = new char[std::max(DigitsBefore, DigitsAfter)];
/* Copy the integer digits into our work space, converting them from
digit characters ('0' to '9') to numbers (0 to 9).
*/
for (size_t i = 0; i < DigitsBefore; ++i)
Decimal[i] = Source[i] - '0';
/* Convert the integer portion of the numeral to binary by repeatedly
dividing it by two. The remainders form a bit string representing
a binary numeral for the integer part of the number. They arrive
in order from low position value to high position value.
This conversion continues until the numeral is exhausted (High <
Low is false) or we see it is so large the result overflows
(Exponent <= MaximumExponent is false).
Note that Exponent may exceed MaximumExponent while we have only
produced 0 bits during the conversion. However, because we skipped
leading zeros above, we know there is a 1 bit coming. That,
combined with the excessive Exponent, guarantees the result will
overflow.
*/
for (char *High = Decimal, *Low = Decimal + DigitsBefore;
High < Low && Exponent <= MaximumExponent;)
{
// Divide by two.
char Remainder = 0;
for (char *p = High; p < Low; ++p)
{
/* This is elementary school division: We bring in the
remainder from the higher digit position and divide by the
divisor. The remainder is kept for the next position, and
the quotient becomes the new digit in this position.
*/
char n = *p + 10*Remainder;
Remainder = n % 2;
n /= 2;
/* As the number becomes smaller, we discard leading zeros:
If the new digit is zero and is in the highest position,
we discard it and shorten the number we are working with.
Otherwise, we record the new digit.
*/
if (n == 0 && p == High)
++High;
else
*p = n;
}
// Push remainder into high end of the bits we are accumulating.
PushBitHigh(Remainder);
}
/* Copy the sub-integer digits into our work space, converting them
from digit characters ('0' to '9') to numbers (0 to 9).
The convert the sub-integer portion of the numeral to binary by
repeatedly multiplying it by two. The carry-outs continue the bit
string. They arrive in order from high position value to low
position value.
*/
for (size_t i = 0; i < DigitsAfter; ++i)
Decimal[i] = Source[DigitsBefore + 1 + i] - '0';
for (char *High = Decimal, *Low = Decimal + DigitsAfter;
High < Low && !Determined();)
{
// Multiply by two.
char Carry = 0;
for (char *p = Low; High < p--;)
{
/* This is elementary school multiplication: We multiply
the digit by the multiplicand and add the carry. The
result is separated into a single digit (n % 10) and a
carry (n / 10).
*/
char n = *p * 2 + Carry;
Carry = n / 10;
n %= 10;
/* Here we discard trailing zeros: If the new digit is zero
and is in the lowest position, we discard it and shorten
the numeral we are working with. Otherwise, we record the
new digit.
*/
if (n == 0 && p == Low-1)
--Low;
else
*p = n;
}
// Push carry into low end of the bits we are accumulating.
PushBitLow(Carry);
}
delete [] Decimal;
}
// Conversion operator. Returns a Float converted from this object.
operator Float() const { return GetValue(); }
};
#include <iostream>
#include <cstdio>
#include <cstdlib>
static void Test(const char *Source)
{
std::cout << "Testing " << Source << ":\n";
DecimalToFloat<float> x(Source);
char *end;
float e = std::strtof(Source, &end);
float o = x;
/* Note: The C printf is used here for the %a conversion, which shows the
bits of floating-point values clearly. If your C++ implementation does
not support this, this may be replaced by any display of floating-point
values you desire, such as printing them with all the decimal digits
needed to distinguish the values.
*/
std::printf("\t%a, %a.\n", e, o);
if (e != o)
{
std::cout << "\tError, results do not match.\n";
std::exit(EXIT_FAILURE);
}
}
int main(void)
{
Test("0");
Test("1");
Test("2");
Test("3");
Test(".25");
Test(".0625");
Test(".1");
Test(".2");
Test(".3");
Test("3.14");
Test(".00000001");
Test("9841234012398123");
Test("340282346638528859811704183484516925440");
Test("340282356779733661637539395458142568447");
Test("340282356779733661637539395458142568448");
Test(".00000000000000000000000000000000000000000000140129846432481707092372958328991613128026194187651577175706828388979108268586060148663818836212158203125");
// This should round to the minimum positive (subnormal), as it is just above mid-way.
Test(".000000000000000000000000000000000000000000000700649232162408535461864791644958065640130970938257885878534141944895541342930300743319094181060791015626");
// This should round to zero, as it is mid-way, and the even rule applies.
Test(".000000000000000000000000000000000000000000000700649232162408535461864791644958065640130970938257885878534141944895541342930300743319094181060791015625");
// This should round to zero, as it is just below mid-way.
Test(".000000000000000000000000000000000000000000000700649232162408535461864791644958065640130970938257885878534141944895541342930300743319094181060791015624");
}
One of the surprising things about a real, practical computer -- surprising to beginning programmers who have been tasked with writing artificial little binary-to-decimal conversion programs, anyway -- is how thoroughly ingrained the binary number system is in an actual computer, and how few and how diffuse any actual binary/decimal conversion routines actually are. In the C world, for example (and if we confine our attention to integers for the moment), there is basically one binary-to-decimal conversion routine, and it's buried inside printf, where the %d directive is processed. There are perhaps three decimal-to-binary converters: atof(), strtol(), and the %d conversion inside scanf. (There might be another one inside the C compiler, where it converts your decimal constants into binary, although the compiler might just call strtol() directly for those, too.)
I bring this all up for background. The question of "what's the actual algorithm for constructing floating-point numbers internally?" is a fair one, and I'd like to think I know the answer, but as I mentioned in the comments, I'm chagrined to discover that I don't, really: I can't describe a clear, crisp "algorithm". I can and will show you some code that gets the job done, but you'll probably find it unsatisfying, as if I'm cheating somehow -- because a number of the interesting details happen more or less automatically, as we'll see.
Basically, I'm going to write a version of the standard library function atof(). Here are my ground rules:
- I'm going to assume that the input is a string of characters. (This isn't really an assumption at all; it's a restatement of the original problem, which is to write a version of
atof.) - I'm going to assume that we can construct the floating-point number "0.0". (In IEEE 754 and most other formats, it's all-bits-0, so that's not too hard.)
- I'm going to assume that we can convert the integers 0-9 to their corresponding floating-point equivalents.
- I'm going to assume that we can add and multiply any floating-point numbers we want to. (This is the biggie, although I'll describe those algorithms later.) But on any modern computer, there's almost certainly a floating-point unit, that has built-in instructions for the basic floating-point operations like addition and multiplication, so this isn't an unreasonable assumption, either. (But it does end up hiding some of the interesting aspects of the algorithm, passing the buck to the hardware designer to have implemented the instructions correctly.)
- I'm going to initially assume that we have access to the standard library functions
atoiandpow. This is a pretty big assumption, but again, I'll describe later how we could write those from scratch if we wanted to. I'm also going to assume the existence of the character classification functions in<ctype.h>, especiallyisdigit().
But that's about it. With those prerequisites, it turns out we can write a fully-functional version of atof() all by ourselves. It might not be fast, and it almost certainly won't have all the right rounding behaviors out at the edges, but it will work pretty well. (I'm even going to handle negative numbers, and exponents.) Here's how it works:
- skip leading whitespace
- look for
'-' - scan digit characters, converting each one to the corresponding digit by subtracting
'0'(aka ASCII 48) - accumulate a floating-point number (with no fractional part yet) representing the integer implied by the digits -- the significand -- and this is the real math, multiplying the running accumulation by 10 and adding the next digit
- if we see a decimal point, count the number of digits after it
- when we're done scanning digits, see if there's an
e/Eand some more digits indicating an exponent - if necessary, multiply or divide our accumulated number by a power of 10, to take care of digits past the decimal, and/or the explicit exponent.
Here's the code:
#include <ctype.h>
#include <stdlib.h> /* just for atoi() */
#include <math.h> /* just for pow() */
#define TRUE 1
#define FALSE 0
double my_atof(const char *str)
{
const char *p;
double ret;
int negflag = FALSE;
int exp;
int expflag;
p = str;
while(isspace(*p))
p++;
if(*p == '-')
{
negflag = TRUE;
p++;
}
ret = 0.0; /* assumption 2 */
exp = 0;
expflag = FALSE;
while(TRUE)
{
if(*p == '.')
expflag = TRUE;
else if(isdigit(*p))
{
int idig = *p - '0'; /* assumption 1 */
double fdig = idig; /* assumption 3 */
ret = 10. * ret + fdig; /* assumption 4 */
if(expflag)
exp--;
}
else break;
p++;
}
if(*p == 'e' || *p == 'E')
exp += atoi(p+1); /* assumption 5a */
if(exp != 0)
ret *= pow(10., exp); /* assumption 5b */
if(negflag)
ret = -ret;
return ret;
}
Before we go further, I encourage you to copy-and-paste this code into a nearby C compiler, and compile it, to convince yourself that I haven't cheated too badly. Here's a little main() to invoke it with:
#include <stdio.h>
int main(int argc, char *argv[])
{
double d = my_atof(argv[1]);
printf("%s -> %g\n", argv[1], d);
}
(If you or your IDE aren't comfortable with command-line invocations, you can use fgets or scanf to read the string to hand to my_atof, instead.)
But, I know, your question was "How does 9 get converted to 1.001 * 2^3 ?", and I still haven't really answered that, have I? So let's see if we can find where that happens.
First of all, that bit pattern 10012 for 9 came from... nowhere, or everywhere, or it was there all along, or something. The character 9 came in, probably with a bit pattern of 1110012 (in ASCII). We subtracted 48 = 1100002, and out popped 10012. (Even before doing the subtraction, you can see it hiding there at the end of 111001.)
But then what turned 1001 into 1.001E3? That was basically my "assumption 3", as embodied in the line
double fdig = idig;
It's easy to write that line in C, so we don't really have to know how it's done, and the compiler probably turns it into a 'convert integer to float' instruction, so the compiler writer doesn't have to know how to do it, either.
But, if we did have to implement that ourselves, at the lowest level, we could. We know we have a single-digit (decimal) number, occupying at most 4 bits. We could stuff those bits into the significand field of our floating-point format, with a fixed exponent (perhaps -3). We might have to deal with the peculiarities of an "implicit 1" bit, and if we didn't want to inadvertently create a denormalized number, we might have to some more tinkering, but it would be straightforward enough, and relatively easy to get right, because there are only 10 cases to test. (Heck, if we found writing code to do the bit manipulations troublesome, we could even use a 10-entry lookup table.)
Since 9 is a single-digit number, we're done. But for a multiple-digit number, our next concern is the arithmetic we have to do: multiplying the running sum by 10, and adding in the next digit. How does that work, exactly?
Again, if we're writing a C (or even an assembly language) program, we don't really need to know, because our machine's floating-point 'add' and 'multiply' instructions will do everything for us. But, also again, if we had to do it ourselves, we could. (This answer's getting way too long, so I'm not going to discuss floating-point addition and multiplication algorithms just yet. Maybe farther down.)
Finally, the code as presented so far "cheated" by calling the library functions atoi and pow. I won't have any trouble convincing you that we could have implemented atoi ourselves if we wanted/had to: it's basically just the same digit-accumulation code we already wrote. And pow isn't too hard, either, because in our case we don't need to implement it in full generality: we're always raising to integer powers, so it's straightforward repeated multiplication, and we've already assumed we know how to do multiplication.
(With that said, computing a large power of 10 as part of our decimal-to-binary algorithm is problematic. As @Eric Postpischil noted in his answer, "Normally we want to figure out the binary floating-point result without actually calculating 10N." Me, since I don't know any better, I'll compute it anyway, but if I wrote my own pow() I'd use the binary exponentiation algorithm, since it's super easy to implement and quite nicely efficient.)
I said I'd discuss floating-point addition and multiplication routines. Suppose you want to add two floating-point numbers. If they happen to have the same exponent, it's easy: add the two significands (and keep the exponent the same), and that's your answer. (How do you add the significands? Well, I assume you have a way to add integers.) If the exponents are different, but relatively close to each other, you can pick the smaller one and add N to it to make it the same as the larger one, while simultaneously shifting the significand to the right by N bits. (You've just created a denormalized number.) Once the exponents are the same, you can add the significands, as before. After the addition, it may be important to renormalize the numbers, that is, to detect if one or more leading bits ended up as 0 and, if so, shift the significand left and decrement the exponent. Finally, if the exponents are too different, such that shifting one significand to the right by N bits would shift it all away, this means that one number is so much smaller than the other that all of it gets lost in the roundoff when adding them.
Multiplication: Floating-point multiplication is actually somewhat easier than addition. You don't have to worry about matching up the exponents: the final product is basically a new number whose significand is the product of the two significands, and whose exponent is the sum of the two exponents. The only trick is that the product of the two M-bit significands is nominally 2M bits, and you may not have a multiplier that can do that. If the only multiplier you have available maxes out at an M-bit product, you can take your two M-bit significands and literally split them in half by bits:
signif1 = a * 2M/2 + b
signif2 = c * 2M/2 + d
So by ordinary algebra we have
signif1 × signif2 = ac × 2M + ad × 2M/2 + bc × 2M/2 + bd
Each of those partial products ac, ad, etc. is an M-bit product. Multiplying by 2M/2 or 2M is easy, because it's just a left shift. And adding the terms up is something we already know how to do. We actually only care about the upper M bits of the product, so since we're going to throw away the rest, I imagine we could cheat and skip the bd term, since it contributes nothing (although it might end up slightly influencing a properly-rounded result).
But anyway, the details of the addition and multiplication algorithms, and the knowledge they contain about the floating-point representation we're using, end up forming the other half of the answer to the question of the decimal-to-binary "algorithm" you're looking for. If you convert, say, the number 5.703125 using the code I've shown, out will pop the binary floating-point number 1.011011012 × 22, but nowhere did we explicitly compute that significand 1.01101101 or that exponent 2 -- they both just fell out of all the digitwise multiplications and additions we did.
Finally, if you're still with me, here's a quick and easy integer-power-only pow function using binary exponentiation:
double my_pow(double a, unsigned int b)
{
double ret = 1;
double fac = a;
while(1) {
if(b & 1) ret *= fac;
b >>= 1;
if(b == 0) break;
fac *= fac;
}
return ret;
}
This is a nifty little algorithm. If we ask it to compute, say, 1021, it does not multiply 10 by itself 21 times. Instead, it repeatedly squares 10, leading to the exponential sequence 101, 102, 104, 108, or rather, 10, 100, 10000, 100000000... Then it looks at the binary representation of 21, namely 10101, and selects only the intermediate results 101, 104, and 1016 to multiply into its final return value, yielding 101+4+16, or 1021, as desired. It therefore runs in time O(log2(N)), not O(N).
And, tune in tomorrow for our next exciting episode when we'll go in the opposite direction, writing a binary-to-decimal converter which will require us to do... (ominous chord)
floating point long division!
You can do it with C++20 std::format:
double number = 123456.789;
auto s = std::format("{:.0e}\n", number); // s == "1e+05"
s.erase(s.size() - 2, 1); // s == "1e+5"
Until std::format is widely available you can use the {fmt} library, std::format is based on:
#include <fmt/core.h>
double number = 123456.789;
auto s = fmt::format("{:.0e}\n", number); // s == "1e+05"
s.erase(s.size() - 2, 1); // s == "1e+5"
Disclaimer: I'm the author of {fmt} and C++20 std::format.
I can't figure out how to get a single digit in the exponent field but the following matches all your other requirements.
#include <iostream>
#include <iomanip>
int main()
{
const double number = 123456.789;
std::cout << std::setprecision(0) << std::scientific << number << std::endl;
}
Output:
1e+05
EDIT:
Did a quick search through the standard (N3291) and couldn't find anything that talked about the number of digits in the exponent field when using scientific notation. This might be implementation defined.
So I'm not going to do quite all of the work for you, because this sounds like homework. But I'll get you started and you can fill in the gaps. So there's a handy data type in c++ that's called a union, with it you can have multiple data types take up the same space. This is very useful, if say you want to see the bit representation of a floating point number. The following code will output the binary representation of a floating point number:
#include <iostream>
using namespace std;
union b{
float flo;
int integ;
};
int main(){
b thing;
thing.flo=-40.1;
for(int i=31;i>=0;i--){
if((thing.integ & (1 << i)))
cout << 1;
else
cout << 0;
}
cout << endl;
}
All that's left for you to do is extract the mantissa and the exponent. You could run the routine once to generate the mantissa and again to generate the exponent. I'll give a brief explanation of how to do both and things to watch out for.
When generating the mantissa remember that IEEE uses a hidden 1 with a reserved code for zero, so there's always going to be an extra one that isn't in the bit representation. Essentially you'll check the sign bit print - or + depending on it, then 1. then skip to the mantissa and print what follows. Then you'll go back to the 23-30 bits, you want to convert it to an int, to do this multiply each bit by 2^i (23 bit is 0, 24 bit is 1, etc) and then you'll want to subtract the offset from the int. Then using the previously outline method output the binary representation of the exponent, I would consider not outputting until you hit a 1. Hope this helps.
You can cheat, and just use frexp.
float var = 1.54334E-34;
double var2 = 1.54334E-34;
printf("\n normal:%f\n sci:%e \n or \n sci:%E \n",var,var,var);
printf("\n normal:%f\n sci:%e \n or \n sci:%E \n",var2,var2* 1.0E3 ,var2 * 1.0e3);
I don't know any OpenCL but 32-bit C floats will hold values in the range of +/- 3.4e +/- 38 (~7 digits), and doubles much more. If you want arbitrary precision arithmetic/math you may want to look into GMP or MPFR.
Although C's floating-point types float and double typically use binary representations internally (almost invariably using formats conforming to IEEE-754), there are no standard routines for printing floating-point numbers in binary, or to convert binary strings to floating-point.
Basically there is almost no need for human-readable binary floating-point strings; floating-point numbers are almost always converted to and from decimal strings. (This can cause certain problems, though, since binary and decimal fractions are incommensurate, and almost always end up being imprecise approximations for each other — but that's a different story.)
The closest you can come to a binary floating-point string involves the %a format, although it's hexadecimal, not binary. But %a with printf will convert a floating-point number to a hexadecimal string, and %a with scanf will convert that sort of hexadecimal string back to a floating-point number.
It is probably easier to explain all this by example. Suppose I have the decimal number 12345.53125, and suppose I store it in a float variable:
float f = 12345.53125;
I can print it back out using %e or %f:
printf("%e\n", f);
printf("%f\n", f);
This prints
1.234553e+04
12345.531250
If I print it out using %a I get the rather odd-looking
0x1.81cc4p+13
Internally (in IEEE-754 single-precision floating-point) the number 12345.53125 is represented by a bit pattern which in hexadecimal is 0x4640e620, consisting of a 23-bit raw significand 0x40e620 and an 8-bit raw exponent 140. Shifting, applying the implicit "1" bit, and removing the exponent bias of 127, these work out to 0x1.81cc4 with an exponent of 13, which nicely matches %a's output.
In actual binary this number is
0b11000000111001.10001
or if you want an exponential notation it might be
0b1.100000011100110001e13
But, as I said, there's no built-in C function that will generate binary representations like that for you automatically.
If you did something like
double fraBinary = 1010.011001;
printf("%.9e\n", fraBinary);
and saw
1.010011001e+03
then you were not working with binary numbers at all: those numbers 1010.011001 and 1.010011001e+03 you saw and typed were pure decimal.
When you're working with ordinary floating-point numbers (using scientific notation or not), you don't usually need to worry too much about the binary representation (other than to know that it's there), and you don't usually have to work with significands ("mantissas") and exponents separately. If you don't already, you should know that the notation exemplified by
1.234553e+04
is almost universal. You can enter constants in your program that way:
double d = 1.234553e+04;
You can scan numbers from the user that way. You can take strings like "1.234553e+04" and convert them to float or double by calling the library functions atof() or strtod(). And as you know you can print them out (in decimal) using printf and %f or %e.
So what is it exactly that you want to do with your significands and/or exponents, in binary?
You might want the stdlib function frexp -- it will return the mantissa and exponent of any floating point number:
#include <math.h>
double val = ... something
int exp;
double mant = frexp(val, &exp);
printf("%f is %f * 2^%d\n", val, mant, exp);
Note that the mantissa will always have an absolute value in the range [0.5,1.0), so in your case you might want to multiply it by 2.
Unclear from your question, but you might also be asking how to print a number in binary ascii. The standard library does not provide any way to do that, so you need to do it manually, converting the number into a sequence of 0/1 digits. You can do that with frexp and repeatedly doubling the number.
void binary_double(double v, FILE *fp) {
int exp;
v = frexp(v, &exp);
if (v < 0) {
fputc('-', fp);
v = -v; }
if (v == 0.0) {
fputc('0', fp);
} else if (v <= 1.0) {
if (exp <= 0) {
fputc('.', fp);
while (exp++ < 0) fputc('0', fp); }
while (v > 0 || exp > 0) {
v *= 2;
if (v >= 1.0) {
fputc('1', fp);
v -= 1.0;
} else {
fputc('0', fp); }
if (exp > 0) {
if (--exp == 0) fputc('.', fp); } }
} else if (v != 0.0) {
fputs("Inf", fp);
} else {
fputs("Nan", fp); }
}
A small modification to this could output in scientific notation.