Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283

Как распараллелить определение является ли число степенью двойки

25.12.2018, 11:22. Показов 1809. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Все числа большие, целые и положительные.

C++
1
2
3
4
5
6
7
8
9
10
    bool BigInt::isPowerOfTwo(const BigInt &x)
    {
        if (x.a[0] & 1 == 1) // если число не чётное - до свидания
            return false;
 
        BigInt v = x; v.sign = positive;
        while ((  (v.a[0] & 1) == 0) && v > 1) /* делим v на 2 пока оно чётное и > 1 */
            v /= (unsigned int)2;
        return (v == 1);
    }
Теоретически, всё работает. Уже несколько часов. Причём трудится только одно ядро процессора.
Остальные 7 ядер нагло увиливают от работы.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.12.2018, 11:22
Ответы с готовыми решениями:

Как на стадии компиляции проверить что число является степенью двойки
Очень простой вопрос - как на стадии компиляции проверить что число является степенью двойки? Как проверить на стадии исполнения знаю, но...

Является ли число степенью двойки
Условие: Входные данные Входной файл INPUT.TXT содержит единственное целое число N, не превосходящее 10000 по абсолютной величине. ...

Является ли число степенью двойки
не понимаю в чём ошибка вроде все условия соблюдены. есть чисел вида 2K, где K – некоторое неотрицательное целое число. Назовем такие...

20
Параллельный Кот
 Аватар для valen10
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
25.12.2018, 12:06
Все верно: один поток - одно ядро. Чтобы занять больше ядер, необходимо тем или иным способом создать больше потоков. Для начала неплохо бы придумать, как такую проверку разделить на части. Вы уже придумали, как это сделать?

Если отвлечься от ядер, и представить, что мы поручили эту задачу группе из 8 человек. Сейчас один человек занимается делением, остальным делать нечего. Если бы этот BigInt разбить на части... Не уверен, что это возможно, поскольку вы о нем ничего не рассказали.

