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

S>

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

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

Это дало еще 15 процентный прирост в скорости!!!!
Spiceman, благодарю за подсказку!

Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!

На это ушло 21 день и 2 часа!

Одновременно эту задачу считало от 2-х до 8 компов попеременно. В среднем гдето 4-5 штук.
Задача без всяких оптимизаций — первоначальный вариант — десятичные числа на чарах!!

Продолжать считать думаю на этом варианте нет смысла — до а(15) — топать в 4 раза дольше! Ой ой ой...

Еще тут на одном проце оптимизированная до интов(9 десятичных цифр на 1 элемент массива — ИНТ) задача посчитала уже свыше 35 000 000. На это ушло уже 7 дней!
Движемся на ней до а(14), интересно же узнать, опередит ли эта оптимальная версия — распределенную..

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

S>Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!

S>На это ушло 21 день и 2 часа!

"Еще три тысячи ведер — и ключик у нас в кармане "

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

N>- если в N-й степени двойки есть K нулей подряд, то в N+1,N+2,N+3 — не менее (K-1), N+4,N+5,N+6 — не менее (K-2) и т.д.
N>И обратно: если в N-й степени двойки есть не более K нулей подряд, то в N-1 — не более (K+1), N-2,N-3,N-4 — не более (K+2)

Что-то я не могу понять как это может помочь.
Т.к. N у нас возрастает, то польза есть только от первого высказывания, а в нем ничего не сказано про то, что в следующих N будет нулей не больше K +- x.
А значит на сколько "прыгать" непонятно. Во втором высказывании N уменьшается, т.е. пользы нет.

Эффект "прыганья" основан на другом высказывании: если N имеет К нулей, то любое значение [N..N+a] имеет не более K+x нулей.
Вопрос в том каково может быть a и x? И здесь все не так очевидно:

Пример:
.....2015625101.....
.....4031250202..... N — 1 ноль
.....8062500404..... N+1 — 2 нуля
....16125000808..... N+2 — 3 нуля
....32250001616..... N+3 — 3 нуля
....64500003232..... N+4 — 4 нуля
...128000006464..... N+5 — 5 нулей

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

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

N>>- если в N-й степени двойки есть K нулей подряд, то в N+1,N+2,N+3 — не менее (K-1), N+4,N+5,N+6 — не менее (K-2) и т.д.
N>>И обратно: если в N-й степени двойки есть не более K нулей подряд, то в N-1 — не более (K+1), N-2,N-3,N-4 — не более (K+2)

B>Что-то я не могу понять как это может помочь.
B>Т.к. N у нас возрастает, то польза есть только от первого высказывания, а в нем ничего не сказано про то, что в следующих N будет нулей не больше K +- x.
B>А значит на сколько "прыгать" непонятно. Во втором высказывании N уменьшается, т.е. пользы нет.

B>Эффект "прыганья" основан на другом высказывании: если N имеет К нулей, то любое значение [N..N+a] имеет не более K+x нулей.
B>Вопрос в том каково может быть a и x? И здесь все не так очевидно:

B>Пример:
B>.....2015625101.....
B>.....4031250202..... N — 1 ноль
B>.....8062500404..... N+1 — 2 нуля
B>....16125000808..... N+2 — 3 нуля
B>....32250001616..... N+3 — 3 нуля
B>....64500003232..... N+4 — 4 нуля
B>...128000006464..... N+5 — 5 нулей

Вот именно! Количество нулей может возрастать практически +1 ноль на +1 степень! А вот убывает заметно медленнее:

...***00000 * 10^N + Y, Y< 10^N, 5 нулей
...***00000 * 10^N + 2*Y
...***00000 * 10^N + 4*Y
...***00000 * 10^N + 8*Y, не менее 4 нулей
...***00000 * 10^N + 16*Y
...***00000 * 10^N + 32*Y
...***00000 * 10^N + 64*Y не менее 3 нулей
и т.д.

Т. е. теоретически если просматривать N в убывающем порядке то можно проверять не все степени подряд, а заметно меньше.
Но, как Вы правильно заметили, N у нас возрастает.
И если прыгнуть на К степеней вперед иногда можно сразу определить, что среди этих степеней нет ни одной, количество нулей в которой превосходит уже просчитаное. Если нельзы это сразу сказать — по крайней иере можно часто можно пропустить сразу несколько степеней

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

