全宇宙の素粒子の数を超えて…C++で巨大数に挑戦！（おまけ）

　前回『巨大数の計算』では、次のように書きました。

本当は不要な部分は元の値を参照した方が（特にBigIntを使う場合に）都合がよいのでしょうが、今回は割愛します。

　が、折角ですのでもうちょっと頑張ってみます。人類の技術が発展したら、マイクロワームホールの先に作った別宇宙を使ってgoogolplex*1程度の整数までなら表現できるようになるかもしれませんし、その時に宇宙を丸々コピーする羽目になるのもよろしくありません。

#include <iostream>
#include <map>
#include <vector>
#include <memory>
#include <initializer_list>
#include <algorithm>

template <class T>
T hyper(const T& a, const T& n, const T& b)
{
  if (0 == n) return (T)(b + 1) ;
  if (1 == n) return (T)(a + b) ;
  if (2 == n) return (T)(a * b) ;

  if (0 == b) return (T)1 ;

  T result = a ;
  T n_1 = (T)(n - 1) ;
  for (T i = b - 1 ; i > 0 ; --i) {
    result = hyper(a, n_1, result) ;
  }
  return result ;
}

template <class Container>
class ref_container
{
public :
  typedef typename Container::value_type value_type ;
  typedef typename Container::const_iterator container_const_iterator ;
  typedef class const_ref_container_iterator const_iterator ;
  typedef class ref_container_iterator iterator ;

public :
  class const_ref_container_iterator : public std::iterator<std::random_access_iterator_tag, typename Container::value_type>
  {
    friend class ref_container ;

  public:
    typedef typename Container::const_iterator container_const_iterator ;

  private :
    const_ref_container_iterator(ref_container &base_container, const container_const_iterator &it)
      : m_base_container(&base_container), m_it(it)
    {}

  public :
    bool operator ==(const const_ref_container_iterator &b) const
    {
      return (this->m_base_container == b.m_base_container) && (this->m_it == b.m_it) ;
    }

    bool operator !=(const const_ref_container_iterator &b) const
    {
      return !(*this == b) ;
    }

    const value_type &operator*() const
    {
      auto found = m_base_container->m_values.find(m_it) ;
      if (found == m_base_container->m_values.end()) return *m_it ;
      return *((*found).second) ;
    }

    const_ref_container_iterator operator +(const size_t n) const
    {
      return const_ref_container_iterator(*m_base_container, m_it + n) ;
    }

    const_ref_container_iterator operator -(const size_t n) const
    {
      return const_ref_container_iterator(*m_base_container, m_it - n) ;
    }

    size_t operator -(const const_ref_container_iterator &b) const
    {
      return m_it - b.m_it ;
    }

    const const_ref_container_iterator &operator --()
    {
      --m_it ;
      return *this ;
    }

    const const_ref_container_iterator &operator ++()
    {
      ++m_it ;
      return *this ;
    }

    const_ref_container_iterator operator --(int)
    {
      return const_ref_container_iterator(*m_base_container, m_it--) ;
    }

    const_ref_container_iterator operator ++(int)
    {
      return const_ref_container_iterator(*m_base_container, m_it++) ;
    }
    
    const ref_container &base_container() const { return *m_base_container ; }
    const container_const_iterator &base_iterator() const { return m_it ; }
    
  protected :
    ref_container *m_base_container ;
    container_const_iterator m_it ;
  } ;

  class ref_container_iterator : public const_ref_container_iterator
  {
  public :
    ref_container_iterator(ref_container &base_container, const container_const_iterator &it)
      : const_ref_container_iterator(base_container, it)
    {}

    ref_container_iterator operator +(const size_t n) const
    {
      return ref_container_iterator(*this->m_base_container, this->m_it + n) ;
    }

    ref_container_iterator operator -(const size_t n) const
    {
      return ref_container_iterator(*this->m_base_container, this->m_it - n) ;
    }

