Я ничего не понимаю в С++, но немного переработал вашу программу, получив ускорение в 300 раз. В одном потоке, на CPU.
Ключевая идея заключается в том, что в магическом квадрате 4х4 помимо вертикалей, горизонталей и диагоналей магическую сумму дает также сумма угловых ячеек и сумма центральных ячеек. Это позволяет намного раньше останавливать перебор вариантов.
Мне кажется, что если вместо Set использовать просто битовую маску, то перебор ускорится еще больше. А потом уже можно и многопоточность, и GPU прикрутить.
В 1996 году [Святослав Вакарчук] поступил в аспирантуру кафедры теоретической физики [Львовского национального] университета. Тема кандидатской диссертации — «Суперсимметрия электронов в магнитном поле». https://ru.wikipedia.org/wiki/Вакарчук,_Святослав_Иванович
К сожалению, потребление памяти О(1) в задаче факторизации невозможно. Потребуется по крайней мере O(n), чтобы было куда прочитать исходное число и сохранить результаты работы.
P. S. Ваша энергия в столь зрелом возрасте вызывает неподдельное уважение. Я восхищен.
Чем ваша методика факторизации предположительно лучше уже известных алгоритмов? Быстрее работает? Потребляет меньше памяти? Наконец, может быть она проще? Из вашего текста это не ясно, а без такого сравнения читатель мало заинтересован разбираться в путанном и непривычном изложении.
Проблема действительного разложения данного числа на простые множители одна из труднейших задач математики. В третьем столетии до н.э. Эрастофен предложил метод нахождения всех простых чисел меньших данного предела А. После некоторого усовершенствования в начале 20 века Бруном, этот способ до сих пор является единственным способом решения данной задачи без использования вычислительных устройств. Другие попытки найти законы распределения простых чисел не дали значительных результатов.
Это, мягко говоря, неправда и, простите, говорит о глубоком невежестве. К сожалению, я не в силах дать синопсис развития вычислительной теории чисел за последний век в рамках комментария на Хабре. Так, например, для нахождения всех простых чисел, меньших данного, в 20-м веке было разработано решето Аткина, превосходящее решето Евклида по скорости работы и все еще доступное для ручных вычислений.
Впрочем, непонятно, почему в статье, посвященной алгоритму факторизации данного числа, вы приводите в качестве примера алгоритм Евклида, который к задаче факторизации отношения не имеет. Сравните свой алгоритм хотя бы с методом факторизации Ферма, которым последний пользовался без всяких компьютеров в 17-м веке.
Тогда с тем же успехом можно сложить первые эннадцать рядом треугольника Паскаля в массив и объявить о революционном алгоритме, который вычисляет биномиальные коэффициенты за O(1).
Для приближенного вычисления больших коэффициентов уж лучше воспользоваться рядом Стирлинга.
> При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
> При вычислении с помощью быстрых Фурье-преобразований трудоёмкость имеет оценку O(n*log n).
Сам массив значений биномиальных коэффициентов от С_n^0 до C_n^n занимает что-то типа O(n^2) бит. Как вы умудрились их посчитать за асимптотически меньшее время?
Мопед не мой, я только перевожу, причем начиная с пятой статьи. До этого переводы готовил Monnoroch.
Пришлите почту личным сообщением, я отправлю пятую и шестую статьи в LaTeX.
С удовольствием, если вы подскажете, по какому критерию он срабатывает или не срабатывает. Я погуглил и не нашел ничего конкретного. Могу, если хотите, выдать вам исходник в markdown для экспериментов.
В Safari вид для чтения доступен во всех трех статьях.
Про коконус и нус — хорошо подмечено. Возможно, что это одна из причин по которой Маклейн избегает этого термина в своем руководстве: «Мы предпочитаем говорить „конус с основанием F“, а не „коконус“».
Проблема теорката в том, что нужно иметь в голове достаточно примеров разных категорий, включая экзотические. Но даже математики многих специальностей всю жизнь работают с какой-то одной и довольно узкой. В этом отношении, кстати, программирование даёт много понятных широким массам примеров, в то время как примеры из книги Маклейна не всегда доступны неалгебраистам-нетопологам.
Замена Set на битовую маску дала ускорение еще в 20 раз, программа отрабатывает за пару сотых секунды.
Во-первых, x22 + x23 + x32 + x33 = 2S — (x21 + x24 + x31 + x34) = 2S — (2S — (x11 + x14 + x41 + x44)) = x11 + x14 + x41 + x44. Но (x22 + x23 + x32 + x33) + (x11 + x14 + x41 + x44) = 2S как сумма двух диагоналей. Отсюда x22 + x23 + x32 + x33 = x11 + x14 + x41 + x44 = S. Насколько я помню, непосредственно это свойство на квадраты высших порядков не обобщается, но я не специалист.
Я ничего не понимаю в С++, но немного переработал вашу программу, получив ускорение в 300 раз. В одном потоке, на CPU.
Ключевая идея заключается в том, что в магическом квадрате 4х4 помимо вертикалей, горизонталей и диагоналей магическую сумму дает также сумма угловых ячеек и сумма центральных ячеек. Это позволяет намного раньше останавливать перебор вариантов.
Мне кажется, что если вместо Set использовать просто битовую маску, то перебор ускорится еще больше. А потом уже можно и многопоточность, и GPU прикрутить.
В тексте статьи написано про wheel optimization.
Разумеется.
К сожалению, потребление памяти О(1) в задаче факторизации невозможно. Потребуется по крайней мере O(n), чтобы было куда прочитать исходное число и сохранить результаты работы.
P. S. Ваша энергия в столь зрелом возрасте вызывает неподдельное уважение. Я восхищен.
Сколько именно? Пусть дано n-битное число. Какой объем памяти понадобится: O(1), O(n), O(2^n), иное?
Ох. Я не имел в виду сравнение уровня прозорливости и вдохновенности. Меня сравнение тактико-технических характеристик интересовало.
Чем ваша методика факторизации предположительно лучше уже известных алгоритмов? Быстрее работает? Потребляет меньше памяти? Наконец, может быть она проще? Из вашего текста это не ясно, а без такого сравнения читатель мало заинтересован разбираться в путанном и непривычном изложении.
Это, мягко говоря, неправда и, простите, говорит о глубоком невежестве. К сожалению, я не в силах дать синопсис развития вычислительной теории чисел за последний век в рамках комментария на Хабре. Так, например, для нахождения всех простых чисел, меньших данного, в 20-м веке было разработано решето Аткина, превосходящее решето Евклида по скорости работы и все еще доступное для ручных вычислений.
Впрочем, непонятно, почему в статье, посвященной алгоритму факторизации данного числа, вы приводите в качестве примера алгоритм Евклида, который к задаче факторизации отношения не имеет. Сравните свой алгоритм хотя бы с методом факторизации Ферма, которым последний пользовался без всяких компьютеров в 17-м веке.
Для приближенного вычисления больших коэффициентов уж лучше воспользоваться рядом Стирлинга.
> При вычислении с помощью быстрых Фурье-преобразований трудоёмкость имеет оценку O(n*log n).
Сам массив значений биномиальных коэффициентов от С_n^0 до C_n^n занимает что-то типа O(n^2) бит. Как вы умудрились их посчитать за асимптотически меньшее время?
Пришлите почту личным сообщением, я отправлю пятую и шестую статьи в LaTeX.
В Safari вид для чтения доступен во всех трех статьях.