Телеграмм чат группы proalgorithms страница 3898

parrot.ru

Рейтинг популярных групп и каналов

В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1896 membersпожаловаться на группу

2021 March 30

DP

Defragmented Panda in pro.algorithms

Anatoly Tomilov

вызывая rand7 я генерирую a = log2(7) бит. Мне надо b = log2(10). Можно ли придумать какой-то "аккумулятор" acc, который бы комбинировал эти a бит с очередной порцией a бит, пока сумма не превысит b бит, а затем можно было бы извлечь b бит и floating-point "счётчик количества бит в аккумуляторе" уменьшить на b? Т.е. вообще без rejection обойтись?

экстракторы энтропии

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

источник

16:24пожаловаться #1

DP

Defragmented Panda in pro.algorithms

это моя фантазия на тему https://en.wikipedia.org/wiki/Middle-square_method

Middle-square method

pseudorandom number generator

источник

16:25пожаловаться #2

DP

Defragmented Panda in pro.algorithms

а это если делать по-хорошему https://en.wikipedia.org/wiki/Randomness_extractor

Randomness extractor

A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.

источник

16:26пожаловаться #3

DP

Defragmented Panda in pro.algorithms

Anatoly Tomilov

почему для этой задачи заходит такое решение?

class Solution {
public:
    int rand10() {
        for (int i = 0; i < 9; ++i) {
            acc += rand7() - 1;
        }
        int result = acc % 10;
        acc /= 10;
        return result + 1;
    }
private:
    int acc = rand7();
};

разве у меня остаток от деления суммы десяти U([0;6]) на 10 не будет распределён неравномерно?

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

тут будет 8 сложений 0...6

в среднем около 21, с очень острым пиком около 21

источник

16:30пожаловаться #4

DP

Defragmented Panda in pro.algorithms

источник

16:33пожаловаться #5

DP

Defragmented Panda in pro.algorithms

возможно они подобрали условия когда перекрытие правой и левой части дает почти равномерное распределение
т.е пик около области 19 20 21 22 23

остатки от %10 там
9 0 1 2 3

но края этой области покрывают те же числа второй раз
11 12 13 14 15 16 17 18 19 20 21
(слева от пика)
с перевесом около 9

справа от пика ситуация обратная. я не уверен что это все выравнивает. но возможно

источник

16:35пожаловаться #6

DP

Defragmented Panda in pro.algorithms

Defragmented Panda

вертикаль - шанс этой суммы
горизонталь - значение в результате sum8(rand 0-6)

источник

16:36пожаловаться #7

DP

Defragmented Panda in pro.algorithms

источник

16:39пожаловаться #8

DP

Defragmented Panda in pro.algorithms

вот. это самое важное - форма распределения от сложения случайных независимых.

чем больше слагаемых - тем уже (относительно) пик. но шире в абсолютных единицах.

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

источник

16:41пожаловаться #9

AT

Anatoly Tomilov in pro.algorithms

Defragmented Panda

экстракторы энтропии

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

class Solution {
public:
    int rand10() {
        for (;;) {
            while (h < 10) {
                h *= 7;
                i *= rand7(); // in {1, 2, ..., 7}
            }
            int a = (h / 10) * 10;
            if (i <= a) {
                int result = (i - 1) % 10 + 1;
                i = (i - 1) / 10 + 1;
                h /= 10;
                return result;
            } else {
                i -= a;
                h -= a;
            }
        }
    }
private:
    int h = 1;
    int i = 1;
};

это тоже не заходит. Я здесь ту часть "случайности", которая не использована, сохраняю до следующего вызова. Сгенерированные 100000 rand10 действительно распределены неравномерно. Не могу понять в чём моя ошибка. Нельзя использовать неиспользованные разряды из предыдущей попытки? h здесь — объём гиперкуба, а i — индекс целой точки (распределённой равномерно (кмк)) в нём.

источник

23:29пожаловаться #10

2021 March 31

@N

@urandon Nikita Khom... in pro.algorithms

Kotomord_λapki

как-то предобсчитать, чтобы каждый запрос на логарифм потом

Сканлайн

источник

00:04пожаловаться #11

K

Kotomord_λapki in pro.algorithms

@urandon Nikita Khomutov

Сканлайн

О, это оффлайн посчитать можно?

источник

00:04пожаловаться #12

K

Kotomord_λapki in pro.algorithms

Сразу много таких запросов

источник

00:04пожаловаться #13

K

Kotomord_λapki in pro.algorithms

Круть

источник

00:04пожаловаться #14

@N

@urandon Nikita Khom... in pro.algorithms

Kotomord_λapki

О, это оффлайн посчитать можно?

Конечно, индекс оффлайн можно считать. Если ещё и на персистентных красно-черных деревьях, то можно гарантию на n log n иметь

источник

00:05пожаловаться #15

K

Kotomord_λapki in pro.algorithms

Так, можно будет потом в личку поспрашивать?

источник

00:05пожаловаться #16

@N

@urandon Nikita Khom... in pro.algorithms

Поспрашивай, правда не факт, что буду доступен

источник

00:06пожаловаться #17

АJ

Артём Jin in pro.algorithms

https://stepik.org/course/Быстрый-старт-в-спортивное-программирование-64454/ ребят, кто проходил, знает, что скажете по поводу курсов, стоит прорешивать?

Stepik: online education

Быстрый старт в спортивное программирование

Курс поможет войти в мир спортивного программирования. Рассматриваются базовые теоретические и практические аспекты, необходимые для успешного участия в состязании по спортивному программированию любого уровня: от базовых линейных алгоритмов до основ теории графов и их обходов. Также рассматриваются вопросы асимптотического анализа и оценки эффективности программы.

источник

00:15пожаловаться #18

АJ

Артём Jin in pro.algorithms

Не бейте за рекламу).

источник

00:16пожаловаться #19

DP

Defragmented Panda in pro.algorithms

Anatoly Tomilov

class Solution {
public:
    int rand10() {
        for (;;) {
            while (h < 10) {
                h *= 7;
                i *= rand7(); // in {1, 2, ..., 7}
            }
            int a = (h / 10) * 10;
            if (i <= a) {
                int result = (i - 1) % 10 + 1;
                i = (i - 1) / 10 + 1;
                h /= 10;
                return result;
            } else {
                i -= a;
                h -= a;
            }
        }
    }
private:
    int h = 1;
    int i = 1;
};

это тоже не заходит. Я здесь ту часть "случайности", которая не использована, сохраняю до следующего вызова. Сгенерированные 100000 rand10 действительно распределены неравномерно. Не могу понять в чём моя ошибка. Нельзя использовать неиспользованные разряды из предыдущей попытки? h здесь — объём гиперкуба, а i — индекс целой точки (распределённой равномерно (кмк)) в нём.

сгенерируй 7 чисел d7

запиши подряд их

сгенерируй восьмое d7 и вставь b000 биты в позицию указанную в этом числе, получив 8 значений 0-7 с идеальным распределением и не теряя ни бита случайности

хочешь меньше предсказуемости о частоте встречаемости b000? используй группы 7*7 чисел d7 или еще больше, 7^n, добавив 2 или n b000

источник

01:05пожаловаться #20