eu_tomat
-
Публикации
2 666 -
Зарегистрирован
-
Посещение
-
Победитель дней
331
Сообщения, опубликованные пользователем eu_tomat
-
-
16 минут назад, whiskas сказал:(Но квант и гравик бы запретил ибо это тупо бесмертие)
А кому мешает бессмертие?
-
1
-
1
-
-
Идея избавиться от всех длинных цепочек вычислений оказалась верной. Моя модификация расширенного алгоритма Евклида выдаёт два целочисленных коэффициента (слегка модифицированные коэффициенты Безу), и для получения результата остаётся лишь разделить длинный интервал на целое число. Дополнительная погрешность возникает только при однократной операции деления вещественного числа на целочисленное.
Итог: благодаря поиску минимального интервала через НОД удалось достичь заметного ускорения вычислений. Теперь результат часто находится за три сканирования, и очень редко требуется больше 10 сканирований.
А ещё я не уверен, можно ли применять термин НОД применительно к вещественным числам. С другой стороны, последовательность целых чисел с единичным шагом является частным случаем математической прогрессии, которая может иметь произвольный шаг. Вот, и вся разница по идее-то. Есть у нас на форуме кто-то хорошо владеющий математической терминологией? Как правильно называть то, что я назвал наибольшим общим делителем?
-
7 минут назад, hohserg сказал:Если есть n вариантов сканирования(при n>3) такие, что для них всех существует единственный общий делитель, то этот делитель является расстоянием между соседними шумами
Да, именно так, находим минимальное расстояние через НОД. И уже это, найденное через НОД расстояние считаем за минимальное, и проверяем соотношение максимальной разницы уже с ним. Максимум разницы я пока продолжаю искать традиционным способом. Я не уверен, что там уместны подобные трюки, и пока не занимался этим.
Сейчас я пытаюсь решить другую проблему. Поиск НОД хорошо работает только для целых чисел, а константа шума не обязана быть целым числом. Пока я считал в scalc, где есть хорошая точность вычислений, всё было просто, понятно и наглядно, даже для константы шума с тысячным долями. А в Lua поиск НОД для вещественного числа пока что выдаёт нестабильные результаты. Сейчас я заменил алгоритм Евклида на его расширенную версию, доработав с целью минимизации накопления погрешности. Пришлось увеличить количество операций в коде, чтобы уменьшить количество операций в отдельно взятой цепочке вычислений. То есть, длинные цепочки каждый раз пересчитываются заново с использованием сокращённой записи. Погрешности пока ещё велики, но и не все вычисления я успел привести к оптимальному виду.
Буду рад любым идеям, как прикрутить поиск НОД применительно к расстояниям между случайными значениями математической прогрессии вещественных чисел.
-
2 минуты назад, hohserg сказал:Т.е. это не деление? 280-10>128?
В данном случае это как раз-таки деление. Я не давал подробных пояснений именно к этой задаче, надеясь на то, что внимательно читавшие методику и сопровождающей её код, и так все поймут.
В 25.04.2020 в 19:27, eu_tomat сказал:В общем виде алгоритм сводится к циклическому получению очередного значения от геосканера и поиску разницы между всеми найденными значениями. И если соотношение максимальной разницы к минимальной превысит 128, то результат достигнут: минимальная разница между найденными значениями обязана быть равной разнице между смежными значениями в полной таблице. Результатом умножения минимальной разницы на 128*33 будет искомая нами константа geolyzerNoise из файла конфигурации.
Следом за этим абзацем идёт код, реализующий описанный алгоритм.
Если моё описание методики в чём-то непонятно, то критикуйте, пожалуйста. Например, я мог опустить очевидные для себя вещи, где-то совершив слишком резкий логический переход. А для читателей это может быть и вовсе неочевидным. Просто спросите, а почему из того следует это. Я дам свой ответ, а позже внесу правки в описание. Или не внесу, чтобы не раздувать описание.
Но вернёмся к задачкам. Описанный алгоритм был для меня актуальным в момент написания методики. Теперь его надо расширить, чтоб решать менее очевидные случаи, не требуя от геосканера новых данных.
Для начала я поясню свои примеры:
4 часа назад, eu_tomat сказал:Имеем массив значений: {10, 12, 280}. Условие (max/min>128) соблюдено. Константа шума равна 2.
Имеем массив значений: {10, 18, 280}. Условие (max/min>128) не соблюдено, но существует решение и для этого случая тоже.Первый пример: Вычисляем расстояния между всеми парами значений:
{abs(10-12), abs(10-280), abs(12-280)}
{2, 270, 268}
min(2, 270, 268)=2
max(2, 270, 268)=270
max/min = 270/2 = 135 > 128
Задача решена:
geolyzerNoise = min = 2
Во втором примере:
{abs(10-18), abs(10-280), abs(18-280)}
{8, 270, 262}
min(8, 270, 268)=8
max(8, 270, 268)=270
max/min = 270/8 = 33.75 < 128
Задача не решается описанным алгоритмом, но небольшое усложнение вычислений обеспечит решение и этого примера тоже.
А теперь я дам намёк на решение: Значения шума геосканера не случайны. Их всего 256. Расстояния между значениями равны. Всегда повторяется один фиксированный интервал. И какие бы два значения шума мы ни выбрали, расстояние между ними всегда будет кратно этому интервалу.
-
9 минут назад, NEO сказал:
Что является мах и мин? В первом массиве 280/10 = 28, что во втором 280/10 = 28.
Нужен минимум и максимум не самих значений, а разниц между ними:
22 минуты назад, eu_tomat сказал:требуется найти минимальную и максимальную разницу между всем значениями, полученными от геосканера, а задача считалась решённой при условии max/min > 128.
-
Я нашёл ещё один способ оптимизации алгоритма чисто математическими средствами.
До этого я говорил, будто бы для полной гарантии решения задачи требуется найти минимальную и максимальную разницу между всем значениями, полученными от геосканера, а задача считалась решённой при условии max/min > 128. Взглянув на эту задачу под новым углом, я считаю, что это условие достаточно, но не является необходимым для решения задачи. Существует подход, обеспечивающий ещё более быструю сходимость к результату.
Желающим размять мозги предлагаю два примера:
Имеем массив значений: {10, 12, 280}. Условие (max/min>128) соблюдено. Константа шума равна 2.
Имеем массив значений: {10, 18, 280}. Условие (max/min>128) не соблюдено, но существует решение и для этого случая тоже.Вопрос: как решить задачу во втором примере?
Для решения достаточно знаний школьного курса математики. Другое дело, что это не типовая задача, скорее всего.
-
1 час назад, GrigST сказал:к микроконтроллеру подключено 2 редстоун контроллера.
как присвоить переменным red1, red2 прокси этих редстоун-контроллеров?(какая переменная к какому контроллеру - не важно)
А хотя бы один красный контроллер уже удалось подключить к микроконтроллеру?
Насколько я помню, микроконтроллер не может работать в внешними компонентами.
-
2
-
-
4 часа назад, hohserg сказал:Чем дальше блок от геосканера, тем выше шанс и амплитуда погрешность измерения. Поэтому, возможно, имеет смысл сканировать блоки на разном расстоянии.
Да, амплитуда шума растёт пропорционально расстоянию. Поэтому при вычисления константы шума требуется полученный от геосканера шум нормализовать, привести к исходному путём деления на расстояние блока от геосканера. В своём алгоритме я избежал этого, сканируя блок на единичном расстоянии, но в общем случае нормализация шума необходима. Нормализация вернёт амплитуду шума к исходной.
Просканировать блоки на разном расстоянии, конечно, можно, но что нам это даст после нормализации шума?
-
Предложенная в теме методика вычисления константы шума весьма эффективна. Но она ещё не исчерпала весь потенциал возможных оптимизаций. Позже я подробно расскажу о найденных мною решениях, но сейчас предлагаю всем, кто любит решать задачи самостоятельно, ответить на вопрос: как ещё сильнее сократить кратность сканирования, не жертвуя при этом точностью результата?
Я нашёл три решения. Два из решений основаны на общем принципе и очевидны для тех, кто активно пользуется геосканером. Одно даёт лучшую сходимость за счёт усложнения установки. Другое же не столь эффективно, но и установка не усложняется. Зато третье решение эффективно, при это не требует усложнения установки, но эксплуатирует некоторые особенности реализации шума геосканера, которые мы ещё не обсуждали.
У кого есть варианты ответов?
Upd:
Третье из найденных мной решений оказалось ошибочным. Код генератора шума не позволит объединить преимущества первых двух решений.
-
1
-
-
-
Кстати, была похожая программка.
-
23 минуты назад, Hemou_ сказал:Не знаю относится ли это к инфраструктуре
Вроде бы ни к чему не относится из имеющихся разделов. Перенёс в "разное".
-
37 минут назад, Doob сказал:Я все-таки не понял, зачем искать коллизии, если геосканер годен только для поиска руды.
Во время поиска руды могут встретиться какие-то полезные блоки из модов. Или наоборот, ненужные. И это не всегда руды. Поэтому желательно знать, как нужное отличить от ненужного, если есть такая возможность.
А для оценки возможностей алгоритма фильтрации шума желательно знать, насколько близко могут находиться две различные плотности.
-
28 минут назад, Pengoid сказал:Я ставил поочередно несколько иридиевых ящиков из ic2 с воронками, под последним ящиком ставился робот. Он поочередно вытаскивал блоки, устанавливал их перед собой, сканировал с помощью .analyze(), записывал твердость в файл, ломал блок ваджрой на шелк и клал в ящик справа от себя, под которым была воронка в другие ящики. Я просто накидал блоки из JEI, это не очень быстро, но зато точно все проверит. Вот откуда у меня столько твердостей было)
Я поленился такое проделать. Надеялся, что есть способ попроще.
34 минуты назад, Doob сказал:Встречный вопрос: зачем?
Для того, чтобы знать, с какими плотностями у нас могут возникнуть коллизии в каждом конкретном случае.
16 минут назад, Pengoid сказал:перебираются плотности блоков для каждого сканирования, пока для нашей итоговой формулы не выполнится условие с целым числом.
Добавлю два условия.
1) Для оптимизации перебираем не все плотности, а те, что в пределах [min,max] с учётом диапазона шума.
2) Также нужно найти не одно, а все целые числа, чтобы проанализировать возможные коллизии.
-
Для фиксации результата к уже сказанным мыслям добавлю, что полученное значение шума должно быть не только целым, но и находиться в диапазоне [-128,+127]. Это правило уменьшает количество коллизий.
О коллизиях теперь и остаётся рассуждать. Алгоритм, эксплуатирующий дискретную природу шума, успешно определяет лишь блоки известной плотности. Даже если первое сканирование ведёт к коллизии, то это коллизия среди известных нам плотностей. Да и коллизия эта с большим шансом разрешится повторным сканированием. Но основой успеха будут заранее известные плотности блоков или хотя бы какая-то более-менее стандартная шкала плотностей.
Вопрос: существует ли возможность сравнительно простыми манипуляциями вытащить таблицу плотностей всех имеющихся блоков в конкретной сборке модов?
-
5 минут назад, Pengoid сказал:Можешь, пожалуйста, объяснить почему результат должен быть не равен нулю? А то я получил противоположный результат с такой же формулой, но без остатка от деления, то есть у меня число должно быть приблизительно целым, а значит по твой формуле у меня результат должен быть очень близким к нулю или нулем.
Полагаю, это описка. А ход рассуждений одинаков, вы оба нашли решение.
-
15 минут назад, Pengoid сказал:Ой, кажись, я понял принцип. У нас при сканировании получается 256 вариантов шума, а на выходе мы имеем точное число с плавающей точкой.
Считаем расстояние R. Тогда шум N = R*0.0606*[рандом от -128 до 127]/128 - P0 (полученное значение после сканирования), и тогда каким-то образом рандом подгоняется к преполагаемому значению твердости сканированного блока.
Да, копать надо здесь. Раскручиваем наш сигнал назад к исходному рандому и проверяем характеристики на соответствие исходным.
1 минуту назад, NEO сказал:Сам написал гпсч и через секунду забыл.
Нет, тут в другом фокус. Я не ищу уязвимость ГПСЧ, т.к. нашёл уязвимость в дальнейших за ГПСЧ преобразованиях. Эта уязвимость останется актуальной, даже если бы получаемый из ГПСЧ набор чисел вдруг оказался совершенно случайным. Так что, наши подходы сейчас различны.
-
3 минуты назад, Pengoid сказал:Насколько я пытался догадаться, вы хотите заранее вычислить рандом, который выдаст генератор, чтобы просто вычесть шум из значения сканированного блока для получения реальной плотности блока.
Нет, это @NEO предлагал найти узявимость в ГПСЧ, а я пока воздержусь от этого способа.
Я же считаю, что значение шума геосканера не совсем случайно, оно содержит своего рода цифровую подпись, по которой можно всегда или почти всегда (это ещё предстоит выяснить) восстановить точное значение именно шума в общем сигнале. Но для этого требуется выполнить обратное преобразование, одним из компонентов которого является расстояние.
Ладно, посмотрим, как там @Doob решит задачу, да я и выложу ответ. Всё равно никто больше не пытается решать.
Кстати, @Doob, у тебя в чём затык-то? Ты не уверен в решении моей задачи? Или в общем решении подобных задач? Решение задачи уже можно выкладывать?
-
28 минут назад, Pengoid сказал:А точно нужно вычислять само расстояние?
А ты уже решил мою задачу, опираясь лишь на первый результат сканирования? Как её решить без извлечения корня, при этом не увеличив объём вычислений на порядок?
1 час назад, Pengoid сказал:есть исключения, например кварцевый блок, у него 0.80000001192093, но я во всех случаях пренебрегал подобными хвостами.
Да, точно же! Получается, что теоретически какое угодно может быть значение плотности. Эти хвосты могут создать проблему для нового метода подавления шумов.
1 час назад, Pengoid сказал:думаю плотность зависит напрямую от времени ломания блока подходящим типом инструмента.
А что у кварца за инструмент такой подходящий для ломания, что получилась такая странная плотность с хвостом?
-
Прошу всех, кто заметил странности в форматировании этой темы, сообщить мне об этом. Использован экспериментальный подход. Основное форматирование было выполнено в asciidoc, отформатированный текст перенесён на форум, после чего осталось вручную раздвинуть абзацы и оформить куски кода тегами. Ссылки вроде бы сохранились, заголовки тоже. Красота. Но всё равно скучаю по старому движку с поддержкой BBCode и продолжаю искать способы быстро публиковать на форуме статьи с более-менее сложным форматированием.
-
Методика ускоренного вычисления константы шума геосканера
Предлагаю ознакомиться с методикой, позволяющий максимально быстро и абсолютно точно вычислить константу шума геосканера (geolyzerNoise в config/OpenComputers.cfg).
Методика и скрипты тестировались в среде OpenComputers-MC1.7.10-1.7.5.1290-universal.jar. Сохранит ли эта методика свою актуальность в будущем, вселцело зависит от авторов мода.
Зачем знать константу шума геосканера?
Не на всех серверах параметр geolyzerNoise сохраняет значение по умолчанию. Алгоритмы же поиска руд, использующие для своей работы геосканер, в большинстве своём эффективны лишь при определённых параметрах шума. При увеличении или уменьшении зашумлённости будут эффективны другие алгоритмы. Поэтому знание точных параметров шума геосканера поможет использовать наиболее эффективные алгоритмы поиска руд на конкретном сервере в конкретных условиях шума.
Традиционный алгоритм
Традиционный алгоритм использует выполнение многократного сканирования плотности блока, поиск минимального и максимального значений и вычисление разницы между ними. Плюсом алгоритма является его простота. Минусом является низкая точность. Для повышения точности используется увеличение кратности сканирования, но даже очень большая кратность не даёт гарантии абсолютной точности. Всегда есть небольшой шанс, что шум окажется немного больше найденного алгоритмом.
Дискретная структура шума
Как было обнаружено в недавнем обсуждении про вычисление погрешности геосканера, шум имеет дискретную природу. Согласно коду OpenComputers для каждого из сканируемых расстояний существует 256 возможных значений шума. Знание этого факта позволяет нам считать результат достигнутым, как только сканер выдаст 256 уникальных значений плотности одного и того же блока. Плюсом такого подхода будет абсолютная точность. Главный же минус заключается в том, что получение всех 256 значений может занять даже больше времени, чем получение реальных минимума и максимума плотности. В моих экспериментах на получение всех 256 значений уходит примерно 10-20k попыток сканирования.
Вот скрипт для наглядности:
-- демонстрация: шум геосканера имеет 256 фиксированных значений -- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc local scan = require'component'.geolyzer.scan local uniqTbl = {} local uniqCnt = 0 local v for i=1,1e4 do v = scan(0,0,-1, 1,1,1)[1] if not uniqTbl[v] then uniqTbl[v] = true uniqCnt = uniqCnt + 1 print(("try: %d, uniqCnt: %d"):format( i, uniqCnt )) end os.sleep(0) -- ^C для останова end
Наблюдая за скриптом, легко заметить, как медленно добираются последние из оставшихся уникальных значений. Алгоритм абсолютно точен, но неоптимален.
Оптимизация поиска
Оптимизировать вычисления нам поможет знание о том, что все 256 значений шума расположены равномерно, расстояния между смежными значениями одинаковы, и они ровно в 256 раз меньше расстояния между максимальным и минимальным из значений. В пределах погрешности вычислений, разумеется.
Это значит, что для вычисления константы шума достаточно найти любые два смежных значения и вычислить разницу между ними. Но смежными эти значения должны быть в своей полной таблице из 256 значений, в то время как в целях оптимизации рабочая таблица должна быть заполнена как можно меньшим количеством данных, и поэтому соседство значений в рабочей таблице не означает обязательности их соседства в полной.
Уменьшать количество значений в рабочей таблице следует ровно до того момента, пока это не мешает обнаружению двух смежных значений. Можно сказать и наоборот: пополнять таблицу новыми значениями следует ровно до тех пор, пока смежные значения не удаётся обнаружить с абсолютной точностью.
Самое очевидное, что приходит в голову, это набрать ровно 129 уникальных значений, и найти среди них ближайших соседей. Почему 129, а не 128? Потому что при 128 уникальных значениях возможна редкая ситуация, когда эти найденные значения находятся в полной таблице ровно через одно. Это маловероятно, но возможно. Зачем рисковать? Тем более, 129 элементов почти всегда находятся примерно за 200 попыток сканирований, что можно увидеть, наблюдая за работой демонстрационного скрипта.
Но внимательный читатель наверняка заметит, что может быть достаточно использовать и 128 значений при условии, что они размещены неравномерно относительно друг друга. Почти всегда 129-ое значение оказывается необязательным. И если развить эту мысль, то выяснится, что и 127 значений почти всегда будет достаточно при введении дополнительных условий. Тем же путём можно перейти к 126 значениям и т.д. В итоге окажется, что роль играет не равномерность расположения значений относительно друг друга, а расстояние между крайними элементами и между двумя ближайшими. А для этой цели может быть достаточно даже трёх найденных значений. В лучшем случае. Но в худшем могут потребоваться и все 129 значений.
Оптимальный алгоритм
В общем виде алгоритм сводится к циклическому получению очередного значения от геосканера и поиску разницы между всеми найденными значениями. И если соотношение максимальной разницы к минимальной превысит 128, то результат достигнут: минимальная разница между найденными значениями обязана быть равной разнице между смежными значениями в полной таблице. Результатом умножения минимальной разницы на 128*33 будет искомая нами константа geolyzerNoise из файла конфигурации.
Результирующий код может выглядеть, например, так:
-- измеритель шума геосканера (константы geolyzerNoise в config/OpenComputers.cfg) -- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc local abs = require'math'.abs local scan = require'component'.geolyzer.scan -- округление до сотых долей для сокрытия погрешностей local function round( v ) return (v*1e2+0.5)//1/1e2 end -- множитель для восстановления значения шума до справочного local mul = 128*33 local uniqTbl = {} local uniqCnt = 0 -- текущее значение, разница с другим значением, минимальная и максимальная разница local val, dif, min, max -- флаг обновления экстремумов local fUpd for i=1,99 do os.sleep(0) val = scan(0,0,-1, 1,1,1)[1] fUpd = false -- обрабатывать только новые уникальные значения if not uniqTbl[val] then -- обновить информацию о минимальной и максимальной разнице for v,_ in pairs(uniqTbl) do dif = abs( val-v ) if not min or min>dif then min=dif fUpd=true end if not max or max<dif then max=dif fUpd=true end end -- пополнить таблицу уникальных значений uniqTbl[val] = true uniqCnt = uniqCnt + 1 end -- при обновлении вывести информацию на экран if fUpd then print(("uniq:%2d/%2d | min:%7.3f | max:%7.3f | max/min:%7.3f"):format( uniqCnt,i, round(min*mul), round(max*mul), round(max/min) )) end -- закончить по достижении результата if fUpd and max/min > 128 then break end end -- сообщить результат if fUpd and max/min > 128 then print(("Congratulations! geolyzerNoise = %f"):format( round(min*mul) )) else print("Failure! Tray again please!") end
Результат
Знание об особенностях генерации шума геосканера, позволило достичь абсолютно точных результатов при очень малом времени сканирования при вычислении константы шума геосканера. В лучшем случае результат можно получить за три сканирования. В типичном случае требуется около 20 сканирований, что требует около одной секунды времени. Самый худший случай не ограничен ничем, но использованное в моём скрипте ограничение в 99 сканирвоаний ни разу не было достигнуто за несколько сотен попыток.
И это ещё не всё, что может дать знание о шуме геосканера. Пошумим, брат!
-
7
-
2
-
-
@Doob, я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу.
1 час назад, Doob сказал:Если я правильно насчитал, надо хранить 6885 значений, эффективность сканера будет 99.89%. Вполне неплохой результат.
Я не планирую хранить хеши шумов. Может быть, подумаю о хранении расстояний, чтобы не вызывать многократно функцию извлечения квадратного корня. Но оставшаяся часть реверсивных вычислений, мне кажется, слишком проста для того, чтобы занимать память этими хешами. Но да, надо будет проверить эти предположения в реальной работе. Тогда заодно и дам свою оценку шанса коллизий.
Кстати, о коллизиях. Плотности блоков чаще всего кратны единице. Но бывает и 1.5 как у камня. Чем определяется плотность того или иного блока? Насколько дробной может быть плотность, как это регламентируется? Может ли, плотность блока быть 1.618, например? Какие они вообще бывают стандартные, типичные плотности?
-
3 часа назад, Doob сказал:Самый быстрый способ определять руду это хеш-таблица. Сгенерировать и хранить в памяти 287889 чисел (количество значений шума * все возможные дистанции). Точность будет 99.998%
Более эффективного метода не придумал.
Да, я тоже пока не придумал ничего лучшего как либо хранить хеш-таблицу, либо каждый раз заново пересчитывать её элементы для каждого вновь просканированного блока. Правда, я пока довольствовался умозрительными экспериментами, а на калькуляторе посчитал только озвученную задачу.
Пока я потренируюсь на задаче пропроще. Для начала попробую оптимизировать вычисление константы шума с учётом новых сведений. Может, после этого появится хорошая идея.
Upd:
Ой, я соврал. Была же нормальная идея. Просто я уже увлёкся новой задачей. Но сейчас заглянул в калькулятор, а там решение моей же задачи.
Даю ещё один намёк. Сделай обратное преобразование зашумлённого значения, исходя из предположения, что сканируется камень или руда. И теперь посмотри, чем эти значения друг от друга отличаются. Конкретно в моей задаче. А потом задайся вопросом, почему одно из них сильно вероятнее другого.
-
9 минут назад, NEO сказал:Не проще посмотреть код генератора "рандомных " чисел? он не криптографически стойкий, тобишь не должен быть сложно устроенным.
Кинь ссылочку на код этого генератора. Посмотрим.
Беседка TC
в TechnoCraft
Опубликовано:
Не надо их замораживать. Недавно и так вайп был. Да и для чего они тогда вообще нужны эти UU, если не использовать их для быстрого старта? Проще тогда вообще от них отказаться. Кто хочет копать руками, пусть копает, препятствовать ему никто не будет.