B>>Пример:
B>>.....2015625101.....
B>>.....4031250202..... N — 1 ноль
B>>.....8062500404..... N+1 — 2 нуля
B>>....16125000808..... N+2 — 3 нуля
B>>....32250001616..... N+3 — 3 нуля
B>>....64500003232..... N+4 — 4 нуля
B>>...128000006464..... N+5 — 5 нулей

N>Вот именно! Количество нулей может возрастать практически +1 ноль на +1 степень! А вот убывает заметно медленнее:

Из этого же примера видно, что убывать нули могут с такой же скоростью!

N>И если прыгнуть на К степеней вперед иногда можно сразу определить, что среди этих степеней нет ни одной, количество нулей в которой превосходит уже просчитаное. Если нельзы это сразу сказать — по крайней иере можно часто можно пропустить сразу несколько степеней

Как? Пусть имеем N с количеством нулей 4, нам надо 8 нулей. Какое число (числа) будут проверены после N, т.е. куда будет осуществлен прыжок (прыжки)?

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

S>Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!

S>На это ушло 21 день и 2 часа!

S>Одновременно эту задачу считало от 2-х до 8 компов попеременно. В среднем гдето 4-5 штук.
S>Задача без всяких оптимизаций — первоначальный вариант — десятичные числа на чарах!!

S>Продолжать считать думаю на этом варианте нет смысла — до а(15) — топать в 4 раза дольше! Ой ой ой...

S>Еще тут на одном проце оптимизированная до интов(9 десятичных цифр на 1 элемент массива — ИНТ) задача посчитала уже свыше 35 000 000. На это ушло уже 7 дней!
S>Движемся на ней до а(14), интересно же узнать, опередит ли эта оптимальная версия — распределенную..

У меня тоже досчиталось.

0 days 00:00:00.000s: 1 : 10
0 days 00:00:00.000s: 2 : 53
0 days 00:00:00.000s: 3 : 242
0 days 00:00:00.000s: 4 : 377
0 days 00:00:00.000s: 5 : 1491
0 days 00:00:00.000s: 6 : 1492
0 days 00:00:00.000s: 7 : 6801
0 days 00:00:00.000s: 8 : 14007
0 days 00:00:00.125s: 9 : 100823
0 days 00:00:03.237s: 10 : 559940
0 days 00:00:13.042s: 11 : 1148303
0 days 00:02:37.769s: 12 : 4036338
0 days 00:02:37.769s: 13 : 4036339
0 days 09:08:41.660s: 14 : 53619497

4-х головый Intel Xeon 1.6GHz, 64 бита, в среднем загрузка CPU 95%

Завтра будет A15, к понедельнику — A16

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

N>У меня тоже досчиталось.

N> 0 days 00:00:00.000s: 1 : 10
N> 0 days 00:00:00.000s: 2 : 53
N> 0 days 00:00:00.000s: 3 : 242
N> 0 days 00:00:00.000s: 4 : 377
N> 0 days 00:00:00.000s: 5 : 1491
N> 0 days 00:00:00.000s: 6 : 1492
N> 0 days 00:00:00.000s: 7 : 6801
N> 0 days 00:00:00.000s: 8 : 14007
N> 0 days 00:00:00.125s: 9 : 100823
N> 0 days 00:00:03.237s: 10 : 559940
N> 0 days 00:00:13.042s: 11 : 1148303
N> 0 days 00:02:37.769s: 12 : 4036338
N> 0 days 00:02:37.769s: 13 : 4036339
N> 0 days 09:08:41.660s: 14 : 53619497

N>4-х головый Intel Xeon 1.6GHz, 64 бита, в среднем загрузка CPU 95%

N>Завтра будет A15, к понедельнику — A16

Хе! Акромя проца еще надо указывать какой алгоритм...

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

B>Как? Пусть имеем N с количеством нулей 4, нам надо 8 нулей. Какое число (числа) будут проверены после N, т.е. куда будет осуществлен прыжок (прыжки)?

Все не так.
Мы прыгаем на 100 (к примеру), надо 8, а там 4. Значит среди 91-100 не более 7 нулей. проверяем 90 — там 3 нуля, значит среди 77-90 не более 7 нулей.
И т.д.
Проблема в том, чтобы уметь далеко прыгать, хотя как показывет практика, кол-во умножений практически не зависит от дальности каждого начального прыжка и составляет примерно 6-8% от достигнутой степени. Я пробовал прыгать на 7 — 50 и оптимальным является прыжок на 13

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

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

N>>У меня тоже досчиталось.

