C++: Счастливый билет с длинной арифметикой

Счастливый трамвайный билет - это такой, у которого сумма первых трёх цифр номера равна сумме трёх последних. При встрече его полагается съесть.

Сколько таких билетов всего? Какова вероятность встретить счастливый?

Алгоритм для этих вычислений в Википедии настолько ужасен, что народ с Хабра довольно быстро породил в комментариях огромное количество вариантов на C++, Perl и... SQL.

Я тоже не смог пройти мимо и написал считалку на C++ с арифметикой указателей и поддержкой длинной арифметики. При желании она может считать хоть 12-значные числа.

Оптимизировал всем, о чём пишут в пособиях для начинающих. Получилась миниатюрная машина Тьюринга, которая бегает указателем по числам и считает разряды:

void inline count_lucky(unsigned int num_length_val)
{
  bool is_odd = (num_length_val % 2) > 0;
  unsigned int num_length = (is_odd) ? num_length_val - 1 : num_length_val;
  register unsigned int lucky=1, total=pow(10.0,(int)num_length), i;
  char *num = new char[num_length], *end=num+(num_length-1);
  register char *pos=end;
  for(i=0; i < num_length; i++)
    num[i]=0;
  while(pos>=num)
  {
     if((*pos)<9)
     {
        (*pos)++;
        if(pos==end)
        {
           if(is_lucky((unsigned char*)num, num_length))
             lucky++;
        }
        else
          pos++;
     }
     else
     {
       *pos=-1;
       pos--;
     }
  }
  printf("Lucky are %d of %d (%.3f%%)\n",(is_odd) ? lucky * 10 : lucky, (is_odd) ? total * 10 : total,((float)lucky/total*100));
  delete[] num;
}
bool inline is_lucky(unsigned char* items, unsigned int items_count)
{
  unsigned char val1=0, val2=0;
  unsigned int half = items_count >> 1;
  for(unsigned int i=0; i < half; i++)
  {
    val1 += items[i];
    val2 += items[items_count-1-i];
  }
  return (val1==val2);
}

Увы! Как показывает практика, уже на 7-значном билете тупой перебор, развёрнутый и оптимизированный компилятором, оказывается эффективней. Похоже, компилятор попросту выполняет сам большую часть явно заданных вычислений.
В этом легко убедиться, запустив тест хотя бы для 7 разрядов:

void inline count_lucky(unsigned int num_length);
bool inline is_lucky(unsigned char* items, unsigned int items_count);

int _tmain(int argc, _TCHAR* argv[])
{
  clock_t start = clock(), mine;
  count_lucky(7);
  mine=clock();
  printf("Mine time was: %d\n", (mine - start));
  count_lucky_fromwiki();
  printf("His time was: %d\n", (clock() - mine));
  return 0;
}

void count_lucky_fromwiki()
{
  int total=0,lucky=0;
  for(int i1=0; i1<10; i1++)
    for(int i2=0; i2<10; i2++)
      for(int i3=0; i3<10; i3++)
        for(int i4=0; i4<10; i4++)
          for(int i5=0; i5<10; i5++)
            for(int i6=0; i6<10; i6++)
              for(int i7=0; i7<10; i7++, total++)
                  if(i1+i2+i3 == i5+i6+i7)
                    lucky++;
  printf("Lucky are %d of %d (%.3f%%)\n",lucky,total,((float)lucky/total*100));
}

Человек уже не может обогнать машину :(. Слава роботам!

В качестве утешения - на 8 вложенный циклах валился компилятор из Borland C++ Builder 6.