Кирпичи Эйлера. Третья итерация. Скорее всего последняя

Чего-то решил я перебраться со своими редкими постами из гугловского Блог-поста в Дзен. У гугла всё потихоньку печальнее и печальнее становится: картинки вот начали пропадать. Того и глядишь, доступ из России закроют... Поэтому вот ссылка на статью на Дзене, здесь буду копии выкладывать.

Короче, про кирпичи. Просчитал я нечетную сторону до 2^32, попутно отловив все ошибки и сделав оптимизацию, которую придумал Иван. Оптимизация, конечно, сильно помогла, ниже покажу, это будет заметно. А здесь оставлю ссылку на файл с рассчитанными кирпичами, вдруг кому станет интересно.

Когда сверялся с образцовым файликом, обнаружил, что ребята-то сильно далеко вперед ушли, мне их даже просто догонять долго. Впрочем, как легкое упражнение в программировании для поддержания тонуса пойдет.

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

И вот пока я там на ассемблере оптимизировал, расчет у меня уперся в ограничение. Уже на нечетной стороне с длиной 5916099741 возникают четные стороны, сумма квадратов которых превышает беззнаковое 128 бит. То есть я не могу проверить, дают ли они пифагорову тройку. Тут возникает задачка написать новый тип, бы что-нибудь вроде UInt192, куда всё точно влезет, но пока что-то лом этим заниматься: никому не нужно, а мне пока лень. Может, со временем возникнет желание написать, ХЗ.

Из того, что посчитано, есть один интересный момент. Если максимально близким к совершенному кубоиду долгое время был мелкий и легко считаемый (37835, 269280, 1244484) с отклонением главной диагонали в ~6.5E-5, позже нашелся лучший кубоид (1939671305, 640347864, 1045085760) с отклонением ~4.1E-5. Ну, то есть раз есть прогресс, значит остается и шанс, что совершенный кубоид все же существует, и он достаточно не хилый, с учетом бесконечного количества натуральных чисел. Вполне вероятно, что среди них хотя бы один примитивный вариант да найдется.

Вообще в диапазоне до 2^32 есть пять примитивных кубоидов, у которых отклонение главной диагонали от целого меньше 1E-4. Но кроме этого, никаких других общих черт у них я выявить не смог.

Ниже ради любопытства зависимость скорости генерации кубоидов в зависимости от длины нечетной стороны.

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

Кирпичи Эйлера. Вторая итерация

Иван в комментариях к предыдущему посту придумал очень быстрый и эффективный способ вычисления пифагоровых троек к нечетному числу. Мне стало интересно, я тоже немного погрузился в тему статьи Матсона.

Правда, той эффективности, что у Ивана, мне достичь не удалось, я пока в процессе. И в этом процессе я обнаружил любопытную вещь.
Мне скучно просто искать совершенный кубоид, поэтому  я решил в процессе еще и сохранять все найденные обычные кирпичи Эйлера. Это чуть более сложная задача, потому должна работать чуть медленнее, чем поиск совершенного кубоида. И для её работы нужно уметь эффективно считать целочисленный корень для больших целых чисел, в моем случае 128-битных.
Я решил проверить, сможет ли FPU (или по-другому x87) выполнить эту задачу. Шансы у него были, так как во внутреннем представлении FPU хранит вещественные в расширенном формате, длиной не стандартные 64, а целых 80 бит.
В процессе обнаружил, что точности как бы не хватает. Начал копать и через непродолжительное время выяснил, что по какой-то странной причине точность FPU оказалась занижена до 64 бит. Да, в FPU с помощью флагов можно менять точность внутреннего представления чисел от 32 до 80 бит, что кроме точности влияет и на производительность, понятное дело.
В документации на сайте AMD утверждается, что по умолчанию FPU установлен на максимальную точность. Но возможно, это было давно и в современных версиях процессора уже не действует? Кроме того, точность может менять Windows, а так же компилятор Delphi. Кто из них повинен в такой ситуации, мне не ведомо.
Интереснее другое: зачем это вообще сделано? Лично я вижу лишь одну причину: что бы пользователи не заметили разницу в решениях своих задач на FPU и SSE, иначе кто-нибудь как-нибудь да непременно выскажет претензии. Но это лишь предположение.

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

Теперь про мою реализацию. Во-первых, я отказался от проверки деления на 19. Конечно, такое деление снижает количество рассматриваемых вариантов, но, если я правильно понял, не так уж значительно по сравнению с делением на 16. В то же время, проверка делимости на 16 происходит гораздо быстрее.
Но возможно здесь я ошибаюсь, так как проверка каждого варианта на то, что он является кирпичом Эйлера стоит гораздо дороже, чем разница в скорости проверок делимости.

Во-вторых, я пока не сделал сохранение найденных делителей для последующего использования, что, конечно, существенно снижает производительность.

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

