k нулей - Этюды для программистов

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, vadimcher, Вы писали:

S>По одному из вариантов программы (пусть не самый быстрый) на процессоре рейтинга 2000 считается 70 000 000 знаков в секунду.

S>число а17 — это приблизительно миллиардная степень двойки.

S>для расчета 2^1 000 000 000 придется обработать (1000000000 ^ 2) / (2 * 3.31) знаков. (3.31 — коэффициент ширины десятичного представления степени двойки)
S>итого это 151 057 401 812 688 821 знаков.
S>для их расчета 1-му процессору потребуется 2 157 962 883 секунд
S>или 599 434 часов
S>или 24 976 суток
S>или 68 лет

S>если на эту задачу бросить 70 процессоров, то потребуется почти год.

S>явно, что а17 расчитывалось, либо каким то другим способом (не удвоением), либо на каком то жутко мощном майнфрэйме

S>ну или на огромном количестве компов...

Сделал алгоритм, работающий заметно быстрее.

В скобках — реальное кол-во умножений.
Основные моменты, из-за которых получилось быстрее:
— если в N-й степени двойки есть K нулей подряд, то в N+1,N+2,N+3 — не менее (K-1), N+4,N+5,N+6 — не менее (K-2) и т.д.
И обратно: если в N-й степени двойки есть не более K нулей подряд, то в N-1 — не более (K+1), N-2,N-3,N-4 — не более (K+2)
Поэтому скакнув на несколько степеней вперед мы частенько сможем отбросить все промежуточные.
— Число хранится в виде групп десятичных цифр, и быстро можно умножить это число на степень двойки, умещающееся в десятичном представлении в одной группе, кол-во нулей в группе берется из заранее посчитаной таблицы — кол-во нулей в начале, кол-во нулей в конце. Поэтому нули, идущие в середине группы, не определяются, и для i=(ширина группы — 2) a(i) неверно

Вот результат:

   0.000:  1 :          1 (         1)
   0.000:  2 :          2 (         2)
   0.000:  3 :        242 (       244)
   0.000:  4 :        377 (       296)
   0.000:  5 :       1491 (       518)
   0.000:  6 :       1492 (       522)
   0.000:  7 :       6801 (      1217)
   0.000:  8 :      14007 (      1922)
   0.469:  9 :     100823 (      9548)
  13.797: 10 :     559940 (     47855)
  55.641: 11 :    1148303 (     94153)
 667.266: 12 :    4036338 (    317876)
 667.281: 13 :    4036339 (    317880)

Pentium(R)D 3.4 MHz
В последнем столбце — реальное кол-во умножений

Аппроксимация времени — квадратичная, и до арда потребуется примерно 667*(1.000.000.000 / 4.036.338)^2 = 40.000.000 сек = 11.111 час = 462 дня

Судя по времени появления a17 и с учетом прогресса подобный алгоритм скорее всего и был использован

А вот и код:

#include "stdafx.h"
#include <vector>
#include <time.h>

#pragma warning (disable : 4244)

#define My_N 4
//#define CORRECT_ZEROS


template<int N>
struct HolderType;

template<>
struct HolderType<1>
{
    typedef unsigned char ValueType;
    typedef unsigned short MulType;
    enum {
        TableSize = 10
    };
};

template<>
struct HolderType<2>
{
    typedef unsigned char ValueType;
    typedef unsigned short MulType;
    enum {
        TableSize = 100
    };
};

template<>
struct HolderType<3>
{
    typedef unsigned short ValueType;
    typedef unsigned MulType;
    enum {
        TableSize = 1000
    };
};

template<>
struct HolderType<4>
{
    typedef unsigned short ValueType;
    typedef unsigned MulType;
    enum {
        TableSize = 10000
    };
};

template<>
struct HolderType<5>
{
    typedef unsigned int ValueType;
    typedef unsigned long long MulType;
    enum {
        TableSize = 100000
    };
};

template<>
struct HolderType<6>
{
    typedef unsigned int ValueType;
    typedef unsigned long long MulType;
    enum {
        TableSize = 1000000
    };
};

template<>
struct HolderType<7>
{
    typedef unsigned int ValueType;
    typedef unsigned long long MulType;
    enum {
        TableSize = 10000000
    };
};

template<>
struct HolderType<8>
{
    typedef unsigned int ValueType;
    typedef unsigned long long MulType;
    enum {
        TableSize = 100000000
    };
};