N>> 0 days 00:00:00.000s: 1 : 10
N>> 0 days 00:00:00.000s: 2 : 53
N>> 0 days 00:00:00.000s: 3 : 242
N>> 0 days 00:00:00.000s: 4 : 377
N>> 0 days 00:00:00.000s: 5 : 1491
N>> 0 days 00:00:00.000s: 6 : 1492
N>> 0 days 00:00:00.000s: 7 : 6801
N>> 0 days 00:00:00.000s: 8 : 14007
N>> 0 days 00:00:00.125s: 9 : 100823
N>> 0 days 00:00:03.237s: 10 : 559940
N>> 0 days 00:00:13.042s: 11 : 1148303
N>> 0 days 00:02:37.769s: 12 : 4036338
N>> 0 days 00:02:37.769s: 13 : 4036339
N>> 0 days 09:08:41.660s: 14 : 53619497

N>>4-х головый Intel Xeon 1.6GHz, 64 бита, в среднем загрузка CPU 95%

N>>Завтра будет A15, к понедельнику — A16

S>Хе! Акромя проца еще надо указывать какой алгоритм...


Ну, алгоритм-то тот же самый, только многопоточный.

Каждый поток берет полученное число, умножает на 2^2000 (примерно) и проверяет этот диапазон
Диапазон проверяется прыжками.

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

N>Каждый поток берет полученное число, умножает на 2^2000 (примерно) и проверяет этот диапазон
N>Диапазон проверяется прыжками.

Так. Понятно.
А если попытаться так же сделать для нескольких компов...
То есть умножаем на большую степень, и результат сохраняем в файл. Чтобы другой комп мог его взять на обработку...
Чтобы скомпенсировать рост числа вширь, и чтобы каждая задача решалась приблизительно равное количество времени, надо каждый раз прыгать на меньшую степень.
А для того чтобы не случалось переполнение памяти, каждый такой блин можно есть по частям справа налево, например долями по 20 000 000 знаков..

А еще лучше чтобы программа сервер — делала эти длинные умножения, и хранила результаты, чтобы потом раздавать клиентам. Это лучче всего будет.
Сервак чтобы торчал в инет, и доступен для скачивания клиент.
Ну а дальше как на БОИНКЕ — раздает одну задачу 3-м разным клиентам, шифрует и так далее... Можно даже для этого заюзать движок ихний. И сделать объяву новой задачи.
Думаю за месяцок МИР расчитает до а50!

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

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

N>>Каждый поток берет полученное число, умножает на 2^2000 (примерно) и проверяет этот диапазон
N>>Диапазон проверяется прыжками.

S>Так. Понятно.
S>А если попытаться так же сделать для нескольких компов...
S>То есть умножаем на большую степень, и результат сохраняем в файл. Чтобы другой комп мог его взять на обработку...
S>Чтобы скомпенсировать рост числа вширь, и чтобы каждая задача решалась приблизительно равное количество времени, надо каждый раз прыгать на меньшую степень.
S>А для того чтобы не случалось переполнение памяти, каждый такой блин можно есть по частям справа налево, например долями по 20 000 000 знаков..

S>А еще лучше чтобы программа сервер — делала эти длинные умножения, и хранила результаты, чтобы потом раздавать клиентам. Это лучче всего будет.
S>Сервак чтобы торчал в инет, и доступен для скачивания клиент.
S>Ну а дальше как на БОИНКЕ — раздает одну задачу 3-м разным клиентам, шифрует и так далее... Можно даже для этого заюзать движок ихний. И сделать объяву новой задачи.
S>Думаю за месяцок МИР расчитает до а50!

Вот только это нахрен никому не надо

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

E>>1) Какие есть ваши доказательства?
S>программа обработала числа до 2^10 000 000. Вероятность появления 2х нулей подряд падала очень быстро.
S>Вероятность встретить 2 нуля подряд в числах такого размера вероятна равна 0.

Ну вероятность — это не доказательство.
>>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
Можно доказать, что не существует такого предела. Я думаю, это можно доказать даже для конкретных позиций ноликов: всегда найдётся сколь угодна большая степень n, так чтобы 2^n в 3 и 4 позиции с конца был нолик.
Как доказать:
Умножение начинается с последних цифр. Умножая любое число мы умножаем сначала последние цифры. Таким образом умножая всё большие и большие числа комбинация последних цифр повторяется циклически. И если мы нашли хоть одно число 2^n в котором встретились два нолика подряд, значит таких чисел будет сколь угодно много.

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