    value_type &operator*()
    {
      auto found = this->m_base_container->m_values.find(this->m_it) ;
      if (found == this->m_base_container->m_values.end()) {
        std::shared_ptr<value_type> p(new value_type(*(this->m_it))) ;
        this->m_base_container->m_values.insert(std::make_pair(this->m_it, p)) ;
        return *p ;
      }
      else if (1 < (*found).second.use_count()) {
        std::shared_ptr<value_type> p(new value_type(*((*found).second))) ;
        this->m_base_container->m_values.insert(std::make_pair(this->m_it, p)) ;
        return *p ;
      }
      return *((*found).second) ;
    }
  } ;

public :
  ref_container(const container_const_iterator &begin, const container_const_iterator &end)
    : m_it(*this, begin), m_it_end(*this, end), m_size(end - begin)
  {}

  ref_container(const const_ref_container_iterator &begin, size_t n)
    : m_it(begin.base_container().m_it), m_it_end(m_it + n), m_values(begin.base_container().m_values), m_size(n)
  {}
  
  const_ref_container_iterator begin() const { return m_it ; }
  const_ref_container_iterator end() const { return m_it_end ; }
  
  ref_container_iterator begin() { return m_it ; }
  ref_container_iterator end() { return m_it_end ; }

  const value_type &operator[](size_t n) const
  {
    return *(((const_ref_container_iterator&)m_it) + n) ;
  }

  size_t size() const { return m_size ; }

  bool pop_back()
  {
    if (0 == m_size) return false ;
    --m_size ;
    --m_it_end ;
    m_values.erase(m_it_end.base_iterator()) ;
    return true ;
  }

private :
  ref_container_iterator m_it ;
  ref_container_iterator m_it_end ;
  std::map<container_const_iterator, std::shared_ptr<value_type>> m_values ;
  size_t m_size ;
} ;


template <class Container>
typename Container::value_type conway_chain(const ref_container<Container>& list)
{
  typedef typename Container::value_type T ;
  const T ONE = (T)1 ;

  auto begin = list.begin() ;
  size_t n = std::find(begin, list.end(), ONE) - begin ; // 「1」が出てくる以降の無視
  if (2 <= n && 2 == *begin && 2 == *(begin + 1)) return (T)4 ;
  switch (n) {
  case 0 : return ONE ;
  case 1 : return *begin ;
  case 2 : return hyper(*begin, (T)3, *(begin + 1)) ;
  case 3 : return hyper(*begin, *(begin + 2) + 2, *(begin + 1)) ;
  default :
    ref_container<Container> v(begin, n) ;

    auto rit0 = v.end() - 1 ;
    auto rit1 = rit0 - 1 ;
    while (true) {
      --*rit1 ;
      *rit1 = conway_chain(v) ;
      if (ONE == --*rit0) {
        v.pop_back() ;
        if (3 == v.size()) {
          const ref_container<Container> &cv = v ;
          return hyper(cv[0], cv[2] + 2, cv[1]) ;
        }

        // イテレータを求め直す
        rit0 = v.end() - 1 ;
        rit1 = rit0 - 1 ;
      }
    }
  }
}

template <class Container>
typename Container::value_type conway_chain(const Container& list)
{
  return conway_chain(ref_container<Container>(list.begin(), list.end())) ;
}

int main()
{
  std::cout << conway_chain(std::vector<unsigned long long>({3ull, 3ull, 2ull})) << std::endl ;
  return 0 ;
}

　アイディアとしては、通常は元のコンテナの内容を参照しつつ、必要に応じて値のコピーを行なうような、特殊なコンテナを使っています。ref_container_iterator::operator*() にて、元のコンテナを参照している場合と、保持しているコピー値が別のコンテナに共有されている場合はコピー値を作る、という処理。
　本当は、参照操作ではなく代入操作の際にコピーが作られるよう、operator*()は参照そのものではなく参照のラッパーを返すようにすればより良いのですが、今回は代入せずに参照のみするようなケースをなくすことができるため、省略しています。

無限論の教室 (講談社現代新書)

*1:10の(10の100乗)乗