struct ZerosInfo 
{
    unsigned char m_beginZeros;
    unsigned char m_endZeros;
#ifdef CORRECT_ZEROS
    unsigned char m_maxZeros;
#endif
    ZerosInfo()
    {}
    ZerosInfo(unsigned b, unsigned e, unsigned m)
        : m_beginZeros(b)
        , m_endZeros(e)
#ifdef CORRECT_ZEROS
        , m_maxZeros(m)
#endif
    {}
};

template<int N>
struct CurrZerosInfo
{
    unsigned maxZeros;
    unsigned currZeros;
    CurrZerosInfo()
#ifdef CORRECT_ZEROS
        : maxZeros(0)
#else
        : maxZeros(N - 2)
#endif
        , currZeros(0)
    {}
    void AddNextDigit(ZerosInfo zi)
    {
        if(zi.m_beginZeros == N)
        {
            currZeros += N;
        }
        else
        {
            if(currZeros + zi.m_endZeros > maxZeros)
            {
                maxZeros = currZeros + zi.m_endZeros;
            }
#ifdef CORRECT_ZEROS
            if(zi.m_maxZeros > maxZeros)
            {
                maxZeros = zi.m_maxZeros;
            }
#endif
            currZeros = zi.m_beginZeros;
        }

    }
    void AddLastDigit(ZerosInfo zi)
    {
        if(currZeros + zi.m_endZeros > maxZeros)
        {
            maxZeros = currZeros + zi.m_endZeros;
        }
#ifdef CORRECT_ZEROS
        if(zi.m_maxZeros > maxZeros)
        {
            maxZeros = zi.m_maxZeros;
        }
#endif
    }
};

template<int N>
struct ZerosInfoRetriever
{
    ZerosInfo operator [] (unsigned i)
    {
        return m_table[i];
    }

    ZerosInfo m_table[HolderType<N>::TableSize];
    ZerosInfoRetriever()
    {
        GenNumber(0, ZerosInfo(0, 0, 0), N);
    }

#ifdef CORRECT_ZEROS
#define INFO_MAX_ZEROS info.m_maxZeros
#else
#define INFO_MAX_ZEROS 0
#endif
    void GenNumber(unsigned upperPart, ZerosInfo info, int n)
    {
        if(n > 0)
        {
            GenNumber(
                upperPart * 10, 
                ZerosInfo(
                    info.m_beginZeros + (upperPart == 0 ? 1 : 0), info.m_endZeros + 1, INFO_MAX_ZEROS),
                n - 1);
#ifdef CORRECT_ZEROS
            if(info.m_endZeros > info.m_maxZeros && upperPart != 0)
                info.m_maxZeros = info.m_endZeros;
#endif
            for(int i = 1; i < 10; ++i)
            {
                GenNumber(
                    upperPart * 10 + i, 
                    ZerosInfo(info.m_beginZeros, 0, INFO_MAX_ZEROS),
                    n - 1);
            }
        }
        else m_table[upperPart] = info;
    }
};

template<int N>
struct DigitsGroup
{
    static ZerosInfoRetriever<N> ms_retriever;
    typename HolderType<N>::ValueType m_digits;
    ZerosInfo GetZerosInfo()
    {
        return ms_retriever[m_digits];
    }
    DigitsGroup(unsigned v)
        : m_digits(v)
    {}
    DigitsGroup()
        : m_digits(0)
    {}
};

template<> ZerosInfoRetriever<My_N> DigitsGroup<My_N>::ms_retriever;


template<int N>
struct Power2
{
    typedef std::vector<DigitsGroup<N> > Container;
    Container m_value;
    int m_power;
    Power2()
        : m_value(1, DigitsGroup<N>(1))
        , m_power(0)
    {}

    void swap(Power2<N>& d)
    {
        m_value.swap(d.m_value);
        int tmp = m_power;
        m_power = d.m_power;
        d.m_power = tmp;
    }

    void print()
    {
        for(Container::reverse_iterator riter = m_value.rbegin(); riter != m_value.rend(); ++riter)
        {
            printf("%0*u", N, riter->m_digits);
        }
        printf("\n");
    }

