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

PO>Кстати, я использую не все 17 цифр. Это связанно с эвристикой

Нифига не понятно!
Нужен КОД!

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

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

PO>>Кстати, я использую не все 17 цифр. Это связанно с эвристикой

S>Нифига не понятно!
S>Нужен КОД!

ok, потерпите часик, мне нужно написать прогу заново

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

V>Найти a(1),...,a(7).

Brute force на J:

  zr =: 3 : '<: >./ 2 -~/\ I. ''0'' ~: ": 2 ^ x: y'
  (>:i.7) i.~ zr"0 i.7000
10 53 242 377 1491 1492 6801

Т.к. тупо и "в лоб" — считает 6 секунд..

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

А>Brute force на J:
А>

А>  zr =: 3 : '<: >./ 2 -~/\ I. ''0'' ~: ": 2 ^ x: y'
А>  (>:i.7) i.~ zr"0 i.7000
А>

О боже! похоже на смайлики
это вообще язык? или у меня проблема с кодировкой?

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

S>О боже! похоже на смайлики
S>это вообще язык? или у меня проблема с кодировкой?

J

Как и обещал, выкладываю прогу. Считал уже дома на Е6550 — 2 ядра, 3,17 GHz (разгон), загрузка где-то на 60%.
Результат: (время указанно не с самого начала расчета, а начиная от прошлого результата)

a(1) = 10. Time 00:00:00.0014568, Length 4
a(2) = 53. Time 00:00:00.0000059, Length 16
a(3) = 242. Time 00:00:00.0005876, Length 73
a(4) = 377. Time 00:00:00.0000536, Length 114
a(5) = 1491. Time 00:00:00.0028288, Length 449
a(6) = 1492. Time 00:00:00.0000014, Length 450
a(7) = 6801. Time 00:00:00.0124860, Length 2048
a(8) = 14007. Time 00:00:00.0414484, Length 4217
a(9) = 100823. Time 00:00:02.1975814, Length 30351
a(10) = 559940. Time 00:01:07.1116630, Length 168559
a(11) = 1148303. Time 00:03:05.2465847, Length 345674
a(12) = 4036338. Time 00:46:04.8292335, Length 1215059

Код:

    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Find();
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex);
            }
        }

        public static void Find()
        {
            int k;
            int power;
            Finder finder = new Finder();
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            do
            {
                watch.Reset();
                watch.Start();
                finder.FindNext(out k, out power);
                watch.Stop();
                Console.WriteLine("a({0}) = {1}. Time {2}, Length {3}", k, power, watch.Elapsed, finder.Length);
            }
            while (k < 12);
        }
    }

    public class Finder
    {
        public static readonly int MaxSegments = 1000000;
        private int[] m_number;
        private int m_length;
        private int m_power;
        private int m_k;
        private int m_segmentLength;
        private int m_maxValue;

        public Finder()
        {
            m_segmentLength = 1;
            m_length = 1;
            m_number = new int[MaxSegments];
            m_number[0] = 1;
            m_k = 0;
            m_power = 0;
            m_maxValue = 9;
        }

        private void Mult()
        {
            int ost = 0;

            for (int index = 0; index < m_length; index++)
            {
                m_number[index] = (m_number[index] << 1) + ost;
                if (m_number[index] > m_maxValue)
                {
                    m_number[index] -= m_maxValue + 1;
                    ost = 1;
                }
                else
                {
                    ost = 0;
                }
            }

            if (ost == 1)
            {
                if (m_length >= MaxSegments) throw new Exception("MaxSegments");
                m_length++;
                m_number[m_length - 1] = 1;
            }
        }

        public void FindNext(out int k, out int power)
        {
            m_k++;
            Rebuild();

            while (!Check())
            {
                m_power++;
                Mult();
                if (m_power % 10000 == 0) Console.WriteLine("{0}, {1}", m_power, Length);
            }
            k = m_k;
            power = m_power;
        }

        public int Length
        {
            get
            {
                int length = m_number[m_length - 1].ToString().Length;
                if (m_length > 0) length += (m_length - 1) * m_segmentLength;
                return length;
            }
        }

        private bool Check()
        {
            int count;
            int x;
            int a;
            bool isOk = false;

            //change first number
            int first = m_number[m_length - 1];
            x = (m_maxValue + 1) / 10;
            a = 0;
            while (first > x && x > 0)
            {
                a += x;
                x /= 10;
            }
            m_number[m_length - 1] += a;

            for (int index = 0; index < m_length; index++)
            {
                if (m_number[index] != 0) continue;
                count = m_segmentLength;

                //previous
                if (index > 0)
                {
                    x = (m_maxValue + 1) / 10;
                    while (x > 0)
                    {
                        if (m_number[index - 1] < x)
                        {
                            count++;
                            x /= 10;
                        }
                        else
                        {
                            x = 0;
                        }
                    }
                }

                //next
                if (index < m_length)
                {
                    a = m_number[index + 1];
                    x = m_segmentLength;
                    while (x > 0)
                    {
                        if (a % 10 == 0)
                        {
                            count++;
                            a /= 10;
                            x--;
                        }
                        else
                        {
                            x = 0;
                        }
                    }
                }

                if (count >= m_k)
                {
                    isOk = true;
                    break;
                }
            }

            m_number[m_length - 1] = first;
            return isOk;
        }

        private void Rebuild()
        {
            if (2 * m_segmentLength >= m_k) return;
            string number = ToString();
            m_segmentLength++;
            m_maxValue = 10 * m_maxValue + 9;
            m_number = new int[MaxSegments];
            m_length = number.Length / m_segmentLength;
            int prefix = number.Length % m_segmentLength;
            for (int index = 0; index < m_length; index++)
            {
                m_number[index] = int.Parse(number.Substring(prefix + m_segmentLength * (m_length - index - 1), m_segmentLength));
            }
            if (prefix > 0)
            {
                m_length++;
                m_number[m_length - 1] = int.Parse(number.Substring(0, prefix));
            }
        }

        public override string ToString()
        {
            StringBuilder builder = new StringBuilder(m_segmentLength * m_length);
            string format = "d" + m_segmentLength.ToString();
            builder.Append(m_number[m_length - 1]);
            for (int index = m_length - 2; index >= 0; index--)
            {
                builder.Append(m_number[index].ToString(format));
            }
            return builder.ToString();
        }
    }

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