Допустим, нам известно, что число кодируется последовательностью байт (слов, двойных слов и т.д.), и каждый такой элемент использует все биты для кодирования (один элемент - одна цифра в системе счисленияhttps://www.cyberforum.ru/cgi-bin/latex.cgi?2^n, где n - количество битов), тогда k таких элементов с их порядковыми номерами можно раздать нескольким людям, чтобы они убедились в том, что элементы с номерами 1, 2, k-1 это нули, а элемент с номером k - степень двойки.

Если же BigInt нельзя так разделить (нет доступа или цифры кодируются в двоично-десятичном коде), то и распараллелить скорее всего не получится.

Добавлено через 6 минут
И еще вопрос: неужели числа настолько большие, что задачу необходимо расараллеливать? Синхронизация потоков - занятие дорогое с точки зрения времени. Возможно, оптимальнее будет изменить алгоритм проверки описанным выше способом, но для одного потока. Это в 8 раз уменьшит количество проверок для k-1 элементов .
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 12:45  [ТС]
Цитата Сообщение от valen10 Посмотреть сообщение
Для начала неплохо бы придумать, как такую проверку разделить на части. Вы уже придумали, как это сделать?
Так я и говорю, что не знаю, как поделить вычисления на части. Скорее всего лучше сколько ядер, столько и частей.
Само-то кодирование дело простое.

Цитата Сообщение от valen10 Посмотреть сообщение
Если же BigInt нельзя так разделить
Разделить BigInt на части можно. Это обыкновенный вектор-int. Правда, непонятно, что Вы предложили.
Из битовых операций, быстро проверить можно только нулевой и старший бит.

Для одного потока я уже всё перепробовал. Разница - 3 копейки.
В том числе и преобразование числа из 10-ной в двоичную(так и не дождался).

Цитата Сообщение от valen10 Посмотреть сообщение
И еще вопрос: неужели числа настолько большие, что задачу необходимо расараллеливать?
Тут вроде бы нашли 49-е число Мерсена. Вот я и захотел проверить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
D:\aProjects\TestBigInt\x64\Release>TestBigInt.exe -isPrime "2^82589933-1"
 
 Generating number 2^82589933-1
 big integer :  1488944 ... 217902591
 number of decimal digits = 24862048
 number of segments       = 2762450
 time : 94.483 sec.
 
 --- Primality test ---
 
 Trial division
 Создаём список простых чисел меньших 1000000
 Пробуем поделить кандидата на 78498 простых чисел.
 
 The divisor is not found. Perhaps this is a prime number.
 time : 1194.41 sec.
 
 Checking, is the candidate "Mersenn number" ?
 Проверяем, является ли кандидат числом Мерсена.
Вот на этом всё и остановилось. С вечера поставил, а к утру так ничего и не посчиталось.
То есть до тестов Lucas-Lemher и Miller-Rabin дело так и не дошло.
0
Параллельный Кот
 Аватар для valen10
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
25.12.2018, 13:31
SerVal, ну вот смотрите, обычный 32-битный int в памяти хранится как 4 байта, при этом все биты задействованы. Число является степенью двойки, если в битах это 1 и хвост из нулей. Чтобы в этом убедиться, нет необходимости двигать все число, достаточно посмотреть, что младшие байты это нули (уже по одной проверке на байт вместо 8 сдвигов), а старший байт сдвинуть и убедиться, что осталась 1.

Ваш BigInt это аналог обычного int, но с большИм количеством байт, или в нем каждый int это десятичная цифра? Все зависит от того, как оно реализовано.

Добавлено через 5 минут
Иными словами, что хранится в этом x.a[], цифры или бинарные части целого?

Добавлено через 6 минут
SerVal, подождите, числа Мерсенна? Тогда не могу понять, что вы делаете. Они же по формуле https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n - 1 вычисляются.
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 13:50  [ТС]
Цитата Сообщение от valen10 Посмотреть сообщение
что хранится в этом x.a[], цифры или бинарные части целого?
Там десятичные числа. a[] - это вектор из десятичных цифр.

Цитата Сообщение от valen10 Посмотреть сообщение
Они же по формуле вычисляются
Не все числа вида 2^n - 1 являются простыми(числами Мерсена). Поэтому, надо проверить на простоту.
0
Параллельный Кот
 Аватар для valen10
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
25.12.2018, 14:01
SerVal, понял. Тогда здесь узкое место это деление на 2. Если от него избавиться, то проверить степень 2 можно будет быстро и одним потоком. Вот деление на простые числа можно и распараллелить...но это потом.

BigInt это ваша собственная реализация? Если так, то предлагаю над ней поработать. Есть возможность избавиться от десятичных цифр, т.к. процессор с ними работает в разы дольше.
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 14:16  [ТС]
Цитата Сообщение от valen10 Посмотреть сообщение
деление на простые числа можно и распараллелить...
Деление на простые числа я уже распараллелил.
Цитата Сообщение от valen10 Посмотреть сообщение
BigInt это ваша собственная реализация?
Ну да.
Цитата Сообщение от valen10 Посмотреть сообщение
Есть возможность избавиться от десятичных цифр
Ну да. Можно хранить в битах. Тогда нужен вектор - в каждом элементе вектора - один бит.
Или в каждом элементе вектора - одна десятичная цифра. Тоже пробовал. Никакой памяти не хватит.
Ладно, надо подумать.. может чего и придумается.
0
Параллельный Кот
 Аватар для valen10
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
25.12.2018, 14:31
SerVal, вектор из битов еще хуже. Можно в unsigned int хранить сразу 32 бита и работать с ними как с одной цифрой по модулю https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{32}. Сейчас у вас длинная арифметика, полагаю, сделана по модулю 10? Если перейти к модулю степени 2, то и само число будет храниться в бинарном, а не десятичном виде.

Если нужно, могу показать на примере.

Добавлено через 7 минут
Вот, почитайте о других вариантах хранения длинного целого: emaxx::Длинная арифметика. Только там приводится пример для https://www.cyberforum.ru/cgi-bin/latex.cgi?10^{9}, я же вам предлагаю https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{32}.
1
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
25.12.2018, 14:40
Ни разу не математик, но может логарифмы как-нибудь прикрутить?
log10(N)=log2(N)/log2(10)
Десятичный логарифм примерно можно оценить по количеству цифр в десятичной записи числа. Таким образом можно быстро оценить нужную степень двойки. Для возведения в степень, вроде, есть более шустрые алгоритмы. Можно получить некое начальное число, дальше его умножать на 2 и сравнивать с имеющимся.
0
 Аватар для COKPOWEHEU
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
25.12.2018, 14:50
Стандартная проверка на степень двойки
(x & (x-1)) == 0
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 15:23  [ТС]
Цитата Сообщение от valen10 Посмотреть сообщение
Сейчас у вас длинная арифметика, полагаю, сделана по модулю 10?
Нет, у меня по модулю 10^9

C++
1
2
3
4
5
6
7
8
9
10
static const unsigned long long BASE = 1000000000;
static const unsigned int BASE_DIGITS = 9;
 
struct BigInt {
 
public:
    std::vector<int> a;
    int sign;
...
}
Я не понимаю, в чём преимущества базы 2^32. Если число будет храниться в бинарном, а не десятичном виде.
разве размер вектора не вырастет?

Добавлено через 9 минут
Цитата Сообщение от Ygg Посмотреть сообщение
Можно получить некое начальное число, дальше его умножать на 2 и сравнивать с имеющимся.
Это я тоже пробовал. Поначалу всё шустренько(пока начальное число маленькое) . А потом начальное число = 2 растёт и всё замедляется ещё больше, чем при делении кандидата на двойку.
Цитата Сообщение от Ygg Посмотреть сообщение
Ни разу не математик, но может логарифмы как-нибудь прикрутить?
log10(N)=log2(N)/log2(10)
Вообще-то вычисление логарифма и сводится к умножению/делению на двойку.
И никакого выигрыша нетути. К тому же, при вычислении логарифмов всегда есть погрешность, которая где-нибудь да вылезет.

Добавлено через 12 минут
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Стандартная проверка на степень двойки
(x & (x-1)) == 0
Это хорошо и правильно, если "&" выполняется аппаратно. А реализация "побитового И" для больших чисел требует программного доступа ко всем битам числа. То есть нужна функция GetBit(number, bit_number). И пройтись по всем битам 2-х чисел.
0
 Аватар для COKPOWEHEU
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
25.12.2018, 16:00
Цитата Сообщение от SerVal Посмотреть сообщение
Я не понимаю, в чём преимущества базы 2^32. Если число будет храниться в бинарном, а не десятичном виде.
разве размер вектора не вырастет?
Нет, уменьшится.
Да и код упростится, за исключением ввода-вывода.
Цитата Сообщение от SerVal Посмотреть сообщение
Это хорошо и правильно, если "&" выполняется аппаратно.
В случае длинных чисел с "круглым" основанием оно и будет выполняться аппаратно.
0
Параллельный Кот
 Аватар для valen10
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
25.12.2018, 16:12
Цитата Сообщение от SerVal Посмотреть сообщение
Если число будет храниться в бинарном, а не десятичном виде. разве размер вектора не вырастет?
Проблема не в размере вектора, а в сложности проверки, является ли число степенью 2. Пока у вас число записано в десятичном виде, вы не можете разбить его на части и каждую часть проверить независимо. Преимущество бинарного кода здесь в том, что любая степень двойки будет записана в виде XX 00 ... 00. Например, если основание https://www.cyberforum.ru/cgi-bin/latex.cgi?2^8, то: https://www.cyberforum.ru/cgi-bin/latex.cgi?1048576_{10} = (00010000\:00000000\:00000000)_{2} = (10\:00\:00)_{16}, и проверять придется только старший байт на степень двойки, а остальные на равенство нулю.

Сложность такой проверки https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n), где n - длина числа (если использовать основание https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{32}, то длина в 4 раза меньше, чем если https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{8}), и никаких сложных действий, только быстрые сравнения. Вариант с делением же даст https://www.cyberforum.ru/cgi-bin/latex.cgi?O(m \cdot n), m - количество двоичных чисел (степень 2), n - количество десятичных цифр, да еще и операция деления выполняется в разы медленнее.

