Все потоки
Поиск
Написать публикацию
Обновить

Комментарии 35

Основательный подход, великолепная статья, и вдвойне приятно, что не перевод!

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)

Рейтинг скрыт
> 1. В .NET нет длинной арифметики…

System.Numerics.BigInteger, на хабре была статья.
Рейтинг скрыт
Согласен исправить фразу.
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. Эффективная реализация китайской теоремы об остатках очень нетривиальная задача. Необходима для поддержки модуляроной арифметики.

Ну и где тут школа?
Рейтинг скрыт
Это не про меня.
ALU не проектирую, криптографией не занимаюсь, теорию чисел знаю не намного лучше продвинутого школьника. Хватило спортивного программирования 12 лет назад.
Речь о том, что когда нужен калькулятор с длинной арифметикой, то BigInteger будет достаточно. А для числодробилки нужны не только алгоритмы, но может еще и FPGA сгодится.
Полюбопытствую, а Вам зачем такие подробности длинной арифметики знать?
Рейтинг скрыт
FPGA приделать достаточно сложно и вряд ли имеет смысл (тут все плохо параллелится), ну разве модулярная арифметика.
Одно из моих увлечений разработка алгоритмов в области компьютерной алгебры. До версии 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 код подобной библиотеки.
Рейтинг скрыт
Кроме того, можно еще парсить и с помощью NRefactory, который к тому же еще и OpenSource. И я, кстати, использую его для еще одного «теоретического» проекта для минификации C# кода: CSharp-Minifier. А он в свою очередь используется для минификации кода в квайнах. Об этом, впрочем, я собираюсь написать в будущем.

Но использование 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
Рейтинг скрыт
Да, он юзает SSE, но при этом вызовов call всего 4 (как и в моей оптимизированной версии), в отличие от оптимизированной версии, где их 6. Так что быстрее или нет это еще вопрос.

Но, в любом случае, спасибо. Протестирую и добавлю листинги чистого ассемблера в статью.
Рейтинг скрыт
А как вы получили этот ассемблер? Если из студии, то там он тоже неоптимизированный. Нужно как-то через WinDbg или через еще что-то.
Рейтинг скрыт
Debug -> Options

1) Снимаем галку Enable Just My Code
2) Снимаем галку Suppress JIT Optimisations

Можно еще всяких галок понаставить, но эти основные
Рейтинг скрыт
Нет, это не то. Функции, как минимум, не инлайнятся, это объяснимо почему: не будут работать точки останова внутри них. Может сейчас, конечно, как-то по-другому, но когда я тестил, все было так, и без дебаггера работало быстрее (Ctrl + F5).
Рейтинг скрыт
Это то.
        static void Main(string[] args)
        {
            Console.WriteLine(Get4());
            Console.ReadKey();
        }

        private static int Get4()
        {
            return 4;
        }

Выполните сказанные мной манипуляции, поставьте сборку release и бряк на return 4. Он не сработает, сразу выведется 4
Рейтинг скрыт
habrahabr.ru/post/270443 — я ссылаюсь на Вас в своей статье. Было бы интересно если Вы предложите дополнительные идеи.
Кстати — там может даже будет нужно ухудшать код программы.
Обработка приватных данных на публичных вычислительных сетях
С удовольствием парочку интересных идей украл бы
Рейтинг скрыт
Хм, спасибо, интересно.
Буду изучать ваши материалы.
Рейтинг скрыт
абстрактный вычислитель Маркова — замена в сроке символов шаблона на последовательность.

абстрактный вычислитель Маркова, абстрактный вычислитель Тьюринга, машина Поста — всё они эквивалентны.
Соответственно, это модель когда на ленте абстрактного вычислителя записан текст программы.
Шаги замен переводят в эквивалентны тексты программ.
Соответственно можно искать оптимизированную программ в каком либо смысле — например — меньше команд или быстрее исполнение.
Глянте в сторону и языка РЕФАЛ с его супер компилятором.
Только надо делать оптимизированную программ в каком либо смысле — а можно чередовать шаги — сперва делаем меньше команд — потом — быстрее. Чередуем несколько раз — и вот алгоритм для обфукации кода.
Может старап забацать чтобы пару баксов срубить?
Сделать habrahabr.ru/post/270443 Коммерческая тулза для обработки приватных данных на публичных сетях — например в облаке MS Azure?
Рейтинг скрыт
Легко рассуждать, сложно сделать. Да и обфускаторов сейчас достаточно, причем бесплатных.
Рейтинг скрыт
буду пытаться для консольного приложения.
пока буду собирать обфукаторы и оптимизаторы разные
считаю что надо реализовывать для платформы .net
шаг 1. слить все dll в один выполняемый утилитой ILMerge
шаг 2. применить обфукаторы разные
шаг 3. передать данные и программу в Azure на исполнение
так что знакомые с подводными камнями нужны советы их
Рейтинг скрыт
например, алгоритм можно записать как последовательное применение операндов — соответственно интересно находить коммутативные элементы, чтобы переупорядочить эту последовательность операндов — чтобы по содержимому данных и кода программы невозможно было бы понять какие исходные данные поступили на обработку и какие данные были возвращены
Рейтинг скрыт
Стоит отметить, что все-таки точности стандартных математических функций и типа double не хватает для нормального распознавания рациональных и вещественных чисел, однако теоретически все работает.

Можно использовать double-double арифметику, я при реализации вот этим документом вдохновлялся.
Рейтинг скрыт
Не рассматривал, но при желании можно реализовать. В репозитории, кстати, сменил GOLD парсер на ANTLR. Но остаются другие рефакторинги, чтобы шаги преобразования были как можно более иммутабельными.

Возможно позже опубликую обновленную статью только уже на английском хабре.
Рейтинг скрыт
Мне кажется, самое востребованное в символьных вычислениях это не скорость, а — автоматическое вычисление пределов. Чтобы вычисляя значения функции sin(pi⋅x)/(x-x³) в точках 0 и ±1 получать корректные значения без дополнительных телодвижений.
Рейтинг скрыт
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr