Topic: ldexp (not sure if it's a "std" or "lang" issue)


Author: "r822" <remi822@hotmail.com>
Date: Thu, 15 Nov 2001 16:57:54 GMT
Raw View
The point is probably that, to compute such a value, you only need to add
'i'
to the exponent of the IEEE representation of the float or double number.

In other words, it's like doing :

struct diy_double {
    int sign : 1 ;
    int mantissa : 23 ;
    int exponent : 8 ;
};

union fake_double {
    double m_double ;
    diy_double m_struct ;

inline double ldexp2(double x, const short i)
{
fae_double my_fake ;
my_fake.m_double = x ;
my_fake.m_struct.exponent += i ;
return m_double ;
}

And it should be much faster in assembly code.


"Mycroft Holmes" <holmes@technologist.REMOVEME.com> a    crit dans le message
news: xS6G7.33758$sq5.1811146@news.infostrada.it...
> I was wandering what the purpose of the ldexp function is.
> I know what it *does*, but it's not clear *why* I should use it.
>
> ldexp(x,i) by definition equals x*2^i, i being a signed integer.
> I expected ldexp to be VERY FAST, because it's a standard library function
> (so should be ultra-optimal pure asm).
> However this is not the case. We tested several compilers, under both
win32
> and unix.
> The following raw implementation of the definition (which btw has minimal
> differences with ldexp):
>
> template <typename real_t>
> inline real_t ldexp2(real_t x, const short i)
> {
>  return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
> }
>
> proved at least 3 times faster than ldexp (for double), not to mention the
> fact that we specialized the template for IEEE floating/double/long
double,
> getting even more speed.
> More, ldexp2 is portable (I think there's no doubt on that).



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "Al Grant" <tnarga@arm.REVERSE-NAME.com>
Date: Thu, 15 Nov 2001 21:26:01 GMT
Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3BEB3B07.A79C992B@wizard.net...
> John Nagle wrote:
> ...
> >     The spec for "ldexp" requires generation of INF and NAN
> > in overflow cases, so the machine-oriented implementation isn't
> > trivial.
>
> I think that applies only to the case where
> std::numeric_traits<double>::is_iec559 is true. Otherwise, overflow
> handling is unspecified.

numeric_limits.  And the C89 math library spec, which is
incorporated by reference, says overflow is a range error,
which must set errno and return a correctly signed HUGE_VAL.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Wed, 7 Nov 2001 16:10:27 GMT
Raw View
Mycroft Holmes wrote:
>
> I was wandering what the purpose of the ldexp function is.
> I know what it *does*, but it's not clear *why* I should use it.
>
> ldexp(x,i) by definition equals x*2^i, i being a signed integer.
> I expected ldexp to be VERY FAST, because it's a standard library function
> (so should be ultra-optimal pure asm).
> However this is not the case. We tested several compilers, under both win32
> and unix.
> The following raw implementation of the definition (which btw has minimal
> differences with ldexp):
>
> template <typename real_t>
> inline real_t ldexp2(real_t x, const short i)
> {
>  return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
> }
>
> proved at least 3 times faster than ldexp (for double), not to mention the
> fact that we specialized the template for IEEE floating/double/long double,
> getting even more speed.
> More, ldexp2 is portable (I think there's no doubt on that).
>
> Feel free to post your comments.

The only legitimate reason for the existence of ldexp(), is the
possibility on some machines of implementing it as direct floating point
instructions that can be much faster than the code you've listed. On
particular platforms, there might be no advantage, but there's no excuse
for an implementation to implement it three times slower than that code.
Except, of course, that this is purely a "quality of implementation"
issue, and hence outside the scope of the standard.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "Anthony Williams" <anthwil@nortelnetworks.com>
Date: Wed, 7 Nov 2001 18:27:07 GMT
Raw View
"Mycroft Holmes" <holmes@technologist.REMOVEME.com> wrote in message
news:xS6G7.33758$sq5.1811146@news.infostrada.it...
> I was wandering what the purpose of the ldexp function is.
> I know what it *does*, but it's not clear *why* I should use it.
>
> ldexp(x,i) by definition equals x*2^i, i being a signed integer.
> I expected ldexp to be VERY FAST, because it's a standard library function
> (so should be ultra-optimal pure asm).
> However this is not the case. We tested several compilers, under both
win32
> and unix.
> The following raw implementation of the definition (which btw has minimal
> differences with ldexp):
>
> template <typename real_t>
> inline real_t ldexp2(real_t x, const short i)
> {
>  return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
> }
>
> proved at least 3 times faster than ldexp (for double), not to mention the
> fact that we specialized the template for IEEE floating/double/long
double,
> getting even more speed.
> More, ldexp2 is portable (I think there's no doubt on that).

The signature of ldexp is

double ldexp(double x,int exp);

So, the first difference between the standard one and your template is the
possible range of the exponent - ints usually have a larger range than
shorts. This isn't really a problem in most cases though, due to arithmetic
overflow - 2^32767 is generally outside the floating point range.

Secondly, and more importantly, doubles can have a range at least of
1e-37 -> 1e+37, so it is OK to multiply by 10^73 for at least some values.
10^73 is ~2^242. I don't know of any implementations where 2^242 can be
represented as an integer. Indeed, for values of exp greater than
log2(INT_MAX)-1 (31 or 63 on common implementations) the results of your
template are wrong, as 1<<i will overflow.

Try

std::cout<<ldexp(1e-37,122)<<std::endl;
std::cout<<ldexp2<double>(1e-37,122)<<std::endl;

on my (32-bit) system it prints

0.531691
6.71088e-30

Unsurprisingly, the result of ldexp is correct, whereas the result of ldexp2
is not. There is no benefit in being fast and wrong.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optical Components Ltd
The opinions expressed in this message are not necessarily those of my
employer



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: Andrew Koenig <ark@research.att.com>
Date: Wed, 7 Nov 2001 19:35:08 GMT
Raw View
Mycroft> template <typename real_t>
Mycroft> inline real_t ldexp2(real_t x, const short i)
Mycroft> {
Mycroft>  return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
Mycroft> }

Mycroft> proved at least 3 times faster than ldexp (for double), not
Mycroft> to mention the fact that we specialized the template for IEEE
Mycroft> floating/double/long double, getting even more speed.  More,
Mycroft> ldexp2 is portable (I think there's no doubt on that).

On the other hand, it doesn't work when the second argument
exceeds the number of bits in an int.

--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: Ron Natalie <ron@sensor.com>
Date: Wed, 7 Nov 2001 19:44:17 GMT
Raw View

Andrew Koenig wrote:
>
> Mycroft> template <typename real_t>
> Mycroft> inline real_t ldexp2(real_t x, const short i)
> Mycroft> {
> Mycroft>  return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
> Mycroft> }
>
> Mycroft> proved at least 3 times faster than ldexp (for double), not
> Mycroft> to mention the fact that we specialized the template for IEEE
> Mycroft> floating/double/long double, getting even more speed.  More,
> Mycroft> ldexp2 is portable (I think there's no doubt on that).
>
> On the other hand, it doesn't work when the second argument
> exceeds the number of bits in an int.
>
or even equals the number of bits in an int.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "Mycroft Holmes" <holmes@technologist.REMOVEME.com>
Date: Thu, 8 Nov 2001 18:02:57 CST
Raw View
Sorry if my 1st posting was not clear enough.
I said nothing about ldexp2 being EQUIVALENT to ldexp, and in fact it
differs in the prototype
(my real ldexp2 uses references), and in being range-limited (and in fact I
overloaded it for floating point, but I didn't post the code since it's
platform-dependent)

I only asked why ldexp is so slow, that I can write a function "by hand"
which outperforms it by 3 times and more. this is unexpected.
If I write my own -say- memcpy, this is expected to be AT MOST as fast as
native memcpy, never FASTER.

To remove the limit range it's not difficult at all:
put something like

static const double two_raised_to[] = { 1, 2, 4, 8, 16, [...], HUGE_VAL };

and then something like

return ( i>=0 ? x*two_raised_to[i] : x/two_raised_to[-i] );


this should use about the same processing power, and have no limitation.

--
 The set of solutions is never empty.
 Two solutions together form a new problem.
-- Mycroft Holmes

> So, the first difference between the standard one and your template is the
> possible range of the exponent - ints usually have a larger range than
> shorts. This isn't really a problem in most cases though, due to
arithmetic
> overflow - 2^32767 is generally outside the floating point range.
>
> Secondly, and more importantly, doubles can have a range at least of
> 1e-37 -> 1e+37, so it is OK to multiply by 10^73 for at least some values.
> 10^73 is ~2^242. I don't know of any implementations where 2^242 can be
> represented as an integer. Indeed, for values of exp greater than
> log2(INT_MAX)-1 (31 or 63 on common implementations) the results of your
> template are wrong, as 1<<i will overflow.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: John Nagle <nagle@animats.com>
Date: Thu, 8 Nov 2001 19:08:32 CST
Raw View
Anthony Williams wrote:
> "Mycroft Holmes" <holmes@technologist.REMOVEME.com> wrote in message
> news:xS6G7.33758$sq5.1811146@news.infostrada.it...
> > I was wandering what the purpose of the ldexp function is.
> > I know what it *does*, but it's not clear *why* I should use it.
> > I expected ldexp to be VERY FAST, because it's a standard library function
> > (so should be ultra-optimal pure asm).
> > However this is not the case.

    "ldexp" has an obvious slow implementation using "pow", and
a machine-oriented implementation for floating point with
binary exponents.  You're probably seeing the former.

    The spec for "ldexp" requires generation of INF and NAN
in overflow cases, so the machine-oriented implementation isn't
trivial.

                                        John Nagle
     Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 9 Nov 2001 10:16:02 CST
Raw View
John Nagle wrote:
...
>     The spec for "ldexp" requires generation of INF and NAN
> in overflow cases, so the machine-oriented implementation isn't
> trivial.

I think that applies only to the case where
std::numeric_traits<double>::is_iec559 is true. Otherwise, overflow
handling is unspecified.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]





Author: "Mycroft Holmes" <holmes@technologist.REMOVEME.com>
Date: Wed, 7 Nov 2001 10:52:21 GMT
Raw View
I was wandering what the purpose of the ldexp function is.
I know what it *does*, but it's not clear *why* I should use it.

ldexp(x,i) by definition equals x*2^i, i being a signed integer.
I expected ldexp to be VERY FAST, because it's a standard library function
(so should be ultra-optimal pure asm).
However this is not the case. We tested several compilers, under both win32
and unix.
The following raw implementation of the definition (which btw has minimal
differences with ldexp):

template <typename real_t>
inline real_t ldexp2(real_t x, const short i)
{
 return ( i<0 ? x /= ( 1 << -i ) : x *= ( 1 << i ) );
}

proved at least 3 times faster than ldexp (for double), not to mention the
fact that we specialized the template for IEEE floating/double/long double,
getting even more speed.
More, ldexp2 is portable (I think there's no doubt on that).


Feel free to post your comments.

M.H.
--
 The set of solutions is never empty.
 Two solutions together form a new problem.
-- Mycroft Holmes

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]