Sunday, April 16, 2017

Digest for comp.lang.c++@googlegroups.com - 13 updates in 7 topics

Tim Rentsch <txr@alumni.caltech.edu>: Apr 16 08:35AM -0700

> flowed format specified in the content type header:
 
> Content-Type: text/plain; charset=utf-8; format=flowed
 
> I.e. you're using a somewhat deficient newsreader. [...]
 
Perhaps so, but let me offer two comments in response.
 
1. I see wrapping problems more often in your postings than
other folks who use format=flowed.
 
2. If what you are posting is primarily code, it's probably a
good idea to turn off format=flowed.
 
(And if the newsreader you're using doesn't let you easily turn
off format=flowed then it too is a somewhat deficient newsreader.)
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 17 01:14AM +0200

On 16-Apr-17 5:35 PM, Tim Rentsch wrote:
> good idea to turn off format=flowed.
 
> (And if the newsreader you're using doesn't let you easily turn
> off format=flowed then it too is a somewhat deficient newsreader.)
 
Flowed format is old, common technology now (I remember we added support
for it in clc++m in the 2000's), and it solves the problem.
 
It's a simple technical solution to a technical problem.
 
If Emacs doesn't handle it well, then just use a newsreader that does. ;-)
 
 
Cheers & hth.,
 
- Alf
ram@zedat.fu-berlin.de (Stefan Ram): Apr 16 03:04PM

>The code below is a first rough scetch only.
 
I used type lists, but now I see that a partial template
specialization can be used for my purpose, and my code gets
smaller and simpler. I now also use »decltype« to avoid an
unecessary nesting of two structs. And I corrected the
size calculation, which now gives the expected results.
 
main.cpp
 
#include <cassert>
#include <cmath>
#include <cstdint>
#include <initializer_list>
#include <iostream>
#include <ostream>
 
/* section "mapping a number to a type" */
template< int I >struct at {};
template<>struct at< 0 >{ uint_least8_t member; };
template<>struct at< 1 >{ uint_least16_t member; };
template<>struct at< 2 >{ uint_least32_t member; };
template<>struct at< 3 >{ uint_least32_t member; };
template<>struct at< 4 >{ uint_least64_t member; };
template<>struct at< 5 >{ uint_least64_t member; };
template<>struct at< 6 >{ uint_least64_t member; };
template<>struct at< 7 >{ uint_least64_t member; };
 
/* section "logarithms" */
constexpr int log256( unsigned long long x )
{ constexpr long double d = log2( 256.0l );
return static_cast< int >
( log2( static_cast< long double >( x ))/d ); }
 
/* section "the range type" */
template<uint_least64_t l, uint_least64_t r>
struct range
{ decltype( at< log256( r - l ) >::member )member; };
 
int main()
{ { struct range<0,100> r; ::std::cout << sizeof r.member <<
'\n'; }
{ struct range<0,1000> r; ::std::cout << sizeof r.member
<< '\n'; }
{ struct range<0,1'000'000> r;
::std::cout << sizeof r.member << '\n'; }
{ struct range<0,1'000'000'000> r;
::std::cout << sizeof r.member << '\n'; }
{ struct range<0,10'000'000'000> r;
::std::cout << sizeof r.member << '\n'; } }
 
transcript
 
1
2
4
4
8
ram@zedat.fu-berlin.de (Stefan Ram): Apr 16 03:59PM

>template<>struct at< 5 >{ uint_least64_t member; };
>template<>struct at< 6 >{ uint_least64_t member; };
>template<>struct at< 7 >{ uint_least64_t member; };
 
This could be made more compact using uplog256:
 
constexpr int log256( unsigned long long const xull )
{ constexpr long double d = log2( 256.0l );
long double x = static_cast< long double >( xull );
long double l2x = log2( x );
long double q = l2x / d;
return static_cast< int >( q ); }
 
constexpr int uplog256( unsigned long long const x )
{ return static_cast< int >
( pow( 2.0l, ceil( log2( 1 + log256( x - 1 ))))); }
 
uplog256 answers the question:
 
Given memory sizes of 1, 2, 4, and 8 octets and 1 < x <
18446744073709551616, how many octets are needed to store
one out of x different values? (It will return one of
the values 1, 2, 4, or 8, e.g., 2 for 65536 and 4 for
65537.)
 
But I get »error: 'ceil(0.0)' is not a constant expression«
here, so I cannot use it as a constant expression.
ram@zedat.fu-berlin.de (Stefan Ram): Apr 16 08:01PM

>But I get »error: 'ceil(0.0)' is not a constant expression«
>here, so I cannot use it as a constant expression.
 
Ok, solved that and did some other modifications.
 
main.cpp
 
#include <cassert>
#include <cmath>
#include <cstdint>
#include <initializer_list>
#include <iostream>
#include <ostream>
#include <climits>
#include <type_traits>
 
/* section "mapping a number to a type" */
template< int I >struct atstruct {};
template<>struct atstruct< 1 >{ using type = uint_least8_t; };
template<>struct atstruct< 2 >{ using type = uint_least16_t; };
template<>struct atstruct< 4 >{ using type = uint_least32_t; };
template<>struct atstruct< 8 >{ using type = uint_least64_t; };
template< int I >using at = typename atstruct< I >::type;
 
/* section "logarithms" */
constexpr int log256( unsigned long long const x )
{ return static_cast< int >
( log2l( static_cast< long double >( x ))/ log2l( 256.0l ) ); }
 
template< typename UnsignedType >
constexpr UnsignedType round_up_to_power_of_2( UnsignedType v)
{ static_assert
( ::std::is_unsigned< UnsignedType >::value,
"Only works for unsigned types" );
v--; for( size_t i = 1; i < sizeof( v )* CHAR_BIT; i *= 2 )
v |= v >> i; return ++v; }
 
/* returns the number of octets (1, 2, 4, or 8) needed to store
one from x possible values. */
constexpr int uplog256( unsigned long long const x )
{ return static_cast< int >
( round_up_to_power_of_2
( static_cast< unsigned >( 1 + log256( x - 1 )))); }
 
/* section "the range type" */
template<uint_least64_t l, uint_least64_t r>
struct range
{ at< uplog256( r - l )> member; };
 
/* section "main" */
int main()
{
{ struct range<0,100> r; ::std::cout << sizeof r.member << '\n'; }
{ struct range<0,1000> r; ::std::cout << sizeof r.member << '\n'; }
{ struct range<0,1'000'000> r;
::std::cout << sizeof r.member << '\n'; }
{ struct range<0,1'000'000'000> r;
::std::cout << sizeof r.member << '\n'; }
{ struct range<0,10'000'000'000> r;
::std::cout << sizeof r.member << '\n'; }}
 
transcript
 
1
2
4
4
8
ram@zedat.fu-berlin.de (Stefan Ram): Apr 16 08:39PM

>>one out of 10 values.
>That depends on whether you want "maximum speed" or "minimum size". IIRC
>an enum tends to be an int under the hood.
 
One also can use an »enum-base«, that is, »":" type-specifier-seq«.
 
For example,
 
enum E : short { a, b, c };
 
.
Tim Rentsch <txr@alumni.caltech.edu>: Apr 16 01:36PM -0700


> I read it mentioned so very often, but never actually
> programmed a solution myself IIRC. So here it is in C++:
 
> [... approximately 120 lines of C++ ...]
 
I'm at a loss for words. I hope you don't give this as an
example to students.
 
> is way too long, but I was not yet able to find a elegant
> decomposition into several smaller function with less than
> three parameters each.
 
This function is clumsy because the abstraction you have chosen
isn't very good. Instead try keeping track of a bitmap of what
squares are covered already (and so putting a queen on any such
square is not allowed). Also, if you always try every possible
position at each level of search, there will be an enormous
number of duplicate solutions (a factor of 8 factorial, IIANM).
One easy way around that problem is to put the k'th queen in
the k'th row, since any solution must have one queen in each row.
Vir Campestris <vir.campestris@invalid.invalid>: Apr 16 09:14PM +0100

On 14/04/2017 21:38, Stefan Ram wrote:
> should be just 1, because one byte is enough to store
> one out of 10 values.
 
That depends on whether you want "maximum speed" or "minimum size". IIRC
an enum tends to be an int under the hood.
 
Andy
Tim Rentsch <txr@alumni.caltech.edu>: Apr 16 08:52AM -0700

>> lines I would like to be able to compile it. If the
>> code is written in "expressive" C++ I can't do that.
 
> I've posted the current version of Expressive C++ on GitHub: [...]
 
I still cast my vote for using regular C++ rather than the
"expressive" flavor. I suppose I could get your libraries and go
to the trouble of making them available for compiling your code,
but in practical terms I know I'm not going to. Plus, the
newsgroup here is supposed to be primarily about C++, and code
written in "expressive C++" kind of detracts from that.
 
> And considering that you offered (if memory serves me!), I would be
> very grateful if you could take over the balanced tree tutorial.
 
My offer was just to explain how threading works (I already gave
an explanation of how balancing works). My reason for wanting to
see the tutorial continue is to see how you would write it in C++.
I understand the algorithm, but I want to get more exposure to
current C++ style.
 
> Another reason for that, if you have time, is that you evidently are
> familiar with the subject, knowing stuff that I didn't know. ;-)
 
I didn't when I started. Plus, if you write the code yourself,
you will get the benefit of both having figured it out yourself
and (presumably) my comments on the result. If I finish it you
won't get either of those (and I won't get the benefit of seeing
how you would do it).
Ralf Goertz <me@myprovider.invalid>: Apr 16 01:39PM +0200

