Логика программирования: Нахождение самого маленького уравнения к большому количеству
Я не знаю много о математике, таким образом, я не знаю, как начать гуглить то, что я ищу, таким образом, я полагаюсь на интеллект экспертов, чтобы помочь мне понять то, что я после...
Я пытаюсь найти самую маленькую строку уравнений для конкретного большого количества. Например, учитывая число
"39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306816"
Самое маленькое уравнение 64^64 (что я знаю о). Это содержит только 5 байтов.
В основном программа инвертировала бы математику, вместо того, чтобы брать выражение и найти ответ, это берет ответ и находит самое упрощенное выражение. Упрощенный самая маленькая строка средств этого случая, не действительно простая математика.
Это было уже создано? Раз так, где я могу найти его? Я надеюсь брать ЧРЕЗВЫЧАЙНО ОГРОМНЫЕ числа (10^10000000) и ломать их к, надо надеяться, выражениям, которые будут похожи на 100 символов в длине. Это даже возможно? разве современные центральные процессоры/GPU не способны к выполнению таких больших вычислений?
Править:
Хорошо. Так нахождение самого маленького уравнения занимает Слишком много времени, судящего на ответах. Существует ли так или иначе к "в лоб" это, и найдите самое маленькое к настоящему времени?
Например, учитывая число, супер супер большой. Иногда взятие квадратного корня числа приведет к выражению, меньшему, чем само число.
До того, какие выражения это началось бы он, хорошо это естественно попробует выражения, которые были бы выражение самое маленькое. Я уверен, что существуют тонны математических вещей, которые я не знаю, но одним из способов сделать число намного меньшим являются полномочия.
8 ответов
Чтобы добавить еще одно ключевое слово в ваш загрузчик Google, см. Сложность Колмогорова . Колмогоровская сложность строки - это размер наименьшей машины Тьюринга, которая выводит строку при пустом вводе. Это один из способов формализовать то, что вам кажется.Однако, как известно, вычисление колмогоровской сложности заданной строки является неразрешимой проблемой :)
Надеюсь, это поможет,
TJ
Для этого есть хорошая программа: http://mrob.com/pub/ries/index.html
Я задал вопрос «какой в этом смысл?», Поскольку я не знаю, смотрите ли вы на этот вопрос с точки зрения математики или точки зрения факторинга большого числа.
Поскольку в других ответах учитывалась точка зрения факторинга, я посмотрю на математический аспект. В частности, проблема, которую вы описываете, - это проблема сжимаемости . Здесь у вас есть число, и вы хотите описать его с помощью самого маленького алгоритма. Сильно случайные числа имеют очень плохую сжимаемость, так как для их описания вам нужно либо записать все цифры, либо описать детерминированный алгоритм, который лишь немного меньше, чем само число.
В настоящее время не существует общей математической теоремы, которая могла бы определить, является ли представление числа наименьшим возможным для этого числа (хотя нижняя граница может быть обнаружена путем понимания теории информации Шеннона). (Я сказал общую теорему, поскольку частные случаи действительно существуют).
Как вы сказали, вы плохо разбираетесь в математике, возможно, это бесполезный ответ для вас ...
Похоже, вы в основном хотите произвести факторинг для произвольно большого числа.Это настолько сложная проблема, что она фактически служит краеугольным камнем современной криптографии.
Вы выполняете форму сжатия без потерь, а сжатие без потерь не работает со случайными данными. Предположим, напротив, что у вас есть способ сжать N-битные числа в N-1-битные числа. В этом случае у вас будет 2 ^ N значений для сжатия в обозначения 2 ^ N-1, что в среднем составляет 2 значения на обозначение, поэтому ваше среднее обозначение не может быть распаковано. Сжатие без потерь хорошо работает с относительно структурированными данными, где данные, которые мы, вероятно, получим, сжимаются небольшого размера, а данные, которые мы не собираемся получать, на самом деле немного увеличиваются.
Это немного сложнее, так как вы частично сжимаете, позволяя больше информации для каждого символа. (Существует больше N-символьных последовательностей, включающих цифры и операторы, чем одних цифр.) Тем не менее, вы не получите сжатия без потерь, которое в среднем лучше, чем просто запись целых чисел в двоичном формате.
На самом деле это проблема математики, а не программирования или информатики. Вы должны спросить об этом на https://math.stackexchange.com/
Хотя ваш вопрос остается неясным, возможно, нахождение целочисленного отношения - это то, что вам нужно.
EDIT:
Есть некоторые предположения, что нахождение "короткой" формы как-то связано с проблемой факторизации. Я не верю, что это так, если только ваше определение не требует произведения в качестве ответа. Рассмотрим следующий псевдоалгоритм, который является лишь наброском и для которого не предпринимается никаких попыток оптимизации.
Если "кратчайший" - это четко определенное понятие, то в общем случае вы получаете "короткие" выражения, используя небольшие целые числа большой силы. Если N - мое целое число, то я могу найти рядом целое число, которое равно 0 mod 4. Насколько близко? В пределах +/- 2. Я могу найти целое число в пределах +/- 4, которое равно 0 по модулю 8. И так далее. И это только для степени 2. Я могу проделать то же упражнение с 3, 5, 7 и т.д. Например, мы можем легко найти ближайшее целое число, которое одновременно является произведением степеней 2, 3, 5, 7, 11, 13 и 17, назовем его N_1. Теперь вычислим N-N_1, назовем его d_1. Возможно, d_1 "короткое". Если да, то N_1 (выраженное как сила простого) + d_1 - это ответ. Если нет, перейдите к поиску "короткого" выражения для d_1.
Мы также можем выбрать целые числа, которые, возможно, дальше, чем наш первый выбор; даже если разность d_1 больше, она может иметь более короткую форму.
Существование бесконечного числа простых чисел означает, что всегда будут числа, которые нельзя упростить. по факторингу. То, о чем вы просите, невозможно, извините.