BigQueryでNewton法

[takegue]

BigQueryでNewton法

Newton法では次の漸化式で、Nの平方根を求めることができる:

$$ x_{n+1} = x_{n} - \frac{x^2 - N}{2 x} $$

漸化式で表されるものは、WITH RECURSIVEで表すことができる.
この実装は次のようになる。

このSQLにおいては、 2~1000までの数字の平方根を求めることができる。

with 
  recursive newton as (
	-- Initial step
    select 0 as n, 1 + 0.5 * (N - 1) as x, N as tgt from unnest(generate_array(2, 1000)) as N
    union all
	-- Update step
    select 
      n + 1
      , x - (x * x - tgt) / (2 * x)
      , tgt
    from newton
    where 
      -- Maximum recursive depth 
      n < 98
      -- tolerance error
      and abs(x * x - tgt) > 1e-06
  )

  select *, tgt - x*x as e from newton
  qualify n = max(n) over (partition by tgt) 
  order by tgt