Skip to content

Approximate Pi

Full Recipe

Shared by: Ethan Bell

Incrementally approximate pi using Leibniz' formula for π

Pi Recipe
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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.

  - 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.7.3.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.

Run this 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.

Get Best Approximation

Quine will manifest a graph similar to this.

Graph structure

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.

Aproximation Stream

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