Tag Archives: geometry

Just for Fun: Estimating pi with Scheme

../img/double-star-from-pentagon-backlit.jpg

A while back I shared some Perl code for calculating the circumference of a circle without knowing 𝛑. Just for fun, and due to my longtime infatuation with all things Schemish, I’ve written a little pi approximator in Scheme. It uses the idea that we can approximate a circle using smaller and smaller triangles stacked on top of each other. (See previously for a better explanation with a picture.)

And now, the code!

;;;; pi.scm -- Estimate the value of 𝛑 using smaller and smaller
;;;; triangles.

;;; Call it like so: (pi-estimate n), where n is the number of
;;; iterations you'd like to go through. It doesn't take many to get
;;; pretty accurate.

(define reference-pi 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679)

(define (circumference radius)
  (* 3.14159 2 radius))

(define (square x)
  (* x x))

(define (hypotenuse a b)
  (sqrt (+ (expt a 2) (expt b 2))))

(define (pi-iter radius a b count maxcount)
  (let* ((hyp (hypotenuse a b))
         (newbase (- radius (sqrt (- (square radius)
                                     (square (/ hyp 2)))))))
    (if (= count maxcount)
        (/
         (* 2 hyp (expt 2 (+ 1 count)))
         (* 2 radius))
        (pi-iter radius newbase (/ hyp 2) (+ count 1) maxcount))))

(define (pi-estimate iterations)
  (pi-iter 128 128 128 0 iterations))

(Origami image courtesy Melisande under Creative Commons license.)

Advertisements

How to calculate the circumference of a circle (without knowing pi)

Some time ago I posted the following little challenge to www.reddit.com/r/programming:

Dear Proggit: Imagine that you must devise a method to calculate the circumference of a circle of any radius. The catch? You are unaware of the existence of Pi.

The other catch? You must begin right now. You may use only what tools you have in front of you (text editor, calculator, pencil and paper with compass(!)), without looking anything up. That means no Google searches, no Wikipedia, no formulas in a book, nothing.

Once you have devised a method, please write a small program in the language of your choice that performs the calculation (the more accurate, the better). Bonus points will be awarded for brevity, cleverness, etc.

I will post my little solution sometime tomorrow. Enjoy!

One final note: If you are a total geometry/math wizard who thinks this is lame, please refrain from posting; I want this to be a fun problem for those of us who will get something out of it.

https://logicgrimoire.files.wordpress.com/2012/09/wpid-circle-diagram.png

Below is my method for calculating (or rather, estimating) the circumference of a circle without using pi. This method involves summing the lengths of the hypotenuses of smaller and smaller triangles, as shown in the diagram above.

Begin by cutting the given circle into quarters. Using the radius r, find the hypotenuse of triangle A using Pythagoras’ method. Cut the hypotenuse in half; using that, and the radius, you can calculate the length of line segment Q. Subtract Q from r, and you have the length of line segment P, which is one side of the right triangle B. That, combined with half the hypotenuse of A, will allow you to calculate the hypotenuse of B. Continue, calculating the hypotenuses of smaller and smaller triangles. Sum as many lengths as are required to cover the quarter-circle arc, and multiply by 4 (or multiply the current length by 2^(n*+1), where *n is the number of iterations of the method you’ve performed).

Below I’ve provided an implementation in Perl. Note that the Perl interpreter doesn’t optimize away recursive function calls (that I know of), so you could in theory blow up the stack. In practice, it only takes a few iterations to arrive at a reasonable estimate, so it’s not a problem.

#!/usr/bin/env perl

use strict;
use warnings;
use autodie;
use Math::Trig ':pi';

my ($radius, $maxiter) = @ARGV;
my $iterations = 0;

sub main {
  my ($radius, $a, $b) = @_;
  my $hyp = hypotenuse($a, $b);
  my $newbase = $radius - sqrt($radius**2 - ($hyp / 2)**2);
  $iterations++;
  die "Current hypotenuse is $hyp after $iterations iterations\n"
    . "Estimated circumference: " . $hyp * (2**($iterations+1)) . "\n"
      . "Actual circumference: " . ($radius*2) * pi . "\n"
        if $iterations == $maxiter;
  main($radius, $newbase, ($hyp / 2));
}

sub hypotenuse {
  my ($a, $b) = @_;
  return sqrt($a**2 + $b**2);
}

main($radius, $radius, $radius);

As you can see, we pretty much mirror the textual description given above, but in code. We then compare our work to the “real” value of pi using the Perl core’s Math::Trig constant. Save the above into a file named circ.pl, and you can run it like so:

mel@foo:~$ ./circ.pl 4 12 # Given a radius of 4, run through 12 iterations
Current hypotenuse is 0.00306796150057116 after 12 iterations
Estimated circumference: 25.132740612679
Actual circumference: 25.1327412287183

I might not want to try to calculate planetary orbits using this kind of rough estimation, but for 99% of real-world cases, it’s good enough.