Небольшая проблема с математикой

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Коллеги, пользующиеся своим мозгом более, чем я (средний уровень - 3%), помогите понять вычислительную проблему... Отчего нижеприведённый код всегда даёт значение переменной y, делящееся нацело на 7?

Может я лопухнулся где с типами переменных?


void setup() {
  long h, l, x, y;

  Serial.begin(115200);

  x = analogRead(A0);
  
  h = x / 127773L;
  l = x % 127773L;
  y = 16807L * l - 2836L * h;
  Serial.print("x: "); Serial.println(x);
  Serial.print("y: "); Serial.println(y);
  Serial.print("y % 7L: "); Serial.println(y % 7L);
}

void loop() {}

 

b707
Онлайн
Зарегистрирован: 26.05.2017

sadman41 пишет:

Отчего нижеприведённый код всегда даёт значение переменной y, делящееся нацело на 7?

потому что математика

Давать ответ сразу или подождать других?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Потому что H всегда равно 0, L - всегда равно X, а Y всегда равно 16807*X. 16807 делится на 7 (2401), а значит и Y-ку деваться некуда.

Это что за тест такой был?

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

b707 пишет:

Давать ответ сразу или подождать других?

Вот, умный человек!

А я, похоже, вляпался. Это ж явно неспроста был вопрос :(

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Че пятница уже с утра ? :)

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Ну, типа, выходной же завтра.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Господа, не могу пока привести оригинал кода (с мобильника пишу). Но ЕвгенийП прав - вопрос был задан не просто так и проистекает из взаимоотношений честного и нечестного Си. 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Ну, я же говорил - подвох како-то. Попал :(

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

Ну, если честный Си честно детектирует делимость на 7, то, вполне вероятно, от нечестного Си можно ожидать всего, что угодно. Тогда теоретически разница может иметь место.

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

А я вопрос не понял...

16807 легко делится на 7 и не один раз подряд, ибо это пятая степень семерки, даже если из нее вычесть 0. 

h - очевидно равно 0 ибо X никогда не будет больше 1024.

В чем подвох? Получается ровно то что должно получиться.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Ждём пояснений. Для чего-то же он это запостил.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Итак...

Берём нечестный random() из Wiring:

long randNumber;

void setup() {
  Serial.begin(9600);

  // if analog input pin 0 is unconnected, random analog
  // noise will cause the call to randomSeed() to generate
  // different seed numbers each time the sketch runs.
  // randomSeed() will then shuffle the random function.
  randomSeed(analogRead(0));
}

void loop() {
  // print a random number from 0 to 299
  randNumber = random(300);
  Serial.println(randNumber);

  // print a random number from 10 to 19
  randNumber = random(10, 20);
  Serial.println(randNumber);

  delay(50);
}

Вместо 300 ставим 7 и получаем каждый запуск первым значением 0 вне зависимости от seed. Задаёмся вопросом - какого лешего....

Лезем в Arduino\hardware\arduino\avr\cores\arduino\WMath.cpp:

long random(long howbig){
  if (howbig == 0) {
    return 0;
  }
  return random() % howbig;
}


void randomSeed(unsigned long seed) {
  if (seed != 0) {
    srandom(seed);
  }
}

Никаких нулей. Продолжаем погружение. avr-lib ->stdlib -> random.c

static unsigned long next = 1;

void srandom(unsigned long seed) {
	next = seed;
}

long random(void) {
	return do_random(&next);
}


static long do_random(unsigned long *ctx) {
	/*
	 * Compute x = (7^5 * x) mod (2^31 - 1)
	 * wihout overflowing 31 bits:
	 *      (2^31 - 1) = 127773 * (7^5) + 2836
	 * From "Random number generators: good ones are hard to find",
	 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
	 * October 1988, p. 1195.
	 */
	long hi, lo, x;

	x = *ctx;
	/* Can't be initialized with 0, so use another value. */
	if (x == 0)
		x = 123459876L;
	hi = x / 127773L;
	lo = x % 127773L;
	x = 16807L * lo - 2836L * hi;
	if (x < 0)
		x += 0x7fffffffL;
	return ((*ctx = x) % ((unsigned long)RANDOM_MAX + 1));
}

А дальше вы и сами знаете...

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Я не очень понял кто придумал пхать в 32 разрядную переменную, для старта рандома, по сути девятиразрядную. Это не си лживый, это кто то другой .... 

Может лучше что то типа (analogRead(0)*1024+analogRead(1))*1024+analogRead(2) ?

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Может и лучше, однако https://www.arduino.cc/reference/en/language/functions/random-numbers/random/ / https://www.arduino.cc/reference/en/language/functions/random-numbers/ra... нам показывает именно такой способ посева.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

sadman41 пишет:
родолжаем погружение. avr-lib ->stdlib -> random.c
Так это уже уровень "честного". 

sadman41
Онлайн
Зарегистрирован: 19.10.2016

ЕвгенийП пишет:

sadman41 пишет:
родолжаем погружение. avr-lib ->stdlib -> random.c
Так это уже уровень "честного". 

Да. Сидишь вот так и думаешь, что нечестный тебя подставил, а выходит, что вовсе нет.

Я вчера ещё прошёлся немного по мануалам и не нашёл рекомендаций или каких-либо ограничений по выбору seed. Да и само дефолтовое значение какбэ намекает, что однобитовое число тоже подходит для такого. 

Нельзя, конечно, сказать, что данный случай - трагедия, однако странные ситуации породить может. Мне вот для отладки надо было получить random(7), наложить на массив структур, в котором дни недели были... И я был очень поражён тем, что каждый раз первым выпадал "понедельник".

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

sadman41 пишет:

... И я был очень поражён тем, что каждый раз первым выпадал "понедельник".

За мутными глазницами HP
ты в непорочности своей как рак-отшельник.
И всё не то и, все вокруг не те и,
каждый день как будто ПОНЕДЕЛЬНИК...???

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Спасибо, будем знать. Чтобы по граблям поменьше топтаться.

wdrakula
wdrakula аватар
Offline
Зарегистрирован: 15.03.2016

вообще тема известная. про первое значение, после посева. самый простой лайфхак - брать второе. а ещё круче сделать случайное число шагов... ну, например, пока random(16) < 12.
ведь уже второе, после посева, вполне себе энтропийное...

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

На ардуине есть millis() и почему не брать случайные значения с него. Но нет ходить по граблями это как по-людски.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Все сомнений, что первооткрывателем я не стал и люди, имеющие практический опыт, давно уже всё это знают. Тем не менее представляется странным, что в пример применения функций random*() суют такой код, который порождает больше вопросов, нежели ответов. Я же не сразу стал постить на форум вопрос, побыстрогуглил на тему данной "проблемы" и ничего мне в глаза не бросилось.

Вчера у меня не было времени размышлять об этом, но с утра я снова посмотрел на формулу и понял, что такой же эффект будет проявляться у random(N), где N - делитель числа 16807.

А вот тут уже проблемы не наблюдается, хотя по исходникам rand() и random() близки.

#include <stdlib.h>
void setup() {
  Serial.begin(115200);
  srand(analogRead(A0));
  long randNumber = rand() % 7;
  Serial.println(randNumber);
}

void loop() {}

Смотрим avr-lib -> stdlib -> rand.c

static int do_rand(unsigned long *ctx) {
#ifdef  USE_WEAK_SEEDING
	/*
	 * Historic implementation compatibility.
	 * The random sequences do not vary much with the seed,
	 * even with overflowing.
	 */
	return ((*ctx = *ctx * 1103515245L + 12345L) %
		((unsigned long)RAND_MAX + 1));
#else   /* !USE_WEAK_SEEDING */
	/*
	 * Compute x = (7^5 * x) mod (2^31 - 1)
	 * wihout overflowing 31 bits:
	 *      (2^31 - 1) = 127773 * (7^5) + 2836
	 * From "Random number generators: good ones are hard to find",
	 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
	 * October 1988, p. 1195.
	 */
	long hi, lo, x;

	x = *ctx;
	/* Can't be initialized with 0, so use another value. */
	if (x == 0)
		x = 123459876L;
	hi = x / 127773L;
	lo = x % 127773L;
	x = 16807L * lo - 2836L * hi;
	if (x < 0)
		x += 0x7fffffffL;
	return ((*ctx = x) % ((unsigned long)RAND_MAX + 1));
#endif  /* !USE_WEAK_SEEDING */
}

Где объявляется USE_WEAK_SEEDING я не нашёл. 

Нагуглил "цитату из интернета" (R):

«Многие генераторы случайных чисел, используемые сегодня, работают не слишком хорошо. Разработчики обычно стараются не вникать, как устроены такие подпрограммы. И часто бывает так, что какой-то старый, неудовлетворительно работающий метод раз за разом слепо перенимается многими программистами, которые зачастую просто не знают о присущих ему недостатках»

Дональд Кнут, «Искусство программирования», том 2.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

qwone пишет:

На ардуине есть millis() и почему не брать случайные значения с него. Но нет ходить по граблями это как по-людски.

С каких пор millis() стал рандомным? Да ещё с его склонностью к пьян... переполнению.

Green
Онлайн
Зарегистрирован: 01.10.2015

Не миллис случаен, а момент его считывания. Например, время когда вы нажмёте на гашетку. Это ж очевидно.)

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