Am Sat, 15 Apr 2017 19:39:21 +0200
> >>> function is bogus here?
> I did the same, with 1 billion iterations (code below **):
> No optimization sincos is faster:
 
Yeah stupid me. I only tried it with -O2 so I got no difference. When I
compared the assembler codes I forgot the -O2.
 
 
> > I had placed [0, M_2_PI)-uniformly distributed angles into the real
> > components of the elements of vc beforehand.
> Note that M_2_PI is defined as "two times the reciprocal of pi"
 
Ouch, thanks. I should have looked at the value. So there seems to be no
constant 2*π defined in math.h? Isn't that constant worth being defined?
Of course I can use 2*M_PI, but then I could also use 2/M_PI.
Tim Rentsch <txr@alumni.caltech.edu>: Apr 16 08:23AM -0700

> bad for single precision floats.
> The iterative multiplication tends to create cumulative errors for
> small angles. Chris's method is by far more accurate. [...]
 
I suggest an intermediate approach that uses sin/cos less but
still has good accuracy. The roots needed are all 'baseroot'
times the nth roots of unity. The nth roots of unity can be
calculated using only O( log n ) calls to sin/cos, plus O(n)
multiplications, as follows. Calculate e ** (k*2*pi*i/n), with
k = all powers of two < n/2 (this is done using sin/cos). Now
all the roots of unity can be calculated using these factors
using only one multiplication per root, using a binary-recursive
expansion. The results take one more multiplication each. (In
case it needs saying the aforementioned multiplications are of
complex numbers.)
 
