sql - 在sql中计算函数的不动点？

Question

我想编写 sql 查询来计算某个函数的 iterated function sequence 直到​​达到固定点，然后返回该固定点:

f(f(f(f ..(x)))) = x0 = f(x0)

例如让 f(x) = (256/x + x)/2:

create function f(x float) returns float as $$
  select (256/x + x) / 2
$$ language sql;

这是我编写查询的尝试:

create function f_sequence(x float) returns table(x0 float) as $$
  with recursive
    t(a,b) as
      (select x, f(x)
        union all
        select b, f(b) from t where a <> b)
    select a from t;
$$ language sql;

现在可以得到收敛到某个固定点的迭代序列:

=# select f_sequence(333);
   f_sequence
------------------
              333
 166.884384384384
 84.2091902577822
 43.6246192451207
 24.7464326525125
 17.5456790321891
 16.0680829640781
 16.0001442390486
 16.0000000006501
               16
(10 rows)

(实际上收敛到√256，因为这是计算平方根的Babylonian method。)

现在我需要一个额外的查询来只获取序列的最后一行:

=# with
    res as (select array_agg(f_sequence) as res from f_sequence(333))
    select res[array_length(res,1)] from res;
 res 
-----
  16
(1 row)

问题是:这个怎么写更简洁？
特别是，我不喜欢那个单独的查询来获取最后一个值(并且我需要在数组中累积所有中间值)。

Answer 1

保留 f 的定义。

在您的序列生成中，在输出中保留 f(x) 的值。

create function f_sequence(x float) returns table(x0 float, fx float) as $$
  with recursive
    t(a,b) as
      (select x, f(x)
        union all
        select b, f(b) from t where a <> b)
    select a, b from t;
$$ language sql;

然后将结果限制为固定值。

select x0 from f_sequence(256) where x0 = fx;

编辑:添加程序版本。

create function iterf(x float) returns float as $$
declare fx float := f(x);
begin
  while fx != x loop
    x := fx;
    fx := f(x);
  end loop;
  return fx;
end;
$$ language plpgsql;