Сортировка - паллиатив, в простых общих случаях (неотрицательные числа и т.п.) математическому доказательству не подлежит, но частично помогает только для trouble1, при небольших размерах массива (массивы реально больших размеров становятся похожи на trouble2 и trouble2a).
ИМХО, сложение деревом с векторизацией (block_pairwise_autovec) более перспективный паллиатив, тоже решает только один вариант из трёх, но как раз тот, который сравнительно часто встречается. Вероятно поэтому оно и реализовано в BLAS (<linalg>, C++26).
Аналогов, math.fsum() или "крейта accurate", извините, на вскидку, не вспомню. Хотя как раз их доказывать, легко и приятно.
P.S.
Да, для сложения деревом, я видел доказательства, что при некоторых странных предположениях, накопление ошибки будет логарифмическое.
Нет, не оговорка. Единственно, что, и сравнительно шустро, и более менее доступно в быту это расширенная точность. Просто Numpy её почти всюду в документации обозначает типом np.float128 и только в паре мест раскрывает его подлинное имя np.longdouble. 😉
Да IEEE 754 определяет тип binary128 (в новом стандарте C23 для него, ну наконец то, завели тип float128_t), но его поддержка, на бытовом уровне, весьма и весьма ограничена и, чаще всего, программная, а не аппаратная (ну, кроме "монстров" SPARC, POWER и т.п.).
Но процессор ж "по умолчанию" это ж x86_64. Как и исторически неплохая поддержка типов языка C long double, Numpy np.longdouble (он же np.float128 для x86_64, поскольку в памяти он занимает 16 байт или 128 бит) неплохая. Опять же пока более менее шустрая аппаратная реализация.
Конечно, новые процессоры ARM, Nvidia GPU и т.п., уже весьма распространены, но пока ограничиваются binary16/32/64.
Ну, а если уж на ARM, Nvidia GPU брать программную реализацию четверной точности для вычислений, а не для ввода/вывода, то уж никак не binary128/binary256 от IEEE, а double-double и quad-double, которые построены на алгоритме Кэхэна и его производных.
Злые языки говорят - спасибо АНБ. В 1979/1980, когда сделали MC68881/Intel 8087, оказалось, что один из возможных вариантов их использования - 64 битная арифметика (64 битный умножитель) на основе 80 битных плавающих чисел (binary80).
Сейчас эти binary80, обычно, хранят в 16 байтах.
... Усреднение с использованием метода PyTorch sum(). В нём, судя по всему, встроены специальные алгоритмы
ИМХО, под капотом numpy.sum(), который суммирует деревом с блоками по 128 чисел, которые ещё разбиваются по 8 для SIMD, т.е. эффективно блок дерева ≈16 чисел.
На практике оказалось, что попарное усреднение словарей (тем более, что оно делается сразу со словарями, а не по отдельным числам из разных словарей), сразу даёт существенную прибавку к точности работы нейросети.
Ну, в деле словарей, возможно так удобнее. Хотя, по два, или большему числу непонятно.
Особенно в случае, преобразования np.float32() в np.float64() для усреднения и последующего обратного преобразования. После этого преобразования имеем, 29 запасных нулевых бит, если у нас 1024 числа, а усредняемые числа изменяются не более чем в 0.5*10⁶ раз, то после обратного преобразования, средний np.float32() будет корректным округлением точного результата.
Алгоритм Кохэна, наверное, ещё что-то улучшит, в особенности на сверхглубоких нейронных сетях, но на моих 16-ти слоях я не увидел смысла его делать.
Вопрос философский, требующий конкретных оценок того, сколько бит надо. Есть вариант с math.fsum(), который является развитием Коэхэна, но не с двумя накопителями, а до 39 (для произвольных double, что бы обеспечить точное представление любой суммы, для данных полученых из np.float32, накопителей никогда не будет больше 6).
Ещё, конечно, есть варианты с предварительной сортировкой массива. В идеале по возрастанию абсолютного значения, но можно и находить "середину" массива, отсортированного по возрастанию или убыванию, бисекцией и дальше считать в обе стороны.
Сортировка - хреновый паллиатив, да она помогает в сравнительно редких случаях вида [1, math.ulp(0.5), math.ulp(0.5)], но в гораздо более типичных случаях вида 10*[1 + math.ulp(1)] уже не помогает, не говоря уж за [-1, math.ulp(0.5), 1] (впрочем, этот вариант тоже сравнительно редкий).
ИМХО, сложение деревом с векторизацией (block_pairwise_autovec) более перспективный паллиатив, тоже решает один вариант из трёх. Вероятно поэтому и он реализован в numpy.sum().
O(n log n) для сортировки это не так дорого
Ну, если недорого, то может и честный math.fsum(), со своими , тоже не так дорого?
Он же даёт оценку для некоторого конкретного алгоритма. А так, да, любые IEEE 754 binary32 могут быть представлены 280 битным целым, а binary64 - 2102 битными. Только вопрос удобства суммирования. У них, если для хранения мантисс используется int32, примерно один перенос на 512 операций (или 256, в зависимости от реализации бита переноса/заёма), типично, одно суммирование и сдвиг не требуется. У Вас переносы гораздо чаще и, типично, два-три суммирования в результате сдвига.
У второго упомянутого варианта, стандартного, math.fadd(), для того же самого используется буфер, формально переменного размера, но не более чем из 39 double. Точная накопленная сумма равна точной сумме элементов буфера, а переносы реализованы в стиле Кэхэна.
Какие конкретно варианты шустрее, сразу не сказать, возможно зависят от архитектуры. Но теоретическая сложность у них одинаковая.
Там попарный древовидный способ указан как тратящий слишком много ресурсов на рекурсию.
У алгоритмов типа скалярного произведения (взвешенной суммы), большая доля ресурсов уходит на обмен кэш L1 с памятью и/или L2/L3. А поэтому параметру древовидный способ проигрывает алгоритму Кэхэна примерно раза два.
А вот то, что алгоритм Кохэна оказался более точным - это интересно.
Ни Вы (при обосновании потребностей), ни они (при создании тестовых наборов), не приводите чисел обусловленности:
Оценка относительной ошибки алгоритма Кэхэна:
Т.е. если Вы преобразовали np.float32() в np.float64(), а потом просумируете алгоритмом Кэхэна, то суммирование будет реализовано примерно с точностью 104 бита. Этого много, мало или достаточно?
Альтернативный вариант - тупое суммирование np.float128() с точностью 63 бита, может оказаться гораздо шустрее.
Как бы, конечно, Unix time понимают далеко лишь не все.
Но, похоже, что всё не так однозначно. Поскольку, у многих, одинаковые приложения TOTP одинаково успешно работают, и с Госуслугами, и с GitHub, и с PyPI (а может, иногда, и одинаково безуспешно, но, главное, что одинаково).
С моего дивана кажется, что проблемы были связаны с ПО телефона и/или особенностями оператора связи. Естественно, это тоже не точно, ибо по фотографии.
Так и да, увы, как оказалось там (RFC 6238) именно это и написано:
...MUST know or be able to derive the current Unix time (i.e., the number of seconds elapsed since midnight UTC of January 1, 1970) for OTP generation. See [UT]...
С ключевым словом MUST (признак нормативного требования) и со ссылкой на Википедии.
Но формулировка с гнильцой. Во-первых, полночь 1970 года измерялась не в UTC, а в GMT (UTC был в планах, но время по нему стали выдавать только через пару лет). Во-вторых, на настоящий момент, от `Jan 1 00:00:00 GMT 1970` прошло на 27 секунд больше, чем значение текущего UNIX time.
Вот почему они эти скобки на хрен не вычеркнули, причём в нормативном абзаце?! Грабли, голимые.
Слова "заметны" и "ближайшие", как выясняется, суть растяжимы есть. 😉
Но даже наше Солнышко раздует под 1 а.е. Так что при измерениях более менее типичных красных гигантов на уровне точности 5...7 микросекунд дуги их радиус будет немного мешаться на всём диапазоне расстояний вплоть до 150...200 кпк.
А в части крупнейших звёзд так и радиус 10 а.е. не предел. К примеру, у Бетельгейзе ≈ 4 а.е., но это неточно, поскольку точность её параллакса, пока едва едва вытянули на уровень 500 микросекунд дуги. Т.е. за счёт радиуса звезды возможна потеря точности на два порядка.
P.S.
Так что это раньше неточность значения а.е. в километрах сильно понижала точность при переводе единиц, сейчас это мало актуально.
Так и да, теперь это значение известно абсолютно точно. Всем просто надоел этот бардак не имеющий, ни физического, ни астрономического смысла. 😉
Но, на самом деле, измерительное, как и нормативное определение а.е. совершенно не влияло на измерения параллаксов (ну или вияло очень и очень слабо). К примеру, Леверье, или даже Эйнштейн (не специалист, конечно, но погружался в эту бодягу ради ОТО), легко смог бы вычислить орбиту Гайи со всей необходимой точностью.
Речь идёт о потерях на то, что потокобезопасный код всё равно захватывает и освобождает блокировки, даже если он, в данный момент, работает в один поток.
К примеру, вывод print() или опрос/установка исключений плавающей запятой. Скажем, в коде NumPy есть примечательный комментарий: "мы сначала опрашиваем маску исключений fegetexceptflag(), а потом устанавливаем fesetexceptflag(), если только нам нужна другая маска, поскольку опрос в 10-50 раз быстрее установки".
Астрометрия имеет много гитик. Да, овал описываемый L2 примерно на 1% дальше земной орбиты, но эксцентриситет земной орбиты ≈ 0,017, т.е. заметно больше. Правда и Гайя не точно в L2, а бултыхается в её районе.
Не говоря уж, за то что наша Солнечная система движется ≈ 200 км/с, да и измеряемые звёзды на месте не стоят и, к тому же, имеют вполне себе заметные радиусы.
Хм, я сразу на капу нажал! В ответ на то, что "измерению поддаются 1% ближайших звёзд" (до Гипаркоса, действительно было где-то так), написал, что "1% только ближайших - это ж проблема прошлого века". 😉
Ну, вот Вы и ответили на сакраментальный вопрос автора "Но почему в России все в порядке?" На который он сам не смог чётко ответить.
К гадалке не ходи, если бы из РФ можно было бы оплатить подписку CrowdStrike, то и в РФ что-нибудь в эти дни массово упало бы. А так, в этот раз, пронесло, и слава Богу.
Хм, как бы наоборот. В Касперском не боги, а такие же люди. Так что, он вполне мог попасть в аналогичную ситуацию, но выглядела бы она так, что мама не горюй.
Думаю, одно другому не мешает. Они же говорят, что "некоторая" оперативная информация у них есть "удалось получить доступ к некоторым сообщениям...".
Но, когда дело дойдёт до суда или до досудебного соглашения с участием адвокатов и прочих законников, у них будут "легально" полученные и процессуально оформленные улики от Хуавей/Самсунг/Гугл/Аппл/.../Израиля/Австралии/... , в общем, полученные без какого-либо нарушения американских законов. Думаю для этого они отправили его, малой скоростью, в лабораторию ФБР и, возможно, далее.
Вдруг сообщники имеются, а доказательства полученные незаконным путём не могут быть представлены в суде, или типа того. А у них же куча всяких законов, а ля DMCA и прочих. Поэтому, ИМХО, нужон аутсорсинг, в Аппл, или в Израиле, да хоть в РФ.
Да, и тот, который 10, компиляторы хранят в 16 байтах.
Хм! Впрочем, и ожидания авторам меня немного порадовали.
Господи, переведу, есть три вида проблем при суммировании массивов (скалярных произведений и т.п.):
Сортировка - паллиатив, в простых общих случаях (неотрицательные числа и т.п.) математическому доказательству не подлежит, но частично помогает только для
trouble1, при небольших размерах массива (массивы реально больших размеров становятся похожи наtrouble2иtrouble2a).ИМХО, сложение деревом с векторизацией (block_pairwise_autovec) более перспективный паллиатив, тоже решает только один вариант из трёх, но как раз тот, который сравнительно часто встречается. Вероятно поэтому оно и реализовано в BLAS (<linalg>, C++26).
Аналогов,
math.fsum()или "крейта accurate", извините, на вскидку, не вспомню. Хотя как раз их доказывать, легко и приятно.P.S.
Да, для сложения деревом, я видел доказательства, что при некоторых странных предположениях, накопление ошибки будет логарифмическое.
Нет, не оговорка. Единственно, что, и сравнительно шустро, и более менее доступно в быту это расширенная точность. Просто Numpy её почти всюду в документации обозначает типом
np.float128и только в паре мест раскрывает его подлинное имяnp.longdouble. 😉Да IEEE 754 определяет тип
binary128(в новом стандарте C23 для него, ну наконец то, завели типfloat128_t), но его поддержка, на бытовом уровне, весьма и весьма ограничена и, чаще всего, программная, а не аппаратная (ну, кроме "монстров" SPARC, POWER и т.п.).Но процессор ж "по умолчанию" это ж x86_64. Как и исторически неплохая поддержка типов языка C
long double, Numpynp.longdouble(он жеnp.float128для x86_64, поскольку в памяти он занимает 16 байт или 128 бит) неплохая. Опять же пока более менее шустрая аппаратная реализация.Конечно, новые процессоры ARM, Nvidia GPU и т.п., уже весьма распространены, но пока ограничиваются
binary16/32/64.Ну, а если уж на ARM, Nvidia GPU брать программную реализацию четверной точности для вычислений, а не для ввода/вывода, то уж никак не
binary128/binary256от IEEE, а double-double и quad-double, которые построены на алгоритме Кэхэна и его производных.Злые языки говорят - спасибо АНБ. В 1979/1980, когда сделали MC68881/Intel 8087, оказалось, что один из возможных вариантов их использования - 64 битная арифметика (64 битный умножитель) на основе 80 битных плавающих чисел (binary80).
Сейчас эти binary80, обычно, хранят в 16 байтах.
ИМХО, под капотом
numpy.sum(), который суммирует деревом с блоками по 128 чисел, которые ещё разбиваются по 8 для SIMD, т.е. эффективно блок дерева ≈16 чисел.Ну, в деле словарей, возможно так удобнее. Хотя, по два, или большему числу непонятно.
Особенно в случае, преобразования
np.float32()вnp.float64()для усреднения и последующего обратного преобразования. После этого преобразования имеем, 29 запасных нулевых бит, если у нас 1024 числа, а усредняемые числа изменяются не более чем в 0.5*10⁶ раз, то после обратного преобразования, среднийnp.float32()будет корректным округлением точного результата.Вопрос философский, требующий конкретных оценок того, сколько бит надо. Есть вариант с
math.fsum(), который является развитием Коэхэна, но не с двумя накопителями, а до 39 (для произвольныхdouble, что бы обеспечить точное представление любой суммы, для данных полученых изnp.float32, накопителей никогда не будет больше 6).Сортировка - хреновый паллиатив, да она помогает в сравнительно редких случаях вида
[1, math.ulp(0.5), math.ulp(0.5)], но в гораздо более типичных случаях вида10*[1 + math.ulp(1)]уже не помогает, не говоря уж за[-1, math.ulp(0.5), 1](впрочем, этот вариант тоже сравнительно редкий).ИМХО, сложение деревом с векторизацией (block_pairwise_autovec) более перспективный паллиатив, тоже решает один вариант из трёх. Вероятно поэтому и он реализован в
numpy.sum().Ну, если недорого, то может и честный
, тоже не так дорого?
math.fsum(), со своимиОн же даёт оценку для некоторого конкретного алгоритма. А так, да, любые IEEE 754 binary32 могут быть представлены 280 битным целым, а binary64 - 2102 битными. Только вопрос удобства суммирования. У них, если для хранения мантисс используется int32, примерно один перенос на 512 операций (или 256, в зависимости от реализации бита переноса/заёма), типично, одно суммирование и сдвиг не требуется. У Вас переносы гораздо чаще и, типично, два-три суммирования в результате сдвига.
У второго упомянутого варианта, стандартного,
math.fadd(), для того же самого используется буфер, формально переменного размера, но не более чем из 39double. Точная накопленная сумма равна точной сумме элементов буфера, а переносы реализованы в стиле Кэхэна.Какие конкретно варианты шустрее, сразу не сказать, возможно зависят от архитектуры. Но теоретическая сложность у них одинаковая.
У алгоритмов типа скалярного произведения (взвешенной суммы), большая доля ресурсов уходит на обмен кэш L1 с памятью и/или L2/L3. А поэтому параметру древовидный способ проигрывает алгоритму Кэхэна примерно раза два.
Ни Вы (при обосновании потребностей), ни они (при создании тестовых наборов), не приводите чисел обусловленности:
Оценка относительной ошибки алгоритма Кэхэна:
Т.е. если Вы преобразовали
np.float32()вnp.float64(), а потом просумируете алгоритмом Кэхэна, то суммирование будет реализовано примерно с точностью 104 бита. Этого много, мало или достаточно?Альтернативный вариант - тупое суммирование
np.float128()с точностью 63 бита, может оказаться гораздо шустрее.Недавно, на Хабр был перевод "Укрощаем суммы с плавающей запятой" с некоторыми сравнениями. Не то, что бы зело профессиональный, но познавательный.
Как бы, конечно, Unix time понимают далеко лишь не все.
Но, похоже, что всё не так однозначно. Поскольку, у многих, одинаковые приложения TOTP одинаково успешно работают, и с Госуслугами, и с GitHub, и с PyPI (а может, иногда, и одинаково безуспешно, но, главное, что одинаково).
С моего дивана кажется, что проблемы были связаны с ПО телефона и/или особенностями оператора связи. Естественно, это тоже не точно, ибо по фотографии.
Так и да, увы, как оказалось там (RFC 6238) именно это и написано:
С ключевым словом MUST (признак нормативного требования) и со ссылкой на Википедии.
Но формулировка с гнильцой. Во-первых, полночь 1970 года измерялась не в UTC, а в GMT (UTC был в планах, но время по нему стали выдавать только через пару лет). Во-вторых, на настоящий момент, от `Jan 1 00:00:00 GMT 1970` прошло на 27 секунд больше, чем значение текущего UNIX time.
Вот почему они эти скобки на хрен не вычеркнули, причём в нормативном абзаце?! Грабли, голимые.
Охотно верю, но поскольку Вы пишите комментарии к статье под заголовком:
То, просто так вышло.
Слова "заметны" и "ближайшие", как выясняется, суть растяжимы есть. 😉
Но даже наше Солнышко раздует под 1 а.е. Так что при измерениях более менее типичных красных гигантов на уровне точности 5...7 микросекунд дуги их радиус будет немного мешаться на всём диапазоне расстояний вплоть до 150...200 кпк.
А в части крупнейших звёзд так и радиус 10 а.е. не предел. К примеру, у Бетельгейзе ≈ 4 а.е., но это неточно, поскольку точность её параллакса, пока едва едва вытянули на уровень 500 микросекунд дуги. Т.е. за счёт радиуса звезды возможна потеря точности на два порядка.
P.S.
Так и да, теперь это значение известно абсолютно точно. Всем просто надоел этот бардак не имеющий, ни физического, ни астрономического смысла. 😉
Но, на самом деле, измерительное, как и нормативное определение а.е. совершенно не влияло на измерения параллаксов (ну или вияло очень и очень слабо). К примеру, Леверье, или даже Эйнштейн (не специалист, конечно, но погружался в эту бодягу ради ОТО), легко смог бы вычислить орбиту Гайи со всей необходимой точностью.
Речь идёт о потерях на то, что потокобезопасный код всё равно захватывает и освобождает блокировки, даже если он, в данный момент, работает в один поток.
К примеру, вывод
print()или опрос/установка исключений плавающей запятой. Скажем, в коде NumPy есть примечательный комментарий: "мы сначала опрашиваем маску исключенийfegetexceptflag(), а потом устанавливаемfesetexceptflag(), если только нам нужна другая маска, поскольку опрос в 10-50 раз быстрее установки".Астрометрия имеет много гитик. Да, овал описываемый L2 примерно на 1% дальше земной орбиты, но эксцентриситет земной орбиты ≈ 0,017, т.е. заметно больше. Правда и Гайя не точно в L2, а бултыхается в её районе.
Не говоря уж, за то что наша Солнечная система движется ≈ 200 км/с, да и измеряемые звёзды на месте не стоят и, к тому же, имеют вполне себе заметные радиусы.
Хм, я сразу на капу нажал! В ответ на то, что "измерению поддаются 1% ближайших звёзд" (до Гипаркоса, действительно было где-то так), написал, что "1% только ближайших - это ж проблема прошлого века". 😉
Ну, вот Вы и ответили на сакраментальный вопрос автора "Но почему в России все в порядке?" На который он сам не смог чётко ответить.
К гадалке не ходи, если бы из РФ можно было бы оплатить подписку CrowdStrike, то и в РФ что-нибудь в эти дни массово упало бы. А так, в этот раз, пронесло, и слава Богу.
Хм, как бы наоборот. В Касперском не боги, а такие же люди. Так что, он вполне мог попасть в аналогичную ситуацию, но выглядела бы она так, что мама не горюй.
Думаю, одно другому не мешает. Они же говорят, что "некоторая" оперативная информация у них есть "удалось получить доступ к некоторым сообщениям...".
Но, когда дело дойдёт до суда или до досудебного соглашения с участием адвокатов и прочих законников, у них будут "легально" полученные и процессуально оформленные улики от Хуавей/Самсунг/Гугл/Аппл/.../Израиля/Австралии/... , в общем, полученные без какого-либо нарушения американских законов. Думаю для этого они отправили его, малой скоростью, в лабораторию ФБР и, возможно, далее.
Вдруг сообщники имеются, а доказательства полученные незаконным путём не могут быть представлены в суде, или типа того. А у них же куча всяких законов, а ля DMCA и прочих. Поэтому, ИМХО, нужон аутсорсинг, в Аппл, или в Израиле, да хоть в РФ.