>если мы нашли хоть одно число 2^n в котором встретились два нолика подряд, значит таких чисел будет сколь угодно много.

Ну вот. А чисел в которых встречается только один ноль подряд будет все меньше! И очень скоро таких совсем не станет.

Ну и я добавлю свой результат до кучи.
Реализовано на C# под .NET 3.5, скомпилировано в Release режиме, выполнено на Core 2 Duo 3.0GHz под Windows Vista.

Результат:

time=00:00:00.0220000, k=1, n=10, len=4
time=00:00:00.0230000, k=2, n=53, len=16
time=00:00:00.0230000, k=3, n=242, len=73
time=00:00:00.0230000, k=4, n=377, len=114
time=00:00:00.0240000, k=5, n=1491, len=449
time=00:00:00.0240000, k=6, n=1492, len=450
time=00:00:00.0360000, k=7, n=6801, len=2048
time=00:00:00.0750000, k=8, n=14007, len=4217
time=00:00:01.7930000, k=9, n=100823, len=30351
time=00:00:53.7840000, k=10, n=559940, len=168559
time=00:03:44.9770000, k=11, n=1148303, len=345674
time=00:45:56.7920000, k=12, n=4036338, len=1215059
time=00:45:56.7930000, k=13, n=4036339, len=1215060

Код (идея моя, но если такое уже было — значит изобрел велосипед):

Основной принцип: цифры обрабатываеются по 16 в ulong (INT64, по 4 бита на цифру). Для каждого возможного 16-циферого числа заготовлен массив с количеством нолей с начала, в середине, и в конце числа.

using System;

namespace KZerosCalculator
{
    class Program
    {
        static void Main()
        {
            DateTime statTime = DateTime.Now;

            CalculateZeros(
                delegate(int zeros, int power2, int digits)
                {
                    TimeSpan ts = DateTime.Now - statTime;
                    Console.WriteLine("time={3}, k={0}, n={1}, len={2}", zeros, power2, digits, ts);
                });
        }

        delegate void OutputResultDelegate(int zeros, int power2, int digits);

        static void CalculateZeros(OutputResultDelegate OutputMethod)
        {
            int[] leadingZerosArray;
            int[] trailingZerosArray;
            int[] separateZerosArray;

            PrepareZerosArrays(out leadingZerosArray, out trailingZerosArray, out separateZerosArray);

            ulong[] groups = new ulong[1024 * 1024];
            for (int i = 0; i < groups.Length; i++)
            {
                groups[i] = 0UL;
            }

            groups[0] = 1UL;
            int groupsCount = 1;
            int lastGroupDigitsCount = 1;

            int searchingForZeros = 1;
            int power2 = 0;

            while (groupsCount < groups.Length)
            {
                power2++;

                unchecked
                {
                    int maxFoundZeros = 0;
                    int foundZeros = 0;
                    ulong shiftFlag = 0;

                    for (int i = 0; i < groupsCount; i++)
                    {
                        // x2

                        ulong source = groups[i];

                        ulong b1 = (source & 0x1111111111111111UL);
                        ulong b2 = (source & 0x2222222222222222UL) >> 1;
                        ulong b4 = (source & 0x4444444444444444UL) >> 2;
                        ulong b8 = (source & 0x8888888888888888UL) >> 3;

                        ulong shifts = b8 | b4 & (b2 | b1);
                        ulong tens = (shifts << 3) | (shifts << 1);
                        ulong summ = (source << 1) - tens + (shifts << 4) + shiftFlag;
                        shiftFlag = shifts >> 60;

                        groups[i] = summ;

                        // Compact zeros

                        b1 = (summ & 0x1111111111111111UL);
                        b2 = (summ & 0x2222222222222222UL) >> 1;
                        b4 = (summ & 0x4444444444444444UL) >> 2;
                        b8 = (summ & 0x8888888888888888UL) >> 3;

                        ulong compact = b1 | b2 | b4 | b8;
                        compact = ((compact & 0xF0F0F0F0F0F0F0F0UL) >>  3) | (compact & 0x0F0F0F0F0F0F0F0FUL);
                        compact = ((compact & 0xFF00FF00FF00FF00UL) >>  6) | (compact & 0x00FF00FF00FF00FFUL);
                        compact = ((compact & 0xFFFF0000FFFF0000UL) >> 12) | (compact & 0x0000FFFF0000FFFFUL);
                        compact = ((compact & 0xFFFFFFFF00000000UL) >> 24) | (compact & 0x00000000FFFFFFFFUL);
                        int compactNumber = (int)compact;

                        if ((i + 1 == groupsCount) && (lastGroupDigitsCount < 16) && ((summ & (0x0FUL << (lastGroupDigitsCount * 4))) > 0UL))
                        {
                            lastGroupDigitsCount++;
                            compactNumber = (compactNumber | (0xFFFF << lastGroupDigitsCount)) & 0xFFFF;
                        }

                        // Find zeros count

                        int leadingZeros = leadingZerosArray[compactNumber] + foundZeros;
                        int separateZeros = separateZerosArray[compactNumber];
                        foundZeros = leadingZeros > separateZeros ? leadingZeros : separateZeros;

                        if (foundZeros > maxFoundZeros)
                        {
                            maxFoundZeros = foundZeros;
                        }

                        int trailingZeros = trailingZerosArray[compactNumber];
                        if (trailingZeros < 16)
                        {
                            foundZeros = trailingZeros;
                        }
                    }

                    if (shiftFlag == 1UL)
                    {
                        groups[groupsCount++] = 1UL;
                        lastGroupDigitsCount = 1;
                    }

                    if (maxFoundZeros >= searchingForZeros)
                    {
                        OutputMethod(maxFoundZeros, power2, (groupsCount - 1) * 16 + lastGroupDigitsCount);
                        searchingForZeros = maxFoundZeros + 1;
                    }
                }
            }
        }