E>>А разве так можно?

RO>и мой код:
RO>

RO>std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count);
RO>++buffer[10 * count];
RO>

RO>делают одно и то же. Меня, правда, смущает то, что диапазоны пересекаются, но результат будет один и тот же, даже если это и не то, что ты планировал.

AFAIK, ты забыл уточнить, что это так в доступной тебе реализации STL.
Вообще-то вроде как стандарт требует чтобы третий аргумент не попадал в интервал, заданный первыми двумя...
Я думал ты круто знаешь STL, поэтому и просил тебя разъяснить можно ли согласно стандарта так писать.
AFAIK, в таком случае надо использовать copy_backwards (или как-то ещё оно называется, я в STL всё время путаюсь, где backwards, а где reverse), а использование таким образом std::copy, AFAIK, это неспецифицированное поведение.

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

S>>>Ну и что же... зато запись какая! :super:
RO>>>>

RO>>>>    ++*--dst;
RO>>>>

RO>>С тем же успехом можно было ++dst[-1].

S>А ВОТ и НЕТ!
S>++*--dst; — уменьшает dst!
S>а ++dst[-1] — НЕТ!!!!!

dst потом не используется нигде.

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

RO>>и мой код:
RO>>

RO>>std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count);
RO>>++buffer[10 * count];
RO>>

RO>>делают одно и то же. Меня, правда, смущает то, что диапазоны пересекаются, но результат будет один и тот же, даже если это и не то, что ты планировал.

E>AFAIK, ты забыл уточнить, что это так в доступной тебе реализации STL. :shuffle:
E>Вообще-то вроде как стандарт требует чтобы третий аргумент не попадал в интервал, заданный первыми двумя...
E>Я думал ты круто знаешь STL, поэтому и просил тебя разъяснить можно ли согласно стандарта так писать.
E>AFAIK, в таком случае надо использовать copy_backwards (или как-то ещё оно называется, я в STL всё время путаюсь, где backwards, а где reverse:)), а использование таким образом std::copy, AFAIK, это неспецифицированное поведение. :shuffle:

Он-то требует, как для copy, так и для copy_backward: «Requires: result shall not be in the range [first, last)».

Просто у тебя при копировании тоже элементы затираются, я решил, что тебе это так надо.

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

RO>Просто у тебя при копировании тоже элементы затираются, я решил, что тебе это так надо.
1) у меня ничего не затирается. Каждый элемент инициализируется ОДИН раз, за исключением тех, кому делают ++*--dst.
2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?

#include <vector>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <boost/cstdint.hpp>
#include <boost/preprocessor/cat.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/foreach.hpp>

#define foreach BOOST_FOREACH
using std::size_t;

#ifndef LOG_BASE
#define LOG_BASE 5
#endif

#ifndef CZ_BITS
#define CZ_BITS 8
#endif

#ifndef DIGIT_BITS
#define DIGIT_BITS 32
#endif

