Быстрый метод расчета квадратного корня и мощности?

Question

Класс математики C # делает корни и полномочия только в двойных. Разные вещи могут пойти немного быстрее, если я добавлю функции с квадратным корнем и мощь на основе числа с плавающей точкой в ​​мой класс Math2 (сегодня день отдыха, и оптимизация мне кажется расслабляющей).

Итак - Быстрые квадратные корни и мощные функции, для которых мне не нужно беспокоиться о лицензировании, plskthx. Или ссылку, по которой я попаду туда.

Answer 1

Я буду считать аксиоматичным, что ни один программный метод не будет конкурировать с инструкцией по аппаратному обеспечению для квадратных корней. Единственная трудность заключается в том, что .NET не дает нам прямого контроля над оборудованием, как во времена встроенного ассемблера для кода C.

Давайте сначала обсудим общую аппаратную перспективу x86.

Инструкция xQ с плавающей запятой FSQRT имеет три точности: одинарную, двойную и расширенную (стандартная точность 80-битных регистров FP), и существует сокращение времени на 25-40% для одинарной и двойной точности , См. здесь для 32-битных инструкций x86.

Это может звучать как большая возможность, но это всего лишь дюжина часов или около того. Такая экономия легко потеряется в накладных расходах, если вы не сможете тщательно управлять кодом от вызова функции до возвращаемого значения. Управляемый C ++ звучит (как предполагает Марсело Кантос) как более практичная основа для этого, чем C #.

Примечание. Синхронизация для FSQRT идентична тем FDIV, с которыми он разделяет исполнительный модуль в архитектуре Intel, и, следовательно, имеет общую задержку.

Лучшая возможность для специализированного кода C #, вероятно, существует в направлении инструкций SSE SIMD, где аппаратное обеспечение допускает параллельное выполнение до 4 квадратных корней одинарной точности. Поддержка компилятора JIT для этого отсутствовала в течение многих лет, но вот некоторые рекомендации по текущей разработке.

Вскочила Intel (15 декабря 2010 г.), увидев, что .NET Framework 4 ничего не делает с SIMD:

[Библиотеки производительности Intel позволяют ... инструкции SIMD в C #]

Еще до этого в проекте Mono добавлена ​​поддержка JIT для SIMD в Mono 2.2:

[Mono: примечание к выпуску Mono 2.2]

Недавно была поднята возможность вызова поддержки Mono SIMD из MS C #:

[Вызов моно кода c # из Microsoft .net? - Stackoverflow]

Предыдущий вопрос также касается (хотя и без особой любви!) Того, как установить поддержку Mono SIMD:

[как включить Mono.Simd - Stackoverflow]

Answer 2

Следует проверить эту ссылку:

http://www.codecodex.com/wiki/Calculate_an_integer_square_root

имеет множество быстрых алгоритмов на множестве разных языков.

Ex:

// Finds the integer square root of a positive number  
public static int Isqrt(int num) {  
    if (0 == num) { return 0; }  // Avoid zero divide  
    int n = (num / 2) + 1;       // Initial estimate, never low  
    int n1 = (n + (num / n)) / 2;  
    while (n1 < n) {  
        n = n1;  
        n1 = (n + (num / n)) / 2;  
    } // end while  
    return n;  
} // end Isqrt()  

но их гораздо больше, некоторые из них на C / C ++ считаются самыми быстрыми, или так утверждают.

для проверки алготрита военнопленных я нашел этот ЗДЕСЬ , вместе с объяснением того, как добраться до этого алгоритма, начиная с более простых.

private double Power(double a, int b) { 
    if (b<0) { 
        throw new ApplicationException("B must be a positive integer or zero"); 
    } 
    if (b==0) return 1; 
    if (a==0) return 0; 
    if (b%2==0) { 
        return Power(a*a, b/2); 
    } else if (b%2==1) { 
        return a*Power(a*a,b/2); 
    } 
    return 0; 
} 

Answer 3

В Википедии есть обширная статья о расчете квадратных корней: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Вычислить x до степени y проще: http://www.osix.net/modules/article/?id=696

Мне понравился этот калькулятор: ... но я, честно говоря, понятия не имею, быстро ли это.

Answer 4

Вероятно, самый простой способ - реализовать плавающие версии в Managed C ++. Я не могу сказать, будет ли это быстрее, чем запеченные двойные версии, или нет.