Все это, конечно, весьма далеко от  гораздо более эффективной реализации Ивана. Но, тем не менее, тоже показывает относительно неплохую производительность: от 100001 до 100000001 по нечетной стороне все варианты кирпичей Эйлера были найдены за час с небольшим, всего 3182002 варианта.
Я решил, что вместо того, что бы проверять на первичность решения в процессе поиска (мне показалось это достаточно затратной операцией), сохранять все найденные варианты. А уже потом быстренько отсеять все составные, ну и плюс тут же проверить и на совершенность.

Кирпичи Эйлера

Как-то раз случайно наткнулся на видео, не помню уж про что оно было, но упомянуто в нем было в том числе и про одну из нерешенных математических проблем. Как раз про совершенный кирпич Эйлера.

Кратко: суть состоит в решение системы четырех диофантовых уравнений второй степени. Это решение соответствует параллелепипеду, у которого все стороны и диагонали являются натуральными числами.

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

Естественно, есть соблазн найти такой кирпич с помощью грубой силы. А раз есть соблазн, значит, есть и те, кто попытается им воспользоваться.
К сожалению, на текущий момент найти совершенный кирпич Эйлера таким методом тоже не удалось. И даже дойти до границы 64-битных чисел для длин сторон кирпича тоже.
Что, если честно, меня несколько удивило. Ведь производительность современных компьютеров просто край как высока. Несколько десятков миллиардов целочисленных операций в секунду.

Естественно, я не удержался и решил сам попробовать, не мудрствуя лукаво, грубой силой в лоб. Ну и в общем да, получил то, что и следовало ожидать: два вложенных цикла – это совсем не быстро, даже с учетом того, что память при таких вычислениях мало задействована.
Оптимизация на ассемблере существенно ускорила вычисления, но, конечно, кардинально решить проблему не смогла: слишком высока размерность задачи.

Больше всего издержек при такой попытке поиска кирпичей Эйлера уходит на проверку того, будет ли целым корень из квадрата длины диагонали.
И тут, по крайней мере, пока квадрат длины не выходит за границы 64-битого беззнакового целого, очень помогают вычисления с плавающей точкой.
Сначала я сделал это на расширенном типе с плавающей точкой (extended), являющейся фишкой x87, так как 64-битное беззнаковое целое можно без какой-либо потери точности загрузить в регистр сопроцессора. Еще подумал: "О, вот и старенький x87 может для чего-нибудь пригодиться".
Однако потом в процессе тестов выяснил, что с достаточной степенью точности для данной задачи корни можно вычислять и на типе double. Впрочем, особой разницы в производительности не увидел.

Но, как только мы выйдем за границы 64 бит для квадратов длин диагоналей, вот возможно там тип extended, вместе с x87 и сгодится.
Целочисленные методы вычисления квадратного корня на основе метода Ньютона (он же вавилонский, он же Герона), даже при хорошем начальном приближении требуют минимум двух итераций с делением, что получается гораздо медленнее, чем с плавающей точкой. Главное, что бы хватало точности у этой самой плавающей точки. И вот тут я не уверен, что ближе к верхней границе 128-битного целого точности даже extended будет достаточно.

В практическом же смысле толку от этих самых кирпичей Эйлера я не вижу. Разве что в холода использовать комп в качестве нагревателя. )
И вот идея: так как кирпичи Эйлера трудно вычислимы, почему бы их не использовать в качестве криптовалюты? Тот же специальный вид криптографического хеша тоже особого смысла не имеет. А на майнинг опять же биткойнов потрачено, наверное, уже несколько тераватт*часов электроэнергии.
При этом хоть какую-то ценность все эти криптовалюты имеют до тех пор, пока у достаточно значительной части населения есть вера в крипту хотя бы с горчичное зерно. Как только такая вера пропадет, стоимость крипты мгновенно обнулится.

Кирпичи Эйлера тут ничем не лучше, но в процессе их расчета может хотя бы получилось решить одну их серьезных математических проблем.

Кстати, большого списка примитивных кирпичей Эйлера я так и не нашел. Наверняка он есть, это мне просто искать лень. Если я на первых двух страницах поисковой выдачи не нахожу нужного мне результата, то сразу как-то теряю интерес к процессу поиска. )
Так я делаю, конечно, когда ищу что-то не сильно важное. А кирпичи Эйлера – это тот самый случай.
Так что выложу те кирпичи, которые я в процессе своих экспериментов насчитал. По ссылке лежат примитивные кирпичи, отсортированные по возрастанию нечетной стороны, далее  для каждого  кирпича указаны меньшая четная, затем большая. Ну и длины диагоналей.
Так как внешний цикл у меня был по нечетной стороне, то остановился я на таком размере, что бы все возможные варианты квадратов диагоналей с учетом четных сторон не превышали диапазона 64-битных чисел.
Возможно, где-то ошибся в программе, так что абсолютно точно не уверен, что нашел все примитивные кирпичи для указанных условий.

Ну и немного статистики. Выяснилось, что примерно 80% длин дают только один вариант кирпича, а вот оставшиеся 20% – несколько. Интересно, что это за числа и чем вызвано такое их свойство? Не знаю, есть ли у математиков ответ на такой вопрос.
Лидером среди нечетных длин является число 51975 – оно дает 12 различных кирпичей, или 24 пифагоровых тройки. Далее идут 32175 и 58905 – по 11 кирпичей.
Четные числа немного отстают. Лидер тут 23760  – 11 кирпичей, 71280 – 9, и у 55440 и 118800 – по 8. Причем такое свойство гораздо чаще встречается у стороны, кратной 16, чем у стороны, кратной лишь только четырем.
Лидер, кратный 4 - 33660, дает 7 кирпичей.

Из найденных вариантов самый близкий к совершенному варианту оказался кирпич с длинами сторон 37835, 269280 и 1244484. Главная диагональ у него 1273846.00006476, что совсем близко к целому числу.
Это дает надежду, что совершенный кирпич Эйлера все же существует. Но скорее всего длины сторон лежат за пределами 64-битных целых, так как значительная часть этого диапазона уже проверена исследователями.
А вот в диапазоне 128-битных целых такой кирпич вполне может прятаться.

Резервирование питания

Долго и мучительно экспериментировал я с резервированием питания, но особых успехов не добился, понятное дело. 😁 

Сначала я разобрал отдавший богу душу дешевенький ИБП. Чисто детали выпаял из него. Ну и заодно, насколько смог, попытался представить как он работает. Получилось у меня что-то вот такое.

Как видим, центром схемы, а заодно и тяжести, является трансформатор питания. Солидный такой... Тем не менее, мощность у него не очень большая – 800 ВА, а значит, и КПД где-нибудь в районе 70%. И он работает постоянно, хоть от сети, хоть от батареи.
Поэтому он греется, а от него греется АКБ, что очень отрицательно сказывается на сроке её службы. Ну и, конечно, совершенно напрасные, не очень нужные потери энергии на тепло тоже совсем не радуют.

Удивительное совпадение, но nabbla примерно в это же время произвел вскрытие практически брата-близнеца моего ИБП. Только он (nabbla ,а не трансформатор), в отличие от меня, имеет хорошее профильное образование, поэтому по ссылке гораздо более детальный и точный обзор всего этого безобразия.
Но, если смотреть укрупнено, то вроде я всё верно нарисовал.

Собственно, моя идея-то была очень простая. Сделать что-то типа такого.

 

Идея тут в том, что бы с такого ИБП отдать питание сразу на материнскую плату, избегая двойного преобразования при использовании обычного ИБП (трансформатор ИБП, БП компьютера).
Тут видно, что все же двойного преобразования избежать не удастся, но, так как мы избавились от трансформатора, то общий КДП будет выше, чем при использовании классической связки ИБП+БП компьютера, но, понятное дело, хуже, чем в случае использования компьютера без ИБП.

Smart ЗУ должно по замыслу подзаряжать АКБ только тогда, когда она разрядиться ниже некоторого порога (например, 12.6 В), а не все время, как в буферном ЗУ. Это и потери энергии снизит, и продлит (по крайней мере в теории), жизнь АКБ.

А срезался я на ключах. Мне всенепременно хотелось сделать ключи на полевых транзисторах. Желание понятное, так как у мощных полевых транзисторов в открытом состоянии очень низкое сопротивление, а значит, и потери.
В традиционном варианте, с использованием диодов, все надежно и просто, на диоде теряется примерно 1 В, а значит, при высокой нагрузке будут и большие тепловые потери. На хороших транзисторах потери могут быть в несколько раз меньше.

В результате накидал я вот такую схемку, потом много раз пытался её улучшить и модернизировать.

 

Тут я сделал общий "плюс", а не "минус", как обычно, только ради того, что бы использовать транзисторы с N-каналом, так как в целом они лучше по характеристикам. И при работе в режиме ключа мощную нагрузку лучше подключать в цепь стока. В результате отключенная нагрузка будет висеть на "плюсе", но по большому счету разницы особой нет.
Схемка в приведенном виде не совсем корректна, ошибки я потом исправил. Но как не исправляй, работать я ее правильно заставить не смог.

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

В конечном итоге плюнул и сделал схему с диодом вместо одного ключа.

 

Намучившись с обратной полярностью, я решил не умничать и сделал схему с общим минусом. В результате пришлось использовать транзистор с P-каналом. Можно было и вместо него диод использовать, если бы не одно но. АКБ надо же будет заряжать, и если использовать вместо ключа диод, то зарядное устройство будет не заряжать, а подавать напряжением, причем повышенное, на материнскую плату.
Транзистор же с P-каналом при большом токе нагрузке будет иметь сопротивление, сравнимое с диодом. Впрочем, поменяв полярность, можно легко перейти на N-канал и снизить потери в несколько раз.

Но все это буду пробовать как-нибудь в следующий раз. 😆