Здравствуйте, 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 дней аптайма анрил...
Вот я не понимаю....
А что? очень тяжело сделать сохранение промежуточных результатов, с возможностью их загрузки и возобновления расчета...
И программу поставить в автозапуск в беловнормале? И хай себе крутится! куда нам спешить то?
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
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);
Да, можно. Вернее даже нужно (теоретически). Поправлю.
Но, к сожалению, это мало повлияет на результат
Если интересно, вот некоторая укрупненная статистика.
При расчете до степени 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), т.е. фактически такая же, как и при ручном расчете.
Лучше сделать так: по числу 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
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>Также лучше совместить подсчет нулей с возведением в степень — кеши и все такое
Здесь надо быть аккуратным. Вариант многопроцессорный, потому, когда сначала все умножается, а потом все подсчитывается заведомо верный, а когда сразу -- вроде бы надо учесть переносы между частями, одданными разным процессорам.
Здравствуйте, 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>Я еще раз просмотрел твой код на предмет поиска нулей, и пришел к выводу, что возможны ошибки при 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), а не то...).
Попробовал я такой вариант. Работает медленнее, почему — не знаю.
И хай себе крутится! куда нам спешить то? 