typedef boost::BOOST_PP_CAT(BOOST_PP_CAT(uint_least, CZ_BITS), _t) cz_t;
typedef boost::BOOST_PP_CAT(BOOST_PP_CAT(uint_fast, DIGIT_BITS), _t) digit;
typedef std::vector<digit> bigint;

template <size_t N> struct power10;
template <>         struct power10<0> { static size_t const value = 1; };
template <size_t N> struct power10    { static size_t const value = power10<N-1>::value * 10; };

template <size_t N>
struct counter_zl;

template <>
struct counter_zl<1>
{
    static inline size_t apply(digit d)
    {
        return d == 0;
    };
};
template <size_t N>
struct counter_zl
{
    static inline size_t apply(digit d)
    {
        return (d < power10<N-1>::value) + counter_zl<N-1>::apply(d);
    };
};

//size_t const LOG_BASE = 5;
digit const BASE = power10<LOG_BASE>::value;

long long ccl = 0, cct = 0;

#ifdef CZL_TABLE
    cz_t _mdczl[BASE];
    inline size_t mdczl(digit d) { ++ccl; return _mdczl[d]; }
#else
    inline size_t mdczl(digit d)
    {
        ++ccl;
        return d >= BASE/10 ? 0 : 1 + counter_zl<LOG_BASE-1>::apply(d);
        //return counter_zl<LOG_BASE>::apply(d);
    }
#endif
cz_t _mdczt[BASE];
inline size_t mdczt(digit d) { ++cct; return _mdczt[d]; } // Map from Digits to Count of Zeros (Trailing)


int main(int argc, char** argv)
{
    assert(argc == 2);
    size_t const k = boost::lexical_cast<size_t>(argv[1]);

    std::ofstream tty("/dev/tty");

#ifdef CZL_TABLE
    _mdczl[0] = LOG_BASE;
#endif
    _mdczt[0] = 0;
    for(digit i = 1; i < BASE; ++i)
    {
#ifdef CZL_TABLE
        _mdczl[i] = mdczl(i / 10) - 1;
#endif
        _mdczt[i] = i % 10 == 0 ? 1 + mdczt(i / 10) : 0;
    }

    if(k == 0)
    {
        for(digit d = 0; d < BASE; ++d)
        {
            std::cout << std::setw(LOG_BASE) << std::setfill('0') << d << " " << mdczl(d) << " " << mdczt(d) << std::endl;
        }
        return 0;
    }

    size_t p = 0;
    bigint n;
    n.reserve(10240);
    n.push_back(1);

    while(1)
    {
        size_t czt = 0;
        for(size_t i = 0; i < n.size(); ++i)
        {
            digit const& d = n[i];
            //czt += mdczt(d);
            if(czt >= k || (czt + LOG_BASE >= k && czt + mdczt(d) >= k))
            {
                std::cout << p << std::endl;
                tty << ccl << " " << cct << std::endl;
                return 0;
            }
            czt &= d ? 0 : ~(size_t)0;
            czt += mdczl(d);
        }

        digit carry = 0;
        for(size_t i = 0; i < n.size(); ++i)
        {
            n[i] *= 2;
            n[i] += carry;
            carry = n[i] >= BASE;
            n[i] -= carry * BASE;
        }
        if(carry > 0)
        {
            n.push_back(carry);
        }

        ++p;

        if(p % 10000 == 0)
        {
            tty << "..." << p << "..." << std::endl;
        }
    }
}

Идея здесь в том, чтобы использовать 10⁵-ричную (параметр настраивается) систему счисления, и хранить в отдельной таблице количество нулей для каждой такой «цифры». В основном алгоритме нет ни единой операции деления. И еще кое-где поэкономил на спичках (например, я заменил «if(d!=0){czt=0}» на «czt &= d ? 0 : ~(size_t)0;», чтобы втолковать компилятору, что здесь нужно поставить sbb). Почерпнул немного дельных мыслей из дотнетовского варианта

Автор: Pro100Oleh
Дата: 22.12.08

, но полностью тот алгоритм не понял.

На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.

Хорошо бы запустить разные решения на одном компьютере, кое-чем померяться ;-).

Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?

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

RO>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?

IMHO надо сразу на "КУДУ" нести...

А вообще-то всё это очень к размеру кэша чувствительно, IMHO...

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

RO>>Просто у тебя при копировании тоже элементы затираются, я решил, что тебе это так надо.
E>1) у меня ничего не затирается. Каждый элемент инициализируется ОДИН раз, за исключением тех, кому делают ++*--dst.

Вот твой код:

