0

我试图从他 1989 年的论文“Why Functional Programming Matters”中近似 Hughes 函数版本的 Newton-Raphson 平方根算法。

我感谢任何有关替代方法的建议：越多越好。我目前的方法使用 Niebler 的 range-v3。您将在代码片段中看到我创建了一个生成器来创建连续迭代并将它们插入到流中。我的问题是终止条件。我需要检测流中连续浮点数之间的差异何时低于阈值：

#include <iostream>
#include <range/v3/all.hpp>

using namespace ranges::view;

int main() {

  auto sqrt_stream = generate([ x = 1.f, n = 3.f ]() mutable {
    auto prevx = x;
    x = (x + n / x) / 2;
    return prevx;
  });

  std::vector<float> sequence = sqrt_stream | take_while([](int x) { ??? });

  return 0;
}

我不确定如何获得任何购买来比较连续元素，例如简单的前向差异。即使我这样做了，一旦我将流转换为前向差异，我将如何从生成器中恢复适当的元素？

4

2 回答 2

1

我能想到的最简单的解决方案是生成成对的序列元素并通过连续的差异进行过滤（live）：

  auto pair_stream = generate([ x = 1., n = 7. ]() mutable {
    auto prevx = x;
    x = (x + n / x) / 2;
    return std::make_pair(prevx, x);
  });

  auto rng = pair_stream | take_while([](auto&& pair) {
    return std::abs(pair.second - pair.first) > epsilon;
  }) | transform([](auto&& x) { return x.second; });

这必然会忽略序列中的第一个估计。

于 2017-06-01T16:51:11.147 回答
0

我从即将出版 的《C++ 函数式编程》一书的作者 Ivan Čukić 那里得到了一个建议。他给了我与 +Casey 相同的建议，即使用对，尽管我对实现进行了一些不同的充实，并使其具有通用性。我使用 zip 来制作对（2 个元组）。完整的解决方案如下，供任何好奇的人将来参考。

我对代码不满意。它当然不漂亮，而且我觉得有很大的空间可以让头脑清醒的思维简化它。但我已经把时间花在了投资上。欢迎进一步改进。

#include <iostream>
#include <list>
#include <range/v3/all.hpp>

using namespace ranges::view;

// create a lazy stream given a function f and a seed value a0.
// stream will contain [a0, f(a0), f(f(a0)), f(f(f(a0))),...]
template <typename T> //
auto repeat_stream(std::function<T(T)> f, T a0) {
  return generate([ f, a = a0 ]() mutable {
    auto prev = a;
    a = f(a);
    return prev;
  });
}

// Consumes a stream until cosnecutive values differ within eps, and then the
// latest value is returned.
template <typename E, typename T>
E within(E eps, T v) {
  std::list<std::tuple<E, E>> converging_list =
      zip(v, v | drop(1))
        | take_while([eps](std::tuple<E, E> x) {
            return std::abs(std::get<0>(x) - std::get<1>(x)) > eps;
        });
  return std::get<0>(converging_list.back());
}

// Newton-Raphson Square Roots
// A la Hughes 1989 "Why Functional Programming Matters"
// http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf
float nr_sqrt(float x, float x0) {
  return within(
      1E-15,
      repeat_stream<float>([n = x](float a) { return (a + n / a) / 2; }, x0));
}

int main() {

  std::cout << nr_sqrt(9, 4) << std::endl;

  return 0;
}

编辑：让我感到困扰的是，休斯函数程序，由我转录成 C++，可能是有史以来最愚蠢的计算平方根的程序。我决定再次解决这个问题。

这一次，我把寻找函数不动点的过程抽象出来了。我使用递归 lambda 来创建迭代循环，并std::bind部分应用于NNewton-Raphson 步骤：

#include <cmath>
#include <functional>
#include <iostream>

using namespace std::placeholders;

template <typename T>
T fixedpoint(std::function<T(T)> f, T start, T eps) {

  std::function<T(T, T)> iter = [&iter, eps, &f](T old, T nw) -> T {
    if (std::abs(old - nw) < eps)
      return nw;
    else
      return iter(nw, f(nw));
  };

  return iter(start, f(start));
}

auto nr_step(double N, double a) { return (a + N / a) / 2; }

int main() {

  std::cout << fixedpoint<double>(std::bind(nr_step, 3, _1), 1.2, 1E-10)
            << std::endl;

  return 0;
}

如果有人知道如何std::function<T(T)>通过自动类型推断来解决，这样我就不必指定fixedpoint<double>我会很高兴听到它。

于 2017-06-01T19:00:20.513 回答