Улучшение эффективности этого кода с отслеживанием переменной?

Question

я написал ниже код наброски, в основном, чтобы подвести массив (а), где каждый элемент умножается на величину х^I:

y = a(0) 
i = 0 
{y = sum from i=0 to (n-1) a(i) * x^i AND 0 <= n <= a.length} //Invariant 

while (i < (n-1)) 
{y = sum from i=0 to (n-1) a(i) * x^i AND 0 <= n <= a.length AND i < (n-1)} 
y = y + a(i)*x^i 
i = i + 1 
end while 

{y = sum from i=0 to (n-1) a(i) * x^i} //Postcondition 

Следует заметить, что я не ожидаю код для компиляции - это просто разумный план того, как код должен работать. Мне нужно повысить эффективность кода, используя переменную отслеживания и, таким образом, связующий инвариант для связывания указанной переменной с остальной частью кода. Вот где я застрял. Что было бы полезно отслеживать в этом случае? Я думал о сохранении значений суммы на каждой итерации, но я не уверен, что это делает трюк. Если бы я мог понять, что отслеживать, я уверен, что было бы тривиально связать его с пространством. Может ли кто-нибудь увидеть, как мой алгоритм может быть улучшен с помощью переменной отслеживания?

Answer 1

Таким образом, кажется, что вы пытаетесь закончить с этим:

(a(0)*x^0) + (a(1)*x^1) + ... + (a(n-1)*x^(n-1)) 

Является ли это правильно?

Единственный способ, который я могу улучшить для повышения производительности, будет, если операция ^ более дорогостоящая, чем операция *. В этом случае вы можете отслеживать переменную x^n по мере того, как вы идете, умножая x на значение через каждую итерацию.

В самом деле, в этом случае вы, вероятно, можете начаться в конце массива и работать ваш путь назад, умножая на x каждый раз, чтобы произвести:

(((...((a(n-1)*x+a(n-2))*x+...)+a(2))*x+a(1))*x)+a(0) 

Это было бы теоретически быть немного быстрее, чем перерасчет x^i каждый раз, но это не будет алгоритмически быстрее. Вероятно, это не будет на порядок быстрее.

Answer 2

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

// Precondition: 1 <= n <= a.length 

// Invariant: 
{ 0 <= i < n AND xi = x^i AND y = sum(j = 0..i) . a(j) * x^j } 

// Establish invariant at i = 0: 
// xi = x^0 = 1 AND y = sum(j=0..0) . a(j) * x^j = a(0) * x^0 = a(0) 
i = 0; 
xi = 1; 
y = a(0); 

while (i < n - 1) { 

    i = i + 1;   // Break the invariant 
    xi = xi * x;   // Re-establish it 
    y = y + a(i) * xi 
} 

// Invariant was last established at i = n-1, so we have post condition: 
{ y = sum(j = 0..n-1) . a(j) * x^j } 

Наиболее распространенный и численно стабильный способ вычисления многочленов с правилом Горнера

y = 0 
for i = n-1 downto 0 do y = y * x + a(i)