        static void PrepareZerosArrays(out int[] leadingZerosArray, out int[] trailingZerosArray, out int[] separateZerosArray)
        {
            leadingZerosArray = new int[0x10000];
            trailingZerosArray = new int[0x10000];
            separateZerosArray = new int[0x10000];

            for (int i = 0; i < 0x10000; i++)
            {
                int number = i;
                int zeros = 0;
                bool separateGroup = false;
                int maxSepareteGroup = 0;

                leadingZerosArray[i] = 0;
                trailingZerosArray[i] = 0;
                separateZerosArray[i] = 0;

                for (int j = 0; j < 16; j++)
                {
                    if ((number & 1) == 0)
                    {
                        zeros++;
                    }
                    else
                    {
                        if (zeros > maxSepareteGroup)
                        {
                            if (separateGroup)
                            {
                                maxSepareteGroup = zeros;
                            }
                            else
                            {
                                leadingZerosArray[i] = zeros;
                            }
                        }

                        separateGroup = true;
                        zeros = 0;
                    }

                    number >>= 1;
                }

                if (zeros == 16)
                {
                    leadingZerosArray[i] = 16;
                    separateZerosArray[i] = 16;
                }
                separateZerosArray[i] = maxSepareteGroup;
                trailingZerosArray[i] = zeros;
            }
        }
    }
}

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

R>Основной принцип: цифры обрабатываеются по 16 в ulong (INT64, по 4 бита на цифру). Для каждого возможного 16-циферого числа заготовлен массив с количеством нолей с начала, в середине, и в конце числа.

Смело

По моему с тем же успехом в инт64 можно запихнуть 18 десятичных цифр...

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

R>>Основной принцип: цифры обрабатываеются по 16 в ulong (INT64, по 4 бита на цифру).
S>Смело

S>По моему с тем же успехом в инт64 можно запихнуть 18 десятичных цифр...
Нельзя — битов не хватит. Я использую INT64 как BCD, и именно на это оптимизированы все операции сдвигов и бинарных & и |.

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

R>Я использую INT64 как BCD, и именно на это оптимизированы все операции сдвигов и бинарных & и |.

И работает быстрее чем предложенный выше вариант с 17/18 цифрами в INT64, и 10-какаятоичная система счисления.
Хотя про вариант с прыжками вперед я прочитал позже, ато бы не выкладывал свой.

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

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

R>>Я использую INT64 как BCD, и именно на это оптимизированы все операции сдвигов и бинарных & и |.

R>И работает быстрее чем предложенный выше вариант с 17/18 цифрами в INT64, и 10-какаятоичная система счисления.

А не факт!

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

S>Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!

S>На это ушло 21 день и 2 часа!

S>Одновременно эту задачу считало от 2-х до 8 компов попеременно. В среднем гдето 4-5 штук.
S>Задача без всяких оптимизаций — первоначальный вариант — десятичные числа на чарах!!

Сегодня посчиталось а14 — оптимизированный вариант (9 десятичных цифр на 1 инт)
Работал 1 процессор Sempron 3400 1.8 ГГЦ.
ушло 15 суток и 13 часов!