Approximate Pi

Full Recipe

Shared by: Ethan Bell

Incrementally approximate pi using Leibniz' formula for π

Pi Recipe

version: 1
title: Pi
contributor: https://github.com/emanb29
summary: Incrementally approximates pi using Leibniz' formula
description: |-
  Incrementally approximates pi using Leibniz' formula -- the arctangent function is incrementally
  (corecursively) computed along :improved_by edges, and each arctangent approximation is quadrupled
  to yield an approximation of pi.

ingestStreams: []

standingQueries:
  - pattern:
      type: Cypher
      query: MATCH (n:arctan) WHERE n.approximation IS NOT NULL AND n.denominator IS NOT NULL RETURN DISTINCT id(n) AS id
    outputs:
      # iterate over arctan
      iterate:
        type: CypherQuery
        query: |-
          MATCH (n)
          WHERE id(n) = $that.data.id
          WITH n, -sign(n.denominator)*(abs(n.denominator)+2) as nextDenom
          WITH n, nextDenom, n.approximation+(1/nextDenom) as nextApprox
          MATCH (next) WHERE id(next) = idFrom(nextDenom)
          SET next:arctan, next.denominator = nextDenom, next.approximation=nextApprox
          CREATE (n)-[:improved_by]->(next)
      # map arctan to piApprox
      piApprox:
        type: CypherQuery
        query: |-
          MATCH (arctan)
          WHERE id(arctan) = $that.data.id
          WITH arctan, arctan.denominator AS denominator, arctan.approximation*4 AS approximatedPi
          MATCH (approximation) WHERE id(approximation) = idFrom('approximation', denominator)
          SET approximation:piApproximation, approximation.approximatedPi = approximatedPi
          CREATE (arctan)-[:approximates]->(approximation)
          RETURN approximatedPi
        andThen:
          type: WriteToFile
          path: $out_file

nodeAppearances:
  - predicate:
      propertyKeys: []
      knownValues: {}
      dbLabel: piApproximation
    icon: π
    size: 40
    color: "#f1c232"
    label:
      type: Property
      key: approximatedPi
      prefix:
  - predicate:
      propertyKeys: []
      knownValues: {}
      dbLabel: arctan
    icon: ⦛
    size: 20
    color: "#000000"
    label:
      type: Constant
      value: 𝚊𝚛𝚌𝚝𝚊𝚗 