Also, the roots of unity are symmetric about the x axis, so
only half of them need to be calculated directly, the other
half can be done with just a sign change of the imaginary
component.
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 15 10:47PM -0700

Fwiw, here is some background, if interested please _read_all_:
 
https://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/296471
 
Okay, I have not yet ported this to C++11 yet, but the fast-pathed
semaphore I posted here happens to be an integral step in the process:
 
https://groups.google.com/d/topic/comp.lang.c++/60IpFwqbtu8/discussion
 
If you read all of the data in the links, one can implement it for
themselves. Is there any interest in my upcoming pure c++ std impl of
this rw-mutex? Thanks.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 16 08:37AM +0200

On 16-Apr-17 7:47 AM, Chris M. Thomasson wrote:
 
> If you read all of the data in the links, one can implement it for
> themselves. Is there any interest in my upcoming pure c++ std impl of
> this rw-mutex? Thanks.
 
I'm not able to follow (grok) much of what you post, but I think, it's
somewhere on the cutting edge, and when you enjoy doing it then it's
worth doing regardless of interest. We the sheeple will follow later,
presumably. Because there's not much incentive to use these techniques
until they're simple to use for the average Joe Sheep, but the
techniques don't become simple until they've been used for some time,
which is where the specially interested play their rôle. ;-)
 
 
Cheers!,
 
- Alf
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)