Так, для M_{82589933} бинарный вариант требует меньше сравнений, чем цифр в этом числе (а их там 24 862 048). Выполнится менее чем за секунду. Для варианта с делением же это будет порядка https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 10^{14}сложных операций. Интереса ради измерил у себя (частота процессора 4.0GHz - 4.5GHz) время https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 10^{11} делений обычного целого на 2, получилось около 101 сек. Для https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 10^{14}это время грозится вырасти до 101000 сек или около 28 часов, что несколько многовато.
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 16:39  [ТС]
Цитата Сообщение от valen10 Посмотреть сообщение
Проблема не в размере вектора, а в сложности проверки, является ли число степенью 2.
Ребятки, я теоретически не против поменять базу. Но как бы не получилось так, что проблема степени двойки решится(это частный случай), а всё остальные базовые операции замедлятся - сложение, вычитание, умножение и деление.
Сейчас умножение сделано при помощи FFT и Карацубы. Деление - методом Нюьтона. Есть ввод вывод из файла в двоичном, десятичном, шестнадцатеричном формате... итд.

Где-нибудь можно взглянуть на длинную арифметику с базой 2^32 ?
Я ведь не такой умный, чтобы самому всё придумать и переделать.
0
 Аватар для COKPOWEHEU
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
25.12.2018, 16:49
Цитата Сообщение от SerVal Посмотреть сообщение
Но как бы не получилось так, что проблема степени двойки решится(это частный случай), а всё остальные базовые операции замедлятся - сложение, вычитание, умножение и деление.
А как выдумаете, как устроены обычные операции сложения и прочего для многобайтных чисел? Точно так же: сложение 0-х (младших) байтов; сложение 1-х (следующих) байтов с учетом переноса; сложение 2-х (еще следующих) байтов с учетом переноса и так далее.
То есть как и с прочими вычислениями: чем ближе представление к машинному, тем проще.
0
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
25.12.2018, 17:35
Цитата Сообщение от SerVal Посмотреть сообщение
А потом начальное число = 2 растёт и всё замедляется ещё больше, чем при делении кандидата на двойку.
Может мы не понимаем друг друга: wiki. Неужели время циклов #1 или #2 будет соизмеримо с временем цикла #3?
C++
1
2
3
4
5
6
7
8
9
10
BigInt v = 2;
// #1
for (int i=0; i<1023; i++)
  v*=2;
