5 июля 2012 г.

Оптимизация вычисления некоторых функций: полиномиальная функция (продолжение)

Начало см. здесь
Решил все же определить насколько действительно алгоритм Горнера быстрее вычисляет значение полиномиальной функции. Для этого сделал имплементацию на C. Код под катом, жми "Далее"

What can you do with bytes? WCYDWB?!

Нашел замечательный проект одного из членов сообщества bytearray.org. Книга «Что можно сделать с байтами?» посвящена целиком и полностью классу ByteArray и его применению в AS3/Flex для работы со звуком, изображениями, формирования PDF.
Главы книги можно скачать отсюда: http://www.bytearray.org/wp-content/projects/wcydwb/http://www.bytearray.org/?p=711
Ничего экстраординарного, однако в книге приведены ряд ссылок на любопытные проекты на AS3:

  1. Commodore 64 emulator, http://codeazur.com.br/stuff/fc64_final/
  2. Intel8080 “Space Invaders” CPU Emulation: http://www.bytearray.org/?p=622
  3. AlivePDF PDF generation library, http://alivepdf.bytearray.org
...и другие. Чтение может вдохновить на создание парсера какого-нибудь формата, например SWF. Кстати приводится и пример кода, читающего формат SWF.

Чтиво для суровых флешеров-байтоёбов. 

2 июля 2012 г.

Поддержка MathML браузерами Webkit

Тестовая страница находится вот тут — https://eyeasme.com/Joe/MathML/MathML_browser_test

Популярная Webkit-линейка нифига MathML не поддерживает. Что, в общем-то, достаточно печально.

На скриншотах, правильно, смотрим в крайнюю правую колонку.

Google Chrome 20.0.1132.47 (Mac OS X Lion)


Safari 5.1.7 (7534.57.2)



1 июля 2012 г.

Алгоритм Томаса (прогонки) на MATLAB

Скопировать или посмотреть код красиво на Pastebin

%{
Тестовый расчет
---------------

Трехдиагональная матрица системы:

1 2 0 0|8
2 3 4 0|17
0 5 6 7|35
0 0 8 9|26
Результат вычисления
x1 = 2
x2 = 3
x3 = 1
x4 = 2

Проверка:
1*2 + 2*3 + 0*1 + 0*2 = 8
2*2 + 3*3 + 4*1 + 0*2 = 17
0*2 + 5*3 + 6*1 + 7*2 = 35
0*2 + 0*3 + 8*1 + 9*2 = 26

USAGE:
  [X, Correct, Stable] = thomas(A,B,C,D)
Заметим, что необходимо передавать -b в параметрах, т.к. исходная формулировка задачи выглядит так:

-b1  c1   0    0  | d1
a1  -b2   c2   0  | d2
0    a2  -b3   c3 | d3
0    0    a3  -b4 | d4

Аналогично для любой размерности задачи.
TEST:
  [[2 3 1 2], true, false] = thomas([2,5,8],[-1,-3,-6,-9],[2,4,7],[8,17,35,26])

%}


function [ X, Correct, Stable ] = thomas( A, B, C, D )
%THOMAS Решение трехдиагональной СЛАУ

N = numel(D); % размерность матрицы

%Начальные значения переменных
X = zeros(1, N);
Correct = true;
Stable = true;
Test = false;

%Прямой ход — преобразуем к наддиагональной матрице
P = zeros(1, N-1);
Q = zeros(1, N);

P(1) = C(1)/B(1);
Q(1) = -D(1)/B(1);
for i=2:1:N
    t = (B(i)-A(i-1)*P(i-1));
    if (t == 0)
        Correct = false;
        X = -1;
    end
    if i < N
        P(i) = C(i)/t;
        if (abs(P(i))>=1)
            Stable = false;
            X = -1;
        end
    end
    Q(i) = (A(i-1)*Q(i-1)-D(i))/t;
end

%Обратный ход
X(N) = Q(N);
for i=N-1:-1:1
    X(i) = P(i)*X(i+1) + Q(i);
end

end


Выполнено по материалам этого блога Алгоритмы: метод прогонки

Оптимизация вычисления некоторых функций: полиномиальная функция

При построении различного рода фильтров сигналов, в расчетах в области трехмерной графики, игровой физики, в ряде приложений при построении пользовательских интерфейсов, возникает необходимость в вычислении значений полиномиальных функций:



Вычисление значения напрямую требует i сложений и i*(i+1)/2 умножений. Реализация такого вычислительного процесса в системах реального времени может оказаться непомерно затратной.
Для оптимизации этого процесса используют алгоритм Горнера, суть которого в представлении исходного выражения в виде:



Вычисление данного выражения требует i умножений и i сложений. Кроме сокращения вычислительной сложности, данный подход требует для реализации меньшее число регистров сумматора, что важно при реализации в встраиваемых системах.

Конечно же имплементация тривиальна. Приведем ее только для справки на Javascript и Erlang.

// We define our own power function for purity of experiment
// Prototype give us "sugar": (2).power(8) => 256
Number.prototype.power = function (q) {
  var result = 1;
  for (var i = 0; i < q; i++)
    result *= this;
  return result;
}

// straightforward implementation
function naive (a, x) {
 var result = 0;
 for (var i = 0; i < a.length; i++)
   result = result + a[i] * x.power(i);
 return result;
}

// recursive implementation of Gorner
function gorner_recursive (a, x, i) { 
 if (i > a.length - 1) return 0;
 i = i || 0;
 return a[i] + x * gorner_recursive(a, x, i+1);
}

// loop implementation from recursive
function gorner_normal (a,x) {
  var b = a[a.length - 1];

  for (var i = a.length - 2; i >= 0; i--) {
    b = a[i] + x * b;    
  }
  return b;
}

// recursive in Erlang
gorner_recursive([H|T], X)->
    H + X*gorner_recursive(T,X);
gorner_recursive([],X)->
    0. 


В следующем посте расскажу про разные подходы в оптимизации тригонометрических функций.