Comments 39
Что такое? Работа с большими числами, AKA длинная арифметика — хорошо изученная тема. Большинство операций выполняются тупо в столбик, хотя есть всякие хитрые алгоритмы вроде карацубы, FFT для умножения и логарифмического возведения в степень, но все уже давно реализовано в библиотеках, в тех же криптографических, например. В java вообще есть BigInteger встроенный, правда там произведение втупую сделано, но для многих задач хватит и его.
В Питоне вообще все из коробки, даже по-моему никакого специального типа не нужно. Это очень полезно - изучать хорошо кем-то раньше (но не тобой) изученные темы. А потом сделать свою рубаху, которая, как известно, ближе к телу.
Я бы хотел более развернуто пояснить свою мысль о том, когда именно я слышу щелчок затвора. Я не слышу его, когда, например, вижу как кто-то использует стандартные криптографические библиотеки (еще и с одобренными алгоритмами). Я не вижу в этом опасности. Так же как я не вижу опасности в том, что кто-то в Apache настраивает протокол https. Но если этот же самый человек начнет интересоваться что там под капотом, что там происходит в ассемблерных вставках и куда девается бит переноса, то это уже гораздо интереснее.
Если еще привести похожий пример из другой области. Высокочастотных трейдеров мало волнуют люди, которые пытаются играть на бирже через стандартные интерфейсы, использующие стандартные методы анализа и получающие информацию через стандартные каналы. Они не обращают на это никакого внимания. Их больше волнует, когда кто-то начинаем мутить свои протоколы с низкой задержкой, эффективные ни на что не похожие методы кодирования финансовой информации и подбираться ближе по времени и расстояниям к реальным данным. Ну и конечно алгоритмы трейдинга каждый пытается придумать свои.
Если честно, мысль не до конца понятна.
Но если этот же самый человек начнет интересоваться что там под капотом,
что там происходит в ассемблерных вставках и куда девается бит
переноса, то это уже гораздо интереснее.
Почему? Вы
чувствуете интерес, потому что копание под капотом интереснее привычных тем?
чувствуете опасность, потому что кто-то может наломать дров со своим велосипедом (см "вы опасно некомпетентны в криптографии")
чувствуете опасность, потому что, если возникла потребность лезть под капот, вероятно, лезущий делает что-то не так/решает не ту проблему/не так?
???
Любая тема - это копание под капотом - иначе вы будете дилетантом.
Действительно, есть мнение, что разрабатывать свои криптографические алгоритмы - попросту невозможно, потому что даже то что разработано самыми выдающимися математиками часто не проходило проверку практикой и временем. А уж то что на коленке разработает студент - это явно будет уязвимо. Но все зависит от ситуации. Взять, например, принцип что успех шифрования не должен зависеть от того, что неизвестен или обфусцирован алгоритм. Но это верно для разработки длительных по времени стандартов. Если цель поделки - продержаться три дня, то здесь любая нестандартная поделка будет лучше стандартного алгоритма. Пока все антивирусы щелкают клювом, пытаясь понять, что это такое - работа будет уже сделана. Я поясню мысль некоей аналогией: двигатели для самолетов с ресурсом 40000 часов делаются совсем по другому, чем двигатели для ракет с ресурсом 3 часа. А запустить что-то на опасную для всех высоту может даже школьник, если прочитает пару учебников.
К сожалению, сейчас мы имеем дело с индустрией сложных вещей, когда лезть под капот не имеет смысла, а иногда даже и опасно. Если раньше можно было продуть карбюратор, то сейчас в инжектор лучше не соваться. Вот зачем ты под капот залез - наверное ты не правильно свою машину эксплуатировал - вовремя масло не залил, техобслуживание не прошел. Но в связи с последними событиями все стали как-то по новому смотреть на чудаков, ездящих на ладах-шестерках и имеющих в гараже небольшой токарный и фрезерный станок.
В любом случае спасибо за эти вопросы - Ваша позиция тоже верна и я конечно ее разделяю - особенно в промышленной разработке.
Судя по вашему посту, вы считате что в длинной арифметике есть какие-то неочевидные подводные камни, о которые новички могут споткнуться и выстрелить себе в ногу. Ну приведите хотя бы парочку.
Если не брать хитрых алгоритмов вроде fft, которые и так релизуются по статьям и гайдам или берутся из библиотек, если оно надо, то дальше там остается только два вопроса — производительность и переполнение. Самое тупое решение с хранением одной десятичной цифры в ячейках массива 32-битных чисел будет не самым эффективным, но будет работать всего лишь в несколько раз медленнее самого продвинутого решения. И никакого переполнения там быть не будет. Это сможет без ошибок написать даже школьник, изучающий программирование.
А вот дальше уже ассемблерные вставки и обработка битов переноса — это то, что называется микрооптимизациями. Чем глубже закапываешься, тем сложнее получается без ошибок выжать еще пару процентов производительности. Но это не идет в моем понимании как "неочевидные подводные камни". И максимум, что новичек сделает — это получит в 2 раза более медленный код. Не очень приятно, но на выстрел в ногу не идет. Это не в 1000 раз медленнее из-за незнания алгоритмов.
Наоборот, если кто-то интересуется этой темой пусть и у них есть время это делать, вместо использования готовой библиотеки, то пусть развлекается. Надо только сказать "помни про переполнение" и может потом подсказывать "а вот если хранить не десятичные цифры, двоичные, то процессору быстрее будет их ворочать", "а вот тут можно SIMD инструкциями сделать", "а ассемблерная вставка сама может и сложить и перенос получить".
Похожая на вашу точка зрения есть про криптографию "Если вы не большой специалист по криптографии, никогда не пишите собственную криптографию". Тут оно оправданно, потому что с большой вероятностью новичок получит не чуть менее производительный код, а не выполняющую свою цель криптографию (которую сколько-нибудь подкованный злыдень легко взломает). Но что не так с длинной арифметикой — мне не понятно.
Вы немного не поняли, смысл моего поста. Смысл в том, что если я вижу, что кто-то самостоятельно мутит в ассемблере целочисленную арифметику, то это неспроста. Я ничего не говорю о том, получится у него это, не получится, сможет он превзойти стандартные решения - не сможет - по большому счету это неважно. Я просто понимаю, что он что-то затеял. Здесь почему-то поняли, что я на стороне этих людей. Я то как раз согласен со всеми - если вы добропорядочный гражданин - нефиг вам в ассемблер лезть, та еще с мутными темами. Фигачьте на Яве - все уже разработано. Как пел Высоцкий - "Так держать - колесо в колесе - и доедешь туда куда все" :).
если вы добропорядочный гражданин — нефиг вам в ассемблер лезть, та еще с мутными темами.
Если кому-то это интересно — милости просим. Тем более в такой безобидной теме, как длинная арифметика. Тем более, для быстрого возведения в степень и других алгоритмов длинной арифметики не надо даже ассемблерных вставок. Повторюсь, рабочее решение напишет даже изучающий программирование школьник. И оно будет лишь в в 10 раз проигрывать лучшим решениям в мире. Программист со стажем и минимальным пониманием как устроен процессор сможет написать решение, уступающее лучшим в мире лишь считанные проценты в эффективности.
Ваша мысль звучит как "длинная арифметика — не всем дано. Это для избранных и очень умных людей". Опять же, это правда про криптографию, но не про длинную арифметику. Или у вас так вообще про все? Коллега спросил: "а как найти путь в графе быстро?" — вы напряглись. Коллега спросил: "как перемножить матрицы?" — вы напряглись. Коллега спросил: "как пересечь две окружности?" — ...
Что такого именно в длинной арифметике?
Да, теперь понял. Спасибо. Я поясню. Сначала скажу, что этот случай не придуманный, а что называется основан на реальных событиях. И вопрос звучал именно так - как возводить в степень большие числа. Любой, кто немного в теме, знает, что это делается для проверки чисел на простоту, ну и потом непосредственно для самого асимметричного шифрования. Других разумных применений всему этому нет. Конечно я напрягся. Но насчет асимметричного кодирования я ошибся - коллеге нужны были только тесты на простоту. Вот собственно о чем пост. Если вы найдете еще какое-нибудь разумное практическое (не академическое) применение многозначной арифметики - то прошу мне сообщить. Если бы меня спросили про графы или геометрию, я бы удивился, но такого эффекта это на меня бы не оказало.
Я сразу скажу, что я вообще не специалист в криптографии, но я кое-что читал, и решая некую олимпиадную задачу мне пришлось реализовывать многозначную арифметику. Никаких Java-библиотек и Питонов тогда не было. Был только TurboС++ на дискете. И конечно там ничего особо сложного. Любой справится. Тем более что системы команд популярных процессоров и их арифметические устройства СПЕЦИАЛЬНО СПРОЕКТИРОВАНЫ для поддержки многозначной арифметики.
Моя мысль не в том что это для избранных, а прямо противоположная - что это слишком доступно - просто нужно задаться целью. Скажите, что сложного в огнестрельном оружии - просверлить дыру и насыпать туда пороха.
Спасибо, теперь и я вас понял. К такой позиции никаких претензий не имею.
У меня возникло еще пара мыслей по поводу того - многозначная арифметика для избранных или нет? Мы тут с Вами допустили одну небольшую неточность. Мы рассматривали только множество программистов - но программисты это очень небольшая часть общества. Возьмите любого человека не имеющего отношения к программированию и попробуйте что-то ему объяснить, хотя бы про двоичную систему счисления. И интересно, сколько времени пройдет, прежде чем он что-либо полезное напишет между begin и end. Вы рассматриваете свои способности, как нечто само собой разумеющееся.
Не секрет, что программистов не хватает, как не хватает сейчас и микрочипов. В школах существуют обязательные предметы информатика и математика. Всех тащат за уши в ИТ. Но программистами становятся единицы.
Я не говорю, что программисты - высшая каста. Все те же рассуждения можно применить и к врачам и к инженерам и к деятелям искусства, и конечно, к ученым. У каждого свое призвание и своя зона ответственности в этом непростом мире. И у каждого свой щелчок затвора. Например для химика будет очень подозрительно если в кто-то в отделе бытовой химии купит что-нибудь в какой-нибудь опасной пропорции.
От компьютеров может исходить большая опасность, так как они сейчас везде. Вот я сижу тут. Мало того что в карманах моих штанов наверное с десяток различных процессоров, а если посмотреть по сторонам, то сотня наберется.
И кроме нас опасности, связанные с ИТ-технологии никто не распознает. Поэтому надо внимательно вслушиваться в двоичную тишину. Кроме нас некому.
Если вы найдете еще какое-нибудь разумное практическое (не академическое) применение многозначной арифметики
Вычисления с большей точностью, чем 64-80-128 бит. Тот же BigDecimal в Java основан на BigInteger. Также (редко, но) встречаются задачи, когда целочисленные вычисления требуют разрядности большей, чем 64 бит. Например, 66 бит. И тип данных long уже не подходит.
Ну и из статьи не совсем понятно, что хотел от вас коллега: спросить алгоритм умножения, или о языковых средствах, реализующих работу с большими числами.
Что касается алгоритмов умножения/деления или быстрого возведения в степень. То я бы не сказал, что там всё так просто. Алгоритмов много. У каждого своя специфика. Один быстрый, но уязвимый к атакам по побочным каналам связи. Другой медленный, но стабильный.
Вы правы, я и пытался тут сказать, что везде все не так просто - постоянно нужно думать головой, а если хочешь каких-то выдающихся результатов - то своей головой (учитывая конечно лучшие мировые практики)
Коллега искал простые числа. Работа требует ресурсов. История такая же как с майнингом биткоина - нужно где-то брать электричество и вычислительные мощности. И любая, пусть даже самая незначительная оптимизация - это небольшой шаг вперед. Здесь говорили, что можно, например без ассемблера, на стандартных типах или даже в символьном виде. Конечно серьезных людей это не устраивает. Тут получается не в разы медленнее а в десятки раз.
Коллега, конечно, знал как возводятся большие числа. И у него все работало. Но пара моих советов ему помогли. Как говорится одна голова хорошо, а две лучше.
Еще решил ответить про числа, превышающие разрядность процессора. Действительно, есть случаи, когда 64 бита мало. Кроме того есть экзотические типы типа денежный. В связи с всеобщей инфляцией и триллионными долгами государств, там вообще непонятно сколько разрядов нужно :). В Oracle например, есть тип Decimal. Я не знаю, что там под капотом, но в описании типа можно указать очень большое количество разрядов.
Вы должны согласиться, что это все-таки не полноценная многозначная арифметика. Конечно, в посте есть некоторое преувеличение, когда сказано - сделать что-то превышающее разрядность процессора.
Но аппетиты приходят во время еды - сначала просто два числа сложил, потом три... Как говорится, я просто взял краcки в руки и тут как закрутилось :)
Ваша фраза про ассемблер просто зделала мне день.
Аж олдскулы свело.
Спасибо.
Последнее время я живу, как в летаргическом сне…Лютый флешбек из фильма Drive 1997 с Марком Дакаскосом.
Но когда мне становится известно, что кто-то хочет что-то сделать с целыми числами, превышающими разрядность процессора (пусть даже просто сложить), я отчетливо слышу этот незаметный для всех щелчок затвора.
"Щелчок затвора" - думал будет что- нибудь про фотографию.
Но когда мне становится известно, что кто-то хочет что-то сделать с целыми числами, превышающими разрядность процессора (пусть даже просто сложить), я отчетливо слышу этот незаметный для всех щелчок затвора.
Красивые, нестандартные вопросы всегда вызывают интерес, это тем более логично для программиста-профи, разумеется на них сразу же ищется ответ — это ж вызов :)
Кстати, про возведение в степень: все ведь не так просто даже для обычных целых чисел. Есть «классический» алгоритм быстрого возведения через умножения по степеням двойки, но проблема в том, что он не дает минимальный по действиям (умножениям и месту для хранению промежуточных результатов) результат. А вот поиск такой минимальной последовательности действий есть непростая задача, и я не смог придумать ничего лучше оптимизированного перебора. Есть и более простая похожая задача про быстрое умножение на константу через сложения и сдвиги, но там решения более-менее известны.
А вот поиск такой минимальной последовательности действий есть непростая задача, и я не смог придумать ничего лучше оптимизированного перебора
Доказано, что эта задача — NP-полная, en.wikipedia.org/wiki/Addition-chain_exponentiation:
related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete
Когда доказано, что задача NP-полная, именно тут-то и нужно засучивать рукава исследовать различные частные случаи и эвристические оптимизации. В посте я упомянул про поиск последовательных простых чисел. Если бы это делалось надежно какой-нибудь стандартной библиотечной функцией в обозримое время, то конечно такого бы соревнования не было. А так - бери в руки то что больше нравится, Яву, Питон, Ассемблер, Пролог - и вперед.
Моя любимая задача из детства: 9^9^9! Кто считал? Как сейчас помню, число из 369693100 цифр.
Не может быть, само 9^9 = 387420489. А тут в эту степень возводиться 9. Почти что 10, а 10 в этой степени будет как раз столько знаков. Вот и получается, что там более 300 миллионов цифр.
Кстати,! там — это не факториал там. Иначе там было бы гораааааздо больше цифр.
Плохо посчитал)
Неа, если в надстрочной нотации, то вычисления надо проводить сверху вниз, 9^9^9=9^(9^9).
9^9^9! Кто считал?
А я в уме посчитать могу. 9^9^9=9 :) (На "C" - "^" это "xor")
Сейчас надо посылать в сторону Googology Wiki И не считать, нет - это начиная с конца Class 2 бесполезно. Проверять себя надо тем, как далеко ты продвинешься, пытаясь понять, что именно считается. Т.е. что такое какое-нибудь TREE[3] и насколько именно оно большое?
Написано здорово и очень интересно читать. Но, мало :) Автор пишите еще, у Вас здорово получается!
Щелчок затвора