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

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

25.12.2018, 11:22. Показов 1931. Ответов 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
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
26.12.2018, 09:54  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Ygg Посмотреть сообщение
Если ничего не путаю, то оно запишется в BigInt как две ячейки. Старшая ячейка 2, младшая 147'483'648.
Да.

С Вашим числом 2147483648 получилось.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    BigInt A = 2147483648L;
    A.printInfo();
 
    double LG10N = log10(2) + 9;
    double LG2N = LG10N / log10(2);
    unsigned long exp = round(LG2N);
    BigInt result = BigInt::pow2(exp);
 
    while (result < A)
    {
        result *= (unsigned int)2;
    }
 
    if (result == A) std::cout << "Number is power of two."     << std::endl;
    else             std::cout << "Number is NOT power of two." << std::endl;
Результат:
C++
1
2
3
4
5
D:\aProjects\TestBigInt\x64\Release>TestBigInt.exe
 big integer :  2147483648
 number of decimal digits = 10
 number of segments       = 2
Number is power of two.
Правда, непонятно, откуда взялась девятка. И что вместо неё должно быть для большого числа.
*число цифр и сегментов в BigInt вычисляются мгновенно.

Добавлено через 10 часов 49 минут
Вроде бы получилось. Вот окончательный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LG10N = log10(<старший элемент вектора>) + 9*(<количество элементов в векторе> - 1).
 
bool    isPowerOfTwo(const BigInt &A)
{
    if (A.a[0] & 1 == 1) return false; // не чётное число
 
    unsigned int high_element_value = A.a[A.a.size() - 1];
 
    double LG10N = std::log10(high_element_value) + 9 * (A.a.size() - 1);
 
    double LG2N = LG10N / std::log10(2);
    unsigned long exp = round(LG2N);
    BigInt result = BigInt::pow2(exp);
 
    while (result < A)
    {
        result *= (unsigned int)2;
    }
 
    if (result == A) return true;
    return false;
}
Всем откликнувшимся ОГРОМНОЕ спасибо. Правда, надо будет написать какой-нибудь тестик для проверки isPowerOfTwo.
А пока поставил проверять недавно найденное новое число Мерсена.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 : 95.208 sec.
 
 --- Primality test ---
 
 Trial division
 Создаём список простых чисел меньших 1000000
 Пробуем поделить кандидата на 78498 простых чисел.
 
 The divisor is not found. Perhaps this is a prime number.
 time : 1231.71 sec.
 
 Checking, is the candidate "Mersenn number" ?
 Проверяем, является ли кандидат числом Мерсена.
 time : 95.209 sec.
 
 The number is Mersenn number, starting Lucas-Lemher test.
 Lucas-Lehmer primality test.
Работает уже 10 часов на Core Quad 9650. Похоже Lucas-Lehmer тест тоже надо подрихтовать.
Или добавить какой-нибудь индикатор прогресса.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.12.2018, 09:54
Помогаю со студенческими работами здесь

Является ли число степенью двойки
Дано натуральное число 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 нет)


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

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
Модель здравосохранения 17. Планы на выгорание
anaschu 23.05.2026
Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона
russiannick 23.05.2026
Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .
Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой
anaschu 23.05.2026
Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .
Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15
anaschu 23.05.2026
Внезапно хорошее здоровье сотрудников не нужно капиталистам?))
Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул
anaschu 23.05.2026
Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .
Диалоги с ИИ
zorxor 23.05.2026
Насколько я понимаю - Вы - Искусственный Интеллект. Это так? Да, всё верно. Я — искусственный интеллект. Я представляю собой большую языковую модель, созданную для помощи в самых разных задачах. . . .
Модель здравосохранения 14. Собираем всю модель вместе.
anaschu 22.05.2026
Модель собрана. В будущих постах на видео я покажу, как она работает. В этом посте запускаем её, проверяем результаты и разбираем что можно с ней делать дальше. Перед запуском проверяем. . .
Модель здравоохранения 13. Добавление самой системы здравоохранения.
anaschu 22.05.2026
В предыдущем посте мы настроили болезни. Теперь добавим события, которые управляют здоровьем всего коллектива, а также настроим рабочий график и расчёт финансов. В Main создаём четыре события. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru