Комментарии 35
Основательный подход, великолепная статья, и вдвойне приятно, что не перевод!
P.S. отдельное спасибо за грамматики — обновил знания.
P.S. отдельное спасибо за грамматики — обновил знания.
1. В .NET нет длинной арифметики. В Java плохая по эффективности реализация (плата за стандарт). Самая хорошая здесь (всегда заморочка при сборке под Windows)
gmplib.org/
2. Lisp как язык программирования лучше подходит для универсальных (есть специализированные. например, Singular, Magma) систем компьютерной алгебры. Так Maxima (произошла от Macsyma) и Reduce значительно быстрее написанных на C и наиболее распространенных Maple, Mathematica. Классический коэффициент, после компиляции Lisp в 5-6 раз медленнее C, но математикам удобнее писать на Lisp свои алгоритмы, чем объяснять их программистам для встраивания их на C.
3. В Reduce встроен следующий оператор
decompose(xˆ8-88*xˆ7+2924*xˆ6-43912*xˆ5+263431*xˆ4-218900*xˆ3+65690*xˆ2-7700*x+234)
-> {U^2 + 35*U + 234, U=V^2 + 10*V, V=X^2 — 22*X}
decompose(uˆ2+vˆ2+2u*v+1)
-> {W^2 + 1, W=U + V}
На Reduce также есть очень неплохой пакет scope. Пример его использования
z:=a^2*b^2+10*a^2*m^6+a^2*m^2+2*a*b*m^4+2*b^2*m^6+b^2*m^2;
Результат
g1 := b*a
g5 := m*m
g2 := g5*b*b
g3 := g5*a*a
g4 := g5*g5
z := g2 + g3 + g1*(2*g4 + g1) + g4*(2*g2 + 10*g3)
gmplib.org/
2. Lisp как язык программирования лучше подходит для универсальных (есть специализированные. например, Singular, Magma) систем компьютерной алгебры. Так Maxima (произошла от Macsyma) и Reduce значительно быстрее написанных на C и наиболее распространенных Maple, Mathematica. Классический коэффициент, после компиляции Lisp в 5-6 раз медленнее C, но математикам удобнее писать на Lisp свои алгоритмы, чем объяснять их программистам для встраивания их на C.
3. В Reduce встроен следующий оператор
decompose(xˆ8-88*xˆ7+2924*xˆ6-43912*xˆ5+263431*xˆ4-218900*xˆ3+65690*xˆ2-7700*x+234)
-> {U^2 + 35*U + 234, U=V^2 + 10*V, V=X^2 — 22*X}
decompose(uˆ2+vˆ2+2u*v+1)
-> {W^2 + 1, W=U + V}
На Reduce также есть очень неплохой пакет scope. Пример его использования
z:=a^2*b^2+10*a^2*m^6+a^2*m^2+2*a*b*m^4+2*b^2*m^6+b^2*m^2;
Результат
g1 := b*a
g5 := m*m
g2 := g5*b*b
g3 := g5*a*a
g4 := g5*g5
z := g2 + g3 + g1*(2*g4 + g1) + g4*(2*g2 + 10*g3)
Согласен исправить фразу.
1. В .NET нет эффективной реализации длинной арифметики.…
А такую по Вашей ссылке можно написать на С за 2-3 дня если знаешь алгоритмы. Если мучится с ассемблером под разные процессоры, то просто долго. Если на GMP, что я дал ссылку несколько лет и небольшой коллектив с хорошим математическим образованием и алгоритмическим мышлением. Maple несколько лет назад тоже перешел GMP со своей реализации. Вроде в Magma хорошая реализация длинной арифметики, но там все коды закрыты и об этом можно судить косвенно по скорости выполнения символьных вычислений.
1. В .NET нет эффективной реализации длинной арифметики.…
А такую по Вашей ссылке можно написать на С за 2-3 дня если знаешь алгоритмы. Если мучится с ассемблером под разные процессоры, то просто долго. Если на GMP, что я дал ссылку несколько лет и небольшой коллектив с хорошим математическим образованием и алгоритмическим мышлением. Maple несколько лет назад тоже перешел GMP со своей реализации. Вроде в Magma хорошая реализация длинной арифметики, но там все коды закрыты и об этом можно судить косвенно по скорости выполнения символьных вычислений.
В длинной арифметике ничего сложного нет. Сами в школе писали, как говорится. А C# очень часто проигрывает чистому Си. Например, BigInteger реализованы как immutable, что очень негативно сказывается на производительности. Преимущество C# в том что программист может быстро сделать, а не в том что код будет идеально быстро работать.
1. Наивный алгоритм умножения O(n^2) проигрывает методу Карацубы O(n^log_2(3)=1.58..) при правильной реализации при размере чисел в 7-8 машинных слов. Умножения Шёнхаге — Штрассена O(N·logN·log logN) использует быстрое преобразование Фурье. Примерно 100-400 машинных слов (сильно зависит от архитектуры). Алгоритм Фюрера 2007 год O(N·logN). Есть еще обобщение алгоритма Карацубы алгоритм Тоома-Кука.
2. Деление на число с машинное слово, на число в два машинных слова. Для больших чисел целочисленное деление заменяют умножением (в зависимости от размера соответствующий быстрый алгоритм умножения) на обратный элемент, который получают используя метод Ньютона.
3. Вычисление НОД (gcd) постоянно необходимо при реализации рациональных чисел. Тут бинарный алгоритм.
4. Про факторизацию и дискретное логарифмирование просто молчу.
5. Эффективная реализация китайской теоремы об остатках очень нетривиальная задача. Необходима для поддержки модуляроной арифметики.
Ну и где тут школа?
2. Деление на число с машинное слово, на число в два машинных слова. Для больших чисел целочисленное деление заменяют умножением (в зависимости от размера соответствующий быстрый алгоритм умножения) на обратный элемент, который получают используя метод Ньютона.
3. Вычисление НОД (gcd) постоянно необходимо при реализации рациональных чисел. Тут бинарный алгоритм.
4. Про факторизацию и дискретное логарифмирование просто молчу.
5. Эффективная реализация китайской теоремы об остатках очень нетривиальная задача. Необходима для поддержки модуляроной арифметики.
Ну и где тут школа?
Это не про меня.
ALU не проектирую, криптографией не занимаюсь, теорию чисел знаю не намного лучше продвинутого школьника. Хватило спортивного программирования 12 лет назад.
Речь о том, что когда нужен калькулятор с длинной арифметикой, то BigInteger будет достаточно. А для числодробилки нужны не только алгоритмы, но может еще и FPGA сгодится.
Полюбопытствую, а Вам зачем такие подробности длинной арифметики знать?
ALU не проектирую, криптографией не занимаюсь, теорию чисел знаю не намного лучше продвинутого школьника. Хватило спортивного программирования 12 лет назад.
Речь о том, что когда нужен калькулятор с длинной арифметикой, то BigInteger будет достаточно. А для числодробилки нужны не только алгоритмы, но может еще и FPGA сгодится.
Полюбопытствую, а Вам зачем такие подробности длинной арифметики знать?
FPGA приделать достаточно сложно и вряд ли имеет смысл (тут все плохо параллелится), ну разве модулярная арифметика.
Одно из моих увлечений разработка алгоритмов в области компьютерной алгебры. До версии GMP < 2.0 имел собственную библиотеку длинной арифметики, которая была быстрее. Но у меня другое направление, хотя воспоминания остались очень приятные. Вдобавок это был мой первый эксперимент по массовому применению метода утверждений (Тройки Хоара) + ООП на C++.
С тех пор постоянно использую два подхода. Криптографией тоже увлекался и придумал пару схем открытого ключа. Но на все время не хватает. Например нет хорошей открытой реализации на C/C++ вычисления НОД (gcd) для полиномов от нескольких переменных. Хорошая есть в Maple и Magma. Тут лучший алгоритм
www.cecm.sfu.ca/CAG/papers/brown.ps
Мало кто знает, что на заре компьютерной техники в ЭВМ при проектировании сразу закладывались возможности эффективной реализации длинной арифметики.
Одно из моих увлечений разработка алгоритмов в области компьютерной алгебры. До версии GMP < 2.0 имел собственную библиотеку длинной арифметики, которая была быстрее. Но у меня другое направление, хотя воспоминания остались очень приятные. Вдобавок это был мой первый эксперимент по массовому применению метода утверждений (Тройки Хоара) + ООП на C++.
С тех пор постоянно использую два подхода. Криптографией тоже увлекался и придумал пару схем открытого ключа. Но на все время не хватает. Например нет хорошей открытой реализации на C/C++ вычисления НОД (gcd) для полиномов от нескольких переменных. Хорошая есть в Maple и Magma. Тут лучший алгоритм
www.cecm.sfu.ca/CAG/papers/brown.ps
Мало кто знает, что на заре компьютерной техники в ЭВМ при проектировании сразу закладывались возможности эффективной реализации длинной арифметики.
В .NET нет эффективной реализации длинной арифметики.…
В чистом .NET — нет. Однако есть библиотека под .NET, которая называется IntXLib (разработчик, кстати, из Украины), в которой используется дискретное преобразование Хартли для эффективной реализации операций с большими числами.
Понятное дело, что GMP будет быстрее .NET версии, потому что в ней, наверное, непосредственно используются специальные команды ассемблера, векторизация, более агрессивная оптимизация (C/C++). В проекте IntXLib есть сравнение производительности с GMP.
Интересный проект. Есть мысль попытаться добавить поддержку кастомных функций.
Ну кастомные функции есть, и даже производные от них берутся в аналитическом виде на этапе дифференцирования (добавляется штрих) и численном виде на этапе компиляции (по определению производной с заданной delta) следующим образом:
Или вы что-то другое имеете в виду? :)
using (var mathAssembly = new MathAssembly("b(x) + 10 * x * a", "x"))
{
var b = new Func<double, double>(x => x * x);
var funcResult = mathAssembly.Func(5, 2, b); // x = 5; a = 2; b = x ^ 2
// funcResult == 5 ^ 2 + 10 * 5 * 2 = 125
var funcDerResult = mathAssembly.FuncDerivative(5, 2, b); // x = 5; a = 2; b = x ^ 2
// funcDerResult == (b(x + dx) - b(x)) / dx + 10 * a = 30
}
Или вы что-то другое имеете в виду? :)
Очень хорошая задача для глубокого понимания многих вопросов CS.
В реальности, для максимального использования проверенного кода, можно сделать проще:
1. Парсить выражения можно с помощью Roslyn (но только стандартные выражения C# ?)
2. Можно парсить выражение в Expression<Func<double[], double>> и затем вызывать .Compile();
А вот в аналитических преобразованиях я дальше производных тоже не двинулся. Интересно было бы посмотреть LGPL код подобной библиотеки.
В реальности, для максимального использования проверенного кода, можно сделать проще:
1. Парсить выражения можно с помощью Roslyn (но только стандартные выражения C# ?)
2. Можно парсить выражение в Expression<Func<double[], double>> и затем вызывать .Compile();
А вот в аналитических преобразованиях я дальше производных тоже не двинулся. Интересно было бы посмотреть LGPL код подобной библиотеки.
Кроме того, можно еще парсить и с помощью NRefactory, который к тому же еще и OpenSource. И я, кстати, использую его для еще одного «теоретического» проекта для минификации C# кода: CSharp-Minifier. А он в свою очередь используется для минификации кода в квайнах. Об этом, впрочем, я собираюсь написать в будущем.
Но использование Roslyn и NRefactory для математических выражений — большой оверхед, и они не позволяют работать с IL кодом напрямую для лучшей оптимизации.
Из наиболее известных и мощных есть система Axiom с документацией и исходниками.
Однако стоит отметить, что даже упрощение выражений (т.е. приведение выражению к виду, содержащему наименьшее количество операций), является довольно сложной задачей, где нужно так или иначе производить перебор (с эвристиками или без). А если говорить об аналитических интегралах и другой символьной математике, то это уже чуть ли не творчество :)
Но использование Roslyn и NRefactory для математических выражений — большой оверхед, и они не позволяют работать с IL кодом напрямую для лучшей оптимизации.
А вот в аналитических преобразованиях я дальше производных тоже не двинулся. Интересно было бы посмотреть LGPL код подобной библиотеки.
Из наиболее известных и мощных есть система Axiom с документацией и исходниками.
Однако стоит отметить, что даже упрощение выражений (т.е. приведение выражению к виду, содержащему наименьшее количество операций), является довольно сложной задачей, где нужно так или иначе производить перебор (с эвристиками или без). А если говорить об аналитических интегралах и другой символьной математике, то это уже чуть ли не творчество :)
В сердечке трудно различить L и 1. Видны какие-то формулы из теоремы косинусов, трёхгранные углы… но некоторые формулы непонятны вообще. И главное, непонятно, зачем сумму квадратов (или 4-х степеней?) вычитать из 1 :) Забавно, что слагаемые можно упорядочить так, что в каждом следующем появляется хотя бы одна новая переменная. В целом, выглядит как какая-то сложная конфигурация точек и углов на сфере.
Хм, хорошая попытка, но не угадали совсем. Вероятно, отгадать сможет только тот, кто видел ее хотя бы раз. Я скажу о правильном результате позже, когда кто-нибудь отгадает или пройдет еще какое-то время :)
Можно ещё предположить, что это что-то, связанное с квантовыми состояниями атома гелия. Но там я совсем не разбираюсь.
Тоже нет, это чистая математика. Добавил правильный ответ в конец статьи.
Финальный IL код является более оптимальным, по сравнению с кодом, сгенерированным стандартным C# компилятором csc.exe в Release режиме, достаточно всего лишь взглянуть на сравнение следующих двух листингов например для функции
Стоит отметить, что csc практически ничего не оптимизирует, т.к. все оптимизации возложены на JIT. Он умеет совершать только совсем небольшие оптимизации. Стоит посмотреть на результирующий ассемблер (и скорость его выполнения, конечно же). Прилагаю ассемблер для случая x64 Release:
00000000 push ebp
00000001 mov ebp,esp
00000003 sub esp,10h
00000006 fld qword ptr [ebp+8]
00000009 fld st(0)
0000000b fld1
0000000d fmulp st(1),st
0000000f sub esp,8
00000012 fstp qword ptr [esp]
00000015 fstp qword ptr [ebp-8]
00000018 call 723800FB
0000001d fld qword ptr [ebp-8]
00000020 fxch st(1)
00000022 fmul dword ptr ds:[013A3608h]
00000028 fsin
0000002a fld st(1)
0000002c fmul st,st(2)
0000002e fmul st,st(2)
00000030 faddp st(1),st
00000032 fld st(1)
00000034 sub esp,8
00000037 fstp qword ptr [esp]
0000003a fld st(1)
0000003c sub esp,8
0000003f fstp qword ptr [esp]
00000042 fstp qword ptr [ebp-8]
00000045 fstp qword ptr [ebp-10h]
00000048 call 723800FB
0000004d fld qword ptr [ebp-10h]
00000050 fxch st(1)
00000052 fmul dword ptr ds:[013A3610h]
00000058 fsin
0000005a fmul dword ptr ds:[013A3618h]
00000060 sub esp,8
00000063 fstp qword ptr [esp]
00000066 fstp qword ptr [ebp-10h]
00000069 call 723800FB
0000006e fld qword ptr [ebp-10h]
00000071 sub esp,8
00000074 fxch st(1)
00000076 fstp qword ptr [esp]
00000079 fstp qword ptr [ebp-10h]
0000007c call 724D0466
00000081 fld qword ptr [ebp-10h]
00000084 fld qword ptr [ebp-8]
00000087 faddp st(2),st
00000089 fld st(0)
0000008b fmul dword ptr ds:[013A3620h]
00000091 fmul st,st(1)
00000093 fmulp st(1),st
00000095 fsubp st(1),st
00000097 mov esp,ebp
00000099 pop ebp
0000009a ret 8
Хотя забавно, что debug на моей машине выдает более быстрый код (юзает SSE) :)
00000038 vmovsd xmm0,qword ptr [rbp+000000B0h]
00000041 vmovsd xmm1,qword ptr [rbp+000000B0h]
0000004a vmulsd xmm0,xmm0,xmm1
0000004f vmovsd xmm1,qword ptr [rbp+000000B0h]
00000058 vmulsd xmm0,xmm0,xmm1
0000005d vmovsd qword ptr [rbp+78h],xmm0
00000063 vmovsd xmm0,qword ptr [000001B8h]
0000006c vmovsd qword ptr [rbp+70h],xmm0
00000072 vmovsd xmm0,qword ptr [rbp+000000B0h]
0000007b vmulsd xmm0,xmm0,mmword ptr [000001C0h]
00000084 call 000000005FCD3BA0
00000089 vmovsd qword ptr [rbp+68h],xmm0
0000008f vmovsd xmm0,qword ptr [rbp+70h]
00000095 vmovsd xmm1,qword ptr [rbp+68h]
0000009b vmulsd xmm0,xmm0,xmm1
000000a0 call 000000005F65C6F0
000000a5 vmovsd qword ptr [rbp+60h],xmm0
000000ab vmovsd xmm0,qword ptr [rbp+78h]
000000b1 vmovsd xmm1,qword ptr [rbp+60h]
000000b7 vaddsd xmm0,xmm0,xmm1
000000bc vmovsd qword ptr [rbp+58h],xmm0
000000c2 vmovsd xmm0,qword ptr [rbp+000000B0h]
000000cb vmovsd qword ptr [rbp+50h],xmm0
000000d1 vmovsd xmm0,qword ptr [000001C8h]
000000da vmovsd qword ptr [rbp+48h],xmm0
000000e0 vmovsd xmm0,qword ptr [000001D0h]
000000e9 vmovsd qword ptr [rbp+40h],xmm0
000000ef vmovsd xmm0,qword ptr [rbp+000000B0h]
000000f8 call 000000005FCD3BA0
000000fd vmovsd qword ptr [rbp+38h],xmm0
00000103 vmovsd xmm0,qword ptr [rbp+40h]
00000109 vmovsd xmm1,qword ptr [rbp+38h]
0000010f vmulsd xmm0,xmm0,xmm1
00000114 call 000000005F65C6F0
00000119 vmovsd qword ptr [rbp+30h],xmm0
0000011f vmovsd xmm0,qword ptr [rbp+48h]
00000125 vmovsd xmm1,qword ptr [rbp+30h]
0000012b vmulsd xmm0,xmm0,xmm1
00000130 call 000000005FCD3BA0
00000135 vmovsd qword ptr [rbp+28h],xmm0
0000013b vmovsd xmm0,qword ptr [rbp+50h]
00000141 vmovsd xmm1,qword ptr [rbp+28h]
00000147 call 000000005FCD3BC8
0000014c vmovsd qword ptr [rbp+20h],xmm0
00000152 vmovsd xmm0,qword ptr [rbp+58h]
00000158 vmovsd xmm1,qword ptr [rbp+20h]
0000015e vaddsd xmm0,xmm0,xmm1
00000163 vmovsd xmm1,qword ptr [rbp+000000B0h]
0000016c vmulsd xmm1,xmm1,mmword ptr [000001D8h]
00000175 vmovsd xmm2,qword ptr [rbp+000000B0h]
0000017e vmulsd xmm1,xmm1,xmm2
00000183 vmovsd xmm2,qword ptr [rbp+000000B0h]
0000018c vmulsd xmm1,xmm1,xmm2
00000191 vsubsd xmm0,xmm0,xmm1
00000196 vmovsd qword ptr [rbp+00000080h],xmm0
0000019f nop
000001a0 jmp 00000000000001A2
000001a2 vmovsd xmm0,qword ptr [rbp+00000080h]
000001ab lea rsp,[rbp+00000090h]
000001b2 pop rsi
000001b3 pop rdi
000001b4 pop rbp
000001b5 ret
А как вы получили этот ассемблер? Если из студии, то там он тоже неоптимизированный. Нужно как-то через WinDbg или через еще что-то.
Debug -> Options
1) Снимаем галку Enable Just My Code
2) Снимаем галку Suppress JIT Optimisations
Можно еще всяких галок понаставить, но эти основные
1) Снимаем галку Enable Just My Code
2) Снимаем галку Suppress JIT Optimisations
Можно еще всяких галок понаставить, но эти основные
habrahabr.ru/post/270443 — я ссылаюсь на Вас в своей статье. Было бы интересно если Вы предложите дополнительные идеи.
Кстати — там может даже будет нужно ухудшать код программы.
Обработка приватных данных на публичных вычислительных сетях
С удовольствием парочку интересных идей украл бы
Кстати — там может даже будет нужно ухудшать код программы.
Обработка приватных данных на публичных вычислительных сетях
С удовольствием парочку интересных идей украл бы
Хм, спасибо, интересно.
Буду изучать ваши материалы.
Буду изучать ваши материалы.
абстрактный вычислитель Маркова — замена в сроке символов шаблона на последовательность.
абстрактный вычислитель Маркова, абстрактный вычислитель Тьюринга, машина Поста — всё они эквивалентны.
Соответственно, это модель когда на ленте абстрактного вычислителя записан текст программы.
Шаги замен переводят в эквивалентны тексты программ.
Соответственно можно искать оптимизированную программ в каком либо смысле — например — меньше команд или быстрее исполнение.
Глянте в сторону и языка РЕФАЛ с его супер компилятором.
Только надо делать оптимизированную программ в каком либо смысле — а можно чередовать шаги — сперва делаем меньше команд — потом — быстрее. Чередуем несколько раз — и вот алгоритм для обфукации кода.
Может старап забацать чтобы пару баксов срубить?
Сделать habrahabr.ru/post/270443 Коммерческая тулза для обработки приватных данных на публичных сетях — например в облаке MS Azure?
абстрактный вычислитель Маркова, абстрактный вычислитель Тьюринга, машина Поста — всё они эквивалентны.
Соответственно, это модель когда на ленте абстрактного вычислителя записан текст программы.
Шаги замен переводят в эквивалентны тексты программ.
Соответственно можно искать оптимизированную программ в каком либо смысле — например — меньше команд или быстрее исполнение.
Глянте в сторону и языка РЕФАЛ с его супер компилятором.
Только надо делать оптимизированную программ в каком либо смысле — а можно чередовать шаги — сперва делаем меньше команд — потом — быстрее. Чередуем несколько раз — и вот алгоритм для обфукации кода.
Может старап забацать чтобы пару баксов срубить?
Сделать habrahabr.ru/post/270443 Коммерческая тулза для обработки приватных данных на публичных сетях — например в облаке MS Azure?
Легко рассуждать, сложно сделать. Да и обфускаторов сейчас достаточно, причем бесплатных.
буду пытаться для консольного приложения.
пока буду собирать обфукаторы и оптимизаторы разные
считаю что надо реализовывать для платформы .net
шаг 1. слить все dll в один выполняемый утилитой ILMerge
шаг 2. применить обфукаторы разные
шаг 3. передать данные и программу в Azure на исполнение
так что знакомые с подводными камнями нужны советы их
пока буду собирать обфукаторы и оптимизаторы разные
считаю что надо реализовывать для платформы .net
шаг 1. слить все dll в один выполняемый утилитой ILMerge
шаг 2. применить обфукаторы разные
шаг 3. передать данные и программу в Azure на исполнение
так что знакомые с подводными камнями нужны советы их
например, алгоритм можно записать как последовательное применение операндов — соответственно интересно находить коммутативные элементы, чтобы переупорядочить эту последовательность операндов — чтобы по содержимому данных и кода программы невозможно было бы понять какие исходные данные поступили на обработку и какие данные были возвращены
Стоит отметить, что все-таки точности стандартных математических функций и типа double не хватает для нормального распознавания рациональных и вещественных чисел, однако теоретически все работает.
Можно использовать double-double арифметику, я при реализации вот этим документом вдохновлялся.
Для преобразования чисел в виде рациональной дроби цепные дроби не рассматривали? Есть и готовые реализации.
Мне кажется, самое востребованное в символьных вычислениях это не скорость, а — автоматическое вычисление пределов. Чтобы вычисляя значения функции sin(pi⋅x)/(x-x³) в точках 0 и ±1 получать корректные значения без дополнительных телодвижений.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция)