Re: Stable priority queue

From: Siemel Naran (SiemelNaran_at_REMOVE.att.net)
Date: 04/07/04 

Date: Wed, 07 Apr 2004 09:53:41 GMT

"Claudio Puviani" <puviani@hotmail.com> wrote in message news:0izcc.26080

> Gaa! Do people no longer do basic back-of-the envelope calculations?
>
> If a 5GHz computer had an integer increment that took only one CPU cycle
and
> did NOTHING but increment a 64-bit int 5 billion times per second 24-hours
a
> day without interruption, it would take 117 _YEARS_ before you ran out of
> numbers!!! If you throw in the obligatory jump to implement the loop and
> made the jump also take a single CPU cycle, the duration leaps to a
whopping
> 234 years.

How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19
possible numbers. In one year we can perform 86,400 seconds * 5 billion
increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9.
Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?

For 32 bit integers, I get 2^32 / 4.32e14 = 9.94e-6 years which is less than
one day.

So now the question is how to get a 64 bit integer. On some platforms, this
will be int, on others long, and on others long long. BTW, is long long a
standard type? My compiler Borland 6 accepts long long but not long long
long.

I thought people proposed adding int32, int64 to the standard. Is there any
update on this?

We could also use std::bitset<64>, but it doesn't have an operator++ or
operator+.

We could also use the sizeof trick though, which is a cool use of template
template parameters.

const int CHAR_BITS=8;
template <class T>
struct Eq16
{
   static const bool result=((sizeof(T)*CHAR_BITS)==16);
};
void test_find_typelist(ostream& out)
{
   typedef typelist<int, typelist<short, typelist<char> > > BasicTypes;
   typedef find_typelist<Eq16, BasicTypes>::result int16;
   out << sizeof(int16) << '\n'; // print 2
}

where

template <class T, class U=void>
struct typelist
{
   typedef T car;
   typedef U cdr;
};

template <template <class> class Predicate, class list>
struct typelist_find
{
   typedef typename list::car car;
   typedef typename list::cdr cdr;

   typedef typename
      template_if<
             Predicate<car>::result,
             car,
             typename find_typelist<Predicate,cdr>::result
> :: result
         result;
};

template <template <class> class Predicate>
struct typelist_find<Predicate,void>
{
   typedef void result;
};

> The most generous thing I can say about using a 128-bit integer for this
> purpose is that it's absurdly over-engineered. There's a lot worse that
> could be said about the idea.

Such as?

Anyway, quantum computers of the future may indeed be much faster. But as a
practical matter I'd just use long long.

Relevant Pages

  • Re: function template
    ... > I was working with a simple function template to find the min of two values. ... struct Promote ... template struct Promote{typedef unsigned long ... template struct Promote{typedef int ...
    (comp.lang.cpp)
  • curiously recurring template pattern problem
    ... typedef typename Derived::type type; ... struct Y: public X ... derived type as a template parameter to X (aka the curiously recurring ...
    (comp.lang.cpp)
  • Re: template typedef
    ... template <typename T> ... Is there a way to typedef the first part, so I can do something like: ... struct typedXptr { ...
    (microsoft.public.vc.language)
  • Re: How to create an array of data types only
    ... > like to do is create a global array of the class types ... through it using the print_type_names template function. ... struct TypeList ... typedef T Head; ...
    (comp.lang.cpp)
  • Re: Process dump facility public API - pdpublic.h
    ... struct _PDOPTIONS *pSystemDefaults; /* Ptr to System Defaults struct */ ... typedef DDPREQUEST *PDDREQUEST; ... also be specified in the DDPREQUEST flags. ... /* PDUNION is used in both the PDPROCESS and PDPROCESS2 structures. ...
    (comp.os.os2.bugs)