Сижу, как обычно в офисе, работаю. На экране ничем не примечательный код. За окнами муторный темный февраль. Скукотища… Сзади подходит руководитель соседнего подразделения и как-то буднично спрашивает:
— Миша, не знаешь, как возводить в степень большие числа?
Делаю вид, что ничего не случилось. Руки по-прежнему лениво перебирают по клавиатуре, взгляд рассеянно блуждает по экрану. Но внутри до предела натянулась невидимая нитка сознания. Я тоже буднично спрашиваю:
— Насколько большие?
Вспоминается отрывок из одного боевика. Супергерой отдыхает после многодневного бессонного утомительного задания, в течение которого он пару раз спасает мир от неминуемой гибели. Происходит это, как водится, в одной придорожной гостинице. Как водится, рядом с ним в постели красивая девушка. Но наш герой по причине огромной усталости на девушку не обращает внимания и засыпает на полтора дня мертвым сном.
Девушка с таким раскладом не согласна, ей нужно сообщить ему что-то важное. Спустя некоторое время она решает его разбудить. Трясет его за плечи, бьет по щекам, поливает холодной водой, тыкает острыми предметами – все безрезультатно.
Но вот к номеру подкрадывается наемный убийца. За пятьдесят метров до двери он осторожно достает пистолет и едва слышно передергивает затвор. Наш герой мгновенно открывает глаза, и в них нет даже малейшего намека на сон или усталость...
Последнее время я живу, как в летаргическом сне. Многоэтажные SQL-запросы, HTML-шаблоны и прочие ИТ-погремушки пишутся практически не приходя в сознание. Из этого состояния меня не могут вытащить ни премии, ни тимбилдинг, ни мотивирующие семинары, ни прочие пляски с бубнами различных корпоративных шаманов. Но когда мне становится известно, что кто-то хочет что-то сделать с целыми числами, превышающими разрядность процессора (пусть даже просто сложить), я отчетливо слышу этот незаметный для всех щелчок затвора. Математика – это самое грозное оружие. Я понимаю, что кто-то выковывает себе меч. А может меч выкован и уже занесен.
Та история закончилась благополучно. Есть такой вид математического спорта – поиск последовательностей равноотстоящих друг от друга простых чисел. Это целый свой мир со своими правилами и законами. Я был рад что помог моему коллеге парой советов по многозначной целочисленной арифметике.
Но все могло выйти совсем по-другому… Не расслабляйтесь.
Комментарии (39)
Oz_Alex
28.04.2022 15:50+2Последнее время я живу, как в летаргическом сне…
Лютый флешбек из фильма Drive 1997 с Марком Дакаскосом.
Но когда мне становится известно, что кто-то хочет что-то сделать с целыми числами, превышающими разрядность процессора (пусть даже просто сложить), я отчетливо слышу этот незаметный для всех щелчок затвора.youtube с таймкодом
Rumidu
28.04.2022 16:02+7"Щелчок затвора" - думал будет что- нибудь про фотографию.
0xd34df00d
28.04.2022 19:21+1Конечно про фотографию. Кто ж в быту носит оружие с недосланным патроном?
headfire Автор
28.04.2022 19:48Правильно, если что задумал, лучше об этом ни с кем не советоваться и ничем не щелкать на людях. Самому до всего доходить.
titbit
28.04.2022 16:34+2Но когда мне становится известно, что кто-то хочет что-то сделать с целыми числами, превышающими разрядность процессора (пусть даже просто сложить), я отчетливо слышу этот незаметный для всех щелчок затвора.
Красивые, нестандартные вопросы всегда вызывают интерес, это тем более логично для программиста-профи, разумеется на них сразу же ищется ответ — это ж вызов :)
Кстати, про возведение в степень: все ведь не так просто даже для обычных целых чисел. Есть «классический» алгоритм быстрого возведения через умножения по степеням двойки, но проблема в том, что он не дает минимальный по действиям (умножениям и месту для хранению промежуточных результатов) результат. А вот поиск такой минимальной последовательности действий есть непростая задача, и я не смог придумать ничего лучше оптимизированного перебора. Есть и более простая похожая задача про быстрое умножение на константу через сложения и сдвиги, но там решения более-менее известны.
lightln2
28.04.2022 16:44А вот поиск такой минимальной последовательности действий есть непростая задача, и я не смог придумать ничего лучше оптимизированного перебора
Доказано, что эта задача — 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
headfire Автор
28.04.2022 18:26Когда доказано, что задача NP-полная, именно тут-то и нужно засучивать рукава исследовать различные частные случаи и эвристические оптимизации. В посте я упомянул про поиск последовательных простых чисел. Если бы это делалось надежно какой-нибудь стандартной библиотечной функцией в обозримое время, то конечно такого бы соревнования не было. А так - бери в руки то что больше нравится, Яву, Питон, Ассемблер, Пролог - и вперед.
garbagecollected
28.04.2022 16:48Моя любимая задача из детства:
9^9^9! Кто считал? Как сейчас помню, число из 369693100 цифр.
shiz0id
28.04.2022 17:06Я только что посчитал, 78 знаков
wataru
28.04.2022 17:17+1Не может быть, само 9^9 = 387420489. А тут в эту степень возводиться 9. Почти что 10, а 10 в этой степени будет как раз столько знаков. Вот и получается, что там более 300 миллионов цифр.
Кстати,! там — это не факториал там. Иначе там было бы гораааааздо больше цифр.
Wizard_of_light
28.04.2022 17:27+1Неа, если в надстрочной нотации, то вычисления надо проводить сверху вниз, 9^9^9=9^(9^9).
Sdima1357
28.04.2022 19:38+49^9^9! Кто считал?А я в уме посчитать могу. 9^9^9=9 :) (На "C" - "^" это "xor")
inkelyad
28.04.2022 20:07Сейчас надо посылать в сторону Googology Wiki И не считать, нет - это начиная с конца Class 2 бесполезно. Проверять себя надо тем, как далеко ты продвинешься, пытаясь понять, что именно считается. Т.е. что такое какое-нибудь TREE[3] и насколько именно оно большое?
bazden
28.04.2022 20:06Написано здорово и очень интересно читать. Но, мало :) Автор пишите еще, у Вас здорово получается!
headfire Автор
28.04.2022 20:31Спасибо на добром слове. Для автора это очень важно. Если вы посмотрите предыдущие посты - они длиннее. Здесь решил попробовать в жанре миниатюры. Но не все сюжеты можно уложить в такой формат. Поэтому если будет следующий пост - он будет длиннее. Спасибо еще раз!
wataru
Что такое? Работа с большими числами, AKA длинная арифметика — хорошо изученная тема. Большинство операций выполняются тупо в столбик, хотя есть всякие хитрые алгоритмы вроде карацубы, FFT для умножения и логарифмического возведения в степень, но все уже давно реализовано в библиотеках, в тех же криптографических, например. В java вообще есть BigInteger встроенный, правда там произведение втупую сделано, но для многих задач хватит и его.
headfire Автор
В Питоне вообще все из коробки, даже по-моему никакого специального типа не нужно. Это очень полезно - изучать хорошо кем-то раньше (но не тобой) изученные темы. А потом сделать свою рубаху, которая, как известно, ближе к телу.
headfire Автор
Я бы хотел более развернуто пояснить свою мысль о том, когда именно я слышу щелчок затвора. Я не слышу его, когда, например, вижу как кто-то использует стандартные криптографические библиотеки (еще и с одобренными алгоритмами). Я не вижу в этом опасности. Так же как я не вижу опасности в том, что кто-то в Apache настраивает протокол https. Но если этот же самый человек начнет интересоваться что там под капотом, что там происходит в ассемблерных вставках и куда девается бит переноса, то это уже гораздо интереснее.
Если еще привести похожий пример из другой области. Высокочастотных трейдеров мало волнуют люди, которые пытаются играть на бирже через стандартные интерфейсы, использующие стандартные методы анализа и получающие информацию через стандартные каналы. Они не обращают на это никакого внимания. Их больше волнует, когда кто-то начинаем мутить свои протоколы с низкой задержкой, эффективные ни на что не похожие методы кодирования финансовой информации и подбираться ближе по времени и расстояниям к реальным данным. Ну и конечно алгоритмы трейдинга каждый пытается придумать свои.
Alex_ME
Если честно, мысль не до конца понятна.
Почему? Вы
чувствуете интерес, потому что копание под капотом интереснее привычных тем?
чувствуете опасность, потому что кто-то может наломать дров со своим велосипедом (см "вы опасно некомпетентны в криптографии")
чувствуете опасность, потому что, если возникла потребность лезть под капот, вероятно, лезущий делает что-то не так/решает не ту проблему/не так?
???
headfire Автор
Любая тема - это копание под капотом - иначе вы будете дилетантом.
Действительно, есть мнение, что разрабатывать свои криптографические алгоритмы - попросту невозможно, потому что даже то что разработано самыми выдающимися математиками часто не проходило проверку практикой и временем. А уж то что на коленке разработает студент - это явно будет уязвимо. Но все зависит от ситуации. Взять, например, принцип что успех шифрования не должен зависеть от того, что неизвестен или обфусцирован алгоритм. Но это верно для разработки длительных по времени стандартов. Если цель поделки - продержаться три дня, то здесь любая нестандартная поделка будет лучше стандартного алгоритма. Пока все антивирусы щелкают клювом, пытаясь понять, что это такое - работа будет уже сделана. Я поясню мысль некоей аналогией: двигатели для самолетов с ресурсом 40000 часов делаются совсем по другому, чем двигатели для ракет с ресурсом 3 часа. А запустить что-то на опасную для всех высоту может даже школьник, если прочитает пару учебников.
К сожалению, сейчас мы имеем дело с индустрией сложных вещей, когда лезть под капот не имеет смысла, а иногда даже и опасно. Если раньше можно было продуть карбюратор, то сейчас в инжектор лучше не соваться. Вот зачем ты под капот залез - наверное ты не правильно свою машину эксплуатировал - вовремя масло не залил, техобслуживание не прошел. Но в связи с последними событиями все стали как-то по новому смотреть на чудаков, ездящих на ладах-шестерках и имеющих в гараже небольшой токарный и фрезерный станок.
В любом случае спасибо за эти вопросы - Ваша позиция тоже верна и я конечно ее разделяю - особенно в промышленной разработке.
wataru
Судя по вашему посту, вы считате что в длинной арифметике есть какие-то неочевидные подводные камни, о которые новички могут споткнуться и выстрелить себе в ногу. Ну приведите хотя бы парочку.
Если не брать хитрых алгоритмов вроде fft, которые и так релизуются по статьям и гайдам или берутся из библиотек, если оно надо, то дальше там остается только два вопроса — производительность и переполнение. Самое тупое решение с хранением одной десятичной цифры в ячейках массива 32-битных чисел будет не самым эффективным, но будет работать всего лишь в несколько раз медленнее самого продвинутого решения. И никакого переполнения там быть не будет. Это сможет без ошибок написать даже школьник, изучающий программирование.
А вот дальше уже ассемблерные вставки и обработка битов переноса — это то, что называется микрооптимизациями. Чем глубже закапываешься, тем сложнее получается без ошибок выжать еще пару процентов производительности. Но это не идет в моем понимании как "неочевидные подводные камни". И максимум, что новичек сделает — это получит в 2 раза более медленный код. Не очень приятно, но на выстрел в ногу не идет. Это не в 1000 раз медленнее из-за незнания алгоритмов.
Наоборот, если кто-то интересуется этой темой пусть и у них есть время это делать, вместо использования готовой библиотеки, то пусть развлекается. Надо только сказать "помни про переполнение" и может потом подсказывать "а вот если хранить не десятичные цифры, двоичные, то процессору быстрее будет их ворочать", "а вот тут можно SIMD инструкциями сделать", "а ассемблерная вставка сама может и сложить и перенос получить".
Похожая на вашу точка зрения есть про криптографию "Если вы не большой специалист по криптографии, никогда не пишите собственную криптографию". Тут оно оправданно, потому что с большой вероятностью новичок получит не чуть менее производительный код, а не выполняющую свою цель криптографию (которую сколько-нибудь подкованный злыдень легко взломает). Но что не так с длинной арифметикой — мне не понятно.
headfire Автор
Вы немного не поняли, смысл моего поста. Смысл в том, что если я вижу, что кто-то самостоятельно мутит в ассемблере целочисленную арифметику, то это неспроста. Я ничего не говорю о том, получится у него это, не получится, сможет он превзойти стандартные решения - не сможет - по большому счету это неважно. Я просто понимаю, что он что-то затеял. Здесь почему-то поняли, что я на стороне этих людей. Я то как раз согласен со всеми - если вы добропорядочный гражданин - нефиг вам в ассемблер лезть, та еще с мутными темами. Фигачьте на Яве - все уже разработано. Как пел Высоцкий - "Так держать - колесо в колесе - и доедешь туда куда все" :).
wataru
Если кому-то это интересно — милости просим. Тем более в такой безобидной теме, как длинная арифметика. Тем более, для быстрого возведения в степень и других алгоритмов длинной арифметики не надо даже ассемблерных вставок. Повторюсь, рабочее решение напишет даже изучающий программирование школьник. И оно будет лишь в в 10 раз проигрывать лучшим решениям в мире. Программист со стажем и минимальным пониманием как устроен процессор сможет написать решение, уступающее лучшим в мире лишь считанные проценты в эффективности.
Ваша мысль звучит как "длинная арифметика — не всем дано. Это для избранных и очень умных людей". Опять же, это правда про криптографию, но не про длинную арифметику. Или у вас так вообще про все? Коллега спросил: "а как найти путь в графе быстро?" — вы напряглись. Коллега спросил: "как перемножить матрицы?" — вы напряглись. Коллега спросил: "как пересечь две окружности?" — ...
Что такого именно в длинной арифметике?
headfire Автор
Да, теперь понял. Спасибо. Я поясню. Сначала скажу, что этот случай не придуманный, а что называется основан на реальных событиях. И вопрос звучал именно так - как возводить в степень большие числа. Любой, кто немного в теме, знает, что это делается для проверки чисел на простоту, ну и потом непосредственно для самого асимметричного шифрования. Других разумных применений всему этому нет. Конечно я напрягся. Но насчет асимметричного кодирования я ошибся - коллеге нужны были только тесты на простоту. Вот собственно о чем пост. Если вы найдете еще какое-нибудь разумное практическое (не академическое) применение многозначной арифметики - то прошу мне сообщить. Если бы меня спросили про графы или геометрию, я бы удивился, но такого эффекта это на меня бы не оказало.
Я сразу скажу, что я вообще не специалист в криптографии, но я кое-что читал, и решая некую олимпиадную задачу мне пришлось реализовывать многозначную арифметику. Никаких Java-библиотек и Питонов тогда не было. Был только TurboС++ на дискете. И конечно там ничего особо сложного. Любой справится. Тем более что системы команд популярных процессоров и их арифметические устройства СПЕЦИАЛЬНО СПРОЕКТИРОВАНЫ для поддержки многозначной арифметики.
Моя мысль не в том что это для избранных, а прямо противоположная - что это слишком доступно - просто нужно задаться целью. Скажите, что сложного в огнестрельном оружии - просверлить дыру и насыпать туда пороха.
wataru
Спасибо, теперь и я вас понял. К такой позиции никаких претензий не имею.
headfire Автор
У меня возникло еще пара мыслей по поводу того - многозначная арифметика для избранных или нет? Мы тут с Вами допустили одну небольшую неточность. Мы рассматривали только множество программистов - но программисты это очень небольшая часть общества. Возьмите любого человека не имеющего отношения к программированию и попробуйте что-то ему объяснить, хотя бы про двоичную систему счисления. И интересно, сколько времени пройдет, прежде чем он что-либо полезное напишет между begin и end. Вы рассматриваете свои способности, как нечто само собой разумеющееся.
Не секрет, что программистов не хватает, как не хватает сейчас и микрочипов. В школах существуют обязательные предметы информатика и математика. Всех тащат за уши в ИТ. Но программистами становятся единицы.
Я не говорю, что программисты - высшая каста. Все те же рассуждения можно применить и к врачам и к инженерам и к деятелям искусства, и конечно, к ученым. У каждого свое призвание и своя зона ответственности в этом непростом мире. И у каждого свой щелчок затвора. Например для химика будет очень подозрительно если в кто-то в отделе бытовой химии купит что-нибудь в какой-нибудь опасной пропорции.
От компьютеров может исходить большая опасность, так как они сейчас везде. Вот я сижу тут. Мало того что в карманах моих штанов наверное с десяток различных процессоров, а если посмотреть по сторонам, то сотня наберется.
И кроме нас опасности, связанные с ИТ-технологии никто не распознает. Поэтому надо внимательно вслушиваться в двоичную тишину. Кроме нас некому.
wataru
Ну ясно, что вопрос о программировании чего-то стоит рассматиривать только среди программистов.
KaminskyIlya
Вычисления с большей точностью, чем 64-80-128 бит. Тот же BigDecimal в Java основан на BigInteger. Также (редко, но) встречаются задачи, когда целочисленные вычисления требуют разрядности большей, чем 64 бит. Например, 66 бит. И тип данных long уже не подходит.
Ну и из статьи не совсем понятно, что хотел от вас коллега: спросить алгоритм умножения, или о языковых средствах, реализующих работу с большими числами.
Что касается алгоритмов умножения/деления или быстрого возведения в степень. То я бы не сказал, что там всё так просто. Алгоритмов много. У каждого своя специфика. Один быстрый, но уязвимый к атакам по побочным каналам связи. Другой медленный, но стабильный.
headfire Автор
Вы правы, я и пытался тут сказать, что везде все не так просто - постоянно нужно думать головой, а если хочешь каких-то выдающихся результатов - то своей головой (учитывая конечно лучшие мировые практики)
Коллега искал простые числа. Работа требует ресурсов. История такая же как с майнингом биткоина - нужно где-то брать электричество и вычислительные мощности. И любая, пусть даже самая незначительная оптимизация - это небольшой шаг вперед. Здесь говорили, что можно, например без ассемблера, на стандартных типах или даже в символьном виде. Конечно серьезных людей это не устраивает. Тут получается не в разы медленнее а в десятки раз.
Коллега, конечно, знал как возводятся большие числа. И у него все работало. Но пара моих советов ему помогли. Как говорится одна голова хорошо, а две лучше.
headfire Автор
Еще решил ответить про числа, превышающие разрядность процессора. Действительно, есть случаи, когда 64 бита мало. Кроме того есть экзотические типы типа денежный. В связи с всеобщей инфляцией и триллионными долгами государств, там вообще непонятно сколько разрядов нужно :). В Oracle например, есть тип Decimal. Я не знаю, что там под капотом, но в описании типа можно указать очень большое количество разрядов.
Вы должны согласиться, что это все-таки не полноценная многозначная арифметика. Конечно, в посте есть некоторое преувеличение, когда сказано - сделать что-то превышающее разрядность процессора.
Но аппетиты приходят во время еды - сначала просто два числа сложил, потом три... Как говорится, я просто взял краcки в руки и тут как закрутилось :)
max851
Ваша фраза про ассемблер просто зделала мне день.
Аж олдскулы свело.
Спасибо.
speshuric
Да ну?
В .Net тоже Карацуба и Том-Кук (ну почти).
wataru
Посыпаю голову пеплом.
speshuric
Но в целом вы правы. Карацуба и Тоом-Кук в асимптоте лучше, но хуже на небольших числах. В обеих библиотеках используется порог для быстрого алгоритма. В .NET это 1024 бит, в Java 2560 бит для Карацубы и 7680 бит (страшно подумать!) для Тоома-Кука.