    int MultplyBy(int digit2, Power2<N>& result)
    {
        result.m_value.resize(m_value.size());
        HolderType<N>::MulType mlt = 1 << digit2;
        result.m_power = m_power + digit2;
        CurrZerosInfo<N> czi;
        unsigned shift = 0;
        Container::iterator iter = m_value.begin();
        Container::iterator end = m_value.end();
        int i = 0;
        for(-- end; iter != end; ++ iter, ++i)
        {
            HolderType<N>::MulType tmp = mlt * iter->m_digits + shift;
            shift = tmp / HolderType<N>::TableSize;
            result.m_value[i].m_digits = tmp % HolderType<N>::TableSize;
            czi.AddNextDigit(result.m_value[i].GetZerosInfo());
        }
        HolderType<N>::MulType tmp = mlt * iter->m_digits + shift;
        shift = tmp / HolderType<N>::TableSize;
        result.m_value[i].m_digits = tmp % HolderType<N>::TableSize;
        czi.AddLastDigit(result.m_value[i].GetZerosInfo());
        if(shift)
        {
            result.m_value.push_back(DigitsGroup<N>(shift));
        }
        return czi.maxZeros;
    }
};

static int distance [] = {0, 1, 4, 7, 10, 14, 17, 20, 23, 27, 30, 33, 36, 39, 42, 46, 49};

int _tmain(int argc, _TCHAR* argv[])
{
    clock_t start = clock();
    static const int deep = 2;
    Power2<My_N> number;
    Power2<My_N> numberNext;
    Power2<My_N> numberTmp;

    int mul_count = 0;

    for(int i = 1; i < 20; ++i)
    {
        unsigned step = 1;
        if(i > 1) 
        {
            step = distance[My_N + 1] - 1;
        }
        do 
        {
            int zeros = number.MultplyBy(step, numberNext);
            mul_count++;
            int currIndex = number.m_power + step;
            if(zeros >= i)
            {
                break;
            }
            while((currIndex -= distance[i - zeros]) > number.m_power)
            {
                int delta = currIndex - number.m_power;
                zeros = number.MultplyBy(delta, numberTmp);
                mul_count++;
                if(zeros >= i)
                {
                    break;
                }
            }
            if(currIndex > number.m_power)
            {
                break;
            }
            number.swap(numberNext);
        } 
        while(true);
        while(number.MultplyBy(1, number) < i)
            mul_count++;
        printf("%8.3f: %2u : %10u (%10u)\n", ((double)(clock() - start)) / CLOCKS_PER_SEC, i, number.m_power, mul_count);
    }
    return 0;
}

Здравствуйте, nikholas, Вы писали:

А можешь посчитать сколько времени уйдет для этого алгоритма на нахождение а14 ?

Здравствуйте, nikholas, Вы писали:

N>Аппроксимация времени — квадратичная, и до арда потребуется примерно 667*(1.000.000.000 / 4.036.338)^2 = 40.000.000 сек = 11.111 час = 462 дня

Круто! Тоже думал про такую оптимизацию, но не думал, что это даст такой прирост производительности.

Чувствую, близок день, когда RSDN BruteForce Team посчитает a(18)

Здравствуйте, Spiceman, Вы писали:

S>Здравствуйте, nikholas, Вы писали:

N>>Аппроксимация времени — квадратичная, и до арда потребуется примерно 667*(1.000.000.000 / 4.036.338)^2 = 40.000.000 сек = 11.111 час = 462 дня

S>Круто! Тоже думал про такую оптимизацию, но не думал, что это даст такой прирост производительности.

S>Чувствую, близок день, когда RSDN BruteForce Team посчитает a(18)

Кстати у меня получилось сделать распределенный вариант этой задачи

Сейчас уже приближаюсь к 50 000 000. (а14)
Расчет ведется одновременно на 8 компах, при чем по моему медленному, и неоптимизированному всякими такими фичами

Задача разбивается на "квадратные" блоки, каждый из которых считает отдельный экземпляр задачи.
Текущий размер блока 100000х200000 знаков. Считается такой блок около 5 минут.
Скорость расчета прямо пропорциональна количеству компов, на которых запущена эта задача. Кого интересует могу поделиццо кодом (С++)

Здравствуйте, Seon, Вы писали:

S>Кстати у меня получилось сделать распределенный вариант этой задачи

S>Сейчас уже приближаюсь к 50 000 000. (а14)
S>Расчет ведется одновременно на 8 компах, при чем по моему медленному, и неоптимизированному всякими такими фичами

Тоже вот хотел распределенную написать. Но после ответа nikholas, захотелось сначала прикрутить его идею.

S>Задача разбивается на "квадратные" блоки, каждый из которых считает отдельный экземпляр задачи.
S>Текущий размер блока 100000х200000 знаков. Считается такой блок около 5 минут.
S>Скорость расчета прямо пропорциональна количеству компов, на которых запущена эта задача. Кого интересует могу поделиццо кодом (С++)