// #2
for (int i=0; i<1023; i++)
  v/=2;
// #3
for (int i=0; i<10; i++)
  v*=v;
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 18:13  [ТС]
Ygg, цикл #3 тут вообще не причём.

C++
1
2
3
4
5
6
7
8
9
10
11
    BigInt candidate = "2^82589933";
    BigInt v = 2;
    while (v <= candidate)
    {
        v *= (unsigned int)2;
    }
 
    if (v == candidate)
        std::cout << "Number is power of two." << std::endl;
    else    
        std::cout << "Number is NOT power of two." << std::endl;
Вот здесь происходит умножение всё большего и большего числа v на двойку.
Плюс, сравнение candidatа со всё большим и большим числом v.
Поэтому, сначала всё шустро, а потом - всё медленнее и медленнее.
А в #2 мы каждый раз уменьшаем делимое-candidate в два раза. Вот и получается быстрее.
0
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
25.12.2018, 19:02
Именно, что причём. Последняя попытка
1) Определяете примерно десятичный логарифм вашего числа. В первом приближении, можно считать его равным количеству десятичный цифр в числе минус один. Или можно его вычислить по формуле:
LG10N = log10(<старший элемент вектора>) + 9*(<количество элементов в векторе> - 1).
2) Определяете примерно двоичный логарифм вашего числа по формуле:
LG2N = LG10N/log10(2)
3) Используя быстрый алгоритм возведения в степень возводите 2 в посчитанную степень:
P=2^LG2N
4.1) В цикле умножаете P на 2, пока число не станет равно или больше N.
4.2) Или в цикле делите N на 2, пока число не станет равно или меньше P.
0
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
25.12.2018, 20:47  [ТС]
Ygg, так нахождение логарифма числа ничем не отличается от поиска, является ли число степенью двойки или десятки.

Вот нахождение log2 и log10. Всё так же в циклах делением ищем экспоненту(result):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    const int  BigInt::log2(const BigInt &A) {
        BigInt v = A;
        int result = 0;
        while (v > 1) {
            result++;
            v /= (unsigned int)2;
        }
        return result;
    }
 
    const int  BigInt::log10(const BigInt &A) {
        BigInt v = A;
        int result = 0;
        while (v > (unsigned int)1) {
            result++;
            v /= (unsigned int)10;
        }
        return result;
    }
Почему всё должно ускорится?
0
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
25.12.2018, 22:22
Потому что мы считаем не циклом, а по формулам.
Пусть у нас есть число 2'147'483'648 (2^31).
Если ничего не путаю, то оно запишется в BigInt как две ячейки. Старшая ячейка 2, младшая 147'483'648.
https://www.cyberforum.ru/cgi-bin/latex.cgi?LG10N\approx \log_{10} 2 + 9\approx 9,3... ()
https://www.cyberforum.ru/cgi-bin/latex.cgi?LG2N\approx \frac{LG10N}{\log_{10} 2}\approx \frac{9,3...}{0,3...}\approx 30,9...
Округляем до меньшего целого, до 30.
Считаем 2^30.
Циклом сравниваем результат с нашим числом и умножаем на 2.
Следующая же итерация даёт ответ.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.12.2018, 22:22
Помогаю со студенческими работами здесь

Является ли число степенью двойки
Дано натуральное число n. Определите, является ли оно степенью числа 2, и выведете слово YES если является,и выведите слово NO если не...

Является ли число степенью двойки?
Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе.

Проверить, является ли число степенью двойки
Если число степень 2, то ДА, иначе НЕТ. #include &lt;fstream&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int main()...

Определить, является ли число степенью двойки
Такая проблема: в проге мне нужно задать количество чисел которые я введу (т.е создать массив под них), потом ввести числа и оно должно мне...

Определить является ли число степенью двойки
Стоит задача Ввести число. Определить является ли оно степенью 2 (число 16 является, а 22 нет)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru