|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||||||
Как распараллелить определение является ли число степенью двойки25.12.2018, 11:22. Показов 1809. Ответов 20
Метки нет (Все метки)
Все числа большие, целые и положительные.
Остальные 7 ядер нагло увиливают от работы.
0
|
||||||
| 25.12.2018, 11:22 | |
|
Ответы с готовыми решениями:
20
Является ли число степенью двойки
|
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
|
| 25.12.2018, 12:06 | |
|
Все верно: один поток - одно ядро. Чтобы занять больше ядер, необходимо тем или иным способом создать больше потоков. Для начала неплохо бы придумать, как такую проверку разделить на части. Вы уже придумали, как это сделать?
Если отвлечься от ядер, и представить, что мы поручили эту задачу группе из 8 человек. Сейчас один человек занимается делением, остальным делать нечего. Если бы этот BigInt разбить на части... Не уверен, что это возможно, поскольку вы о нем ничего не рассказали. Допустим, нам известно, что число кодируется последовательностью байт (слов, двойных слов и т.д.), и каждый такой элемент использует все биты для кодирования (один элемент - одна цифра в системе счисления Если же BigInt нельзя так разделить (нет доступа или цифры кодируются в двоично-десятичном коде), то и распараллелить скорее всего не получится. Добавлено через 6 минут И еще вопрос: неужели числа настолько большие, что задачу необходимо расараллеливать? Синхронизация потоков - занятие дорогое с точки зрения времени. Возможно, оптимальнее будет изменить алгоритм проверки описанным выше способом, но для одного потока. Это в 8 раз уменьшит количество проверок для k-1 элементов .
0
|
|
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
|||||||||
| 25.12.2018, 12:45 [ТС] | |||||||||
|
Само-то кодирование дело простое. Из битовых операций, быстро проверить можно только нулевой и старший бит. Для одного потока я уже всё перепробовал. Разница - 3 копейки. ![]() В том числе и преобразование числа из 10-ной в двоичную(так и не дождался).
То есть до тестов Lucas-Lemher и Miller-Rabin дело так и не дошло.
0
|
|||||||||
|
Параллельный Кот
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, подождите, числа Мерсенна? Тогда не могу понять, что вы делаете. Они же по формуле
0
|
|
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
|||
| 25.12.2018, 13:50 [ТС] | |||
|
0
|
|||
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
|
| 25.12.2018, 14:01 | |
|
SerVal, понял. Тогда здесь узкое место это деление на 2. Если от него избавиться, то проверить степень 2 можно будет быстро и одним потоком. Вот деление на простые числа можно и распараллелить...но это потом.
BigInt это ваша собственная реализация? Если так, то предлагаю над ней поработать. Есть возможность избавиться от десятичных цифр, т.к. процессор с ними работает в разы дольше.
0
|
|
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||||
| 25.12.2018, 14:16 [ТС] | ||||
|
Или в каждом элементе вектора - одна десятичная цифра. Тоже пробовал. Никакой памяти не хватит. Ладно, надо подумать.. может чего и придумается.
0
|
||||
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
|
| 25.12.2018, 14:31 | |
|
SerVal, вектор из битов еще хуже. Можно в unsigned int хранить сразу 32 бита и работать с ними как с одной цифрой по модулю
Если нужно, могу показать на примере. Добавлено через 7 минут Вот, почитайте о других вариантах хранения длинного целого: emaxx::Длинная арифметика. Только там приводится пример для
1
|
|
|
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
|
|
| 25.12.2018, 14:40 | |
|
Ни разу не математик, но может логарифмы как-нибудь прикрутить?
log10(N)=log2(N)/log2(10) Десятичный логарифм примерно можно оценить по количеству цифр в десятичной записи числа. Таким образом можно быстро оценить нужную степень двойки. Для возведения в степень, вроде, есть более шустрые алгоритмы. Можно получить некое начальное число, дальше его умножать на 2 и сравнивать с имеющимся.
0
|
|
|
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
|
|
| 25.12.2018, 14:50 | |
|
Стандартная проверка на степень двойки
(x & (x-1)) == 0
0
|
|
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||||||||||
| 25.12.2018, 15:23 [ТС] | ||||||||||
разве размер вектора не вырастет? Добавлено через 9 минут И никакого выигрыша нетути. К тому же, при вычислении логарифмов всегда есть погрешность, которая где-нибудь да вылезет. Добавлено через 12 минут
0
|
||||||||||
|
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
|
|||
| 25.12.2018, 16:00 | |||
|
Да и код упростится, за исключением ввода-вывода.
0
|
|||
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
||
| 25.12.2018, 16:12 | ||
|
Сложность такой проверки Так, для M_{82589933} бинарный вариант требует меньше сравнений, чем цифр в этом числе (а их там 24 862 048). Выполнится менее чем за секунду. Для варианта с делением же это будет порядка
0
|
||
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||
| 25.12.2018, 16:39 [ТС] | ||
|
Сейчас умножение сделано при помощи FFT и Карацубы. Деление - методом Нюьтона. Есть ввод вывод из файла в двоичном, десятичном, шестнадцатеричном формате... итд. Где-нибудь можно взглянуть на длинную арифметику с базой 2^32 ? Я ведь не такой умный, чтобы самому всё придумать и переделать.
0
|
||
|
4083 / 2681 / 432
Регистрация: 09.09.2017
Сообщений: 11,910
|
||
| 25.12.2018, 16:49 | ||
|
То есть как и с прочими вычислениями: чем ближе представление к машинному, тем проще.
0
|
||
|
2734 / 888 / 331
Регистрация: 10.02.2018
Сообщений: 2,099
|
|||||||
| 25.12.2018, 17:35 | |||||||
0
|
|||||||
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||||||
| 25.12.2018, 18:13 [ТС] | ||||||
|
Ygg, цикл #3 тут вообще не причём.
Плюс, сравнение 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
|
|
|
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
|
||||||
| 25.12.2018, 20:47 [ТС] | ||||||
|
Ygg, так нахождение логарифма числа ничем не отличается от поиска, является ли число степенью двойки или десятки.
Вот нахождение log2 и log10. Всё так же в циклах делением ищем экспоненту(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. Округляем до меньшего целого, до 30. Считаем 2^30. Циклом сравниваем результат с нашим числом и умножаем на 2. Следующая же итерация даёт ответ.
0
|
|
| 25.12.2018, 22: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 полиномов. . .
|