У меня на C# многопроцессорный вариант — посчитал до 2^16млн за 8 часов на двухядернике.
Лучше делиться не кодом, а идеями, чтобы их можно было в свой код прикручивать.

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, nikholas, Вы писали:

S>А можешь посчитать сколько времени уйдет для этого алгоритма на нахождение а14 ?

а14 : 667*(53.619.497 / 4.036.338)^2 = 117705 сек = 32 часа
a15 : 667*(119.476.156 / 4.036.338)^2 = 584404 сек = 162 часа
a16 : 667*(146.226.201 / 4.036.338)^2 = 243 часа — всего 10 суток!

К меня есть идеи как распараллелить, но ускорение в 2 раза не особо поможет, а других систем под рукой нет

Здравствуйте, Spiceman, Вы писали:

S>Здравствуйте, Seon, Вы писали:

S>>Кстати у меня получилось сделать распределенный вариант этой задачи

S>>Сейчас уже приближаюсь к 50 000 000. (а14)
S>>Расчет ведется одновременно на 8 компах, при чем по моему медленному, и неоптимизированному всякими такими фичами

S>Тоже вот хотел распределенную написать. Но после ответа nikholas, захотелось сначала прикрутить его идею.

S>>Задача разбивается на "квадратные" блоки, каждый из которых считает отдельный экземпляр задачи.
S>>Текущий размер блока 100000х200000 знаков. Считается такой блок около 5 минут.
S>>Скорость расчета прямо пропорциональна количеству компов, на которых запущена эта задача. Кого интересует могу поделиццо кодом (С++)

S>У меня на C# многопроцессорный вариант — посчитал до 2^16млн за 8 часов на двухядернике.
S>Лучше делиться не кодом, а идеями, чтобы их можно было в свой код прикручивать.

Легко.
Вариант мультиматериночный

Что из себя представляет это число?
Треугольник знаков.

                      1
                     11
                    111
                   1111
                  11111
                 111111
                1111111
               11111111
              111111111
             1111111111
            11111111111
           111111111111
          1111111111111
         11111111111111
        111111111111111
       1111111111111111
      11111111111111111
     111111111111111111
    1111111111111111111
   11111111111111111111
  111111111111111111111
 1111111111111111111111
11111111111111111111111

Видно, что его легко разбить на блоки вот так


                      1
                     11
                    111
                   1111
                  11111
                 322222
                3322222
               33322222
              333322222
             3333322222
            65555544444
           665555544444
          6665555544444
         66665555544444
        666665555544444
       1999998888877777
      11999998888877777
     111999998888877777
    1111999998888877777
   11111999998888877777

и так далее

После вычисления каждого блока имеем 2 файла результатов:

      1
      2
      4
      8
     16
     32
     64
    128
    256
    512
  1 024
  2 048
  4 096 
  8 192
--6 384                    
|
| 2 768 - это файл результата по ширине блока
|
|
--> 1 2 4 8 6 - это файл результата по высоте блока

Каждый из файлов будет исходными данными для следующего блока.
Вот основная идея. Можете работать

У меня файл по высоте содержит значение переноса из предыдущего разряда, а не само число, как в примере...

Кроме этого содержит максимальное количество нулей подряд из вычисленного куска числа, и количество нулей в конце этого числа — потому как число нового блока может начаться с нулей и надо знать сколько их было в предыдущем блоке.
Этот файл содержит 1 слово на каждое значение последовательности:
ABBBBBBB 0CCCCCCC
A — бит переноса из предыдущего разряда
B — максимальное количество нулей
C — количество нулей на конце блока

Разбивка вычисления на блоки — это только половина задачи.
Вторая половина — это чтобы N запущенных задач брали блоки по порядку и вычисляли:

Примерно так:

      A
     AA
    AAA
   AAAA
  AAAAA
 AAAAAA
AAAAAAA
 111111  - вычисляет экземпляр приложения I
  22222  - вычисляет экземпляр приложения II
   3333  - вычисляет экземпляр приложения III
    444  - вычисляет экземпляр приложения IV
     55  - вычисляет экземпляр приложения V
      6  - вычисляет экземпляр приложения VI

A — уже посчитанные числа
Жирным показаны текущие вычисляемые блоки
Если вот для этого примера сейчас запустить 7-й экземпляр, программа будет ожидать появления свободной задачи. Он появится как только экземпляр приложения VI перейдет к следующему левому блоку.

Сейчас у меня расчитана уже 35 000 000 степень. Так как размер блока у меня 100000х200000, то имеем уже 175 строку. Количество блоков по ширине = 105.
То есть одновременно можно запустить 105 компов.

В моем варианте программа просто натравливается на расшаренный по сети каталог с файлами результатов, захватывает 2 из них, вычисляет блок, и записывает в этот каталог результаты, затем цикл повторяется.
Но лучше сделать такой вариант: Одна программа — сервер-шедулер, занимается менеджментом заданий, остальные — клиенты: запрашивают у сервера задачи, вычисляют и отдают результаты назад.

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Spiceman, Вы писали:

S>>Здравствуйте, nikholas, Вы писали:

N>>>Аппроксимация времени — квадратичная, и до арда потребуется примерно 667*(1.000.000.000 / 4.036.338)^2 = 40.000.000 сек = 11.111 час = 462 дня

S>>Круто! Тоже думал про такую оптимизацию, но не думал, что это даст такой прирост производительности.

S>>Чувствую, близок день, когда RSDN BruteForce Team посчитает a(18)

S>Кстати у меня получилось сделать распределенный вариант этой задачи

S>Задача разбивается на "квадратные" блоки, каждый из которых считает отдельный экземпляр задачи.
S>Текущий размер блока 100000х200000 знаков. Считается такой блок около 5 минут.
S>Скорость расчета прямо пропорциональна количеству компов, на которых запущена эта задача. Кого интересует могу поделиццо кодом (С++)

Боюсь до конца ты не доживешь

Для a17 надо посчитать 10^9 (кол-во строк) * 3*10^8 (~длина 2^1000000000 в десятичном представлении) / 2 знаков, у тебя считается 10^5 * 2*10^5 за 300 сек, скорость < 10^8 знаков в сек., итого тебе потребуется 10^9 * 3 * 10^8 / ( 2 * 10^8) сек = 17000 дней, даже на 100 компах пол-года

Здравствуйте, nikholas, Вы писали:

N>Боюсь до конца ты не доживешь

N>Для a17 надо посчитать 10^9 (кол-во строк) * 3*10^8 (~длина 2^1000000000 в десятичном представлении) / 2 знаков, у тебя считается 10^5 * 2*10^5 за 300 сек, скорость < 10^8 знаков в сек., итого тебе потребуется 10^9 * 3 * 10^8 / ( 2 * 10^8) сек = 17000 дней, даже на 100 компах пол-года

Так вот же и пытаемся придумать оптимальное решение.

Вчера сделал еще одну оптимизацию.
Теперь у меня система не десятичная а миллиардичная. Каждый знак теперь не от 0 до 9 а от 0 до 999999999!!!
Обрабатываем не массив чаров а массив интов. Подобная идея уже кем то тут описывалась... сори не помню

Конечно пришлось пожертвовать вычислениями от а1 до а8, но их и так все давно знают

ЗАТО это дало прирост в скорости пятикратно!

=====================================================
a(9) [2^100823] Time: 0:0:0:10
a(10) [2^559940] Time: 0:0:5:15
a(11) [2^1148303] Time: 0:0:16:38
a(12) [2^4036338] Time: 0:2:51:17
=====================================================
скорость 2.4 * 10^8 знаков в сек
по старому у меня а(12) считалось около 13 часов — 5 * 10^7 зн/сек

Здравствуйте, nikholas, Вы писали:

N>Вот результат:

N>

N>   0.000:  1 :          1 (         1)
N>   0.000:  2 :          2 (         2)
N>   0.000:  3 :        242 (       244)
N>   0.000:  4 :        377 (       296)
N>   0.000:  5 :       1491 (       518)
N>   0.000:  6 :       1492 (       522)
N>   0.000:  7 :       6801 (      1217)
N>   0.000:  8 :      14007 (      1922)
N>   0.469:  9 :     100823 (      9548)
N>  13.797: 10 :     559940 (     47855)
N>  55.641: 11 :    1148303 (     94153)
N> 667.266: 12 :    4036338 (    317876)
N> 667.281: 13 :    4036339 (    317880)
N>

N>Pentium(R)D 3.4 MHz

У меня ваша прога считалась вот так

   0.000:  1 :          1 (         1)
   0.000:  2 :          2 (         2)
   0.000:  3 :        242 (       244)
   0.000:  4 :        377 (       296)
   0.000:  5 :       1491 (       518)
   0.000:  6 :       1492 (       522)
   0.020:  7 :       6801 (      1217)
   0.060:  8 :      14007 (      1922)
   2.680:  9 :     100823 (      9548)
  77.260: 10 :     559940 (     47855)
 308.470: 11 :    1148303 (     94153)

Athlon 2300+ 1 proc
ubuntu g++

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, nikholas, Вы писали:

N>>Вот результат:

N>>

N>>   0.000:  1 :          1 (         1)
N>>   0.000:  2 :          2 (         2)
N>>   0.000:  3 :        242 (       244)
N>>   0.000:  4 :        377 (       296)
N>>   0.000:  5 :       1491 (       518)
N>>   0.000:  6 :       1492 (       522)
N>>   0.000:  7 :       6801 (      1217)
N>>   0.000:  8 :      14007 (      1922)
N>>   0.469:  9 :     100823 (      9548)
N>>  13.797: 10 :     559940 (     47855)
N>>  55.641: 11 :    1148303 (     94153)
N>> 667.266: 12 :    4036338 (    317876)
N>> 667.281: 13 :    4036339 (    317880)
N>>

N>>Pentium(R)D 3.4 MHz

S>У меня ваша прога считалась вот так

S>   0.000:  1 :          1 (         1)
S>   0.000:  2 :          2 (         2)
S>   0.000:  3 :        242 (       244)
S>   0.000:  4 :        377 (       296)
S>   0.000:  5 :       1491 (       518)
S>   0.000:  6 :       1492 (       522)
S>   0.020:  7 :       6801 (      1217)
S>   0.060:  8 :      14007 (      1922)
S>   2.680:  9 :     100823 (      9548)
S>  77.260: 10 :     559940 (     47855)
S> 308.470: 11 :    1148303 (     94153)
S>

S>Athlon 2300+ 1 proc
S>ubuntu g++

На другой машине у меня так:
0.000: 1 : 1 ( 1)
0.002: 2 : 2 ( 2)
0.002: 3 : 242 ( 244)
0.002: 4 : 377 ( 296)
0.002: 5 : 1491 ( 518)
0.002: 6 : 1492 ( 522)
0.006: 7 : 6801 ( 1217)
0.022: 8 : 14007 ( 1922)
0.872: 9 : 100823 ( 9548)
22.653: 10 : 559940 ( 47855)

AMD Athlon64 3000+ 1.99 GHz
Visual C++ 2005 Express Edition

Видимо дело в размерах кешей

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, nikholas, Вы писали:

N>>Боюсь до конца ты не доживешь

N>>Для a17 надо посчитать 10^9 (кол-во строк) * 3*10^8 (~длина 2^1000000000 в десятичном представлении) / 2 знаков, у тебя считается 10^5 * 2*10^5 за 300 сек, скорость < 10^8 знаков в сек., итого тебе потребуется 10^9 * 3 * 10^8 / ( 2 * 10^8) сек = 17000 дней, даже на 100 компах пол-года

А>Так вот же и пытаемся придумать оптимальное решение.

А>Вчера сделал еще одну оптимизацию.
А>Теперь у меня система не десятичная а миллиардичная. Каждый знак теперь не от 0 до 9 а от 0 до 999999999!!!
А>Обрабатываем не массив чаров а массив интов. Подобная идея уже кем то тут описывалась... сори не помню

А>Конечно пришлось пожертвовать вычислениями от а1 до а8, но их и так все давно знают

А>ЗАТО это дало прирост в скорости пятикратно!

А>=====================================================
А>a(9) [2^100823] Time: 0:0:0:10
А>a(10) [2^559940] Time: 0:0:5:15
А>a(11) [2^1148303] Time: 0:0:16:38
А>a(12) [2^4036338] Time: 0:2:51:17
А>=====================================================
А>скорость 2.4 * 10^8 знаков в сек
А>по старому у меня а(12) считалось около 13 часов — 5 * 10^7 зн/сек

Круто!

А каким способом подсчитывается кол-во нулей? 9 делений и 9 if-ов ?
Или это просто вычисление 2-в-нужной-степени?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, nikholas, Вы писали:

N>>Боюсь до конца ты не доживешь

А>Конечно пришлось пожертвовать вычислениями от а1 до а8, но их и так все давно знают

Здравствуйте, nikholas, Вы писали:

N>Здравствуйте, Seon, Вы писали:

S>>Здравствуйте, nikholas, Вы писали:

N>>>Вот результат:

N>>>

N>>>   0.000:  1 :          1 (         1)
N>>>   0.000:  2 :          2 (         2)
N>>>   0.000:  3 :        242 (       244)
N>>>   0.000:  4 :        377 (       296)
N>>>   0.000:  5 :       1491 (       518)
N>>>   0.000:  6 :       1492 (       522)
N>>>   0.000:  7 :       6801 (      1217)
N>>>   0.000:  8 :      14007 (      1922)
N>>>   0.469:  9 :     100823 (      9548)
N>>>  13.797: 10 :     559940 (     47855)
N>>>  55.641: 11 :    1148303 (     94153)
N>>> 667.266: 12 :    4036338 (    317876)
N>>> 667.281: 13 :    4036339 (    317880)
N>>>

N>>>Pentium(R)D 3.4 MHz

S>>У меня ваша прога считалась вот так

S>>

S>>   0.000:  1 :          1 (         1)
S>>   0.000:  2 :          2 (         2)
S>>   0.000:  3 :        242 (       244)
S>>   0.000:  4 :        377 (       296)
S>>   0.000:  5 :       1491 (       518)
S>>   0.000:  6 :       1492 (       522)
S>>   0.020:  7 :       6801 (      1217)
S>>   0.060:  8 :      14007 (      1922)
S>>   2.680:  9 :     100823 (      9548)
S>>  77.260: 10 :     559940 (     47855)
S>> 308.470: 11 :    1148303 (     94153)
S>>

S>>Athlon 2300+ 1 proc
S>>ubuntu g++

N>На другой машине у меня так:
N> 0.000: 1 : 1 ( 1)
N> 0.002: 2 : 2 ( 2)
N> 0.002: 3 : 242 ( 244)
N> 0.002: 4 : 377 ( 296)
N> 0.002: 5 : 1491 ( 518)
N> 0.002: 6 : 1492 ( 522)
N> 0.006: 7 : 6801 ( 1217)
N> 0.022: 8 : 14007 ( 1922)
N> 0.872: 9 : 100823 ( 9548)
N> 22.653: 10 : 559940 ( 47855)

N>AMD Athlon64 3000+ 1.99 GHz
N>Visual C++ 2005 Express Edition

N>Видимо дело в размерах кешей

У меня на лаптопе (2x1.87GHz, с наполовину задействованным процессором) Visual C++ 2008 Express дало:

   0.000:  1 :          1 (         1)
   0.000:  2 :          2 (         2)
   0.001:  3 :        242 (       244)
   0.002:  4 :        377 (       296)
   0.004:  5 :       1491 (       518)
   0.005:  6 :       1492 (       522)
   0.011:  7 :       6801 (      1217)
   0.022:  8 :      14007 (      1922)
   0.636:  9 :     100823 (      9548)
  18.600: 10 :     559940 (     47855)
  73.947: 11 :    1148303 (     94153)

Здравствуйте, nikholas, Вы писали:

N>Круто!

N>А каким способом подсчитывается кол-во нулей? 9 делений и 9 if-ов ?
N>Или это просто вычисление 2-в-нужной-степени?

3 ифа
1 деление

int zeros_left(BaseType c)
{
  int z;
  if (c < 10000)
  {
    z = 5;
    if (c < 100)
    {
      z += 2;
      if (c < 10)
        z++;
    }
    else
      if (c < 1000)
        z++;    }
  else
  {
    if (c < 1000000)
    {
      z = 3;
      if (c < 100000)
        z++;
    }
    else
    {
      if (c < 100000000)
      {
        z = 1;
        if (c < 10000000)
          z++;
      }
      else
        z = 0;
    }
  }
  return z;
}

bool zeros_right(BaseType c, int z)
{
  BaseType t;
  switch(z)
  {
  case 1:
    t = 10;
    break;
  case 2:
    t = 100;
    break;
  case 3:
    t = 1000;
    break;
  case 4:
    t = 10000;
    break;
  case 5:
    t = 100000;
    break;
  case 6:
    t = 1000000;
    break;
  case 7:
    t = 10000000;
    break;
  case 8:
    t = 100000000;
    break;
  default:
    return false;
  }
  if ((c % t) == 0)
    return true;
  return false;
}

А теперь кусок вызывающей функции

  BaseType ost = 0;
  bool z = false;
  int nz = 0;
  BaseType res;
  BaseType c;
  for(int n = 0; n < size; ++n)
  {
    c = arr[n];
    res = c << 1;
    if (ost) res++;
    if (res > 999999999)
    {
      c = res - 1000000000;
      ost = 1;
    }
    else
    {
      c = res;
      ost = 0;
    }
    if (c)
    {
      if (zeros_right(c, zeros - nz))
        z = true;
      nz = zeros_left(c);
    }
    else
      nz += 9;
    arr[n] = c;
  }
  if (ost)
    arr[size++] = ost;
  if (z)
  {
    // нашли очередное число нулей
  }

Здравствуйте, Seon, Вы писали:

S>3 ифа
S>1 деление

Пардонте!

Тут пропущен 1 кейс


S>bool zeros_right(BaseType c, int z)
S>{
S>  BaseType t;
S>  switch(z)
S>  {
    case 0:
      return 0;
S>  case 1:
S>    t = 10;
S>    break;
S>  case 2:
S>    t = 100;
S>    break;
S>  case 3:
S>    t = 1000;
S>    break;
S>  case 4:
S>    t = 10000;
S>    break;
S>  case 5:
S>    t = 100000;
S>    break;
S>  case 6:
S>    t = 1000000;
S>    break;
S>  case 7:
S>    t = 10000000;
S>    break;
S>  case 8:
S>    t = 100000000;
S>    break;
S>  default:
S>    return false;
S>  }
S>  if ((c % t) == 0)
S>    return true;
S>  return false;
S>}
S>

Здравствуйте, Seon, Вы писали:

S>3 ифа
S>1 деление

Функцию "int zeros_left(BaseType c)" можно сделать так:

return (int)Math.Log10(n) + 1;

У себя в коде я разницы в скорости не увидел.

Функцию "bool zeros_right(BaseType c, int z)" можно сделать так:

return (z == 0) || ((c & Pow2[z]) == 0 && ((c >> z) % Base5[z]) == 0);

Где,
Pow2[] = {0, 1, 3, 7, 15,...}, то есть 2^n — 1.
Base5[] = {1, 5, 25, 125, 625, ...}, то есть 5^n
z — вместо степени 10 использовать показатель степени, то есть, вместо 10 использовать 1, вместо 100 — 2, вместо 1000 — 3 и т.д.
Пояснение. Число делится на 100, если делится на 4 и на 25. В данном слечае:
(c & Pow2[2]) == 0 — проверка делимости на 4,
((c >> z) % Base5[2]) == 0 — проверка делимости на 25.

Код становится менее лапшеобразным без потери скорости.

Здравствуйте, Spiceman, Вы писали:

S>

S>return (int)Math.Log10(n) + 1;
S>

S>return (z == 0) || ((c & Pow2[z]) == 0 && ((c >> z) % Base5[z]) == 0);
S>

S>Код становится менее лапшеобразным без потери скорости.

Забыл добавить. В таком виде функции инлайнятся, так как состоят из одной строчки кода с ретурном.

Здравствуйте, Spiceman, Вы писали:

S>Функцию "int zeros_left(BaseType c)" можно сделать так:

Вот тут точно не скажу..
S>

S>return (int)Math.Log10(n) + 1;
S>

Вызывать функцию вычисления логарифма вместо 3-х сравнений???

S>Функцию "bool zeros_right(BaseType c, int z)" можно сделать так:

S>

S>return (z == 0) || ((c & Pow2[z]) == 0 && ((c >> z) % Base5[z]) == 0);
S>

S>Где,
S>Pow2[] = {0, 1, 3, 7, 15,...}, то есть 2^n — 1.
S>Base5[] = {1, 5, 25, 125, 625, ...}, то есть 5^n
S>z — вместо степени 10 использовать показатель степени, то есть, вместо 10 использовать 1, вместо 100 — 2, вместо 1000 — 3 и т.д.
S>Пояснение. Число делится на 100, если делится на 4 и на 25. В данном слечае:
S>(c & Pow2[2]) == 0 — проверка делимости на 4,
S>((c >> z) % Base5[2]) == 0 — проверка делимости на 25.

S>Код становится менее лапшеобразным без потери скорости.

На счет массивов — я как то про них и забыл...

тогда так

BaseType  step[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};

bool zeros_right(BaseType c, int z)
{
  if (z && z < 9)
  {
    if ((c % step[z]) == 0)
      return true;
  }
  return false;
}

Это еще меньше, без всяких проверок делимостей...

	От:	nikholas
	Дата:	15.01.09 15:59
	Оценка:	14 (2)

	От:	Seon
	Дата:	16.01.09 08:36
	Оценка:

	От:	Spiceman
	Дата:	16.01.09 08:41
	Оценка:

	От:	Seon
	Дата:	16.01.09 09:43
	Оценка:

	От:	Spiceman
	Дата:	16.01.09 09:58
	Оценка:

	От:	Аноним
	Дата:	17.01.09 05:47
	Оценка:	5 (1)