static void expand10times( small* buffer, int count )
{
    const small* src = buffer + 1;
    small* dst = buffer + 1 + count;
    for( int i = count * 9; i > 0; --i )
        *dst++ = *src++;
    ++*--dst;
}

Пусть count = 1:

0123456789
^^^
|||
||dst
|src
buffer

И теперь цикл возымеет такое действие: buffer[2]=buffer[1], buffer[3]=buffer[2]... т. е., вместо смещения данных первые count элементов будут размножены 8 раз.

E>2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?

Не предоставляет, естественно.

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

RO>>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?

E>IMHO надо сразу на "КУДУ" нести...

E>А вообще-то всё это очень к размеру кэша чувствительно, IMHO...

Воистину. У меня зависимость от LOG_BASE экстремальная, хотя казалось бы, что чем больше, тем лучше.

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

RO>И теперь цикл возымеет такое действие: buffer[2]=buffer[1], buffer[3]=buffer[2]... т. е., вместо смещения данных первые count элементов будут размножены 8 раз.
9 раз.
Я знаю как работает мой код. Он это и должен делать, вообще-то, а не какое-то там "смещение данных" выполнять. Хотя я понимаю, что ты имеешь в виду, и мог бы, например, написать аналогичный код на memcpy, например. И тоже непереносимый.

E>>2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?
RO>Не предоставляет, естественно.

Ну и хрен ли тогда советовать заменить корректный С++ цикл на некорректное использование стандартного алгоритма?

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

RO>Воистину. У меня зависимость от LOG_BASE экстремальная, хотя казалось бы, что чем больше, тем лучше.
Очевидно, что нет
Кроме того, не понятно почему ты 100 000 за "цифру" взял. Казалось бы 10 000 помещается в два байта, а 100 000 уже в 4, так что каш тратится менее эффективно...

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

RO>>Воистину. У меня зависимость от LOG_BASE экстремальная, хотя казалось бы, что чем больше, тем лучше.
E>Очевидно, что нет :)
E>Кроме того, не понятно почему ты 100 000 за "цифру" взял. Казалось бы 10 000 помещается в два байта, а 100 000 уже в 4, так что каш тратится менее эффективно...

Это ни при чем.

Данные из n у меня берутся последовательно, а вот из mdczt — случайным образом, поэтому именно таблица должна полностью помещаться в кеше, не число.

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

RO>>И теперь цикл возымеет такое действие: buffer[2]=buffer[1], buffer[3]=buffer[2]... т. е., вместо смещения данных первые count элементов будут размножены 8 раз.
E>9 раз.
E>Я знаю как работает мой код. Он это и должен делать, вообще-то, а не какое-то там "смещение данных" выполнять. Хотя я понимаю, что ты имеешь в виду, и мог бы, например, написать аналогичный код на memcpy, например. И тоже непереносимый.

Хм, надо было смотреть на название функции...

E>>>2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?
RO>>Не предоставляет, естественно.

E>Ну и хрен ли тогда советовать заменить корректный С++ цикл на некорректное использование стандартного алгоритма? :)

А хрен ли слушать всякие вредные советы? :-)

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

[]
RO>Идея здесь в том, чтобы использовать 10⁵-ричную (параметр настраивается) систему счисления, и хранить в отдельной таблице количество нулей для каждой такой «цифры». В основном алгоритме нет ни единой операции деления. И еще кое-где поэкономил на спичках (например, я заменил «if(d!=0){czt=0}» на «czt &= d ? 0 : ~(size_t)0;», чтобы втолковать компилятору, что здесь нужно поставить sbb). Почерпнул немного дельных мыслей из дотнетовского варианта

Автор: Pro100Oleh
Дата: 22.12.08

, но полностью тот алгоритм не понял.

RO>На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.

Странно, в твоей предыдущей "неоптимизированной" версии a(8) считалось за 0.46 секунд...

Кстати, если сравнить твой лучший показатель для a(10) -- 1:14 с вариантом Pro100Oleh -- a(10) за 1:10, то наблюдается "сходимость". Понятно, что тест проводился на разных машинах, с разным кэшем и т.д. и т.п., но тем не менее. Интересно, возможен ли какой-то "идеологический прорыв", который позволит посчитать на персоналках a(15), a(16) и т.д., или же все упирается в GHz-ы и кэши?

Хочу отметить, что то, чего вы (вы с маленькой, т.к. "все вы") добились на этом форуме -- уже не мало. Вы можете прочитать по той ссылке, что я приводил ранее, что в то время как первые члены последовательности "безымянные", про последние члены этой последовательности уже отмечено кто и когда их получил. Так вот первые именные члены этой последовательности -- a(12) и a(13) -- уже были получены здесь за более чем приемлемое время!

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

RO>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?

Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.