Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!
На это ушло 21 день и 2 часа!
Одновременно эту задачу считало от 2-х до 8 компов попеременно. В среднем гдето 4-5 штук.
Задача без всяких оптимизаций — первоначальный вариант — десятичные числа на чарах!!
Продолжать считать думаю на этом варианте нет смысла — до а(15) — топать в 4 раза дольше! Ой ой ой...
Еще тут на одном проце оптимизированная до интов(9 десятичных цифр на 1 элемент массива — ИНТ) задача посчитала уже свыше 35 000 000. На это ушло уже 7 дней!
Движемся на ней до а(14), интересно же узнать, опередит ли эта оптимальная версия — распределенную..
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
Решение этой части этюда
Предисловие. Пытаясь найти какие-нибудь зависимости в последовательности натолкнулся на интересный результат
Написал программку, которая вычисляет количество возможных остатков чисел 2^n при делении их на 10^k
Например 1, 2, 4, 8, 16, 32, 64, 128 ... при делении на 10^1 дает остатки 1, 2, 4, 8, 6, 2, 4, 8, 6 ...
После некоторого числа остатки начинают повторяться (в данном случае после 6).
Количество возможных остатков при делении на 10 равно 5. Это 1, 2, 4, 8 и 6
Аналогично для деления на 100 получаем 22 остатка, при делении на 1000 получаем 103 остатка.
Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ...
Обобщив ее получаем f(k) = 100*5^(k-3) + k
Как уже сказал, остатки после некоторого числа начинают повторяться.
Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ...
Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1)
Вот такой вот результат.
Попытался доказать, что это верно не только для протестированных чисел (k <= 8), но и для всех.
Получилось вот что:
1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)
Итак f(m)-1 = 100 * 5^(m-3) + m - 1 и g(m) = 5*10^(m-1) + 2^(m-1).
Подставляя в выражением получим
2^(100 * 5^(m-3) + m - 1) = x*10^m + 5*10^(m-1) + 2^(m-1)
Умножаем на 2
2^(100 * 5^(m-3) + m) = 2x*10^m + 10^m + 2^m
Переносим 2^m в левую часть и выносим общий множитель
2^m * (2^(100 * 5^(m-3)) - 1) = 10^m * (2x + 1)
Делим на 10^m
(2^(100 * 5^(m-3)) - 1) / 5^m = 2x + 1
Обозначим 5^(m-1) = y, заметим, что y нечетно
(2^(4y) - 1) / 5y = 2x + 1
Откуда
x = (16^y - 1 - 5y) / (2*5y)
а) (16^y - 1 - 5y) делится на 2, т.к. 16^y четное, 5y - нечетное, 1 - нечетное
б) 5y делится на 5y :)
в) (16^y - 1) делится на 5y, т.к.
16^y - 1 = (15+1)^y - 1,
т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем),
а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y
Из этого следует, что x - целое число, для любых m>0
2. Очевидно, что в последовательности g(m) мы найдем число с k нулями.
А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей.
Из этого следует решение этюда :)
3. Более того, такие n не только существуют, но их существует бесконечное количество.
К сожалению, представленные выше рассуждения хотя и позволяют найти нужное n для k нулей,
но не позволяют высчитывать члены той-самой последовательности, которая обсуждается в этом топике.
Т.к. в последовательности присутствуют только минимальные 2^n содержащие k нулей.
Этот же алгоритм позволяет всего лишь доказать их существование
Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
Этюд для программиста.
Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
Найти a(1),...,a(7).
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
А>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)
А>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"
Подобная задача, по-моему, вошла в сборник всероссийских (или всесоюзных?) математических олимпиад (такая красненькая книжка). И решение там было такое же. Я всегда думал, что только с этого "конца" задачу и можно решить, но вроде бы можно и с другого...
Теорема Эйлера
a^φ(m)-1 = 0 (mod m), где φ(m) = m(1 — 1/p1)(1 — 1/p2)...(1 — 1/pk) и a и m взаимно простые.
В нашем случае имеем:
2^φ(5^k)-1=0 (mod 5^k)
φ(5^k)=5^(k-1)*4
2^(5^(k-1)*4+k)=2^k (mod 10^k)
2^k содержит приблизительно k*lg(2) десятичных знаков
Значит,2^(5^(k-1)*4+k) имеем как минимум k*(1-lg(2)) подряд идущих нулей.
Здравствуйте, 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) неверно
Как и обещал, выкладываю прогу. Считал уже дома на Е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 numberint 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;
//previousif (index > 0)
{
x = (m_maxValue + 1) / 10;
while (x > 0)
{
if (m_number[index - 1] < x)
{
count++;
x /= 10;
}
else
{
x = 0;
}
}
}
//nextif (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();
}
}
Здравствуйте, Pro100Oleh, Вы писали:
PO>Считал на проце Q6600 на C# .Net 3.5 sp1. Программа однопоточная, но юзалось четыре проца где-то по 25% каждый.
PO>
PO>a(1) = 10. Time 00:00:00.0038011, Length 4
PO>a(2) = 53. Time 00:00:00.0000592, Length 16
PO>a(3) = 242. Time 00:00:00.0006503, Length 73
PO>a(4) = 377. Time 00:00:00.0008813, Length 114
PO>a(5) = 1491. Time 00:00:00.0204129, Length 449
PO>a(6) = 1492. Time 00:00:00.0000576, Length 450
PO>a(7) = 6801. Time 00:00:00.4025472, Length 2048
PO>a(8) = 14007. Time 00:00:00.1214338, Length 4217
PO>a(9) = 100823. Time 00:00:08.0502971, Length 30351
PO>a(10) = 559940. Time 00:03:16.3552767, Length 168559
PO>a(11) = 1148303. Time 00:10:54.2630780, Length 345674
Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.
Здравствуйте, vadimcher, Вы писали:
V>Все верно расчитали. Тут можно посмотреть вплоть до a(17): здесь. Внизу комментарий: некто Sacha Roscoe добавил a(15), затем через пару недель a(16), а затем еще a(17)... через 4 года.
... а потом он защитил докторскую диссертацию в своём Западно-Австралийском Университете и забил.
Здравствуйте, Seon, Вы писали:
S>А можно подкорректировать Вашу программу, чтобы писало текущее значение степени, ну типа как
S>std::cout << p << "\r";
import Data.List
import Debug.Trace
zeros n = head [p | p <- [1..], trace ("curent = " ++ show p) $ (replicate n '0') `isInfixOf` (show $ 2^p)]
Здравствуйте, Seon, Вы писали:
S>Распределенный вариант программы сегодня нашел а(14) = 2^53619497 !!!!
S>На это ушло 21 день и 2 часа!
S>Одновременно эту задачу считало от 2-х до 8 компов попеременно. В среднем гдето 4-5 штук. S>Задача без всяких оптимизаций — первоначальный вариант — десятичные числа на чарах!!
Сегодня посчиталось а14 — оптимизированный вариант (9 десятичных цифр на 1 инт)
Работал 1 процессор Sempron 3400 1.8 ГГЦ.
ушло 15 суток и 13 часов!
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher. А>После нового года я постараюсь выложить и саму олимпиадную задачу и решение из сборника задач.
А>Заодно узнаем насколько она старая.
К сожалению, я так и не нашёл книги с решением задачи с помощью логарифмов.
Зато в книге "Зарубежные математические олимпиады" нашёл решение в стиле теоремы Эйлера:
Intel Core 2 Duo 2.67 GHz. Загрузка процессоров 100%.
Работает достаточно быстро. Хотелось бы увидеть результат на 4-ядернике, но у меня такого нет.
2^100823 contains 9 zeros ===> 0 days 00:00:00.45
2^559940 contains 10 zeros ===> 0 days 00:00:06.75
2^1148303 contains 11 zeros ===> 0 days 00:00:23.38
2^4036338 contains 12 zeros ===> 0 days 00:03:58.80
2^4036339 contains 13 zeros ===> 0 days 00:03:58.81
1. Число состоит из "цифр" от 0000 до 9999 (unsigned short). Это позволило сделать умножение на степень двойки и определение количества нулей без использования деления — на таблицах. Таблицы готовятся заранее.
2. Используется обычное прыганье вперед на (нужное количество нулей — текущее количество нулей).
3. Алгоритм многопоточный, на основе OpenMP (надо включить поддержку в VS). Многопоточность используется при умножении и вычислении количества нулей. Причем потоки все вместе работают над одним и тем же большим числом (это удалось разрулить вроде).
Длинненько, но зато полный вариант:
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <omp.h>
// #define TEST_MULT_COUNT
/////////////////////////////////////
/// BIG NUM
// число в памяти представлено в виде массива слов (unsigned short)
// каждое слово - число от 0000 до 9999#define CELL_TYPE unsigned short
#define MAX_CELL 10000
/////////////////////////////////////
// УМНОЖЕНИЕ ЧИСЛА НА СТЕПЕНЬ ДВОЙКИ
/////////////////////////////////////
// mulTable - вспомогательная таблица для быстрого умножения чисел от 0000 до 9999 на степени двойки
// mulTable[x * 16 + pow] = struct {result, carry}
// x - число от 0000 до 9999
// pow - степень двойки, на которую умножается число x (от 0 до 15)
// result - результат умножения % 10000
// carry - перенос в соседнюю клетку = результат умножения / 10000 (т.е. то, что не поместилось в result)#define MUL_TABLE_LEN 10000
struct MulInfo {
CELL_TYPE result;
CELL_TYPE carry;
};
MulInfo mulTable[MUL_TABLE_LEN*16];
void initMulTable() {
for (int i = 0; i < MUL_TABLE_LEN; i++) {
for (unsigned char pow = 0; pow < 16; pow++) {
unsigned int y = i << pow;
mulTable[(i << 4) + pow].result = y % 10000;
mulTable[(i << 4) + pow].carry = y / 10000;
}
}
}
// умножение длинного числа arr длиной len на 2^pow
// результат записывается в arr2 (может совпадать с arr), новая длина записывается в len2 (может совпадать с len)
// многопоточная реализация - массив разбивается на равные части, каждый поток обрабатывает свою частьvoid multArrayC(CELL_TYPE * arr, size_t len, CELL_TYPE * arr2, size_t & len2, int pow)
{
#pragma omp parallel
{
CELL_TYPE carry = 0;
unsigned int index = 0;
// поток берет каждый разряд и умножает его на степень двойки, прибавляя перенос если он есть#pragma omp for
for (int i = 0; static_cast<unsigned int>(i) < len; i++) {
index = i;
MulInfo x = mulTable[ (arr[i] << 4) + pow ];
CELL_TYPE res = x.result + carry;
carry = res >= 10000 ? (res -= 10000, x.carry + 1) : x.carry;
arr2[i] = res;
}
// после обработки своей части массива у нас остался перенос carry, который относится к "чужой части"
// в index хранится индекс последнего обработанного потоком "разряда"
// каждый поток прибавляет оставшийся в конце перенос к следующему "разряду"
// один из потоков, который обрабатывал самые старшие "разряды" числа, при необходимости, увеличивает длину массива
index++; // index = i + 1#pragma omp critical
if (carry != 0) {
if (index < len) {
arr2[ index ] += carry;
if (arr2[index] >= 10000) {
arr2[index] -= 10000;
arr2[index+1]++;
}
} else {
len2++;
arr2[index] = carry;
}
}
}
}
/////////////////////////////////////
// ПОДСЧЕТ КОЛИЧЕСТВА НУЛЕЙ
/////////////////////////////////////
// zerosTable - вспомогательная таблица для быстрого поиска нулей в числах от 0000 до 9999
// учитываются только нули в начале и в конце таких чисел, нули в середине не подсчитываются
// zerosTable[x] = struct {left, right}
// x - число от 0000 до 9999
// left - количество начальных (левых) нулей
// right - количество конечных (правых) нулей#define ZEROS_TABLE_LEN 10000
struct ZerosInfo {
unsigned char left;
unsigned char right;
};
ZerosInfo zerosTable[ZEROS_TABLE_LEN];
void initZerosTable() {
zerosTable[0].left = 0;
zerosTable[0].right = 4;
for (int i = 1; i < ZEROS_TABLE_LEN; i++) {
zerosTable[i].left = 0;
zerosTable[i].right = 0;
char buf[10];
sprintf_s<10>(buf, "%04d", i);
int len = 4;
for (int x = len-1; x >= 0 && buf[x] == '0'; x--)
zerosTable[i].right++;
for (int x = 0; x < len && buf[x] == '0'; x++)
zerosTable[i].left++;
}
}
// возвращает максимальное количество последовательных нулей в числе arr длиной len
// многопоточная реализация - массив разбивается на части, каждый поток обрабатывает свою частьint countZeros(CELL_TYPE * arr, size_t len) {
char globalMax = 0;
#pragma omp parallel
{
char max = 0;
char cur = 0;
CELL_TYPE x;
int index = -1;
// каждый поток подсчитывает нули в своей части#pragma omp for
for (int i = 0; static_cast<unsigned int>(i) < len-1; i++) {
index = i;
x = arr[i];
cur += zerosTable[x].right;
if (x != 0 && max >= cur) {
cur = zerosTable[x].left;
} else if (x != 0) {
max = cur;
cur = zerosTable[x].left;
}
}
// после обработки каждый поток хранит в max максимальное количество нулей в его части
// в index хранится индекс последнего обработанного потоком "разряда" или -1 если цикл не выполнялся
// если поток что-то обрабатывал, обработаем еще один дополнительный (старший) "разряд"if (index != -1) {
cur += zerosTable[ arr[index+1] ].right;
max = max < cur ? cur : max;
// globalMax - максимальное количество нулей в массиве#pragma omp critical
globalMax = max > globalMax ? max : globalMax;
}
}
return globalMax;
}
////////////////////////////////////////////
/// LOGGING
// печать длинного числа в файл и консольvoid print_num(FILE * f, CELL_TYPE * arr, size_t len) {
fprintf(f, "%d ", (int)arr[len-1]);
for (int i = len-2; i >= 0; i--) {
fprintf(f, "%04d ", (int)arr[i]);
}
fflush(f);
}
void printProgress(FILE * f, int i, clock_t start, clock_t end) {
double duration = (end - start) * 1.0f / CLOCKS_PER_SEC + 0.00000005;
int t = (int) duration; // secondsdouble s = t % 60 + (duration - t);
int m = t / 60 % 60;
int h = t / 60 / 60 % 24;
int d = t / 60 / 60 / 24;
fprintf(f, "%12d mln ===> %d days %02d:%02d:%05.2f ===> %5.2f * 10^9 bits per sec\n",
i, d, h, m, s, i * 1.0f * (i+1) / 2e9 / duration);
fflush(f);
}
void printResult(FILE * f, int i, int k) {
fprintf(f, "\n!!!!! 2^%d contains %d zeros\n\n", i, k);
fflush(f);
}
////////////////
///// MAIN
////////////////
CELL_TYPE * arr;
int _tmain(int argc, _TCHAR* argv[]){
// init tables
initZerosTable();
initMulTable();
// file for logging
FILE * f = fopen("log.txt", "w");
// arr = 2^0
arr = (CELL_TYPE *) malloc(1000*1000*1000); // хватит на 6.500.000.000 степеней двойки
size_t len = 1;
arr[0] = 1;
// time measure
clock_t start = clock();
int i = 0; // текущая степень двойкиint last = 0; // последняя степень двойки, информацию о которой записывали в файлint k = 2; // ищем степень двойки с таким количеством нулей#ifdef TEST_MULT_COUNT
for (int i=1; i < 100; i++) {
//doubleArrayC(arr, len);
multArrayC(arr, len, arr, len, 1);
printf("i = %d ===> ", i);
print_num(arr, len);
printf(" ===> zeros = %d", countZeros(arr, len));
printf("\n");
}
#else
while (true) {
// каждую тысячу выводим сообщение, чтобы показать что не завислиif (i - last > 100000) {
last = i;
printProgress(f, i, start, clock());
printProgress(stdout, i, start, clock());
}
int zeros = countZeros(arr,len);
// если нашли нужное количество нулей, то выводим результатwhile (zeros >= k) {
printProgress(f, i, start, clock());
printProgress(stdout, i, start, clock());
printResult(f, i, k);
printResult(stdout, i, k);
k++;
}
// "прыгаем" на расстояние (нужноеКоличествоНулей - найденноеКоличествоНулей)
// нельзя прыгнуть дальше 13, иначе переписывать функцию multArray int step = k - zeros <= 13 ? k - zeros : 13;
multArrayC(arr, len, arr, len, step);
i += step;
}
#endif
free(arr);
puts("Press Enter\n");
getchar();
return 0;
}
И еще.
Можно было бы ускорить все это, используя SSE инструкции. Но мне пока непонятно как на основе арифметических функций и минимума if-ов реализовать умножение на степень двойки. Возьмем например, 128-битное число. В него влезет 8 "разрядов". ABCDEFGH. При умножении на 2^x должно получиться A'B'C'D'E'F'G'H' и некий перенос в следующий разряд. Вот как такое реализовать оперируя этим 128-битным числом как единым целым? Ну или 64-битным.
Еще я экспериментировал с алгоритмом nikholas (с "хитрым" прыганьем). И сделал вывод, что "простое прыганье" работает не медленнее, чем "хитрое". Причина в том, что умножение на большую степень двойки производится "столбиком". Т.е. если надо умножить некое большое число на 2^x и это число включает в себя n "разрядов", то мы должны сделать n больших умножений и потом n больших сложений. При умножении же на маленькую степень мы должны сделать одно большое умножение и одно большое сложение (переносы).
Вот и получается, что время умножения на большую степень двойки сравнимо с последовательным умножением несколько раз на маленькую степень двойки (если алгоритм учитывает, что умножение произодится только на маленькую степень). Например, время умножения на 2^22, сравнимо с умножением на 2^13 и затем на 2^9.
Здравствуйте, Beam, Вы писали:
B>Intel Core 2 Duo 2.67 GHz. Загрузка процессоров 100%. B>Работает достаточно быстро. Хотелось бы увидеть результат на 4-ядернике, но у меня такого нет.
B>2^100823 contains 9 zeros ===> 0 days 00:00:00.45 B>2^559940 contains 10 zeros ===> 0 days 00:00:06.75 B>2^1148303 contains 11 zeros ===> 0 days 00:00:23.38 B>2^4036338 contains 12 zeros ===> 0 days 00:03:58.80 B>2^4036339 contains 13 zeros ===> 0 days 00:03:58.81
Я еще раз просмотрел твой код на предмет поиска нулей, и пришел к выводу, что возможны ошибки при k=2 и k>=5. Стал сравнивать результаты. Выяснилось: ошибки при k=2,3.
Для k=2, понятно. Два нуля оказались внутри 4-хзначной цифры. (Вероятность этого была достаточно маленькая, но я решил проверить, вдруг ты попал как раз в эту вероятность? Попал!) Так что и по логике, и на практике следует начинать с k=3.
Для k=3 у меня выдал 243 вместо 242. Почему? Непонятно. Я этого не ожидал.
Для k>=5. Когда один процессор обработал блок, он смотрит, какое там число стоит дальше, cur += zerosTable[ arr[index+1] ].right. Но что, если там стоит 0000, тогда надо двигать дальше, пока не встретится наконец ненулевое число! Т.е. надо что-то типа int j = 1, z; do { z = zerosTable[ arr[index+j] ].right; cur += z; } while (z == 4);
Тут проблема не только в том, что можно пропустить искомое число нулей, но и в том, что иногда шаг, с которым ты прыгаешь к следующему числу может оказаться больше, чем положено.
Верно?
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Аноним, Вы писали: А>>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)
А>>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"
V>Выделенное не понял.
Ну, как я уже говорил, это вопрос с бородой. Поэтому автор поста написал схематично, опуская детали.
Между прочим, а что имелось в виду
в условиях задачи: ровно k нулей и на к-ом месте не ноль или имелось в виду как минимум к нулей? Если ровно k нулей, то через теорему Эйлера ответ получить
будет тяжело.
Теперь расшифрую Анонима.
Можно доказать более сильное утверждение: для любого натурального числа найдётся степень двойки, которая на него начинается.
Из этого утверждения всё следует.
Докажем это более сильное утверждение.
Пусть какая-то степень двойки начинается на x, тогда для некоторого m выполняется
x*10^m < 2^n <x*10^m+10^m-1.
Таким образом, задачу свелась к следующему: для данного x найти m и n, удовлетворяющие
x*10^m < 2^n <x*10^m+10^m-1
или
n*ln(2)<ln(x*10^m+10^m-1) и ln(x)+ln(10)*m < ln(2)*n
Значит, мы ищем целое число n в интервале ( ln(x)/ln(2)+ln(10)*m/ln(2), ln(x*10^m+10^m-1)/ln(2) )
При больших m ln(x*10^m+10^(m-1)) < ln(x*10^m+10^m-1), поэтому если мы найдём число n в меньшем интервале
Если обозначить очевидно иррациональное число ln(10)/ln(2) через alpha, ln(x) / ln(2) через x1, ln(x+1/10)/ln(2) через
x2, то получаем
Найти m и n такие, что
alpha *m-n лежит в (x1, x2)
А это можно доказать самому. Например, через теорему Лиувилля о приближении иррационального числа рациональной дробью.
Или из Вейля, или как-то ещё.
Что-то получилось многословно. Я помню решение в сборнике олимпиадных задач было совсем короткое...
Но задавать такие задачи детям... Есть в этом что-то садистское.
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Все верно расчитали. Тут можно посмотреть вплоть до a(17): здесь. Внизу комментарий: некто Sacha Roscoe добавил a(15), затем через пару недель a(16), а затем еще a(17)... через 4 года.
Идея здесь в том, чтобы использовать 10⁵-ричную (параметр настраивается) систему счисления, и хранить в отдельной таблице количество нулей для каждой такой «цифры». В основном алгоритме нет ни единой операции деления. И еще кое-где поэкономил на спичках (например, я заменил «if(d!=0){czt=0}» на «czt &= d ? 0 : ~(size_t)0;», чтобы втолковать компилятору, что здесь нужно поставить sbb). Почерпнул немного дельных мыслей из дотнетовского варианта
На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.
Хорошо бы запустить разные решения на одном компьютере, кое-чем померяться ;-).
Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?
Здравствуйте, 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 зн/сек
Ну и я добавлю свой результат до кучи.
Реализовано на C# под .NET 3.5, скомпилировано в Release режиме, выполнено на Core 2 Duo 3.0GHz под Windows Vista.
Код (идея моя, но если такое уже было — значит изобрел велосипед):
Основной принцип: цифры обрабатываеются по 16 в ulong (INT64, по 4 бита на цифру). Для каждого возможного 16-циферого числа заготовлен массив с количеством нолей с начала, в середине, и в конце числа.
Лучше сделать так: по числу x от 0000 до 9999 по таблице получаем zero-mask: на месте нулей — нули, на месте не-нулей — единицы (получаем число от 0 до 15)
для текущей позиции при подсчете нулей помним: максимальное число нулей найденое ранее (max, 0 — 19), число нулей на конце(curr, 0-19)
и далее по таблице [max, curr, zero-mask] получаем новые значения для max и curr
Для того чтоб не заморачиваться насчет конца числа curr может быть больше max, тогда в конце, после любого кол-ва финишных нулей, мы получаем точное значение max(главное в таблице сделать curr(19)->curr(19), а не то...).
Также лучше совместить подсчет нулей с возведением в степень — кеши и все такое
B>Еще я экспериментировал с алгоритмом nikholas (с "хитрым" прыганьем). И сделал вывод, что "простое прыганье" работает не медленнее, чем "хитрое". Причина в том, что умножение на большую степень двойки производится "столбиком". Т.е. если надо умножить некое большое число на 2^x и это число включает в себя n "разрядов", то мы должны сделать n больших умножений и потом n больших сложений. При умножении же на маленькую степень мы должны сделать одно большое умножение и одно большое сложение (переносы).
Я особо не мерял но у меня сложилось впечатление что умножение на 3-х разрядное число (с подсчетом нулей) практически не отличается по времени от умножения на одноразрядное.
И возведение в большую степень работает быстро — я прикидывал, что 2^(10^9) можно получить дней за 7-8
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, Seon, Вы писали:
S>>Моя прога посчитала а(8)
B>Поздравляю
S>>Мдя до 100000 это неделя, не меньше...
B>Может попробовать готовые библиотеки использовать? B>Надо всего-то — работа с большими числами и поиск подстроки. B>Уверен, что такие библиотеки для си есть.
Та тут можно проще сделать... думаю хаскел так и работает...
берем сразу десятичное число в строковом виде и удваиваем его, и проверяем нули!
это будет на несколько порядков быстрее...
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Pro100Oleh, Вы писали:
S>1. Вы в каждом элементе храните число от 0 до 9? Или от 0 до 999999999? S>2. Как у вас получилось вот это PO>>a(12) = 4036338. Time 00:46:04.8292335, Length 1215059 S>при вот этом PO>>
PO>> public static readonly int MaxSegments = 1000000;
PO>> m_number = new int[MaxSegments];
PO>>
S>??? S>4. В функции Check — похоже на перевод из двоичной системы в десятичную... Но я не до конца понял что там происходит.. можете пояснить?
S>В общем идея понятна в таком смысле, поправьте если не так:
S>В каждом инте храним числа от 0 до 999999999. (только мне не понятно максвалуе = 9 ) S>+ легко умножать. S>+ колоссальная экономия памяти S>-- тяжело искать десятичные 0. для этого надо переводить в 10-ю каждый инт, при чем потом каждое переведенное число шерстить на нули. S>не понятно как достигнута скорость (если не брать во внимание разгон )
S>и последнее: как на вашем мегакомпьютере будет работать версия, где 1 байт хранит 1 число от 0 до 9? (по скорости)
У меня переменная длинна используемых чисел в m_numbers[]. Эта длинна равна m_segmentLength. Соответсвенно m_maxValue = 10^m_segmentLength — 1. m_k — текущее количетсво нулей, которые нужно найти. При каждом следующем m_k я вычисляю m_segmentLength (функция Rebuild()) по формуле m_segmentLength = Round(m_k / 2) — округление вверх. Идея в том, что при представленни длинного числа сегментами длинной m_segmentLength последовательность из m_k нулей обязательно заполнит один сегмент нулями полностью. Поэтому я ищю лишь нулевые сегменты, а когда нашел, то парсю его соседей чтобы найти в них нули тоже.
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, vadimcher, Вы писали:
V>>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны? B>Представим 2^n в виде a*10^k + b (b — остаток от деления на 10^k). B>Я говорю, что есть такое m при которых b содержит k нулей. В моем случае b = g(x). B>И доказываю, что cуществует n, такое что 2^n можно представить в такой форме. В моем случае n=f(m)-1. B>Чтобы доказать возможность представления 2^n в такой форме, я доказываю, что при заданных целых b и 2^n, вычисленных по этим формулам, частное "a" тоже будет целым.
Это все понятно. Я тебя про другое, по-моему, спрашивал.
B>>>в) (16^y — 1) делится на 5y, т.к. V>>Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется). B>Я об этом говорил. y = 5^(m-1), а следовательно нечетно. B>А пример не подходит, т.к. 13 не является степенью 5.
И где ты в своем доказательстве того, что 16^y-1 делится на 5y использовал, что y нечетное, или что оно является степенью 5? Вот твое доказательство:
16^y — 1 = (15+1)^y — 1,
т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем),
а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y
S>>Та тут можно проще сделать... думаю хаскел так и работает... S>>берем сразу десятичное число в строковом виде и удваиваем его, и проверяем нули! S>>это будет на несколько порядков быстрее...
S>ДААААААА!!!!!! S>а(9) — меньше 2х минут!!! в дэбаге !!!! S>ща мы его....
Кароче
а(8) — до 2х секунд!
а(9) — 80 секунд!
С++ рулит! главно правильно задачу ему поставить!
а то я сначала мегаматематику подключил универсальную.... перевожу из двоичного числа в десятичное, проверяю.... ХА ХА!
Здравствуйте, Skazitel, Вы писали:
S>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
S>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел... S>Может кто-то глубже и написал, все читать не стал — долго.
S>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Skazitel, Вы писали:
S>>Здравствуйте, vadimcher, Вы писали:
V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>Этюд для программиста. V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>Найти a(1),...,a(7).
S>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел... S>>Может кто-то глубже и написал, все читать не стал — долго.
S>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
V>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
Нигде не сказано => не понятно. А главное, что в первой строчке нету минимуальности И если бы мне дали только первую стоку, то точно не понятно....
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Skazitel, Вы писали:
S>>отрицательные -- n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то? E>Прикольно, но скучно. ВО всяком случае, в качестве этюда для программистов
Каков вопрос, таков ответ. Задачу поставили, я написал решение
Здравствуйте, Erop, Вы писали:
RO>>Просто у тебя при копировании тоже элементы затираются, я решил, что тебе это так надо. E>1) у меня ничего не затирается. Каждый элемент инициализируется ОДИН раз, за исключением тех, кому делают ++*--dst.
И теперь цикл возымеет такое действие: buffer[2]=buffer[1], buffer[3]=buffer[2]... т. е., вместо смещения данных первые count элементов будут размножены 8 раз.
E>2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?
Здравствуйте, Erop, Вы писали:
RO>>И теперь цикл возымеет такое действие: buffer[2]=buffer[1], buffer[3]=buffer[2]... т. е., вместо смещения данных первые count элементов будут размножены 8 раз. E>9 раз. E>Я знаю как работает мой код. Он это и должен делать, вообще-то, а не какое-то там "смещение данных" выполнять. Хотя я понимаю, что ты имеешь в виду, и мог бы, например, написать аналогичный код на memcpy, например. И тоже непереносимый.
Хм, надо было смотреть на название функции...
E>>>2) STL не предоставляет гарантий, что std::copy будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может? RO>>Не предоставляет, естественно.
E>Ну и хрен ли тогда советовать заменить корректный С++ цикл на некорректное использование стандартного алгоритма? :)
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Erop, Вы писали:
E>>Здравствуйте, Pro100Oleh, Вы писали:
PO>>>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.
E>>Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету. E>>Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...
E>>Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...
V>Мне тоже подумалось сначала что-то навроде этого. Т.е. если длина n*k цифр, то n головам отдаем по k цифр на растерзание, причем следующим образом: i-я голова получает на вход цифры c (i-1)*k+1 по i*k а также перенос от правого соседа, который можно тут же вычислить (если правое число начинается с 5 или больше, то будет перенос в эту часть, если нет -- то не будет), далее умножает свою часть на два с прибавлением полученного переноса, а также игнорируя возможный перенос в левую часть (он уже учтен у соседа слева при получении задания) и возвращает вектор значений (l, lb, le), где l -- максимальная найденная строка из нулей, lb -- длина строки из нулей в начале, le -- длина строки из нулей в конце. Все, что остается, только "скомпостировать" результаты, пока головы трудятся над своей частью дальше. Далее, если грамотно организовать, то можно сначала самой левой голове выделить кусок поменьше, а остальным -- одинаковые большие. Тогда в течение многих циклов все могут трудиться над своим куском без остановок, ну а у самого левого длина куска будет расти. Как только она достигнет длины всех остальных кусков происходит синхронное перераспределение кусков.
V>К сожалению, глобально это проблемы не решит. Действительно, как уже обратили внимание, a(n) растет экспоненциально. loga(n) выглядит как прямая, допустим, что она такая и есть, по крайней мере для "видимого диапазона" это почти так (далее никто не бывал, так что остается только догадываться). Вот результат, полученный на коленке в Excel: log[a(n)+1]=n/2+1/2 (на самом деле полученные коэффициент и константа оба равны 0.497), короче a(n)=sqrt(10^(n+1)). Число цифр m в таких числах связано соотношением m-1<lg2*a(n)~0.30103*a<m, т.е. V>m~0.3*a(n)~0.3*10^[(n+1)/2]. Т.е. при увеличении n на два, число цифр увеличивается где-то в десять раз. А значит, чтобы просчитать очередные две цифры с той же скоростью надо в десять раз больше компов (голов). Не хило. Т.е. если хотим до a(17) быстренько досчитать, то надо найти 100 добровольцев . Причем подключать их будем последовательно по мере роста числа.
V>Кстати, последнюю аппроксимацию можно проверить: V>для n=11 дает 0.3*10^6=300000 цифр, истинное значение 345674 V>для n=12 дает 0.3*10^6.5=948683 цифр, истинное значение 1215059 V>для n=13 дает 0.3*10^7=3000000 цифр, истинное значение 1215060 -- в 2 с половиной раза меньше, но a(13) на самом деле оказалось равным a(12)+1 V>А так порядок держит вроде.
Даже так: если просчитать a(14) за приемлемое время и привлечь 100 компов с rsdn, то мы получим a(18)... И опубликуем его на сайте at&t... И прославим rsdn как Дульсинею Тобосскую во веки веков!
Здравствуйте, Beam, Вы писали:
B>Intel Core 2 Duo 2.67 GHz. Загрузка процессоров 100%. B>Работает достаточно быстро. Хотелось бы увидеть результат на 4-ядернике, но у меня такого нет.
B>2^100823 contains 9 zeros ===> 0 days 00:00:00.45 B>2^559940 contains 10 zeros ===> 0 days 00:00:06.75 B>2^1148303 contains 11 zeros ===> 0 days 00:00:23.38 B>2^4036338 contains 12 zeros ===> 0 days 00:03:58.80 B>2^4036339 contains 13 zeros ===> 0 days 00:03:58.81
B>1. Число состоит из "цифр" от 0000 до 9999 (unsigned short). Это позволило сделать умножение на степень двойки и определение количества нулей без использования деления — на таблицах. Таблицы готовятся заранее. B>2. Используется обычное прыганье вперед на (нужное количество нулей — текущее количество нулей). B>3. Алгоритм многопоточный, на основе OpenMP (надо включить поддержку в VS). Многопоточность используется при умножении и вычислении количества нулей. Причем потоки все вместе работают над одним и тем же большим числом (это удалось разрулить вроде).
Вопрос: а зачем ты так делаешь
int step = k - zeros <= 13 ? k - zeros : 13;
multArrayC(arr, len, arr, len, step);
когда вроде можно так
int step = k - zeros;
while (step > 13) {
multArrayC(arr, len, arr, len, 13);
step -= 13;
}
multArrayC(arr, len, arr, len, step);
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
S>a(1) [2^10] = 1024 S>a(2) [2^53] = 9007199254740992 S>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104 S>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272
S>вот пока что успел просчитать...
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, vadimcher, Вы писали:
V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>Этюд для программиста. V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>Найти a(1),...,a(7).
S>>a(1) [2^10] = 1024 S>>a(2) [2^53] = 9007199254740992 S>>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104 S>>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272
S>>вот пока что успел просчитать...
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, Seon, Вы писали:
S>>>Здравствуйте, vadimcher, Вы писали:
V>>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>>Этюд для программиста. V>>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>>Найти a(1),...,a(7).
S>>>a(1) [2^10] = 1024 S>>>a(2) [2^53] = 9007199254740992 S>>>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104 S>>>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272
S>>>вот пока что успел просчитать...
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Решение на Haskell.
import Data.List
zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
А>Решение на Haskell. А>
А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>
Аноним — это я Че-то не залогинился.
S>От блин.... быстро! S>Я а(8) считаю уже час, только до 11000 дошел
Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
А вот девятку до сих пор считает
S>Что за кирпич?
Это вопрос? Или утверждение?
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, Seon, Вы писали:
B>Аноним — это я Че-то не залогинился.
S>>От блин.... быстро! S>>Я а(8) считаю уже час, только до 11000 дошел
B>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек. B>А вот девятку до сих пор считает
S>>Что за кирпич? B>Это вопрос? Или утверждение?
я спрашиваю проц какой?
B>А почему у Вас медленно? Что за язык?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
А>Решение на Haskell. А>
А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>
Блин...
завожу ваш пример в GHC, а мне выдает:
<interactive>:1:8: parse error on input `='
Prelude Data.List>
Здравствуйте, Seon, Вы писали:
S>Блин... S>завожу ваш пример в GHC, а мне выдает:
S><interactive>:1:8: parse error on input `=' S>Prelude Data.List>
S>что это?
S>.... я его тока поставил. еще не шуруплю...
В ghci надо let добавить: let zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, Beam, Вы писали:
B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек. B>>А вот девятку до сих пор считает
B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц B>Просчиталось достаточно быстро — около 13 минут
B>2^100823 содержит 9 нулей подряд B>т.е. a(9) = 100823
B>Само число содержит более 30 тыс. цифр
Здравствуйте, Seon, Вы писали:
S>Моя прога посчитала а(8)
Поздравляю
S>Мдя до 100000 это неделя, не меньше...
Может попробовать готовые библиотеки использовать?
Надо всего-то — работа с большими числами и поиск подстроки.
Уверен, что такие библиотеки для си есть.
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, Beam, Вы писали:
B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек. B>>А вот девятку до сих пор считает
B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц B>Просчиталось достаточно быстро — около 13 минут
B>2^100823 содержит 9 нулей подряд B>т.е. a(9) = 100823
B>Само число содержит более 30 тыс. цифр
А можно подкорректировать Вашу программу, чтобы писало текущее значение степени, ну типа как
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Обратная задача
Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !!
Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, Beam, Вы писали:
B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек. B>>А вот девятку до сих пор считает
B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц B>Просчиталось достаточно быстро — около 13 минут
B>2^100823 содержит 9 нулей подряд B>т.е. a(9) = 100823
B>Само число содержит более 30 тыс. цифр
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Beam, Вы писали:
B>>Здравствуйте, Seon, Вы писали:
S>>>Моя прога посчитала а(8)
B>>Поздравляю
S>>>Мдя до 100000 это неделя, не меньше...
B>>Может попробовать готовые библиотеки использовать? B>>Надо всего-то — работа с большими числами и поиск подстроки. B>>Уверен, что такие библиотеки для си есть.
S>Та тут можно проще сделать... думаю хаскел так и работает... S>берем сразу десятичное число в строковом виде и удваиваем его, и проверяем нули! S>это будет на несколько порядков быстрее...
ДААААААА!!!!!!
а(9) — меньше 2х минут!!! в дэбаге !!!!
ща мы его....
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
S>Обратная задача
S>Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !! S>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
Не существует. Если мы докажем (теоретически), что a(k) есть для любого k, то последовательность таких чисел уходит в бесконечность.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>Этюд для программиста. V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>Найти a(1),...,a(7).
А>Решение на Haskell. А>
А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>
Здравствуйте, vadimcher, Вы писали:
А>>zeros 9 считает уже 7 минут А>>Не дождался — написал, то что есть
V>Волшебный чудо-язык haskell.
#include"stdafx.h"#include <vector>
#include <assert.h>
#include <iostream>
const int logPeriod = 100 * 1000;
const int tryTo = 2 * 1000 * 1000;
class PowerOf2VeryLongNumber {
typedef std::vector<unsigned char> TDigits;
TDigits digits;
public:
PowerOf2VeryLongNumber() { digits.push_back( 1 ); }
int Mult2AndRetMax0Count()
{
int zerCount = 0;
int bestZerCount = 0;
if( digits[digits.size() - 1] != 0 )
digits.push_back( 0 );
int carry = 0;
for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
int res = (*i) * 2 + carry;
if( res > 9 ) {
assert( res < 20 );
carry = 1;
*i = ( res -= 10 );
} else {
*i = res;
carry = 0;
}
if( res == 0 ) {
++zerCount;
} else {
if( zerCount > bestZerCount ) {
bestZerCount = zerCount;
}
zerCount = 0;
}
}
assert( carry == 0 );
return bestZerCount;
}
template<typename TStream>
TStream& Output( TStream& dst ) const
{
for( TDigits::const_reverse_iterator i = digits.rbegin(); i != digits.rend(); ++i ) {
dst << (int)*i;
}
return dst;
}
};
template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
return x.Output( dst );
}
struct Result {
int PowerValue;
PowerOf2VeryLongNumber x;
};
int _tmain(int argc, _TCHAR* argv[])
{
PowerOf2VeryLongNumber x;
std::vector<Result> result;
Result tmp = { 0 };
result.push_back( tmp );
for( int i = 1; i < tryTo; i++ ) {
int zCount = x.Mult2AndRetMax0Count();
bool outputProgressLog = ( i % logPeriod ) == 0;
while( result.size() <= zCount ) {
Result r = { i, x };
result.push_back( r );
outputProgressLog = true;
}
if( outputProgressLog ) {
std::cout << "2^" << i << " = " << zCount << ", " << result.size() - 1 << std::endl;
}
}
std::cout << "--------------------------" << std::endl;
for( int i = 1; i < result.size(); i++ ) {
std::cout << "a(" << i << ") = 2^" << result[i].PowerValue /*<< " = " << result[i].x */<< std::endl;
}
return 0;
}
9 -- меньше минуты. Написал из головы, вроде сразу заработало...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>9 -- меньше минуты. Написал из головы, вроде сразу заработало...
10 -- 14 минут ужо...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
а(10) посчитался на 11-й минуте...
Возможно можно ещё разогнать, если сразу парами цифп оперировать, или, даже, 4-ками...
Может попробую. Интересно же
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>>>9 -- меньше минуты. Написал из головы, вроде сразу заработало... E>>10 -- 14 минут ужо...
E>а(10) посчитался на 11-й минуте... E>Возможно можно ещё разогнать, если сразу парами цифп оперировать, или, даже, 4-ками... E>Может попробую. Интересно же
2^4036338, 12, len = 1215059
2^4036339, 13, len = 1215060
за ночь нашёл, потом, похоже, закончился кэш
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, vadimcher, Вы писали:
V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>Этюд для программиста. V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>Найти a(1),...,a(7).
S>>Обратная задача
S>>Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !! S>>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
V>Не существует. Если мы докажем (теоретически), что a(k) есть для любого k, то последовательность таких чисел уходит в бесконечность.
Почему?
Чем длинее числа, тем вероятность того что встретится два нуля подрад — увеличивается, следовательно когда то наступит момент что эта вероятность будет равна 1
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, vadimcher, Вы писали:
V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>Этюд для программиста. V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>Найти a(1),...,a(7).
S>>Обратная задача
S>>Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !! S>>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
V>Не существует. Если мы докажем (теоретически), что a(k) есть для любого k, то последовательность таких чисел уходит в бесконечность.
Последнее число, в котором нет двух нулей подряд — 2^2114 !
Здравствуйте, Erop, Вы писали:
E>>>>9 -- меньше минуты. Написал из головы, вроде сразу заработало... E>>>10 -- 14 минут ужо...
E>>а(10) посчитался на 11-й минуте... E>>Возможно можно ещё разогнать, если сразу парами цифп оперировать, или, даже, 4-ками... E>>Может попробую. Интересно же
Над парами цифр:
#include"stdafx.h"#include <vector>
#include <assert.h>
#include <iostream>
#include <iomanip>
const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
const int digitsCount = 2;
const int maxDigitsVal = 99;
typedef signed char small;
small left_z_count[maxDigitsVal + 1] = { -100 };
small right_z_count[maxDigitsVal + 2] = { -100 };
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;
}
static void fillLeft( small* dst, int start, small init_to )
{
small* from = dst + start;
small* to = dst + start * 10;
while( from != to )
*from++ = init_to;
}
static void initPartOfStaticTable( int& factor, int& left0cnt )
{
expand10times( right_z_count, factor );
fillLeft( left_z_count, factor, left0cnt );
left0cnt--;
factor *= 10;
}
static void initTables()
{
int factor = 1;
int leftDigCount = digitsCount - 1;
initPartOfStaticTable( factor, leftDigCount );
initPartOfStaticTable( factor, leftDigCount );
}
class PowerOf2VeryLongNumber {
typedef small TDigit;
typedef std::vector<TDigit> TDigits;
TDigits digits;
public:
PowerOf2VeryLongNumber() { digits.push_back( 1 ); }
int Mult2AndRetMax0Count()
{
int z_count = 0;
int best_z_count = 0;
int carry = 0;
for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
int newVal = *i*2+carry;
if( newVal > maxDigitsVal ) {
newVal -= maxDigitsVal + 1;
carry = 1;
} else {
carry = 0;
}
*i = newVal;
if( newVal == 0 ) {
z_count += digitsCount;
} else {
z_count += right_z_count[newVal];
if( z_count > best_z_count ) {
best_z_count = z_count;
}
z_count = left_z_count[newVal];
}
}
if( carry != 0 ) {
digits.push_back( carry );
if( z_count > best_z_count ) {
best_z_count = z_count;
}
}
return best_z_count;
}
template<typename TStream>
TStream& Output( TStream& dst ) const
{
for( TDigits::const_reverse_iterator i = digits.rbegin(); i != digits.rend(); ++i ) {
dst << std::setw( digitsCount ) << (int)*i;
}
return dst;
}
int Length() const { return digits.size() - ( digits[digits.size() - 1] == 0 ); }
};
template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
return x.Output( dst );
}
struct Result {
int PowerValue;
PowerOf2VeryLongNumber x;
};
int _tmain(int argc, _TCHAR* argv[])
{
initTables();
PowerOf2VeryLongNumber x;
std::vector<Result> result;
Result tmp = { 0 };
result.push_back( tmp );
for( int i = 1; i < tryTo; i++ ) {
int zCount = x.Mult2AndRetMax0Count();
if( ( i % logPeriod ) == 0 ) {
std::cout << "2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length() << " \r";
}
while( result.size() <= zCount ) {
Result r = { i, x };
result.push_back( r );
std::cout << "2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length() /*<< ", " << x*/ << std::endl;
}
}
std::cout << "--------------------------" << std::endl;
for( int i = 1; i < result.size(); i++ ) {
std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length()
/*<< " = " << result[i].x */<< std::endl;
}
return 0;
}
a(9) за пять минут
Core(TM)2 Duo, 2.66 GHz, однопоточная программа.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Seon, Вы писали:
S>Последнее число, в котором нет двух нулей подряд — 2^2114 !
Два вопроса.
1) Какие есть ваши доказательства?
2) "2114!" -- это факториал?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, vadimcher, Вы писали:
V>>Здравствуйте, Seon, Вы писали:
S>>>Здравствуйте, vadimcher, Вы писали:
V>>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>>Этюд для программиста. V>>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>>Найти a(1),...,a(7).
S>>>Обратная задача
S>>>Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !! S>>>Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?
V>>Не существует. Если мы докажем (теоретически), что a(k) есть для любого k, то последовательность таких чисел уходит в бесконечность.
S>Почему? S>Чем длинее числа, тем вероятность того что встретится два нуля подрад — увеличивается, следовательно когда то наступит момент что эта вероятность будет равна 1
Здравствуйте, Roman Odaisky, Вы писали:
RO>Ты настолько не любишь STL?
Даже ещё больлше, в отличии от функций memcpy и memset
Просто сначала этот код на другой библиотеке был. Потом я её отковырял...
RO>std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count); RO>++buffer[10 * count];
А разве так можно?
E>>a(9) за пять минут
RO>Мой результат похуже, выкладывать не стану. Я решил использовать 10¹⁶-ричную систему счисления, но из того ничего дельного не вышло.
Зато он, наверное, на хорошем STL
Выкладывай, не стесняйся.
Я сейчас опубликую более вменяемый вариант...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>9 -- меньше минуты. Написал из головы, вроде сразу заработало...
Вот, теперь попробовал несколько вариантов. Как и следовало ожидать самый быстрый работает 4-ками цифр.
Пробовал на Core(TM) Duo CPU T2450 2,00 GHz, да ещё и под вистой
Итого:
Вариант с цифрой на байт:
0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:32 : 2^100823 = 9, 9, len = 30351
0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:18 : 2^100823 = 9, 9, len = 30351
#include"stdafx.h"#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>
const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
typedef signed char small_num;
const int digits_count = 2;
const int max_dig_value = 99;
typedef small_num TAllDigitsNum;
void set_if_g( int& dst, int src )
{
if( dst < src )
dst = src;
}
static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
char buffer[1024];
assert( seconds >= 0 );
sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
return buffer;
}
class CDigitsParser {
public:
CDigitsParser( int num_, int max_dig_count = digits_count ) :
num( num_ ), dig_count( -1 ), left_count( max_dig_count )
{
assert( max_dig_count > 0 && num != 0 );
shift_one_dig();
assert( !is_processed() );
right_count = shift_right_z();
max_in_count = 0;
shift_right_nz();
while( num != 0 ) {
const int in_count = shift_right_z();
set_if_g( max_in_count, in_count );
shift_right_nz();
}
assert( dig_count > 0 && dig_count <= left_count );
left_count -= dig_count;
assert( is_processed() );
}
int GetLeftCount() const { assert( is_processed()); return left_count; }
int GetInCount() const { assert( is_processed()); return max_in_count; }
int GetRightCount() const { assert( is_processed()); return right_count; }
private:
enum { base = 10 };
int num;
int dig;
int dig_count;
int left_count;
int max_in_count;
int right_count;
bool is_processed() const { return num == 0 && dig == 0; }
void shift_one_dig()
{
dig = num % base;
num /= base;
dig_count++;
}
int shift_right_z()
{
assert( !is_processed() );
int count = 0;
while( dig == 0 ) {
shift_one_dig();
count++;
}
return count;
}
int shift_right_nz()
{
int count = 0;
while( dig != 0 ) {
shift_one_dig();
count++;
}
return count;
}
}; // CDigitsParser
small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };
void init_tables()
{
for( int i = 1; i <= max_dig_value; ++i ) {
CDigitsParser p( i );
left_z_count[i] = p.GetLeftCount();
in_z_count[i] = p.GetInCount();
right_z_count[i] = p.GetRightCount();
}
}
class PowerOf2VeryLongNumber {
typedef TAllDigitsNum TDig;
typedef std::vector<TDig> TDigits;
TDigits digits;
public:
PowerOf2VeryLongNumber() { digits.push_back( 1 ); }
int Mult2AndRetMax0Count()
{
int cur_z_count = 0;
int best_z_count = 0;
int carry = 0;
for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
int dig = *i*2 + carry;
if( dig > max_dig_value ) {
carry = 1;
dig -= max_dig_value + 1;
} else {
carry = 0;
}
*i = dig;
if( dig == 0 ) {
cur_z_count += digits_count;
} else {
set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
//set_if_g( best_z_count, in_z_count[dig] ); // для больших чисел не важно...
cur_z_count = left_z_count[dig];
}
}
if( carry != 0 ) {
digits.push_back( carry );
}
return best_z_count;
}
template<typename TStream>
TStream& Output( TStream& dst ) const
{
TDigits::const_reverse_iterator i = digits.rbegin();
dst << (int)*i;
for( ++i; i != digits.rend(); ++i ) {
dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
}
return dst;
}
int Length() const
{
assert( digits[digits.size() - 1] != 0 );
return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]];
}
};
template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
return x.Output( dst );
}
struct Result {
int PowerValue;
PowerOf2VeryLongNumber x;
};
int _tmain(int argc, _TCHAR* argv[])
{
init_tables();
PowerOf2VeryLongNumber x;
std::vector<Result> result;
Result tmp = { 0 };
result.push_back( tmp );
for( int i = 1; i < tryTo; i++ ) {
int zCount = x.Mult2AndRetMax0Count();
if( ( i % logPeriod ) == 0 ) {
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/* << ", " << x */<< " <-\r";
}
while( result.size() <= zCount ) {
Result r = { i, x };
result.push_back( r );
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/** << ", " << x **/<< " " << std::endl;
}
}
std::cout << "--------------------------" << std::endl;
for( int i = 1; i < result.size(); i++ ) {
std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length()
/*<< " = " << result[i].x */<< std::endl;
}
return 0;
}
Вариант с четырьмя цифрами на short:
0:00:01 : 2^10 = 1, 1, len = 4
0:00:01 : 2^53 = 2, 2, len = 16
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:10 : 2^100823 = 9, 9, len = 30351
#include"stdafx.h"#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>
const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
typedef signed char small_num;
const int digits_count = 4;
const int max_dig_value = 9999;
typedef short TAllDigitsNum;
void set_if_g( int& dst, int src )
{
if( dst < src )
dst = src;
}
static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
char buffer[1024];
assert( seconds >= 0 );
sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
return buffer;
}
class CDigitsParser {
public:
CDigitsParser( int num_, int max_dig_count = digits_count ) :
num( num_ ), dig_count( -1 ), left_count( max_dig_count )
{
assert( max_dig_count > 0 && num != 0 );
shift_one_dig();
assert( !is_processed() );
right_count = shift_right_z();
max_in_count = 0;
shift_right_nz();
while( num != 0 ) {
const int in_count = shift_right_z();
set_if_g( max_in_count, in_count );
shift_right_nz();
}
assert( dig_count > 0 && dig_count <= left_count );
left_count -= dig_count;
assert( is_processed() );
}
int GetLeftCount() const { assert( is_processed()); return left_count; }
int GetInCount() const { assert( is_processed()); return max_in_count; }
int GetRightCount() const { assert( is_processed()); return right_count; }
private:
enum { base = 10 };
int num;
int dig;
int dig_count;
int left_count;
int max_in_count;
int right_count;
bool is_processed() const { return num == 0 && dig == 0; }
void shift_one_dig()
{
dig = num % base;
num /= base;
dig_count++;
}
int shift_right_z()
{
assert( !is_processed() );
int count = 0;
while( dig == 0 ) {
shift_one_dig();
count++;
}
return count;
}
int shift_right_nz()
{
int count = 0;
while( dig != 0 ) {
shift_one_dig();
count++;
}
return count;
}
}; // CDigitsParser
small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };
void init_tables()
{
for( int i = 1; i <= max_dig_value; ++i ) {
CDigitsParser p( i );
left_z_count[i] = p.GetLeftCount();
in_z_count[i] = p.GetInCount();
right_z_count[i] = p.GetRightCount();
}
}
class PowerOf2VeryLongNumber {
typedef TAllDigitsNum TDig;
typedef std::vector<TDig> TDigits;
TDigits digits;
public:
PowerOf2VeryLongNumber() { digits.push_back( 1 ); }
int Mult2AndRetMax0Count()
{
int cur_z_count = 0;
int best_z_count = 0;
int carry = 0;
for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
int dig = *i*2 + carry;
if( dig > max_dig_value ) {
carry = 1;
dig -= max_dig_value + 1;
} else {
carry = 0;
}
*i = dig;
if( dig == 0 ) {
cur_z_count += digits_count;
} else {
set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
set_if_g( best_z_count, in_z_count[dig] ); // для больших чисел не важно...
cur_z_count = left_z_count[dig];
}
}
if( carry != 0 ) {
digits.push_back( carry );
}
return best_z_count;
}
template<typename TStream>
TStream& Output( TStream& dst ) const
{
TDigits::const_reverse_iterator i = digits.rbegin();
dst << (int)*i;
for( ++i; i != digits.rend(); ++i ) {
dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
}
return dst;
}
int Length() const
{
assert( digits[digits.size() - 1] != 0 );
return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]];
}
};
template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
return x.Output( dst );
}
struct Result {
int PowerValue;
PowerOf2VeryLongNumber x;
};
int _tmain(int argc, _TCHAR* argv[])
{
init_tables();
PowerOf2VeryLongNumber x;
std::vector<Result> result;
Result tmp = { 0 };
result.push_back( tmp );
for( int i = 1; i < tryTo; i++ ) {
int zCount = x.Mult2AndRetMax0Count();
if( ( i % logPeriod ) == 0 ) {
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/* << ", " << x */<< " <-\r";
}
while( result.size() <= zCount ) {
Result r = { i, x };
result.push_back( r );
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/** << ", " << x **/<< " " << std::endl;
}
}
std::cout << "--------------------------" << std::endl;
for( int i = 1; i < result.size(); i++ ) {
std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length()
/*<< " = " << result[i].x */<< std::endl;
}
return 0;
}
Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:09 : 2^100823 = 9, 9, len = 30351
#include"stdafx.h"#include <vector>
#include <assert.h>
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>
const int logPeriod = 10 * 1000;
const int tryTo = 20 * 1000 * 1000;
typedef signed char small_num;
const int digits_count = 4;
const int max_dig_value = 9999;
typedef short TAllDigitsNum;
void set_if_g( int& dst, int src )
{
if( dst < src )
dst = src;
}
static int seconds_since_prog_start() { return ( clock() + CLOCKS_PER_SEC - 1 ) / CLOCKS_PER_SEC; }
static std::string time_report( int seconds = seconds_since_prog_start() )
{
char buffer[1024];
assert( seconds >= 0 );
sprintf_s( buffer, "%d:%2.2d:%2.2d", ( seconds / 60 ) / 60, ( seconds / 60 ) % 60, seconds %60 );
return buffer;
}
class CDigitsParser {
public:
CDigitsParser( int num_, int max_dig_count = digits_count ) :
num( num_ ), dig_count( -1 ), left_count( max_dig_count )
{
assert( max_dig_count > 0 && num != 0 );
shift_one_dig();
assert( !is_processed() );
right_count = shift_right_z();
max_in_count = 0;
shift_right_nz();
while( num != 0 ) {
const int in_count = shift_right_z();
set_if_g( max_in_count, in_count );
shift_right_nz();
}
assert( dig_count > 0 && dig_count <= left_count );
left_count -= dig_count;
assert( is_processed() );
}
int GetLeftCount() const { assert( is_processed()); return left_count; }
int GetInCount() const { assert( is_processed()); return max_in_count; }
int GetRightCount() const { assert( is_processed()); return right_count; }
private:
enum { base = 10 };
int num;
int dig;
int dig_count;
int left_count;
int max_in_count;
int right_count;
bool is_processed() const { return num == 0 && dig == 0; }
void shift_one_dig()
{
dig = num % base;
num /= base;
dig_count++;
}
int shift_right_z()
{
assert( !is_processed() );
int count = 0;
while( dig == 0 ) {
shift_one_dig();
count++;
}
return count;
}
int shift_right_nz()
{
int count = 0;
while( dig != 0 ) {
shift_one_dig();
count++;
}
return count;
}
}; // CDigitsParser
small_num left_z_count[max_dig_value + 1] = { -100 };
small_num in_z_count[max_dig_value + 1] = { -100 };
small_num right_z_count[max_dig_value + 1] = { -100 };
void init_tables()
{
for( int i = 1; i <= max_dig_value; ++i ) {
CDigitsParser p( i );
left_z_count[i] = p.GetLeftCount();
in_z_count[i] = p.GetInCount();
right_z_count[i] = p.GetRightCount();
}
}
class PowerOf2VeryLongNumber {
typedef TAllDigitsNum TDig;
typedef std::vector<TDig> TDigits;
TDigits digits;
public:
PowerOf2VeryLongNumber() { digits.push_back( 1 ); }
int Mult2AndRetMax0Count()
{
int cur_z_count = 0;
int best_z_count = 0;
int carry = 0;
for( TDigits::iterator i = digits.begin(); i != digits.end(); ++i ) {
int dig = *i*2 + carry;
if( dig > max_dig_value ) {
carry = 1;
dig -= max_dig_value + 1;
} else {
carry = 0;
}
*i = dig;
if( dig == 0 ) {
cur_z_count += digits_count;
} else {
set_if_g( best_z_count, cur_z_count + right_z_count[dig] );
//set_if_g( best_z_count, in_z_count[dig] ); // для больших чисел не важно...
cur_z_count = left_z_count[dig];
}
}
if( carry != 0 ) {
digits.push_back( carry );
}
return best_z_count;
}
template<typename TStream>
TStream& Output( TStream& dst ) const
{
TDigits::const_reverse_iterator i = digits.rbegin();
dst << (int)*i;
for( ++i; i != digits.rend(); ++i ) {
dst << std::setw( digits_count ) << std::setfill( '0' ) << (int)*i;
}
return dst;
}
int Length() const
{
assert( digits[digits.size() - 1] != 0 );
return digits.size() * digits_count - left_z_count[digits[digits.size() - 1]];
}
};
template<typename TStream>
TStream& operator << ( TStream& dst, const PowerOf2VeryLongNumber& x )
{
return x.Output( dst );
}
struct Result {
int PowerValue;
PowerOf2VeryLongNumber x;
};
int _tmain(int argc, _TCHAR* argv[])
{
init_tables();
PowerOf2VeryLongNumber x;
std::vector<Result> result;
Result tmp = { 0 };
result.push_back( tmp );
for( int i = 1; i < tryTo; i++ ) {
int zCount = x.Mult2AndRetMax0Count();
if( ( i % logPeriod ) == 0 ) {
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/* << ", " << x */<< " <-\r";
}
while( result.size() <= zCount ) {
Result r = { i, x };
result.push_back( r );
std::cout << time_report() << " : 2^" << i << " = " << zCount << ", " << result.size() - 1
<< ", len = " << x.Length()/** << ", " << x **/<< " " << std::endl;
}
}
std::cout << "--------------------------" << std::endl;
for( int i = 1; i < result.size(); i++ ) {
std::cout << "a(" << i << ") = 2^" << result[i].PowerValue << ", len = " << result[i].x.Length()
/*<< " = " << result[i].x */<< std::endl;
}
return 0;
}
Будет время -- попробую обработать переполнение кэша.
Идея такая, что как только массив "цифр" перестаёт помещаться в кэш, так сразу и приходят тормоза.
Если отказаться от хранения самих степеней двойки, для каждого k, то можно сделать хитро.
Фактически Mult2AndRetMax0Count() идёт по массиву "цифр" и меняет его, накапливая некоторое состояние (перенос, длина максимальной обнаруженной цепочки 0, длина текущей обнаруженной цепочки 0, позиция). Можно проходить по куску массива "цифр", который помещается в кэш, и накапливать массив состояний, полученных на границе куска после первого прохода, после второго и т. д. Пока кэш не закончится.
Потом можно переходить к обработке след. куска массива "цифр" и т. д. А когда дойдём до конца массива "цифр" -- узнаем несколько a(k), если повезёт...
Хотя конечно, для радикального ускорения всё этой сосиски её надо на "КУДУ" перенести. Типа массивы *_z_count затолкать в текстурную память, хранить пары "цифр" и переносов, и потом прогонять логарифмическим суммированием по всей этой штуке. Должно быть очень сильно быстрее. Раз в 1000 на хорошей карточке, наверное...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Seon, Вы писали:
S>>>а(8) — до 2х секунд! S>>>а(9) — 80 секунд!
S>>а(10) — 2^559940 — 24 минуты и 20 секунд
S>а(11) — 2^1148303 — 47 минут и 16 секунд
0:00:01 : 2^242 = 3, 3, len = 73
0:00:01 : 2^377 = 4, 4, len = 114
0:00:01 : 2^1491 = 5, 5, len = 449
0:00:01 : 2^1492 = 6, 6, len = 450
0:00:01 : 2^6801 = 7, 7, len = 2048
0:00:01 : 2^14007 = 8, 8, len = 4217
0:00:09 : 2^100823 = 9, 9, len = 30351
0:04:24 : 2^559940 = 10, 10, len = 168559
0:18:23 : 2^1148303 = 11, 11, len = 345674
Гонял на Core(TM) Duo CPU T2450 2,00 GHz под вистой...
А ты?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
Может кто-то глубже и написал, все читать не стал — долго.
отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
Здравствуйте, Skazitel, Вы писали:
S>отрицательные -- n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
Прикольно, но скучно. ВО всяком случае, в качестве этюда для программистов
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Skazitel, Вы писали:
S>>Здравствуйте, vadimcher, Вы писали:
V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>Этюд для программиста. V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>Найти a(1),...,a(7).
S>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел... S>>Может кто-то глубже и написал, все читать не стал — долго.
S>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
V>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое?
образование: математик, системный программист
Здравствуйте, Skazitel, Вы писали:
S>Каков вопрос, таков ответ. Задачу поставили, я написал решение
Ой ли?
Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел...
Может кто-то глубже и написал, все читать не стал — долго.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило!
Ради интереса написал на Лиспе (DrScheme):
#lang scheme
(require srfi/40/stream)
;Поток степеней двойки. Состоит из пар: степень, показатель степени.
(define (double-stream-from n k)
(stream-cons (cons n k)
(double-stream-from (* 2 n) (+ k 1))))
(define pow2-stream (double-stream-from 1 0))
;Функция проверки количества нулей подряд в десятичной системе.
(define (check n k)
(define (check-iter n k z)
(if (= n 0)
false
(if (= k z)
true
(if (= (remainder n 10) 0)
(check-iter (quotient n 10) k (+ z 1))
(check-iter (quotient n 10) k 0)))))
(check-iter n k 0))
;Поток отфильтрованных степеней двойки.
(define (filtered-pow2-stream-from n s)
(if (check (car (stream-car s)) n)
(stream-cons (stream-car s)
(filtered-pow2-stream-from (+ n 1) (stream-cdr s)))
(filtered-pow2-stream-from n (stream-cdr s))))
(define filtered-pow2-stream (filtered-pow2-stream-from 1 pow2-stream))
;Отображение потока.
(define (display-pow2-stream s)
(stream-for-each display-pow s))
(define (display-pow x)
(newline)
(display (cdr x)))
(define display-filtered-pow2-stream (display-pow2-stream filtered-pow2-stream))
Работает очень медленно. Зато функционально И что интересно, сам распараллелился на два потока — один строит степени двойки, а другой эти степени фильрует.
Лисп изучаю, если кто покритикует, буду рад.
Re[2]: k нулей
От:
Аноним
Дата:
21.12.08 15:53
Оценка:
Здравствуйте, Аноним, Вы писали:
А>Решение на Haskell. А>
А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>
Здравствуйте, Erop, Вы писали:
E>Вариант с двумя цифрами на байт: E>Вариант с четырьмя цифрами на short: E>Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)
А как на счет 8 на INT?
... а еще есть вариант 4 цифры на ИНТ, (по 1 на байт)
E>Будет время -- попробую обработать переполнение кэша.
Есть более радикальное решение:
Обрабатывать числа по частям. Ведь для удвоения нам достаточно знать цифру с которой начинать, а это всегда 1, и значение переноса из предыдущего разряда, это 1 или 0 — его запоминать в файле.
Расчитываем числа, длиной например в 1 000 000, — это приблизительно 3 200 000-я степень двойки. Продолжаем считать их например до 1000 000 000 000, запоминая в файле для каждой степени один байт, в котором 1 бит — значение переноса, остальные биты — количество нулей, которые имело число с левой стороны. Таким образом получаем файл в 1000 000 байт.
Затем мы расчитываем числа со степени 3 200 000, начиная с 1, учитывая значения переноса из файла. А при подсчете нулей, начальное количество нулей берем так же из файла.
Ресурс файла по количеству нулей — 127. То есть эта схема файла позволит рассчитать числа до 127 нулей подряд.
Этот алгоритм позволит избавить поиск чисел от зависимости на количество используемой памяти программой. И кстати легко может быть распределен между компьютерами.
1-й ищет части числа 1 000 000 000 000? второй 1 000 000 000 000, третий 1 000 000 000 000, четвертый 1 000 000 000 000.
Кто возьмется писать такую программу, просьба маленькая :
— сделать консольную программу, которая в качестве параметров принимает количество итераций, выходной файл переносов, входной файл переносов. (2 параметра — считать что перенос всегда 0)
— программа должна делать периодическое сохранение промежуточных данных (всего массива чисел), для того чтобы в любой момент можно было продолжить вычисления.
— должна позволить продолжить вычисления, получив четвертый параметр — текущее состояние
Здравствуйте, Erop, Вы писали: E>Здравствуйте, Seon, Вы писали: S>>Последнее число, в котором нет двух нулей подряд — 2^2114 ! E>Два вопроса. E>1) Какие есть ваши доказательства?
программа обработала числа до 2^10 000 000. Вероятность появления 2х нулей подряд падала очень быстро.
Вероятность встретить 2 нуля подряд в числах такого размера вероятна равна 0. E>2) "2114!" -- это факториал?
Нет, просто 2^2114
Здравствуйте, Skazitel, Вы писали:
S>Здравствуйте, vadimcher, Вы писали:
V>>Здравствуйте, Skazitel, Вы писали:
S>>>Здравствуйте, vadimcher, Вы писали:
V>>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>>>>Этюд для программиста. V>>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>>>>Найти a(1),...,a(7).
S>>>Что-то я не понял пролемы... Первое, что я увидел — дикие мучения на тему вычисления огромных чисел... S>>>Может кто-то глубже и написал, все читать не стал — долго.
S>>>отрицательные n решение проблемы. Вроде же очевидно все становится, нет? Огроничений на n нигде нету... в чем проблема то?
V>>Из примеров понятно о чем речь. К тому же a(k) -- "минимальное такое n", которое, если допустить отрицательные n, не существует. У Вас образование не юридическое? S>Нигде не сказано => не понятно. А главное, что в первой строчке нету минимуальности И если бы мне дали только первую стоку, то точно не понятно....
По моему и из первой строки все ясно без проблем..
Не вижу проблем в постановке задачи...
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Erop, Вы писали:
E>>Вариант с двумя цифрами на байт: E>>Вариант с четырьмя цифрами на short: E>>Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)
S>А как на счет 8 на INT?
S>... а еще есть вариант 4 цифры на ИНТ, (по 1 на байт)
E>>Будет время -- попробую обработать переполнение кэша.
S>Есть более радикальное решение: S>Обрабатывать числа по частям. Ведь для удвоения нам достаточно знать цифру с которой начинать, а это всегда 1, и значение переноса из предыдущего разряда, это 1 или 0 — его запоминать в файле.
S>Расчитываем числа, длиной например в 1 000 000, — это приблизительно 3 200 000-я степень двойки. Продолжаем считать их например до 1000 000 000 000, запоминая в файле для каждой степени один байт, в котором 1 бит — значение переноса, остальные биты — количество нулей, которые имело число с левой стороны. Таким образом получаем файл в 1000 000 байт.
S>Затем мы расчитываем числа со степени 3 200 000, начиная с 1, учитывая значения переноса из файла. А при подсчете нулей, начальное количество нулей берем так же из файла.
S>Ресурс файла по количеству нулей — 127. То есть эта схема файла позволит рассчитать числа до 127 нулей подряд.
S>Этот алгоритм позволит избавить поиск чисел от зависимости на количество используемой памяти программой. И кстати легко может быть распределен между компьютерами. S>1-й ищет части числа 1 000 000 000 000? второй 1 000 000 000 000, третий 1 000 000 000 000, четвертый 1 000 000 000 000.
S>Кто возьмется писать такую программу, просьба маленькая : S>- сделать консольную программу, которая в качестве параметров принимает количество итераций, выходной файл переносов, входной файл переносов. (2 параметра — считать что перенос всегда 0) S>- программа должна делать периодическое сохранение промежуточных данных (всего массива чисел), для того чтобы в любой момент можно было продолжить вычисления. S>- должна позволить продолжить вычисления, получив четвертый параметр — текущее состояние
S>
S>Удачи, программисты!
Кстати отсюда вылезает задача о повторяемости:
Через какое количество итераций, числа 1 000 000 000 начнут повторяться, и можно будет для 1 000 000 000 использовать один и тот же файл...
0:00:01 : 2^242 = 3, 3, len = 73
E>>0:00:01 : 2^377 = 4, 4, len = 114
E>>0:00:01 : 2^1491 = 5, 5, len = 449
E>>0:00:01 : 2^1492 = 6, 6, len = 450
E>>0:00:01 : 2^6801 = 7, 7, len = 2048
E>>0:00:01 : 2^14007 = 8, 8, len = 4217
E>>0:00:09 : 2^100823 = 9, 9, len = 30351
E>>0:04:24 : 2^559940 = 10, 10, len = 168559
E>>0:18:23 : 2^1148303 = 11, 11, len = 345674
Гонял на Core(TM) Duo CPU T2450 2,00 GHz под вистой... E>>А ты?
S> Семпрон 1.8 W2003 в belownormal
S>a(12) — 2^4036332 11 часов 18 минут
3:47:15 : 2^4036338 = 12, 12, len = 1215059
3:47:16 : 2^4036339 = 13, 13, len = 1215060
Не совсем понятно от чего 13 не попался сразу. Короче медленно всё. Даже до известного a(17), который пол миллиард, и то бесконечно долго считать будет
S>сейчас приближается к 10 миллионам со скоростью где-то 20 чисел в секунду
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Spiceman, Вы писали:
S>Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило!
Ну на любом языке с поддержкой длинных чисел будет коротко. Вот на С++ с соответствующей библиотекой, например
Другое дело, что будет медленно.
Кстати, чтобы было веселее, предлагаю немного изменить условие задачи — посчитать функцию a( k, base ), где base -- основание системы счисления.
Конечно для степеней двойки задача вырождается, но можно рассмотреть основание 9 или 11, например...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Roman Odaisky, Вы писали:
RO>А вот моя версия. Подход немножко другой, используется 10¹⁶-ричная система счисления.
И что? Как работает?
IMHO, отдельно умножать, и отдельно подсчитывать нули очень невыгодно, так как достаточно длинное число придётся тягать в кэш дважды за тестируемую степень двойки, о хотелось бы на много степеней двойки тягать число в кэш только один раз...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Seon, Вы писали:
S>Не понял, почему вырождается?
потому, что "2 в степени 666" в 8-ричной системе записывается как 1 с 222 нулями
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, vadimcher, Вы писали:
V>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.
Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее.
Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет .
Здравствуйте, Seon, Вы писали:
S>А где же результаты работы? :)) S>Степени + временные интервалы? :shuffle:
~/src :) time ./kzeros 7
6801
./kzeros 7 0.12s user 0.00s system 100% cpu 0.124 total
~/src :) time ./kzeros 8
...10000...
14007
./kzeros 8 0.46s user 0.01s system 99% cpu 0.472 total
Здравствуйте, Pro100Oleh, Вы писали:
PO>Здравствуйте, vadimcher, Вы писали:
V>>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.
PO>Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее. PO>Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет .
Вот вас и просят показать свой алгоритм...
Интересно как это вы в инт64 впихнули 17 цифр
вы говорите в 17 раз быстрее...
У вас на 4 кирпичах — a(11) — 10 минут
У меня на 1 кирпиче — а(11) — 47 минут
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Seon, Вы писали:
S>>Не понял, почему вырождается? E>потому, что "2 в степени 666" в 8-ричной системе записывается как 1 с 222 нулями
RO>~/src :) time ./kzeros 7
RO>6801
RO>./kzeros 7 0.12s user 0.00s system 100% cpu 0.124 total
RO>~/src :) time ./kzeros 8
RO>...10000...
RO>14007
RO>./kzeros 8 0.46s user 0.01s system 99% cpu 0.472 total
RO>
Мдя... медленновато.
Вы тратите много времени на перевод в 10-ю, видимо.
Мы тутачки работаем ужо сразу в десятичной.
14007 считается — 1-2 секунды.
S>>Меня смутил ретурн вот здесь S>>
RO>Это же return из main. Там раньше был еще return 1 на случай ненахождения результата, но я потом его убрал.
Та при чем тут 0 или 1. Зачем вываливаться из цикла как только нашли результат? Не уж-то нельзя продолжить поиск следующего числа?
Зачем потом тратить время опять на умножение сначала?
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Pro100Oleh, Вы писали:
PO>>Здравствуйте, vadimcher, Вы писали:
V>>>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.
PO>>Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее. PO>>Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет .
S>Вот вас и просят показать свой алгоритм... S>Интересно как это вы в инт64 впихнули 17 цифр
S>вы говорите в 17 раз быстрее...
S>У вас на 4 кирпичах — a(11) — 10 минут S>У меня на 1 кирпиче — а(11) — 47 минут
S>Где же тут в 17 раз быстрее? интересно
В 17 раз — имеется ввиду теоретическое улутчение в операции умножения, так как я за раз умножаю 17 цифр, а не одну. Но кроме самого умножения выполняются и проверка на нули. Кстати, здесь минус моего алгоритма, так как мне приходится искать втутри многоцифренномго числа нули.
На самом деле можно использовать даже 18 цифр, потому что мы используем только умножения на два: (10е18-1)*2 < Int64.MaxValue = 9,223,372,036,854,775,807. По поводу алгоритма — чуть розже, так как с сегодняшнего дня я в отпуске, а код остался на работе.
RO>>~/src :) time ./kzeros 7
RO>>6801
RO>>./kzeros 7 0.12s user 0.00s system 100% cpu 0.124 total
RO>>~/src :) time ./kzeros 8
RO>>...10000...
RO>>14007
RO>>./kzeros 8 0.46s user 0.01s system 99% cpu 0.472 total
RO>>
S>Мдя... медленновато. :-\
S>Вы тратите много времени на перевод в 10-ю, видимо. S>Мы тутачки работаем ужо сразу в десятичной. S>14007 считается 1—2 секунды.
Написано же — 0,46 с.
S>Зачем вываливаться из цикла как только нашли результат? Неужто нельзя продолжить поиск следующего числа? S>Зачем потом тратить время опять на умножение сначала?
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Pro100Oleh, Вы писали:
PO>>Кстати, я использую не все 17 цифр. Это связанно с эвристикой
S>Нифига не понятно! S>Нужен КОД!
ok, потерпите часик, мне нужно написать прогу заново
RO>делают одно и то же. Меня, правда, смущает то, что диапазоны пересекаются, но результат будет один и тот же, даже если это и не то, что ты планировал.
AFAIK, ты забыл уточнить, что это так в доступной тебе реализации STL.
Вообще-то вроде как стандарт требует чтобы третий аргумент не попадал в интервал, заданный первыми двумя...
Я думал ты круто знаешь STL, поэтому и просил тебя разъяснить можно ли согласно стандарта так писать.
AFAIK, в таком случае надо использовать copy_backwards (или как-то ещё оно называется, я в STL всё время путаюсь, где backwards, а где reverse), а использование таким образом std::copy, AFAIK, это неспецифицированное поведение.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
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 будет работать именно так, в случае такого нарушения. Например, какая-нибудь реализация, может копировать в каком-то хитром порядке Скажем группами... Или таки не может?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Roman Odaisky, Вы писали:
RO>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?
IMHO надо сразу на "КУДУ" нести...
А вообще-то всё это очень к размеру кэша чувствительно, IMHO...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, 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 — случайным образом, поэтому именно таблица должна полностью помещаться в кеше, не число.
[] RO>Идея здесь в том, чтобы использовать 10⁵-ричную (параметр настраивается) систему счисления, и хранить в отдельной таблице количество нулей для каждой такой «цифры». В основном алгоритме нет ни единой операции деления. И еще кое-где поэкономил на спичках (например, я заменил «if(d!=0){czt=0}» на «czt &= d ? 0 : ~(size_t)0;», чтобы втолковать компилятору, что здесь нужно поставить sbb). Почерпнул немного дельных мыслей из дотнетовского варианта
, но полностью тот алгоритм не понял.
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) например. Здесь бы ядра использовались в полную силу.
Здравствуйте, Pro100Oleh, Вы писали:
PO>Здравствуйте, Roman Odaisky, Вы писали:
RO>>Кстати, задача довольно легко параллелизуется. Как удвоение, так и поиск нулей можно поручить разным процессорам, разделив число на части. Чьи программы здесь масштабируются при наличии нескольких процессоров?
PO>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.
Да, если бы, например, были какие-то верхние и нижние границы. Хотя бы рекурсивные...
Здравствуйте, vadimcher, Вы писали:
RO>>На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.
V>Странно, в твоей предыдущей "неоптимизированной" версии a(8) считалось за 0.46 секунд...
Здравствуйте, Roman Odaisky, Вы писали:
RO>Здравствуйте, vadimcher, Вы писали:
RO>>>На Pentium 4 (3 ГГц, мегабайт кеша L2) считает a(8) за 6,7 с (при -DLOG_BASE=7), интеловский компилятор справляется за 6,3 с. На сервере, где Intel Q6600 и 4 МБ кеша, работает за 2,6 с. a(10) — 379 с здесь и 74 с там.
V>>Странно, в твоей предыдущей "неоптимизированной" версии a(8) считалось за 0.46 секунд...
RO>Прошу прощения, не a(8) за 6,7 с, а a(9).
Здравствуйте, Roman Odaisky, Вы писали:
RO>Хм, надо было смотреть на название функции...
+1, ну вообще весь остальной код
E>>Ну и хрен ли тогда советовать заменить корректный С++ цикл на некорректное использование стандартного алгоритма? RO>А хрен ли слушать всякие вредные советы?
Ну так я и не послушал. Зато теперь я ещё больше углубился во мнении, что прежде чем куда совать STL надо пару раз подумать
А то даже такие последовательные поклонники этой библиотеки, как ты, на ровном месте с ней лажают Куда уж нам, простым привыкшим к MFL парням?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Roman Odaisky, Вы писали:
RO>Данные из n у меня берутся последовательно, а вот из mdczt — случайным образом, поэтому именно таблица должна полностью помещаться в кеше, не число.
Ну если в кэш помещается всё, то быстрее получится, чем, если не всё. Я так думаю, что пока всё число лезет в кэш вместе с таблицами, не имеет смысла ускорять обработку одной цифры, за счёт риска перестать помещаться в кэш...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pro100Oleh, Вы писали:
PO>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.
Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету.
Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...
Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pro100Oleh, Вы писали:
PO>>Распараллерировать не интересно. Здесь нужен математических подход в решении задачи, который бы позволил на порядок уменьшить сложность вычислений. Играться же в командах, чтобы выполнить оператор не за 5 тактов, а за 4 — малоэффективно (пусть и увеличится скорость работы в 2-3 раза). Возращаясь к параллельности — распараллерировать нужно не саму итерацию умножение числа 2^x на 2 и далее проверку на нули. Нужно, чтобы был один главный поток, который бы давал своим рабочим потокам задачу: проверитьвсе числа в диапазоне 2^x ... 2^(x+1000) например. Здесь бы ядра использовались в полную силу.
E>Можно хорошо распарарллелить, на самом деле. И просто довольно. Только мне пока некогда и машин многоголовых всё равно нету. E>Могу отладить на двухголовой, и выложить, если есть желающие/могущие на кластере запустить...
E>Общая идея такая, что тормоза начинаются на реально длинных числах. Скажем на числах длинною в десятки миллионов цифр. Соответственно такую задачу и надо параллелить. Параллелить надо так. Каждый процесс идёт по куску числа и всё что надо считает. Доходит до какой-то границы, скажем в миллион цифр, и отдаёт задание в очередь для следующего процесса. А сам возвращается ждать задания от предыдущего. Будет линейно масштабироваться...
Мне тоже подумалось сначала что-то навроде этого. Т.е. если длина n*k цифр, то n головам отдаем по k цифр на растерзание, причем следующим образом: i-я голова получает на вход цифры c (i-1)*k+1 по i*k а также перенос от правого соседа, который можно тут же вычислить (если правое число начинается с 5 или больше, то будет перенос в эту часть, если нет -- то не будет), далее умножает свою часть на два с прибавлением полученного переноса, а также игнорируя возможный перенос в левую часть (он уже учтен у соседа слева при получении задания) и возвращает вектор значений (l, lb, le), где l -- максимальная найденная строка из нулей, lb -- длина строки из нулей в начале, le -- длина строки из нулей в конце. Все, что остается, только "скомпостировать" результаты, пока головы трудятся над своей частью дальше. Далее, если грамотно организовать, то можно сначала самой левой голове выделить кусок поменьше, а остальным -- одинаковые большие. Тогда в течение многих циклов все могут трудиться над своим куском без остановок, ну а у самого левого длина куска будет расти. Как только она достигнет длины всех остальных кусков происходит синхронное перераспределение кусков.
К сожалению, глобально это проблемы не решит. Действительно, как уже обратили внимание, a(n) растет экспоненциально. loga(n) выглядит как прямая, допустим, что она такая и есть, по крайней мере для "видимого диапазона" это почти так (далее никто не бывал, так что остается только догадываться). Вот результат, полученный на коленке в Excel: log[a(n)+1]=n/2+1/2 (на самом деле полученные коэффициент и константа оба равны 0.497), короче a(n)=sqrt(10^(n+1)). Число цифр m в таких числах связано соотношением m-1<lg2*a(n)~0.30103*a<m, т.е.
m~0.3*a(n)~0.3*10^[(n+1)/2]. Т.е. при увеличении n на два, число цифр увеличивается где-то в десять раз. А значит, чтобы просчитать очередные две цифры с той же скоростью надо в десять раз больше компов (голов). Не хило. Т.е. если хотим до a(17) быстренько досчитать, то надо найти 100 добровольцев . Причем подключать их будем последовательно по мере роста числа.
Кстати, последнюю аппроксимацию можно проверить:
для n=11 дает 0.3*10^6=300000 цифр, истинное значение 345674
для n=12 дает 0.3*10^6.5=948683 цифр, истинное значение 1215059
для n=13 дает 0.3*10^7=3000000 цифр, истинное значение 1215060 -- в 2 с половиной раза меньше, но a(13) на самом деле оказалось равным a(12)+1
А так порядок держит вроде.
1. Вы в каждом элементе храните число от 0 до 9? Или от 0 до 999999999?
2. Как у вас получилось вот это PO>a(12) = 4036338. Time 00:46:04.8292335, Length 1215059
при вот этом PO>
PO> public static readonly int MaxSegments = 1000000;
PO> m_number = new int[MaxSegments];
PO>
???
4. В функции Check — похоже на перевод из двоичной системы в десятичную... Но я не до конца понял что там происходит.. можете пояснить?
В общем идея понятна в таком смысле, поправьте если не так:
В каждом инте храним числа от 0 до 999999999. (только мне не понятно максвалуе = 9 )
+ легко умножать.
+ колоссальная экономия памяти
-- тяжело искать десятичные 0. для этого надо переводить в 10-ю каждый инт, при чем потом каждое переведенное число шерстить на нули.
не понятно как достигнута скорость (если не брать во внимание разгон )
и последнее: как на вашем мегакомпьютере будет работать версия, где 1 байт хранит 1 число от 0 до 9? (по скорости)
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в десятичной[i] записи числа 2^n, встречается k нулей подряд.
B>Решение этой части этюда
Мне твое доказательство пока не до конца ясно. Пройдемся...
B>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ... B>Обобщив ее получаем f(k) = 100*5^(k-3) + k B>Как уже сказал, остатки после некоторого числа начинают повторяться. B>Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ... B>Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1) B>Вот такой вот результат. B>Попытался доказать, что это верно не только для протестированных чисел (k <= 8), но и для всех.
Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
Впрочем, может это и не важно для твоего доказательства, т.к. как я понял, то, что ты пытаешься доказать в пункте 1, означает, что g(m) -- возможный остаток при делении [i]некоторой степени двойки на 10^m. Этого достаточно, т.к. 10^m > g(m). Однако это может оказаться важным, если пункт 1 твоего доказательства неверен.
B>1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)
[] B>в) (16^y — 1) делится на 5y, т.к.
Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется).
B>2. Очевидно, что в последовательности g(m) мы найдем число с k нулями. B>А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей. B>Из этого следует решение этюда
Ты, видимо, имел в виду "при делении 2^n на 10^m получим остаток, сожержащий k нулей."
Тем не менее, интересный подход, и такое впечатление, что он может привести к решению.
А вот зайца кому, зайца-выбегайца?!
Re: k нулей
От:
Аноним
Дата:
24.12.08 02:55
Оценка:
Здравствуйте, vadimcher, Вы писали:
V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
V>Этюд для программиста. V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д. V>Найти a(1),...,a(7).
Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)
Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"
Здравствуйте, vadimcher, Вы писали:
V>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны?
Представим 2^n в виде a*10^k + b (b — остаток от деления на 10^k).
Я говорю, что есть такое m при которых b содержит k нулей. В моем случае b = g(x).
И доказываю, что cуществует n, такое что 2^n можно представить в такой форме. В моем случае n=f(m)-1.
Чтобы доказать возможность представления 2^n в такой форме, я доказываю, что при заданных целых b и 2^n, вычисленных по этим формулам, частное "a" тоже будет целым.
B>>в) (16^y — 1) делится на 5y, т.к.
V>Здесь прокол в доказательстве. Во-первых, ты нигде не использовал, что y нечетное, а утверждение очевидно неверное для четных y. Кроме того, 16^13-1 не делится на 65 (число 13 взял наобум, может еще для каких не выполняется).
Я об этом говорил. y = 5^(m-1), а следовательно нечетно.
А пример не подходит, т.к. 13 не является степенью 5.
B>>2. Очевидно, что в последовательности g(m) мы найдем число с k нулями. B>>А значит существует такое число n, что при делении 2^n на 10^k получим остаток, содержащий k нулей. B>>Из этого следует решение этюда
V>Ты, видимо, имел в виду "при делении 2^n на 10^m получим остаток, сожержащий k нулей."
Здравствуйте, Beam, Вы писали:
B>Здравствуйте, vadimcher, Вы писали:
V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.
B>Решение этой части этюда
B>Предисловие. Пытаясь найти какие-нибудь зависимости в последовательности натолкнулся на интересный результат
B>Написал программку, которая вычисляет количество возможных остатков чисел 2^n при делении их на 10^k B>Например 1, 2, 4, 8, 16, 32, 64, 128 ... при делении на 10^1 дает остатки 1, 2, 4, 8, 6, 2, 4, 8, 6 ... B>После некоторого числа остатки начинают повторяться (в данном случае после 6). B>Количество возможных остатков при делении на 10 равно 5. Это 1, 2, 4, 8 и 6 B>Аналогично для деления на 100 получаем 22 остатка, при делении на 1000 получаем 103 остатка. B>Т.е. имеем последовательность f(k) = 5, 22, 103, 504, 2505, 12506, 62507, 312508 ... B>Обобщив ее получаем f(k) = 100*5^(k-3) + k
B>Как уже сказал, остатки после некоторого числа начинают повторяться. B>Найдя эти "последние" остатки получил еще одну интересную последовательность 6, 52, 504, 5008, 50016, 500032, 5000064 ... B>Обобщив ее получаем g(k) = 5*10^(k-1) + 2^(k-1)
2^(2505-1)
60132483752768192589337987035581840778837848281481388329043814365157069039734033365
71723612042541509339239323992416924164947646261625884250430516975500483783435104693
05978499434759066365745810932149966577954528288850798772444024927951838520227542350
58879180375008327907459992704354324702525063610134325603963613584257226698077210866
97965594178563342037853359202620643016368419959048118246112515022278177758493915308
05029190273917571539320710435893386487658970495023503337021002531803558460354723583
98630634564189720424240469835564945762960051260079413879992251123446696070679668135
05060724474749961684572680842562091232767971493355989701146839512474920828253732280
043454304126203636001132485604207238035424461476759780217566076674821411534921911832150016
B>1. Докажем что, для любых целых m > 0, существует целое x, такое что 2^(f(m)-1) = x*10^m + g(m)
Здравствуйте, Spiceman, Вы писали:
S>Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило! S>Ради интереса написал на Лиспе (DrScheme): S>[skip] S>Работает очень медленно. Зато функционально И что интересно, сам распараллелился на два потока — один строит степени двойки, а другой эти степени фильрует.
Новое решение на лиспе:
#lang scheme
(require srfi/40/stream)
(require srfi/19)
;Числа представлены по основанию k в виде списка.
(define (base k)
(if (< k 14)
(cond ((= k 0) 1)
((= k 1) 10)
((= k 2) 100)
((= k 3) 1000)
((= k 4) 10000)
((= k 5) 100000)
((= k 6) 1000000)
((= k 7) 10000000)
((= k 8) 100000000)
((= k 9) 1000000000)
((= k 10) 10000000000)
((= k 11) 100000000000)
((= k 12) 1000000000000)
((= k 13) 10000000000000))
(cond ((= k 14) 100000000000000)
((= k 15) 1000000000000000)
((= k 16) 10000000000000000)
((= k 17) 100000000000000000)
((= k 18) 1000000000000000000)
((= k 19) 10000000000000000000))))
;p - показатель степени двойки, b - основание системы.
(define (make-number p b)
(define (iter n)
(if (= n 0)
'()
(cons (remainder n b)
(iter (quotient n b)))))
(iter (expt 2 p)))
;s - список, m - знак переноса разрядов, b - основание системы.
(define (double-list s m b)
(if (null? s)
(if (= m 0)
'()
(cons m '()))
(let ((n (* (car s) 2)))
(let ((c (+ n m)))
(if (>= n b)
(cons (- c b)
(double-list (cdr s) 1 b))
(cons c
(double-list (cdr s) 0 b)))))))
(define (order n k)
(if (>= n (base k))
(+ k 1)
(order n (- k 1))))
(define (mult n p)
(if (odd? n)
false
(let ((b (base p)))
(if (= (remainder n b) 0)
true
false))))
;s - список, p - порядок предыдущего числа в списке, k - проверяемое число нулей.
(define (check s p k)
(if (null? s)
false
(if (= (car s) 0)
true
(if (mult (car s) p)
true
(check (cdr s) (order (car s) k) k)))))
;k - проверяемое число нулей, s - текущее число, p - показатель степени двойки этого числа.
(define (start k s p)
(if (check s k k)
(begin ((println (cons p k))
(start (+ k 1) (make-number (+ p 1) (base (+ k 1))) (+ p 1))))
(start k (double-list s 0 (base k)) (+ p 1))))
(define (println x)
(newline)
(display x)
(display (date->string (current-date) "~r")))
(define run (start 1 '(1) 0))
Числа представлены списком. Каждый элемент — это разряд числа в системе по основанию 10^k, где k — проверяемое число нулей.
А можно идею алгоритма в кратце, а то не все понятно
Все же не очень быстро...
А почему списком?
Re[5]: С++ версии...
От:
Аноним
Дата:
24.12.08 12:52
Оценка:
У меня вышла вот такая вещь...
#include <stdio.h>
#include <string.h>
#include <vector>
#include <time.h>
// constantsconst unsigned int BlockSize = 1023;
// group of digitsstruct digitgroup
{
digitgroup(): binary(0L) { }
digitgroup(unsigned int bin): binary(bin) { }
union
{
struct
{
unsigned char digit0: 4;
unsigned char digit1: 4;
unsigned char digit2: 4;
unsigned char digit3: 4;
unsigned char digit4: 4;
unsigned char digit5: 4;
unsigned char digit6: 4;
unsigned char digit7: 4;
};
unsigned int binary;
};
};
// block of digitsstruct digitblock
{
// create one block using carry value
digitblock(unsigned char carry = 0)
{
for (int i = 0; i < BlockSize; groups[i++].binary = 0L);
if (carry)
{
count = 1;
groups[0].digit0 = 1;
}
else
count = 0;
}
digitgroup groups[BlockSize];
unsigned int count;
};
// vector of pointers to digit blockstypedef std::vector<digitblock*> digitvector;
// temporary and total execution resultstruct result
{
result(): carry(0), zeros(0), maxzeros(0) { }
unsigned char carry;
unsigned short zeros;
unsigned short maxzeros;
};
// multiply one digitinline unsigned char multiply(unsigned char digit, result& r)
{
// multiply digit
digit <<= 1;
digit += r.carry;
// check carryif (digit > 9)
{
r.carry = 1;
digit -= 10;
}
else
r.carry = 0;
// count zerosif (digit)
{
r.maxzeros = r.zeros > r.maxzeros ? r.zeros : r.maxzeros;
r.zeros = 0;
}
else
++r.zeros;
// return resultreturn digit;
}
// multiply one digit group by twoinline void multiply(digitgroup& part, result& r)
{
// mult digits
part.digit0 = multiply(part.digit0, r);
part.digit1 = multiply(part.digit1, r);
part.digit2 = multiply(part.digit2, r);
part.digit3 = multiply(part.digit3, r);
part.digit4 = multiply(part.digit4, r);
part.digit5 = multiply(part.digit5, r);
part.digit6 = multiply(part.digit6, r);
part.digit7 = multiply(part.digit7, r);
}
void multiply(digitblock& dblock, result& r)
{
// multiply all groups in blockfor (digitgroup *i = dblock.groups, *end = dblock.groups + dblock.count; i != end; multiply(*(i++), r));
// if we have carry and some free groups in block,
// then initialize new group and clear carryif (r.carry && dblock.count < (BlockSize - 1))
{
dblock.groups[dblock.count++].digit0 = 1;
r.carry = 0;
}
}
void multiply(digitvector& digits, result& r)
{
for (digitvector::iterator i = digits.begin(), end = digits.end(); i != end; multiply(**(i++), r));
// if carriage taken out of last block, create, initialize and process new oneif (r.carry)
{
digits.push_back(new digitblock());
multiply(*(digits.back()), r);
}
}
size_t digitscount(const digitvector& digits)
{
if (!digits.size())
return 0;
// count full blocks, each block contains BlockSize groups, each group contains 8 digits
size_t sz = (digits.size() - 1) * BlockSize * 8;
// count full groups in last block which can't be empty, each group contains 8 digits
sz += (digits.back()->count - 1) * 8;
// count active digits in last group
digitgroup &i = digits.back()->groups[digits.back()->count - 1];
if (i.digit7) return sz+8;
if (i.digit6) return sz+7;
if (i.digit5) return sz+6;
if (i.digit4) return sz+5;
if (i.digit3) return sz+4;
if (i.digit2) return sz+3;
if (i.digit1) return sz+2;
if (i.digit0) return sz+1;
return sz;
}
void printtime(clock_t t)
{
size_t msecs = t % CLOCKS_PER_SEC;
size_t secs = (t / CLOCKS_PER_SEC) % 60;
size_t mins = (t / CLOCKS_PER_SEC / 60) % 60;
size_t hours = t / CLOCKS_PER_SEC / 3600;
printf("[%02u:%02u:%02u.%03u]", hours, mins, secs, msecs);
}
void checkzeros(digitvector& digits, size_t& power, size_t& border, size_t zeros)
{
for (result r = result(); r.maxzeros < zeros;)
{
r = result();
power++;
multiply(digits, r);
if (!(power % border))
{
printf("Reached %u power of 2, %u digits total\n", power, digitscount(digits));
border *= 10;
fflush(stdout);
}
}
printtime(clock());
printf(" a(%u) = %u, %u digits total\n", zeros, power, digitscount(digits));
fflush(stdout);
}
int main(int argc, char** argv)
{
digitvector digits;
digits.push_back(new digitblock(1));
size_t power = 0;
size_t border = 1000;
size_t zeros = 1;
while(true)
checkzeros(digits, power, border, zeros++);
}
простенько до одури, но вроде работает
слегка оптимизировал работу с памятью за счёт блоков
результаты пока такие
[00:00:00.000] a(1) = 10, 4 digits total
[00:00:00.000] a(2) = 53, 16 digits total
[00:00:00.000] a(3) = 242, 73 digits total
[00:00:00.000] a(4) = 377, 114 digits total
Reached 1000 power of 2, 302 digits total
[00:00:00.000] a(5) = 1491, 449 digits total
[00:00:00.000] a(6) = 1492, 450 digits total
[00:00:00.062] a(7) = 6801, 2048 digits total
Reached 10000 power of 2, 3011 digits total
[00:00:00.296] a(8) = 14007, 4217 digits total
Reached 100000 power of 2, 30127 digits total
[00:00:15.734] a(9) = 100823, 30375 digits total
[00:08:06.140] a(10) = 559940, 168719 digits total
Found KNumber 0 with power 1
Found KNumber 1 with power 10
Found KNumber 2 with power 61
Found KNumber 3 with power 271
Found KNumber 4 with power 583
power 1000 calculated in 28 ms
Found KNumber 5 with power 1330
Found KNumber 6 with power 1492
power 2000 calculated in 59 ms
power 3000 calculated in 131 ms
power 4000 calculated in 208 ms
power 5000 calculated in 348 ms
power 6000 calculated in 563 ms
Found KNumber 7 with power 6802
power 7000 calculated in 817 ms
power 8000 calculated in 963 ms
power 9000 calculated in 1131 ms
power 10000 calculated in 1315 ms
power 11000 calculated in 1518 ms
power 12000 calculated in 1742 ms
power 13000 calculated in 1983 ms
power 14000 calculated in 2246 ms
Found KNumber 8 with power 14007
power 15000 calculated in 2526 ms
power 16000 calculated in 2830 ms
power 17000 calculated in 3149 ms
power 18000 calculated in 3486 ms
power 19000 calculated in 3849 ms
power 20000 calculated in 4227 ms
power 21000 calculated in 4623 ms
power 22000 calculated in 5100 ms
power 23000 calculated in 5559 ms
power 24000 calculated in 6021 ms
power 25000 calculated in 6494 ms
power 26000 calculated in 6993 ms
power 27000 calculated in 7505 ms
power 28000 calculated in 8284 ms
power 29000 calculated in 8838 ms
power 30000 calculated in 9414 ms
power 31000 calculated in 10021 ms
power 32000 calculated in 10633 ms
power 33000 calculated in 11272 ms
power 34000 calculated in 11919 ms
power 35000 calculated in 12587 ms
power 36000 calculated in 13273 ms
power 37000 calculated in 13982 ms
power 38000 calculated in 14705 ms
power 39000 calculated in 15452 ms
power 40000 calculated in 16214 ms
power 41000 calculated in 17008 ms
исходник (3.5)
using System.Collections.Generic;
using System;
using BytePair = System.Collections.Generic.KeyValuePair<byte, byte>;
using System.Diagnostics;
using System.Threading;
namespace KZero
{
class KNumber
{
public int MaxZeroCount;
public int Power;
public byte[] NumberPairs;
}
class Program
{
private static readonly BytePair[] HexAddition = new BytePair[100 + 100];
private static readonly bool[] HexAdditionExists = new bool[100 + 100];
private static BytePair InitializeHexAdditionValue(byte val1, byte val2)
{
var reminder = (byte)((val1 + val2) % 100);
var primary = (byte)((val1 + val2 - reminder) / 100);
return new BytePair(primary, reminder);
}
private static int GetHexAdditionIndex(byte val1, byte val2)
{
return val1 + val2;
}
private static BytePair GetHexAdditionValue(byte val1, byte val2)
{
var index = GetHexAdditionIndex(val1, val2);
if (HexAdditionExists[index])
return HexAddition[index];
HexAdditionExists[index] = true;
return HexAddition[index] = InitializeHexAdditionValue(val1, val2);
}
private static BytePair TripleAdd(byte val1, byte val2, byte val3)
{
if (val3 == 0)
{
return GetHexAdditionValue(val1, val2);
}
var pair1 = GetHexAdditionValue(val1, val2);
var pair2 = GetHexAdditionValue(pair1.Value, val3);
return new BytePair((byte)(pair1.Key + pair2.Key), pair2.Value);
}
static void Main()
{
const bool PrintOutput = false;
//InitializeHexAddition();var kNumber = new KNumber { MaxZeroCount = 0, Power = 0, NumberPairs = new byte[] { 1 } };
var kNumbers = new Dictionary<int, KNumber>();
var watch = new Stopwatch();
while (true)
{
watch.Start();
kNumber = CalculateNextKNumber(kNumber);
watch.Stop();
if (kNumber.Power % 1000 == 0)
Console.WriteLine(" power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms");
if (PrintOutput)
{
Console.Write("Power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms - ");
var tmp = (byte[])kNumber.NumberPairs.Clone();
Array.Reverse(tmp);
Array.ForEach(tmp, b => Console.Write(b < 10 ? ("0" + b) : b.ToString()));
Console.WriteLine();
Thread.Sleep(100);
}
if (kNumbers.ContainsKey(kNumber.MaxZeroCount))
{
continue;
}
kNumbers[kNumber.MaxZeroCount] = kNumber;
Console.WriteLine("Found KNumber " + kNumber.MaxZeroCount + " with power " + kNumber.Power);
}
}
private static KNumber CalculateNextKNumber(KNumber seed)
{
var nextNumberPairsLength = seed.NumberPairs[seed.NumberPairs.Length - 1] == 0
? seed.NumberPairs.Length
: seed.NumberPairs.Length + 1;
var nextNumberPairs = new byte[nextNumberPairsLength];
var kNumber = new KNumber { Power = seed.Power + 1, MaxZeroCount = 0 };
var append = (byte)0;
var i = 0;
for (; i < seed.NumberPairs.Length; i++)
{
var val = seed.NumberPairs[i];
var pair = TripleAdd(val, val, append);
append = pair.Key;
nextNumberPairs[i] = pair.Value;
}
if (append > 0)
{
nextNumberPairs[i] = append;
}
if (nextNumberPairs[nextNumberPairs.Length - 1] == 0)
{
var tmp = new byte[nextNumberPairs.Length - 1];
Array.Copy(nextNumberPairs, tmp, tmp.Length);
nextNumberPairs = tmp;
}
kNumber.NumberPairs = nextNumberPairs;
CalculateMaxZeroCount(kNumber);
return kNumber;
}
private static void CalculateMaxZeroCount(KNumber kNumber)
{
var currentZeroCount = 0;
for (var i = 0; i < kNumber.NumberPairs.Length; ++i)
{
switch (kNumber.NumberPairs[i])
{
case 0:
currentZeroCount += 2;
break;
case 10:
currentZeroCount += 1;
UpdateKMaxZero(kNumber, currentZeroCount);
break;
case 01:
UpdateKMaxZero(kNumber, currentZeroCount);
if (i != kNumber.NumberPairs.Length - 1)
{
currentZeroCount = 1;
}
break;
default:
UpdateKMaxZero(kNumber, currentZeroCount);
currentZeroCount = 0;
break;
}
}
UpdateKMaxZero(kNumber, currentZeroCount);
}
private static void UpdateKMaxZero(KNumber kNumber, int count)
{
if (count > kNumber.MaxZeroCount)
kNumber.MaxZeroCount = count;
}
}
}
Found KNumber 0 with power 1, Number calculated in 3 ms is: 02
Found KNumber 1 with power 10, Number calculated in 3 ms is: 1024
Found KNumber 2 with power 53, Number calculated in 3 ms is: 9007199254740992
Found KNumber 3 with power 242, Number calculated in 3 ms is: 07067388259113537318333190...
Found KNumber 4 with power 377, Number calculated in 4 ms is: 307828173409331868845930000...
Found KNumber 5 with power 1491, Number calculated in 16 ms is: 068505199434441481928960132734923...
Found KNumber 6 with power 1492, Number calculated in 16 ms is: 1370103988688829638579202654698471015372
Found KNumber 7 with power 6801, Number calculated in 242 ms is: 20183687373087460349606707870495174...
Found KNumber 8 with power 14007, Number calculated in 1023 ms is: 33662724701763990788983568556041...
Found KNumber 9 with power 100823, Number calculated in 55332 ms is: 558795409300670784...
считалось на P4 2.6GHz, 3GB Ram
using System.Collections.Generic;
using System;
using BytePair = System.Collections.Generic.KeyValuePair<byte, byte>;
using System.Diagnostics;
namespace KZero
{
class KNumber
{
public int MaxZeroCount;
public int Power;
public byte[] NumberPairs;
}
class Program
{
#region stuff
private static readonly BytePair[] HexAddition = new BytePair[100 + 100];
private static readonly bool[] HexAdditionExists = new bool[100 + 100];
private static BytePair InitializeHexAdditionValue(byte val1, byte val2)
{
var reminder = (byte)((val1 + val2) % 100);
var primary = (byte)((val1 + val2 - reminder) / 100);
return new BytePair(primary, reminder);
}
private static int GetHexAdditionIndex(byte val1, byte val2)
{
return val1 + val2;
}
private static BytePair GetHexAdditionValue(byte val1, byte val2)
{
var index = GetHexAdditionIndex(val1, val2);
if (HexAdditionExists[index])
return HexAddition[index];
HexAdditionExists[index] = true;
return HexAddition[index] = InitializeHexAdditionValue(val1, val2);
}
private static BytePair TripleAdd(byte val1, byte val2, byte val3)
{
if (val3 == 0)
{
return GetHexAdditionValue(val1, val2);
}
var pair1 = GetHexAdditionValue(val1, val2);
var pair2 = GetHexAdditionValue(pair1.Value, val3);
return new BytePair((byte)(pair1.Key + pair2.Key), pair2.Value);
}
private static void PrintNumber(Stopwatch watch, KNumber kNumber)
{
Console.WriteLine("Found KNumber " + kNumber.MaxZeroCount + " with power " + kNumber.Power);
Console.Write("Number calculated in " + watch.ElapsedMilliseconds + " ms is: ");
var tmp = (byte[])kNumber.NumberPairs.Clone();
Array.Reverse(tmp);
Array.ForEach(tmp, b => Console.Write(b < 10 ? ("0" + b) : b.ToString()));
Console.WriteLine();
}
#endregion stuff
static void Main()
{
var kNumber = new KNumber { MaxZeroCount = 0, Power = 0, NumberPairs = new byte[] { 1 } };
var kNumbers = new Dictionary<int, KNumber>();
var watch = new Stopwatch();
while (true)
{
watch.Start();
kNumber = CalculateNextKNumber(kNumber);
watch.Stop();
if (kNumber.Power % 1000 == 0)
Console.WriteLine(" power " + kNumber.Power + " calculated in " + watch.ElapsedMilliseconds + " ms");
if (kNumbers.ContainsKey(kNumber.MaxZeroCount)) {
continue;
}
kNumbers[kNumber.MaxZeroCount] = kNumber;
PrintNumber(watch, kNumber);
}
}
private static KNumber CalculateNextKNumber(KNumber seed)
{
var nextNumberPairs = new byte[seed.NumberPairs.Length + 1];
var kNumber = new KNumber { Power = seed.Power + 1, MaxZeroCount = 0 };
var append = (byte)0;
var i = 0;
for (; i < seed.NumberPairs.Length; i++)
{
var val = seed.NumberPairs[i];
var pair = TripleAdd(val, val, append);
append = pair.Key;
nextNumberPairs[i] = pair.Value;
}
if (append > 0)
{
nextNumberPairs[i] = append;
}
if (nextNumberPairs[nextNumberPairs.Length - 1] == 0)
{
var tmp = new byte[nextNumberPairs.Length - 1];
Array.Copy(nextNumberPairs, tmp, tmp.Length);
nextNumberPairs = tmp;
}
kNumber.NumberPairs = nextNumberPairs;
CalculateMaxZeroCount(kNumber);
return kNumber;
}
private static void CalculateMaxZeroCount(KNumber kNumber)
{
var currentZeroCount = 0;
for (var i = 0; i < kNumber.NumberPairs.Length; ++i)
{
switch (kNumber.NumberPairs[i])
{
case 0:
currentZeroCount += 2;
break;
case 10:case 20:case 30:case 40:case 50:case 60:case 70:case 80:case 90:
currentZeroCount += 1;
UpdateKMaxZero(kNumber, currentZeroCount);
currentZeroCount = 0;
break;
case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:
UpdateKMaxZero(kNumber, currentZeroCount);
if (i != kNumber.NumberPairs.Length - 1)
{
currentZeroCount = 1;
}
break;
default:
UpdateKMaxZero(kNumber, currentZeroCount);
currentZeroCount = 0;
break;
}
}
UpdateKMaxZero(kNumber, currentZeroCount);
}
private static void UpdateKMaxZero(KNumber kNumber, int count)
{
if (count > kNumber.MaxZeroCount)
kNumber.MaxZeroCount = count;
}
}
}
Здравствуйте, Seon, Вы писали:
S>Здравствуйте, Spiceman, Вы писали:
S>А можно идею алгоритма в кратце, а то не все понятно
Да вобщем-то идея примерно та же, что у Pro100Oleh-а. Представляем число в 10-ричной системе, если ищем 1 ноль, в 100-ричной системе, если ищем 2 ноля, и т.д. Число у меня список (начиная с младших разрядов) — например, 512 = (2 1 5), 1024 = (4 2 0 1), 2^53 = (92 09 74 54 92 19 07 90). В таком списке довольно просто найти k нолей подряд. Это так, если:
1. элемент списка равен 0, либо
2. элемент списка (начиная с единиц, то есть слева) меньше 10^m и следующий элемент кратен 10^m. Например, для 2^53 элемент 07 < 10 и 90 кратно 10. m подбирается минимальным.
S>Все же не очень быстро...
Ну я не спец в лиспе, не знаю библиотек и функций. Написал как смог. Спецы, думаю, оптимизировали бы лучше. Теперь попробую тоже на C#
S>А почему списком?
Так получилось
Здравствуйте, Spiceman, Вы писали:
S>Здравствуйте, Seon, Вы писали:
S>>Здравствуйте, Spiceman, Вы писали:
S>>А можно идею алгоритма в кратце, а то не все понятно S>Да вобщем-то идея примерно та же, что у Pro100Oleh-а. Представляем число в 10-ричной системе, если ищем 1 ноль, в 100-ричной системе, если ищем 2 ноля, и т.д. Число у меня список (начиная с младших разрядов) — например, 512 = (2 1 5), 1024 = (4 2 0 1), 2^53 = (92 09 74 54 92 19 07 90). В таком списке довольно просто найти k нолей подряд. Это так, если: S>1. элемент списка равен 0, либо S>2. элемент списка (начиная с единиц, то есть слева) меньше 10^m и следующий элемент кратен 10^m. Например, для 2^53 элемент 07 < 10 и 90 кратно 10. m подбирается минимальным.
S>>Все же не очень быстро... S>Ну я не спец в лиспе, не знаю библиотек и функций. Написал как смог. Спецы, думаю, оптимизировали бы лучше. Теперь попробую тоже на C#
S>>А почему списком? S>Так получилось
Принципиальный вопрос:
в вашем варианте есть перевод из 2-й в десятичную, или сразу работаете в десятичной?
умножаете 10-тичные числа или 2-ичные?
Здравствуйте, Аноним, Вы писали: А>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k)
А>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля"
Здравствуйте, vadimcher, Вы писали:
V>И где ты в своем доказательстве того, что 16^y-1 делится на 5y использовал, что y нечетное, или что оно является степенью 5? Вот твое доказательство: V>
V>16^y — 1 = (15+1)^y — 1,
V>т.е. получим многочлен в котором y+1 членов, один из которых 1 (мы эту единицу отнимаем),
V>а остальные члены являются степенью 15 (таких членов y). Значит и весь многочлен делится на 5y
Да уж. Действительно. Я перечитал это еще раз и ужаснулся
Вообще я изначально доказывал это высказывание, подсчитывая количество множителей 5 в каждом члене выражения (15+1)^y — 1, где y=5^n. Потом меня "осенило", нашел более простое "доказательство" , ну т.е. то, которое я написал. Но, действительно, это не только ничего не доказывает, но и неверно в принципе. Благо, что ответ оказался все же верен.
Исправляю ошибку. Докажем, что 16^y — 1 делится на 5y, где y = 5^n.
Более простое доказательство на основе теоремы Эйлера (к сожалению, я ее не знал, ээх!).
Теорема Эйлера: a^ф(m) === 1 (mod m), ф - функция Эйлера, a и m взаимно просты
ф имеет следующее свойство: ф(p^n) = (p-1)*p^(n-1), когда p - простое
Доказать, что
16^(5^n) - 1 === 0 (mod 5*5^n))
Преобразовываем
2^(4*5^n) === 1 (mod 5^(n+1))
На основе указанного свойства ф, т.к. 5 - простое:
ф(5^(n+1)) = 4*5^n,
Отсюда:
2^(4*5^n) === 1 (mod 5^(n+1)) ч.т.д.
V>>>Вопрос 1. Доказал ли ты в итоге, что остатки повторяются (это, впрочем, очевидно), и что формулы f() и g() верны? V>Это все понятно. Я тебя про другое, по-моему, спрашивал.
Я все-таки не совсем понял, о чем идет речь.
Что значит верны? Речь об этом?
Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
Количество возможных остатков равно f(k)
Последний неповторяющийся остаток равен g(k)
Здравствуйте, Beam, Вы писали:
B>Исправляю ошибку. Докажем, что 16^y — 1 делится на 5y, где y = 5^n. B>Более простое доказательство на основе теоремы Эйлера (к сожалению, я ее не знал, ээх!).
Да, именно теоремой Эйлера проще всего доказывать. Просто я хотел обратить твое внимание, что утверждение неверно не только для четных y, но и для многих нечетных, как, например, 13.
B>Я все-таки не совсем понял, о чем идет речь. B>Что значит верны? Речь об этом?
B>
B>Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
B>Количество возможных остатков равно f(k)
B>Последний неповторяющийся остаток равен g(k)
B>
B>Это можно доказать.
Да, именно об этом. Просто в итоге ты использовал конкретные выражения для того, чтобы привести пример остатка (g(m)) при делении некоторой большой степени двойки (f(m)-1) на 10^m. Т.е., как я написал до этого, в твоем доказательстве не важно, действительно ли f() и g() выражают то, с чего ты начал. Т.е. для доказательства это не важно. Тем не менее, просто интересно.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, vadimcher, Вы писали: V>>Здравствуйте, Аноним, Вы писали: А>>>Теоретическая часть доказывается сразу. из утверждения, что степень 2 может начинаться на любую наперед заданную последовательность цифр (берем 10^k) А>>>Схема доказательства первого утверждения — 2^n начинается на число x <=> {n*ln 2} (в смысле дробная часть) лежит в неком непустом интервале. собственно, все... всюду плотность доказывается вручную... ну или гуглом по "критерий Вейля" V>>Выделенное не понял.
Выделенное я не понял, потому как оно кажется мне неверным. А автор в ответе писал это так, как будто это очевидно. Мне нет. Потому я переспросил.
А>Ну, как я уже говорил, это вопрос с бородой. Поэтому автор поста написал схематично, опуская детали.
Ну с бородой, или нет -- я не знаю. Это мне напоминает, как когда кто-то что-то постит, и обязательно найдется кто-нибудь: "баян!". Баян (по определению ) -- шутка, которую постоянно все пересказывают, и которая уже всем уши пробаянила, а если кто-то что-то там постил три года назад, то это не баян. Не надо путать "небаянность" и "уникальность" сообщения.
Короче, для меня эта задача новая, а потому просто интересно ее красивое решение. Так, в копилку. Я пока видел здесь два таких. Оба в итоге доказываются с помощью теоремы Эйлера. Просто и красиво! Это же решение также выглядит правильным, за исключением того, что вместо того, чтобы говорить, что тут все очевидно, надо было просто аккуратнее написать, что именно доказывается. Видимо, ты как раз и расписал это ниже. Спасибо.
А>Между прочим, а что имелось в виду А>в условиях задачи: ровно k нулей и на к-ом месте не ноль или имелось в виду как минимум к нулей? Если ровно k нулей, то через теорему Эйлера ответ получить будет тяжело.
Имелось в виду "как минимум", но вторая интерпретация тоже интересная.
А>Теперь расшифрую Анонима. А>Можно доказать более сильное утверждение: для любого натурального числа найдётся степень двойки, которая на него начинается. А>Из этого утверждения всё следует. А>Докажем это более сильное утверждение. А>Пусть какая-то степень двойки начинается на x, тогда для некоторого m выполняется А>x*10^m < 2^n <x*10^m+10^m-1
[] А>Если обозначить очевидно иррациональное число ln(10)/ln(2) через alpha, ln(x) / ln(2) через x1, ln(x+1/10)/ln(2) через А>x2, то получаем А>Найти m и n такие, что А>alpha *m-n лежит в (x1, x2) А>А это можно доказать самому. Например, через теорему Лиувилля о приближении иррационального числа рациональной дробью.
n-ln(10)/ln(2)*m в (ln(x)/ln(2),ln(x+1/10)/ln(2))
Это утверждение совсем не то, что было в том топике. Поэтому это не пояснение к тому, а скорее попытка решить тем же путем.
А вот зайца кому, зайца-выбегайца?!
Re[5]: k нулей
От:
Аноним
Дата:
27.12.08 22:23
Оценка:
Здравствуйте, vadimcher.
После нового года я постараюсь выложить и саму олимпиадную задачу и решение из сборника задач.
Здравствуйте, vadimcher, Вы писали:
V>Да, именно об этом. Просто в итоге ты использовал конкретные выражения для того, чтобы привести пример остатка (g(m)) при делении некоторой большой степени двойки (f(m)-1) на 10^m. Т.е., как я написал до этого, в твоем доказательстве не важно, действительно ли f() и g() выражают то, с чего ты начал. Т.е. для доказательства это не важно. Тем не менее, просто интересно.
B>>
B>>Для любых целых k > 0, целых n>=0, при делении чисел 2^n на 10^k:
B>>Количество возможных остатков равно f(k)
B>>Последний неповторяющийся остаток равен g(k)
B>>
1. Последний неповторяющийся остаток равен g(k) = 5*10^(k-1) + 2^(k-1)
Во-первых остатки повторяются (это очевидно и так).
Во-вторых g(k) действительно является остатком (это мы уже доказали).
Следуюший остаток после него будет 2*(5*10^(k-1) + 2^(k-1)) mod 10^k = 2^k
Минимальное n при котором остаток может быть равен 2^k равно k.
Также очевидно, что g(k) не является остатком при n < k.
Из этого следует, что минимальное n для остатка g(k) больше минимального n для остатка 2^k.
А это говорит о том, что для следующего n список остатков зациклится, а значит g(k) является последним неповторяющимся остатком.
2. Чему равно n, которое приводит к остатку g(k)?
Т.к. g() — остаток от деления 2^n на 10^k можем записать:
x*10^k + 5*10^(k-1) + 2^(k-1) = 2^n
По теореме Эйлера:
a^ф(m) = 1 (mod m)
ф(5^k) = 4*5^(k-1)
Отсюда получаем:
a^(4*5^(k-1)) === 1 (mod 5^k), где a и 5^k взаимно простые
Возвращаясь к нашей степени двойки:
a^(4*5^(k-1)) = 2^(n-k+1)
Логарифмируем по основанию 2:
4*5^(k-1) * log a = n-k+1
Обозначим log a = s, откуда a = 2^s. Заметим также, что s>0 т.к. "a" не может быть 1 (не взаимно простое с 5^k)
n = s*4*5^(k-1) + k — 1, где s >= 1
Это формула n при котором получается остаток g()
3. Количество остатков f(k) = 4*5^(k-1) + k = 100*5^(k-3) + k
Теперь можно определить количество остатков от деления на 10^k
Возьмем минимальное n при котором получается последний неповторяющийся остаток g(k).
Тогда общее количество остатков будет равно n+1 (единицу прибавляем, т.к. степени начинаем считать с нуля)
В нашем случае минимальное n = 4*5^(k-1) + k — 1 (при s = 1)
Откуда f(k) = 4*5^(k-1) + k, ч.т.д.
P.S.Интересно, что остатки, стоящие самыми первыми в списке (т.е. для n < k) никогда не повторяются.
Например существует единственное число 2^n, которое при делении на 100 дает в остатке 2. Это само число 2 ,
т.е. числа вида 2^n никогда не заканчиваются на 02 и т.д.
По одному из вариантов программы (пусть не самый быстрый) на процессоре рейтинга 2000 считается 70 000 000 знаков в секунду.
число а17 — это приблизительно миллиардная степень двойки.
для расчета 2^1 000 000 000 придется обработать (1000000000 ^ 2) / (2 * 3.31) знаков. (3.31 — коэффициент ширины десятичного представления степени двойки)
итого это 151 057 401 812 688 821 знаков.
для их расчета 1-му процессору потребуется 2 157 962 883 секунд
или 599 434 часов
или 24 976 суток
или 68 лет
если на эту задачу бросить 70 процессоров, то потребуется почти год.
явно, что а17 расчитывалось, либо каким то другим способом (не удвоением), либо на каком то жутко мощном майнфрэйме
ну или на огромном количестве компов...
Здравствуйте, Аноним, Вы писали:
А>К сожалению, я так и не нашёл книги с решением задачи с помощью логарифмов.
Да его легко восстановить, вообще-то.
Пусть у нас есть An = 2**n;
Найдём число Q(n, k), представляющее k старших цифр An:
Это будет Q(n, k) = 2**n / 10**q(n), где q(n) = [log10( 2**n )] — k = [n log10( 2 )] — k.
(тут [х] обозначает "целая часть х")
Соотвественно, log10 Q(n, k) = log10( 2**n / 10**q(n) ) = n*log10( 2 ) — q(n) = n*log10( 2 ) + k — [n log10( 2 )]
То есть log10 Q(n, k) = k + { n log10( 2 ) }, где {x} -- это дробная часть x.
Довольно очевидно, что для любого иррационального x последовательность Bn = { n x } всюду плотна на [0, 1] (под "всюду плотна" я имею в виду, что в любой окрестности любой точки отрезка найдётся хотя бы одна точка из Bn)
Но это обозначает, что Q(n, k) принимает все значения на [10**k, 10**(k+1) — 1]...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>Довольно очевидно, что для любого иррационального x последовательность Bn = { n x } всюду плотна на [0, 1] (под "всюду плотна" я имею в виду, что в любой окрестности любой точки отрезка найдётся хотя бы одна точка из Bn)
Если кому не очевидно, то вот док-во:
Рассмотрим наматывание на окружность радиуса 1/(2pi) угла в x радиан. По условию х иррационально, соответственно несоизмеримо с длинной нашей окружности, равной 1.
То есть если мы будем брать углы в Bn радиан, то ни при каких n != m не получится так, что точки Bn и Bm совпадут.
Соотвественно, мы всегда можем поставить на окружности столько разных точек, сколько нам надо.
Рассмотрим теперь диапазон углов длины 2a > 0. (скажем такой: [t0-a, t0+a]). Докажем, что в нём обязательно найдётся одна из точек Bn.
Лема 1. Найдутся два такие k < m, что расстояние от Bk до Bm на окружности будет меньше, чем 2a. Это очевидно, так как если мы возьмём первые [1 / a] + 1 точек, то где-то на окружности должно найтись две точки, на расстоянии меньшем чем 2a... Выберем ту из них, у которой меньший индекс за Bk, а ту, у которой больший за Bm.
Лема 2.
Очевидно, что длинна отрезка [Bn, Bn+k] зависит только от k, просто в силу осевой симметрии окружности
Лема 3.
Можно покрыть всю окружность точками, отстоящими друг от друга менее, чем на 2a.
Тоже очевидно. Берём пару точек из леммы 1, и с таким шагом покрываем постепенно всю окружность с шагом меньшем чем 2a
Ну, а из этого всего следует, что найдётся точка в диапазоне углов [t0-a, t0+a], для любого t0 и любого положительного a...
ЧТД.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, 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 часов на двухядернике.
Лучше делиться не кодом, а идеями, чтобы их можно было в свой код прикручивать.
Здравствуйте, 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>Лучше делиться не кодом, а идеями, чтобы их можно было в свой код прикручивать.
Легко.
Вариант мультиматериночный
Что из себя представляет это число?
Треугольник знаков.
После вычисления каждого блока имеем 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>Сейчас уже приближаюсь к 50 000 000. (а14) S>Расчет ведется одновременно на 8 компах, при чем по моему медленному, и неоптимизированному всякими такими фичами
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 компах пол-года
Ну полгода на 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 зн/сек
Круто!
А каким способом подсчитывается кол-во нулей? 9 делений и 9 if-ов ?
Или это просто вычисление 2-в-нужной-степени?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, 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>А каким способом подсчитывается кол-во нулей? 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)
{
// нашли очередное число нулей
}
Где,
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.
Код становится менее лапшеобразным без потери скорости.
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, Вы писали:
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? И здесь все не так очевидно:
Здравствуйте, 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%
Здравствуйте, Beam, Вы писали:
B>Как? Пусть имеем N с количеством нулей 4, нам надо 8 нулей. Какое число (числа) будут проверены после N, т.е. куда будет осуществлен прыжок (прыжки)?
Все не так.
Мы прыгаем на 100 (к примеру), надо 8, а там 4. Значит среди 91-100 не более 7 нулей. проверяем 90 — там 3 нуля, значит среди 77-90 не более 7 нулей.
И т.д.
Проблема в том, чтобы уметь далеко прыгать, хотя как показывет практика, кол-во умножений практически не зависит от дальности каждого начального прыжка и составляет примерно 6-8% от достигнутой степени. Я пробовал прыгать на 7 — 50 и оптимальным является прыжок на 13
Здравствуйте, 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 в котором встретились два нолика подряд, значит таких чисел будет сколь угодно много.
Ну вот. А чисел в которых встречается только один ноль подряд будет все меньше! И очень скоро таких совсем не станет.
Здравствуйте, 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-какаятоичная система счисления.
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, vadimcher, Вы писали:
N>4-х головый Intel Xeon 1.6GHz, 64 бита, в среднем загрузка CPU 95%, занимает памяти 200 MB:
N>
N> 0 days 00:00:00.000s: 1 : 10 ( 586)
N> 0 days 00:00:00.000s: 2 : 53 ( 586)
N> 0 days 00:00:00.000s: 3 : 242 ( 586)
N> 0 days 00:00:00.000s: 4 : 377 ( 586)
N> 0 days 00:00:00.015s: 5 : 1491 ( 586)
N> 0 days 00:00:00.015s: 6 : 1492 ( 586)
N> 0 days 00:00:00.015s: 7 : 6801 ( 1456)
N> 0 days 00:00:00.015s: 8 : 14007 ( 2266)
N> 0 days 00:00:00.140s: 9 : 100823 ( 10009)
N> 0 days 00:00:03.468s: 10 : 559940 ( 48503)
N> 0 days 00:00:13.875s: 11 : 1148303 ( 94967)
N> 0 days 00:02:47.601s: 12 : 4036338 ( 318504)
N> 0 days 00:02:47.601s: 13 : 4036339 ( 318504)
N> 0 days 08:28:36.830s: 14 : 53619497 ( 4135670)
N> 1 days 18:08:30.187s: 15 : 119476156 ( 9202865)
N> 2 days 14:49:08.222s: 16 : 146226201 ( 11260686)
N>
N>Дальше считать не вижу смысла, 100 дней аптайма анрил...
Вот я не понимаю....
А что? очень тяжело сделать сохранение промежуточных результатов, с возможностью их загрузки и возобновления расчета...
И программу поставить в автозапуск в беловнормале? И хай себе крутится! куда нам спешить то?
Да, можно. Вернее даже нужно (теоретически). Поправлю.
Но, к сожалению, это мало повлияет на результат
Если интересно, вот некоторая укрупненная статистика.
При расчете до степени 4 млн. (т.е. искали до 12 нулей) с помощью прыжков мы прыгали в 95% случаев на шаг от 5 до 7 (на 6 — 44%, на 7 — 35%, на 5 — 17%).
При увеличении искомого количества нулей эти цифры смещаются в большую сторону, но очень медленно, и прыжок на 14 (и более) понадобится нам при поиске a(19), a(20)
Если мы рассмотрим все степени двойки от 0 до 4 млн. (подряд, без прыжков), то процентное отношение количества нулей в них будет такое:
4 нулей — 8%, 5 нулей — 51%, 6 нулей — 33%, 7 нулей — 4%. Т.е. 84% степеней содержат 5-6 нулей, а 95% содержат 4-7 нулей.
Насчет расчета a(18).
Если посмотреть последовательность a(), то можно увидеть, что следующий член может увеличиваться до 10 раз!
Предположим, что так оно и есть, т.е. a(18) = 10^10. В алгоритмах используется приблизительное соотношение 1 байт = 2 десятичные цифры.
Значит нам понадобится 10^10 / 2 = 5 * 10^9 байт памяти для работы с числом.
Далее. Время. У меня в программе вычисляется средняя скорость работы программы. В битах в секунду. Где биты — количество бит в обработанных степенях двойки.
т.е. для 2^n обрабатывается n бит. А для всех чисел от 2^0 до 2^n соответственно n(n+1)/2 бит. Так вот средняя скорость на двухядерниках пока не превышала 50*10^9 бит/сек (обычно 30 млрд. бит / сек). Т.е. для 10^10 * 10^10 / 2 = 10^20 / 2 / 50 / 10^9 = 10^(20 — 2 — 9) = 10^9 секунд. 30 лет.
Хотя конечно для a(18) = 1.5 млрд все не так плохо. 1 Гб памяти + пол-года. Так что попробовать можно
B>Вот и получается, что время умножения на большую степень двойки сравнимо с последовательным умножением несколько раз на маленькую степень двойки (если алгоритм учитывает, что умножение произодится только на маленькую степень). Например, время умножения на 2^22, сравнимо с умножением на 2^13 и затем на 2^9.
Кстати, если я не ошибся и это действительно так, то не все способы распараллеливания между несколькими компьютерами могут работать.
Например, не будет работать метод, в котором один компьютер подсчитывает степени от 0 до 1 млн., второй от 1 до 2 млн. и т.д., т.к. чтобы сообщить второму компьютеру число 2^(1 млн.) надо его сначала посчитать, а значит сдеолать большую часть работы.
Можно, конечно, передавать не само число, а просто степень (например 1 млн), но тогда тот компьютер должен либо опять же посчитать степени от 0 до 1 млн, либо перевести число 2^n в десятичную форму. Насколько мне известно, быстрых алгоритмов для этого не существует. Их сложность O(n^2), т.е. фактически такая же, как и при ручном расчете.
S>Здесь можно существенно убыстрить, если заменить деления чем нибудь более быстрым. условиями например...
Это всего лишь инициализация таблицы
кстати, по моим ощущениям табличное "умножение" проигрывает в скорости двум делениям непосредственно в цикле(/ %)
а вот а if-ов надо стараться избегать...
Здравствуйте, nikholas, Вы писали:
N>Это всего лишь инициализация таблицы
Да, именно так.
N>кстати, по моим ощущениям табличное "умножение" проигрывает в скорости двум делениям непосредственно в цикле(/ %)
Я тоже так думал, но оказалась, что таблицы выигрывают около 20%. Даже по отношению к оптимизированному компилятором коду: он достаточно умен, чтобы определить, что нужен и результат и остаток, поэтому не делает два деления. Во-вторых он это деление заменяет на умножение. Но все равно таблицы быстрее. Хотя может все зависит от кэша и т.п.
N>а вот а if-ов надо стараться избегать...
Это точно.
Здравствуйте, nikholas, Вы писали:
N>Лучше сделать так: по числу x от 0000 до 9999 по таблице получаем zero-mask: на месте нулей — нули, на месте не-нулей — единицы (получаем число от 0 до 15) N>для текущей позиции при подсчете нулей помним: максимальное число нулей найденое ранее (max, 0 — 19), число нулей на конце(curr, 0-19) N>и далее по таблице [max, curr, zero-mask] получаем новые значения для max и curr N>Для того чтоб не заморачиваться насчет конца числа curr может быть больше max, тогда в конце, после любого кол-ва финишных нулей, мы получаем точное значение max(главное в таблице сделать curr(19)->curr(19), а не то...).
Отличная идея!
Мне приходила в голову похожая — я заводил таблицу [0000..9999, cur, max] = {new_cur, new_max}, но это работало долго, из-за большого размера таблицы (20*20*10000 = 4000000 = 4 Мб).
Здесь же получается таблица [0000..9999] = {mask} (10 кБ) и [max, cur, mask] = {new_cur, new_max} (20*20*16*2 = 12,8 кБ). Поэтому должно быть быстрее => внесу изменения.
N>Также лучше совместить подсчет нулей с возведением в степень — кеши и все такое
Это да. Пока что не сделал, т.к. возможна ситуация, что умножать будет нужно, а нули считать нет. Но если такое не понадобится, то объединю.
N>Я особо не мерял но у меня сложилось впечатление что умножение на 3-х разрядное число (с подсчетом нулей) практически не отличается по времени от умножения на одноразрядное. N>И возведение в большую степень работает быстро — я прикидывал, что 2^(10^9) можно получить дней за 7-8
Я мерял, но может что-то упустил из виду. Было бы интересно увидеть твои замеры умножения. Ну хотя бы 1 млн, 5 млн, 10 млн (бех подсчета нулей). Все-таки если умножение идет "столбиком", то я реально не понимаю почему может быть быстрее
Здравствуйте, nikholas, Вы писали:
N>Также лучше совместить подсчет нулей с возведением в степень — кеши и все такое
Здесь надо быть аккуратным. Вариант многопроцессорный, потому, когда сначала все умножается, а потом все подсчитывается заведомо верный, а когда сразу -- вроде бы надо учесть переносы между частями, одданными разным процессорам.
Здравствуйте, vadimcher, Вы писали:
V>Я еще раз просмотрел твой код на предмет поиска нулей, и пришел к выводу, что возможны ошибки при k=2 и k>=5. Стал сравнивать результаты. Выяснилось: ошибки при k=2,3. V>Для k=2, понятно. Два нуля оказались внутри 4-хзначной цифры. (Вероятность этого была достаточно маленькая, но я решил проверить, вдруг ты попал как раз в эту вероятность? Попал!) Так что и по логике, и на практике следует начинать с k=3.
Да верно. Я просто об этом не упомянул. Для 1 и 2 это может не работать.
И это было бы ерундой, если бы не ...
V>Для k=3 у меня выдал 243 вместо 242. Почему? Непонятно. Я этого не ожидал.
Я тоже не ожидал Это реальный баг.
При подсчете он попадает на 240. Считает нули. На самом деле их там максимум 2, но также есть и по одному.
Но! Они все попадают в середину четырехзначных цифр А значит не учитываются. В итого думаем что количество нулей = 0, прыгаем на 3-0, т.е. на 3 => 240 + 3 = 243
В приниципе, такое может повториться и на других числах, хотя вероятность этого очень низкая, к тому же снижается при увеличении длины числа.
V>Для k>=5. Когда один процессор обработал блок, он смотрит, какое там число стоит дальше, cur += zerosTable[ arr[index+1] ].right. Но что, если там стоит 0000, тогда надо двигать дальше, пока не встретится наконец ненулевое число! Т.е. надо что-то типа int j = 1, z; do { z = zerosTable[ arr[index+j] ].right; cur += z; } while (z == 4);
Все таки не до конца я разрулил потоки
V>Тут проблема не только в том, что можно пропустить искомое число нулей, но и в том, что иногда шаг, с которым ты прыгаешь к следующему числу может оказаться больше, чем положено.
Да. Маловероятно, но верно => исправлю. Спасибо
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, vadimcher, Вы писали:
N>4-х головый Intel Xeon 1.6GHz, 64 бита, в среднем загрузка CPU 95%, занимает памяти 200 MB:
N>
N> 0 days 00:00:00.000s: 1 : 10 ( 586)
N> 0 days 00:00:00.000s: 2 : 53 ( 586)
N> 0 days 00:00:00.000s: 3 : 242 ( 586)
N> 0 days 00:00:00.000s: 4 : 377 ( 586)
N> 0 days 00:00:00.015s: 5 : 1491 ( 586)
N> 0 days 00:00:00.015s: 6 : 1492 ( 586)
N> 0 days 00:00:00.015s: 7 : 6801 ( 1456)
N> 0 days 00:00:00.015s: 8 : 14007 ( 2266)
N> 0 days 00:00:00.140s: 9 : 100823 ( 10009)
N> 0 days 00:00:03.468s: 10 : 559940 ( 48503)
N> 0 days 00:00:13.875s: 11 : 1148303 ( 94967)
N> 0 days 00:02:47.601s: 12 : 4036338 ( 318504)
N> 0 days 00:02:47.601s: 13 : 4036339 ( 318504)
N> 0 days 08:28:36.830s: 14 : 53619497 ( 4135670)
N> 1 days 18:08:30.187s: 15 : 119476156 ( 9202865)
N> 2 days 14:49:08.222s: 16 : 146226201 ( 11260686)
N>
У меня тоже посчиталось a(16).
a(14) = 53'619'497 ===> 10 час 16 мин (21% медленнее)
a(15) = 119'476'156 ===> 2 дня 00 час 36 мин (15% медленнее)
a(16) = 146'226'201 ===> 2 дня 22 час 38 мин (12% медленнее)
В принципе, результаты по времени сравнимы с предыдущим полученным a(16). Хотя и получилось немного медленнее, необходимо учитывать разницу в количестве ядер и частоте.
Т.к. архитектуры у процессоров вроде одинаковые (Core), то можно сравнивать по частоте:
4-х головый Intel Xeon 1.6GHz ~~ 1.6 * 4 = 6.4 ГГц
2-я ядерный Intel Core 2 Duo 2.67 GHz ~~ 2.67 * 2 = 5.3 ГГц
Т.е. программа на 2-ядернике должна быть на 17% медленнее. Как видно, ситуация даже лучше (15%, 12%), т.е. имеется незначительное улучшение. Но это в теории, как будет в реальности на 4-ядернике — неизвестно
N>Дальше считать не вижу смысла, 100 дней аптайма анрил...
Дальше считать действительно нет смысла. Если уж и счтать то начиная с 1 млрд., чтобы искать a(18), а так... какой смысл.
Но a(18) один компьютер будет рассчитывать от 0 до 30 лет. Чтобы максимум уменьшить хотя бы до 1 года, надо 30 компьютеров. Сомневаюсь, что на RSDN найдется столько желающих.
Тем более, мне так и не понятна эффективная схема распределения работы между компьютерами по сети.
P.S. В общем, пока я для себя эту тему закрываю. Пока не придумается какая-нибудь эвристика (из области математики) для вычислений... Интересная задачка, однако.
Здравствуйте, Beam, Вы писали:
B>P.S. В общем, пока я для себя эту тему закрываю. Пока не придумается какая-нибудь эвристика (из области математики) для вычислений... Интересная задачка, однако.
Я не знаю, подправил ты код или нет (там было две проблемы -- число нулей между соседними процессами и поиск двух нулей, в принципе, два нуля можно и не искать, а для того, чтобы шаг не был слишком большим, просто считать, что если найденное максимальное число нулей подряд в числе меньше 2, то считать, что оно равно 2 -- это не должно никак повлиять на быстродействие, но исключит возможность перепрыгнуть через искомое число). Но я не об этом. Есть ли у тебя какая статистика по тому, сколько времени тратится на умножение, а сколько -- на поиск нулей?
Здравствуйте, vadimcher, Вы писали:
V>Я не знаю, подправил ты код или нет (там было две проблемы -- число нулей между соседними процессами и поиск двух нулей, в принципе, два нуля можно и не искать, а для того, чтобы шаг не был слишком большим, просто считать, что если найденное максимальное число нулей подряд в числе меньше 2, то считать, что оно равно 2 -- это не должно никак повлиять на быстродействие, но исключит возможность перепрыгнуть через искомое число).
Код я поправил. Позже причешу и выложу сюда. Может кто продолжит.
V>Но я не об этом. Есть ли у тебя какая статистика по тому, сколько времени тратится на умножение, а сколько -- на поиск нулей?
Соотношение (Умножение:Поиск) очень близко к (2:1)
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, Beam, Вы писали:
N>По поводу подсчета нулей:
N>Лучше сделать так: по числу x от 0000 до 9999 по таблице получаем zero-mask: на месте нулей — нули, на месте не-нулей — единицы (получаем число от 0 до 15) N>для текущей позиции при подсчете нулей помним: максимальное число нулей найденое ранее (max, 0 — 19), число нулей на конце(curr, 0-19) N>и далее по таблице [max, curr, zero-mask] получаем новые значения для max и curr N>Для того чтоб не заморачиваться насчет конца числа curr может быть больше max, тогда в конце, после любого кол-ва финишных нулей, мы получаем точное значение max(главное в таблице сделать curr(19)->curr(19), а не то...).
Попробовал я такой вариант. Работает медленнее, почему — не знаю.
Перекуём баги на фичи!
)