sadman41 пишет:

Нагуглил "цитату из интернета" (R):

«Многие генераторы случайных чисел, используемые сегодня, работают не слишком хорошо. Разработчики обычно стараются не вникать, как устроены такие подпрограммы. И часто бывает так, что какой-то старый, неудовлетворительно работающий метод раз за разом слепо перенимается многими программистами, которые зачастую просто не знают о присущих ему недостатках»

Дональд Кнут, «Искусство программирования», том 2.

Ну, у Кнута вся глава 3 (около 200 страниц) полностью посвящена исключительно генерации псевдослучайной последовательности.

Т.е. это совершенно отдельная и достаточно сложная тема. Вряд ли ее стоит даже начинать обсуждать, не прочитав эти 200 страниц. 

А после прочтения, вполне вероятно, что темы для обсуждения уже не обнаружится.

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Не хочу говорить грубо, но у Вас проблема не только с рандомом, но и теорией вероятности.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Green пишет:

Не миллис случаен, а момент его считывания. Например, время когда вы нажмёте на гашетку. Это ж очевидно.)

Я согласен с тем, что он может выдавать "рандомные" значения, если кто-то внешний жмёт на гашетку. Однако не вижу никакого смысла в том, чтобы опираться на него для получения случайных чисел в системе, которая выполняет свои инструкции с тем же тактом, что и тикает millis(). 

Надеюсь, что qwone не хочет сказать, что в нижеприведённом коде millis() каждый раз будет выдавать различные значения?

void setup() {
  Serial.begin(115200);
  srand(analogRead(A0));
  long randNumber = rand() % 7;
  Serial.println(randNumber);
  Serial.println(millis());
}

 

sadman41
Онлайн
Зарегистрирован: 19.10.2016

andriano пишет:

Т.е. это совершенно отдельная и достаточно сложная тема. Вряд ли ее стоит даже начинать обсуждать, не прочитав эти 200 страниц. 

А после прочтения, вполне вероятно, что темы для обсуждения уже не обнаружится.

Цитату я привёл только для того, чтобы подвердить её - randomSeed(analogRead(0)); таскается из кода в код...

А насчёт второго... даже и не знаю, что лучше - прочитать и необсуждать или непрочитывать и получить немного общения на форуме хоббистов ))

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

sadman41 пишет:

Надеюсь, что qwone не хочет сказать, что в нижеприведённом коде millis() каждый раз будет выдавать различные значения?

Вот теперь Вы напоминаете новичка, который сует delay() и жалуется почему у него не работает скетч. А когда предлагают использовать вместо него millis(), то просто поменяв delay() на millis() не получил желаемого. Вы это перестаньте "включать новичка".

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Qwone, я предлагаю вам спорить не со мной, а с мантайнерами Wiring (а то и avr-lib). Спросите у них - на кой там random(), если есть прекрасный millis(). 

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Вот зачем мне спорить с ними. Я не хочу поступать как Архат или подобные им. У меня есть нормальный рецепт и я им пользуюсь. А у других есть их важность своего мнения, вот пусть они и получают последствия важности их мнения, включая и мантайнерами Wiring.

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Вот и отлично. Надеюсь, что Вы и со мной не будете спорить насчёт внутреннего устройства служебной функции random() языка C и о необходимости включения библиотеку stdlib функции millis(), которая позволит всем неверующим узреть свет Истины о правильной генерации ряда случайных чисел. А то напридумали тут алгоритмов, математики недобитые. Соловки по ним плачут.

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

если кто-то делает что-то плохо, значить кому-то это выгодно.

Но это не значить, что лично Вы должны это жрать.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

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

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

sadman41 пишет:

andriano пишет:

Т.е. это совершенно отдельная и достаточно сложная тема. Вряд ли ее стоит даже начинать обсуждать, не прочитав эти 200 страниц. 

А после прочтения, вполне вероятно, что темы для обсуждения уже не обнаружится.

Цитату я привёл только для того, чтобы подвердить её - randomSeed(analogRead(0)); таскается из кода в код...

А насчёт второго... даже и не знаю, что лучше - прочитать и необсуждать или непрочитывать и получить немного общения на форуме хоббистов ))

Если не учитывать полутонов, то на форум можно писать по одной из двух причин:

- хочется получить информацию,

- хочтся пообщаться.

В первом приближении для первого существуют тематические разделы, для второго - "Отвлеченные темы".

Я ни в коей мере не отрицаю важности общения "хоббистов" между собой, но место размещения темы IMHO вступает в противоречие с ее содержанием.

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

DetSimen,похоже и вам надо освежить теорию верояности. Проблема не в случайности появления, а равновероятности , которое у всех генераторов псевдослучайных чисел страдает. А о жестком детерменировании получения случайного числа, так не делайте его жестким. Или Вы в программировании новичек.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

qwone пишет:

у всех генераторов псевдослучайных чисел страдает.

А у millis(), надо понимать, не страдает?

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

ЕвгенийП пишет:
А у millis(), надо понимать, не страдает?

Разумеется . Ведь millis() проходит все значения от 0 до переполнения. Конечно ждать 48 дней не надо. Чет/нечет меняется очень быстро и ждать не надо долго. Так что он уже равновероятен.

byte kubik=millis()%6;//<- чем вам не кубик
А если ван нужен первичный посев так можно и так
unsigned long past=/*некоторое смещение*/;
byte rendomNum=(millis()-past)/%6;//<- удивительно как все просто
Для быстро меняющих можно micros() подтянуть

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Ну-ка ну-ка, вот с этого места

qwone пишет:

unsigned long past=/*некоторое смещение*/;

можно поподробнее. Что Вы туда всунете? Уж не любимый ли analogRead()? :)

А вообще, Вы бы это практически сделали и посчитали распределение. Узнали бы, что в действительности, оно всё совсем не так, как на самом деле :)

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Можно цифровой автомат всунуть или лямбда-функцию...

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

qwone пишет:

ЕвгенийП пишет:
А у millis(), надо понимать, не страдает?

Разумеется . Ведь millis() проходит все значения от 0 до переполнения. Конечно ждать 48 дней не надо. Чет/нечет меняется очень быстро и ждать не надо долго. Так что он уже равновероятен.

byte kubik=millis()%6;//<- чем вам не кубик
А если ван нужен первичный посев так можно и так
unsigned long past=/*некоторое смещение*/;
byte rendomNum=(millis()-past)/%6;//<- удивительно как все просто
Для быстро меняющих можно micros() подтянуть

 

void setup() {
  Serial.begin(115200);
  Serial.println("MyRandoM: ");
}

void loop() {
  static long i = 0;
  if(i < 100) {
   Serial.println(millis());
  }
  if(i < 1000)i++;
}
MyRandoM: 
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
6
7
7
7
7
8
8
8
8
9
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23

 

sadman41
Онлайн
Зарегистрирован: 19.10.2016

andriano пишет:

Если не учитывать полутонов, то на форум можно писать по одной из двух причин:

- хочется получить информацию,

...

Я ни в коей мере не отрицаю важности общения "хоббистов" между собой, но место размещения темы IMHO вступает в противоречие с ее содержанием.

Тогда это уже не форум, а справочная получится. Пришёл, запрос в окошко сунул, оттудова женщина ответила или справку с печатью дала и всё, уходить извольте.

Начиналось-то всё именно с программной проблемы связанной с внутренней реализацией рандомайза. Это потом уже пошло-поехало...

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

sadman41 пишет:

Можно цифровой автомат всунуть или лямбда-функцию...

Это да. А то вон andriano попробовал без лямда-функции, так чё попало получилось :(

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

sadman41 пишет:

Начиналось-то всё именно с программной проблемы связанной с внутренней реализацией рандомайза. Это потом уже пошло-поехало...

Нет, упоминание о random появились значительно позже. 

И как только оно появилось, тема перестала быть специфичной для раздела "Программирование".

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

ЕвгенийП пишет:
можно поподробнее. Что Вы туда всунете? Уж не любимый ли analogRead()? :)
А включит сообразительность. Вы вроде Метр на форуме, или же только сантиМетр.

unsigned long past;
void setup(){
past=/*прочитать с Ерома*/;
byte rendom(){
byte rendomNum=(millis()-past)/%6;
unsigned long num=/*прочитать с Ерома*/;
/*записать с Ером*/=num+millis();
return rendomNum;
}

И ваши волосы будут шелковисты каждый день. А при каждом новом включении платы всегда будут по настоящему случайные числа.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

qwone пишет:
А включит сообразительность

Было б - включил бы, а то нечего включать :(

Как раз из-за отсутствия сообразительности, предпочитаю скучные и нудные формулы.

qwone пишет:
или же только сантиМетр.

Мне больше "нано" нравится. За него по нынешним временам платють больше.

qwone пишет:

byte rendomNum=(millis()-past)/%6;

И ваши волосы будут шелковисты каждый день.

И как у Вас это получается? Я аж завидую! У меня такая хрень вообще не компилируется - аж лысина вспотела. А у Вас как-то ещё и волосы шелковятся :)

qwone пишет:
по настоящему случайные числа

Настоящих случайных чисел в таких алгоритмах не бывает в принципе (это по формулам - по сообразительности не знаю, Вам виднее). А распределение Вы всё ж посчитайте. Много интересного узнаете :)))

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

qwone пишет:

 Или Вы в программировании новичек.

В таком - да. 

Ворота
Ворота аватар
Offline
Зарегистрирован: 10.01.2016

Ой, да тут пятница!

— Ну, — сказала Сова, — обычная процедура в таких случаях нижеследующая…
— Что значит Бычья Цедура? — сказал Пух. — Ты не забывай, что у меня в голове опилки и длинные слова меня только огорчают. 
— Ну, это означает то, что надо сделать. 
— Пока она означает это, я не возражаю, — смиренно сказал Пух. 
 
(Алан А. Милн «Винни-Пух и все-все-все», перевод: Борис Заходер)
 
sadman41
Онлайн
Зарегистрирован: 19.10.2016

Что же делать системам без EEPROM - просить пользователя на бумажке записывать последнее число, а потом вводить его при необходимости? Прямо какой-то сериал Lost.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

sadman41 пишет:

просить пользователя на бумажке записывать

Так и это и есть "обычная процедура в таких случаях" :)

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

sadman41 пишет:

Что же делать системам без EEPROM - просить пользователя на бумажке записывать последнее число, а потом вводить его при необходимости? Прямо какой-то сериал Lost.

Да блин, что вы за системы программируете. Еще скажите что, там нет millis(). Да хоть в дополнительной памяти для часов реального времени. Или их тоже нет.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

У Интела я как-то пытался использовать младшый байт RDTSC для "псевдослучайности" да быстро бросил, хоть он и был примерно на 3 порядка "случайнее"  millis().