LINUX.ORG.RU

Длинная математика в rust

 


0

3

Господа растафарианцы, расскажите пожалуйста, если какой-нибудь крейт для раста с длинными числами вроде Integer в хаскеле? Которые неатомарные, но никогда не переполняются? Я чет не могу ничего нагуглить кроме i128. Это, конечно, длинный тип, но конечный, а потому не подходит.

★★★★★

если какой-нибудь крейт

Вся суть разработки на русте.

ЗЫЖ. Юзал из OpenSSL,

anonymous
()
Ответ на: комментарий от anonymous

Ты так говоришь как будто в этом есть что-то плохое

AntonyRF ★★★★
()
Ответ на: комментарий от intelfx

привычнее в гугл.
мне, когда нужно было, я нашел их штук 5 разной степени готовости. и это за минуту

рустоманы не умеют в поиск, это и по их телеграммчикам понятно.

Ну и на любой мелкий чих ищут крейт, даже там, где код писать минут 5.

anonymous
()
Ответ на: комментарий от anonymous

Мне кажется это скорее камингаут у них такой. Лишний ровод упомянуть раст в инфошуме. Эдакие кодер-веганы. :)

anonymous
()
Ответ на: комментарий от hateyoufeel

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

anonymous
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от Siborgium

Т.е. судя по описанию "стринги, используемые в проекте (a/b/c), у них уже в каждом проекте можно сказать своя реализация строк? Мухаха.

anonymous
()
Ответ на: комментарий от anonymous

дык дело делать скучно и трудно. А лисапед, да побегать по проектам с «have you considered rewrite ___ in rust?» – легко и весело)

P.S. После появления такой должности в этом вашем айти как «Евангелист», думаю давно пора ввести - «Овцы».))

anonymous
()
Ответ на: комментарий от anonymous

Вся суть разработки на русте

Если ты под каждую типовую изобретаешь велосипед, то ты не очень хороший инженер

Aswed ★★★★★
() автор топика
Ответ на: комментарий от anonymous

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

Siborgium ★★★★★
()
Ответ на: комментарий от Aswed

Если ты под каждую типовую изобретаешь велосипед

Ну у тебя же не типовая. Иначе зачем раст? Типовую можно на скриптах писать.

cloun1902
()
Ответ на: комментарий от cloun1902

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

Aswed ★★★★★
() автор топика
Ответ на: комментарий от Aswed

Ты так говоришь, будто скрипты это что-то плохое

Нет, почему. Наоборот, для типового самое то.

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

ок.

cloun1902
()
Ответ на: комментарий от anonymous

в стандартной библиотеке языка, которая безальтернативно уделывает любую другую реализацию.

такое бывает только в сказке

seiken ★★★★★
()
Ответ на: комментарий от anonymous

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

anonymous
()
Ответ на: комментарий от Aswed

У меня ещё и все зависимости завендорены, чтоб каргогавно не тянуть.

anonymous
()
Ответ на: комментарий от anonymous

где код писать минут 5

Продемонстрируешь написанную тобой за 5 минут длинную математику? Мы посмеемся.

trex6 ★★★★★
()
Ответ на: комментарий от anonymous-angler

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

t184256 ★★★★★
()
Ответ на: комментарий от anonymous

Ну да ну да.

Я тут как-то один модулёк вычислительный, тупо конвертнув с помощью f2c и чутка поправив извращения с индексами после f2c, ускорил раза этак в полтора.

Так что нихрена он давно уже не заточен.

Тру-ультра-хардкор всё-таки уж лучше на сишечке с плюсами писать. Ну или на Расте, если хочется нового.

А Фортран ценен только тем, что во времена оные на нём 100500 тонн строк кода было написано, которые никто переписывать не собирается, но поддерживать их надо.

WatchCat ★★★★★
()
Ответ на: комментарий от trex6

ты поехавший чтоль? где там про математику за 5 минут? там за «любую проблему, где решение за 5 минут» было. Хотя чего это я. рустомане не умеют читать же. им для этого крейта не завезли

anonymous
()
Ответ на: комментарий от WatchCat

поправив извращения с индексами

Они там изначально вообще в правильном порядке использовались? Первый индекс быстрее меняется.

Для фортрана обычно достаточно хорошие оптимизирующие компиляторы. Процентов в 10% выигрыша на временах больших миллисекунд легче поверить, т.к. на мелких слишком большие погрешности.

которые никто переписывать не собирается

И правильно, нечего переписывать то, что работает. За переписывание денег никто не заплатит.

grem ★★★★★
()
Ответ на: комментарий от grem

Они там изначально вообще в правильном порядке использовались?

Ты видать никогда не смотрел выхлоп f2c. Там заводится отдельный указатель на -1 от оригинального массива и испорльзуется без изменения индексации, т.к. в фортране индексация с единицы, а не с 0.

Т.е. int a[]; int* b = a - 1; b[1] = 5; (грубо говоря).

И вот в таком случае не факт, что оптимизатор нормально отработает.

Ну и я опускаю случай двумерных массивов, т.к. там то ещё извращение получается.

Они там изначально вообще в правильном порядке использовались?

Ага, проще железа на 100500 килобаксов купить.

WatchCat ★★★★★
()
Ответ на: комментарий от t184256

Нет, не лучше. Тащить библиотеку с кучей разного ненужного (e.g. если тебе нужны только безразмерные рациональные числа, то вся остальная OpenSSL тебе не нужна) и под несколькими лицензиями - какой-то оверкилл.

Это проблему решили крейты: куча мелких компонентов.

ИМХО, многие не так смотрят на проблему гор мусора на crates.io. Когда чего-то нет и вдруг оно становится востребованным, то все бегут изобрести велосипед, да, такого там много. Но из всех велосипедов выживает только тот, который оказался лучшим, может парочка. И дальше изобретай - не изобретай, но выпереть лидера из ниши будет либо тяжело, либо невозможно.

  1. Было когда-то несколько способов сериализовывать данные - да, теперь из живых остался только serde и бэкенды.
  2. Былы десятки крейтов, которые позволяли определять enum-ы ошибок. Упокоились. Потому что изобрели thiserror и anyhow.
  3. Есть, как где-то в треде упомянули, крейты со слегка разными строками, где-то с интернингом, где-то с CoW. Но кто это использует? Правильно - почти никто. Ни разу ещё не встречал ситуации, где бы мне приходилось использовать что-то помимо стандартных строк.
  4. Были попытки изобрести что-то для data parallelism. Умерли. Все используют rayon.

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

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

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

anonymous-angler ★☆
()
Ответ на: комментарий от WatchCat

Ну и я опускаю случай двумерных массивов, т.к. там то ещё извращение получается.

Я как раз про это, так как при конвертации циклы должны быть вывернуты наизнанку. Если были правильно записаны.

Ты видать никогда не смотрел выхлоп f2c.

Нет. Зато как-то переписывал какую-то разностную схему с дельфи на c++, где были вложенные циклы по 3 индексам, которые друг из друга вычитались. Вот тут веселье было при учёте, где нужно единичку вычесть, а где уже нет.

grem ★★★★★
()
Последнее исправление: grem (всего исправлений: 1)
Ответ на: комментарий от grem

так как при конвертации циклы должны быть вывернуты наизнанку.

И это тоже. Но f2c это делает тупо, но извращённо. Т.е. да, он сохраняет поведение, чтобы не пролюбить индексацию, но как мне показалось, сишечный компилятор не может в нормальную оптимизацию на том коде.

И как в итоге f2c->руки->gcc оказалось быстрее gfortran. Sad but true.

Зато как-то переписывал какую-то разностную схему с дельфи

О-о-о, паскалеизвращения. Ну, так-то я ничего не имею против Паскаля как исторического языка, но переводить с него на сишечку примерно то же, что и с фортранчика, да.

WatchCat ★★★★★
()
Последнее исправление: WatchCat (всего исправлений: 1)
Ответ на: комментарий от grem

О-о-о, мсье познал вкус истинного извращения.

WatchCat ★★★★★
()
Ответ на: комментарий от anonymous-angler

Былы десятки крейтов, которые позволяли определять enum-ы ошибок. Упокоились. Потому что изобрели thiserror и anyhow.