sampleQueries:
  - name: "[No Output] Run this query to begin processing."
    query: WITH 1 AS initialDenominator MATCH (n) WHERE id(n) = idFrom(1) SET n.denominator = toFloat(1), n.approximation = toFloat(1), n:arctan
  - name: "[Node] Get Best Approximation (so far)"
    query:
      CALL recentNodes(15) YIELD node AS nId
      MATCH (n)
      WHERE id(n) = nId AND n.approximatedPi IS NOT NULL
      RETURN n LIMIT 1
  - name: "[Text] Get Best Approximation (so far)"
    query:
      CALL recentNodes(15) YIELD node AS nId
      MATCH (n)
      WHERE id(n) = nId AND n.approximatedPi IS NOT NULL
      RETURN n.approximatedPi LIMIT 1
  - name: "[Text] Repeatedly Get Best Approximation (so far)"
    query:
      UNWIND range(0, 1000) AS x UNWIND range(0, 1000) AS y
      CALL util.sleep(1000)
      CALL cypher.doIt("
        CALL recentNodes(15) YIELD node AS nId
        MATCH (n)
        WHERE id(n) = nId AND n.approximatedPi IS NOT NULL
        RETURN n.approximatedPi AS approximatedPi LIMIT 1
      ") YIELD value
      RETURN value.approximatedPi AS approximatedPi, abs(pi() - value.approximatedPi) AS error
quickQueries: [ ]

Download Recipe

Scenario

Incrementally approximates pi using Leibniz' formula for π -- the arctangent function is incrementally (corecursively) computed along :improved_by edges, and each arctangent approximation is quadrupled to yield an approximation of pi.

How it Works

The recipe is completely self contained. We take advantage of the unique match, output action structure of a standing query to improve the approximation of pi by continuously streaming nodes back into the graph.

YAMLJSON

  - pattern:
      type: Cypher
      query: MATCH (n:arctan) WHERE n.approximation IS NOT NULL AND n.denominator IS NOT NULL RETURN DISTINCT id(n) AS id
    outputs:
      # iterate over arctan
      iterate:
        type: CypherQuery
        query: |-
          MATCH (n)
          WHERE id(n) = $that.data.id
          WITH n, -sign(n.denominator)*(abs(n.denominator)+2) as nextDenom
          WITH n, nextDenom, n.approximation+(1/nextDenom) as nextApprox
          MATCH (next) WHERE id(next) = idFrom(nextDenom)
          SET next:arctan, next.denominator = nextDenom, next.approximation=nextApprox
          CREATE (n)-[:improved_by]->(next)
      # map arctan to piApprox
      piApprox:
        type: CypherQuery
        query: |-
          MATCH (arctan)
          WHERE id(arctan) = $that.data.id
          WITH arctan, arctan.denominator AS denominator, arctan.approximation*4 AS approximatedPi
          MATCH (approximation) WHERE id(approximation) = idFrom('approximation', denominator)
          SET approximation:piApproximation, approximation.approximatedPi = approximatedPi
          CREATE (arctan)-[:approximates]->(approximation)
          RETURN approximatedPi
        andThen:
          type: WriteToFile
          path: $out_file

/api/v1/query/standing/STANDING-1

{
  "pattern": {
    "type": "Cypher",
    "query": "MATCH (n:arctan) WHERE n.approximation IS NOT NULL AND n.denominator IS NOT NULL RETURN DISTINCT id(n) AS id"
  },
  "outputs": {
    "iterate": {
      "type": "CypherQuery",
      "query": "MATCH (n)\nWHERE id(n) = $that.data.id\nWITH n, -sign(n.denominator)*(abs(n.denominator)+2) as nextDenom\nWITH n, nextDenom, n.approximation+(1/nextDenom) as nextApprox\nMATCH (next) WHERE id(next) = idFrom(nextDenom)\nSET next:arctan, next.denominator = nextDenom, next.approximation=nextApprox\nCREATE (n)-[:improved_by]->(next)"
    },
    "piApprox": {
      "type": "CypherQuery",
      "query": "MATCH (arctan)\nWHERE id(arctan) = $that.data.id\nWITH arctan, arctan.denominator AS denominator, arctan.approximation*4 AS approximatedPi\nMATCH (approximation) WHERE id(approximation) = idFrom('approximation', denominator)\nSET approximation:piApproximation, approximation.approximatedPi = approximatedPi\nCREATE (arctan)-[:approximates]->(approximation)\nRETURN approximatedPi",
      "andThen": {
        "type": "WriteToFile",
        "path": "$out_file"
      }
    }
  }
}

We use a tag propagation technique set up in the standing query to perform the calculation.

Submitting the [No Output] Run this query to begin processing. sample query creates a seed node (n:arctan) in the graph with an initial approximation of 1.0.

WITH 1 AS initialDenominator 
MATCH (n) 
WHERE id(n) = idFrom(1) 
  SET n.denominator = toFloat(1), 
      n.approximation = toFloat(1), 
      n:arctan

Once the seed node is set in the graph, iteration over the approximation is done in several parts.

1. Detect when the seed node or its descendants enter the graph.

   MATCH (n:arctan) 
   WHERE n.approximation IS NOT NULL 
     AND n.denominator IS NOT NULL 
   RETURN DISTINCT id(n) AS id
   

2. Iterate over arctan.

   MATCH (n)
   WHERE id(n) = $that.data.id
   WITH n, -sign(n.denominator)*(abs(n.denominator)+2) as nextDenom
   WITH n, nextDenom, n.approximation+(1/nextDenom) as nextApprox
   MATCH (next) WHERE id(next) = idFrom(nextDenom)
   SET next:arctan, next.denominator = nextDenom, next.approximation=nextApprox
   CREATE (n)-[:improved_by]->(next)
   

3. Map arctan to piApprox.

   MATCH (arctan)
   WHERE id(arctan) = $that.data.id
   WITH arctan, arctan.denominator AS denominator, arctan.approximation*4 AS approximatedPi
   MATCH (approximation) WHERE id(approximation) = idFrom('approximation', denominator)
   SET approximation:piApproximation, approximation.approximatedPi = approximatedPi
   CREATE (arctan)-[:approximates]->(approximation)
   RETURN approximatedPi
   

Running the Recipe

❯ java -jar quine-1.8.2.jar -r pi.yaml -x out_file=approximation.log
Graph is ready
Running Recipe: Pi
Using 2 node appearances
Using 4 sample queries
Running Standing Query STANDING-1
Quine web server available at http://localhost:8080

 | => STANDING-1 count 0

Connect to Quine once it is started and submit the [No Output] Run this query to begin processing. sample query.

Warning

Once you submit the [No Output] Run this query to begin processing. query, Quine will immediately begin to produce new approximations for pi. You must quit Quine (Ctrl+C) to stop the sequence.

You will immediately see the count of STANDING-1 matches increase and entries in the approximation.log fie.

Terminal Window

 | => STANDING-1 count 5043

approximation.log

{"meta":{"isPositiveMatch":true,"resultId":"106f731f-be27-2650-af22-b3010744124c"},"data":{"approximatedPi":3.141791500277029}}

Submit the [Node] Get Best Approximation (so far) sample query to display the latest approximation of pi as a node.

Quine will manifest a graph similar to this.

Submit the [Text] Repeatedly Get Best Approximation (so far) sample query with Shift+Enter to view the stream of updated approximations in the Exploration UI.

Build your skills

What ingest query could be added to replace the function of the [No Output] Run this query to begin processing. sample query?

Solution

We solved this by modifying the ingest query to use the NumberIteratorIngest type.

Replace the empty ingest query with this one.

  - type: NumberIteratorIngest
      startAtOffset: 1
      ingestLimit: 1
      format:
          type: CypherLine
          query: |-
              WITH $that AS initialDenominator
              MATCH (n)
              WHERE id(n) = idFrom(1)

              SET n.denominator = toFloat(1),
                  n.approximation = toFloat(1),
                  n:arctan