Или failure и snafu? (:

P.S. Сам использую thiserror и anyhow, но не уверен, что это финальная итерация. Да и не все проекты ещё слезли с error_chain и чего-то там ещё.

DarkEld3r ★★★★★
()
Ответ на: комментарий от anonymous-angler

Были попытки изобрести что-то для data parallelism. Умерли. Все используют rayon.

crossbeam еще тоже живой, хотя они не слишком пересекаются.

anonymous
()
Ответ на: комментарий от anonymous

Они вообще не пересекаются

anonymous
()
Ответ на: комментарий от DarkEld3r

failure было до фикса std::error::Error и до thiserror с anyhow. Оно, в общем то, мертво.

Про snafu слышу впервые.

Я думаю, что финальная. Тому есть объяснение: std::error::Error привели в порядок, а thiserror и anyhow, строясь на std::error::Error покрыли 2 основные потребности: легко определять свои типы ошибок и dynamic dispatch ошибок.

anonymous-angler ★☆
()
Ответ на: комментарий от t184256

Уточню, ты говоришь, что писать несколько небольших компонентов, решающих одну задачу каждый, всем человечеством, - хуже, чем писать один большой монолит, не влезающий в каждую нишу и вынуждающий плодить велосипеды? Logik.

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

anonymous-angler ★☆
()
Последнее исправление: anonymous-angler (всего исправлений: 1)
Ответ на: комментарий от anonymous-angler

Ну давай, сколько в мире хорошо оттестированных, и много кем отревьюенных либ для constant-time execution long math?

t184256 ★★★★★
()
Ответ на: комментарий от t184256

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

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

Ну и ещё то, что написание с нуля, например, такой отдельной реализации с помощью другого инструмента может помочь человечеству наконец запилить нормальную реализацию. Именно может позволить, а не однозначно позволит, понимаешь?

Далее, как ты себе представляешь O(1) в случае с безразмерными числами? Это ведь даже в теории невозможно.

anonymous-angler ★☆
()
Последнее исправление: anonymous-angler (всего исправлений: 1)
Ответ на: комментарий от anonymous-angler

Могу перефразировать: чем лучшая из написанных реализаций, вынесенная в отдельную библиотеку, хуже этой же реализации в составе бОльшего проекта?

Тем, что она by definition непопулярная и незрелая.

Правильно - ничем. Это я тебе и пытаюсь донести.

Неправильно.

Далее, как ты себе представляешь O(1) в случае с безразмерными числами? Это ведь даже в теории невозможно.

Отлично, через задание максимального размера на время операции. Длинная математика не значит безгранично резиновая, TLS-соединение все-таки за конечное время надо бы установить =D

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Тем, что она by definition непопулярная и незрелая.

Т.е. если, например, разработчики OpenSSL вынесут популярную и зрелую реализацию в отдельную библиотеку, сделав её зависимостью, то она внезапно станет непопулярной и незрелой?

Logik x2. Серьёзно, что это за дичь?

Неправильно

Да нет, правильно. Монолиты можно и нужно делить.

Отлично, через задание максимального размера на время операции. Длинная математика не значит безгранично резиновая, TLS-соединение все-таки за конечное время надо бы установить =D

Ну задал ты максимальный размер, окей. Те же рациональные степени, упомянутые выше, как ты будешь считать за O(1)? Подскажу - никак. А TLS-соединение устанавливается не за O(1), да и OpenSSL содержит криптографию далеко не только касательно TLS-соединений. Помнится их софтом ещё и ключи можно генерировать, по несколько десятков минут.

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

Т.е. если, например, разработчики OpenSSL вынесут популярную и зрелую реализацию в отдельную библиотеку, сделав её зависимостью, то она внезапно станет непопулярной и незрелой?

Logik x2. Серьёзно, что это за дичь?

Лютая, полная, твоя. Я тебе про новые модноязычковые реализации, ты мне про ребрендинг старой.

Ну задал ты максимальный размер, окей. Те же рациональные степени, упомянутые выше, как ты будешь считать за O(1)? Подскажу - никак.

Думай дальше.

А TLS-соединение устанавливается не за O(1).

Подсказка: За конечное время устанавливается? Значит и за O(1) можно.

да и OpenSSL содержит криптографию далеко не только касательно TLS-соединений. Помнится их софтом ещё и ключи можно генерировать, по несколько десятков минут.

Вот это откровение, а то я не знал.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Лютая, полная, твоя. Я тебе про новые модноязычковые реализации, ты мне про ребрендинг старой.

Я тебе про разделение монолитов, ты мне - про переписывание. Впрочем, раз ты хочешь про новые языки, ок. Ещё раз повторю: из того что всё человечество не может написать нормально что либо на языке X, не следует ровным счётом ничего относительно переписывания на языке Y.

Думай дальше.

Уже.

Подсказка: За конечное время устанавливается? Значит и за O(1) можно.

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

Вот это откровение, а то я не знал.

То есть знал, но преднамеренно упомянул частный случай - соединение, который всё равно ни разу не O(1). Двойной провал :D

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

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

Сам погугли, позоришься же. Для чего ещё невозможен в твоём мире constant-time execution? И O(сколько) оно у математиков твоего измерения?

t184256 ★★★★★
()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от t184256

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

https://en.wikipedia.org/wiki/Time_complexity

Все эти «длинные» числа внутри разбиты на те единицы, которые машина способна считать за O(1) - например N * uint64. Поэтому даже у bit-wise операций будет сложность O(N), не говоря уже о более сложных вещах, вроде возведения в рациональную степень, где будет что-то сильно большее, чем O(N).

Если тебе до сих пор голоса в голове говорят, что там O(1), передай им что два «длинных» числа могут иметь разную длину и осознай уже наконец, что даже сложность какого-нибудь сложения будет зависить от длины, поэтому там никак не может быть O(1).

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

Все эти «длинные» числа внутри разбиты на те единицы, которые машина способна считать за O(1) - например N * uint64. Поэтому даже у bit-wise операций будет сложность O(N)

Стой, стой, стой, остановись, твои голоса то ли матан проспали, то ли не ту статью открыли. Прочитай https://en.m.wikipedia.org/wiki/Big_O_notation, прими, что O(100500) = O(1). Потом расскажи мне, где у тебя в компе применяемый для криптографии АЛУ, который делает побитовые операции за O(N). Потом продолжим, а то дальше пока нет смысла даже соваться.

t184256 ★★★★★
()
Ответ на: комментарий от anonymous-angler

Если есть цикл, то есть и какая-то повторяющаяся элементарная операция. Ещё один пруф что там ни разу не O(1).

for i in 0..100:
    print("раздуплись")
print("где я говорил, что в openssl успешно реализована constant-time long math?")
t184256 ★★★★★
()
Ответ на: комментарий от t184256

Явно не говорил, но это ответ в ветке комментариев, где эталонным примером был OpenSSL, и в которой ты топишь за то, что не нужно ничего менять.

Окей, окей, я притормозил.

Вообще, я с тобой частично соглашусь. Если ты подразумеваешь что все «большие» числа, участвующие в операции, имеют фиксированную размерность, то это можно считать O(1). Если их размер неопределён - это не O(1). При этом вычисление какой-нибудь рациональной степени может быть или не быть O(1), в зависимости от того, является ли желаемая точность константой или нет, и являются ли числа «безразмерными» или нет.

Окей, в случае с криптографией я недостаточно компетентен, что бы сраться дальше.

Впрочем, хрен с ним. Ты же согласен, что не каждая реализация «long math» может быть «constant-time execution», что это будет работать только с большими числами фиксированной длины? Если да, то срач можно считать законченным.

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

Окей, тот срач закрываем.

эталонным примером был OpenSSL, и в которой ты топишь за то, что не нужно ничего менять.

Хехе, поверь, OpenSSL не идеален и менять его надо. Если б был идеален, наш отдел бы небось весь сократили.

Теперь остался маленький тезис, который я походу плохо донес: openssl суть очень популярная реализация криптографии. Даже в ее лице «человечество вместе взятое нормально написать не может» некоторые тонкие вещи типа constant-time long math. Что будет, если каждому rustу дать волю писать свою криптографию (реализацию TLS, менеджер пакетов…)? Язычково-локальная недоделка. И неважно, что «на ту сотню крейтов умрет, реально все юзают только один». Это на один больше, чем и так все плохо. На один на каждый язык.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Что будет, если каждому rustу дать волю писать свою криптографию (реализацию TLS, менеджер пакетов…)? Язычково-локальная недоделка. И неважно, что «на ту сотню крейтов умрет, реально все юзают только один». Это на один больше, чем и так все плохо. На один на каждый язык.

Это всего лишь догадка. Давай не будем брать Rust, это мешает объективности. Вообразим что появился новый, модный, стильный, молодёжный язык X. О свойствах этого языка нам ничего неизвестно. На нём пишут альтернативу OpenSSL, к счастью или сожалению. Почему эта альтернатива по твоему мнению обязательно должна быть «язычково-локальной поделкой» и не может вытеснить OpenSSL из ниши? Почему ты считаешь, что что у неё нет даже шанса стать чем-то лучше OpenSSL?

anonymous-angler ★☆
()
Ответ на: комментарий от anonymous-angler

Шанс есть, просто пренебрежимо малый. Чтобы приблизиться к OpenSSL по качеству кода, надо, чтобы интеграл от количества людей, пишущих на этом NeoLang’е, помноженный на долю NeoLangистов, занимающихся именно NeoSSL от начала написания NeoSSL до текущего момента стал сопоставим с аналогичным значением на C. Ну или произошёл качественный сдвиг и языковые поделки начали применяться за пределами языковой экосистемы, а на эту тему пока видны одни лишь ложные надежды.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Ну, тут соглашусь наверно. Не думаю что в ближайшие лет 10 мы увидим как какой-нибудь «NeoSSL» занимает нишу OpenSSL. ИМХО, для такого перехода нужен катализатор, вроде Heartbleed, и что бы NeoSSL уже лежала готовой выстрелить.

anonymous-angler ★☆
()
Последнее исправление: anonymous-angler (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.