Click here to monitor SSC
Av rating:
Total votes: 9
Total comments: 12


Alex Kuznetsov
Brain Teaser for Pi Day
02 March 2009

Alex has come up with a great idea for Pi Day. We should celebrate by trying to come up with a way, in SQL, of generating a an accurate value for Pi. If only Archimedes had possessed a laptop, his work would have been easier!

To celebrate Pi Day (14th March) we have decided to introduce a competition: Using T-SQL, find the best approximation of Pi number as a ratio of two integer numbers, both less than 1000. The ideal solution is a ratio that cannot be reduced.

Pi Day is the brainchild of the physicist Larry Shaw of San Francisco's Exploratorium, and is observed on March 14 (3/14 in American date format), due to ? being roughly equal to 3.14: At 1:59:26 pm (3.1415926) pizza and fruit pies are consumed; Celebrations can be extended: on March 14, 2004, Daniel Tammet calculated and recited 22514 decimal digits of pi.

We owe it to Archimedes that he proved that the area of a circle is equal to that of a triangle of base equal to the circumference of the circle and its height equal to the radius. The problem then became one of determining the ratio between circumference and diameter. Archimedes had to determine the value of Pi by means of seeking the limit approached by the sides of regular polygons both inscribed within, and circumscribed outside the circle. We don't know how long it took him without a laptop!

Currently we developers do not need to do it ourselves - many languages provide Pi number for us. For instance, SQL has PI() and you can use System.Math.PI in C#. However, calculating Pi as an exercise or as a brainteaser is still a fascinating way of understanding the scale of the achievements of the Ancient Greek mathematicians..

Consider the following brainteaser: using only commands, features and functions described in Books Online except for PI(), find the best approximation of Pi number as a ratio of two integer numbers, both less than 1000. The ideal solution is a ratio that cannot be reduced. You can use a helper table populated with integer numbers.

We'll reveal a solution a week after Pi Day (2009.3.14) The author of the winning solution, nominated by our distinguished panel of judges on accuracy, clarity, and ingenuity, will receive a $50 Amazon token.



This article has been viewed 5163 times.
Alex Kuznetsov

Author profile: Alex Kuznetsov

Alex Kuznetsov has been working with object oriented languages and databases for more than a decade. He has worked with Sybase, SQL Server, Oracle and DB2. He regularly blogs on sqlblog.com, mostly about database unit testing, defensive programming, and query optimization. Alex has published multiple articles on simple-talk.com and devx.com and wrote a book entitled "Defensive Database Programming with SQL Server". Currently he works with DRW Trading Group in Chicago, where he leads a team of developers, practicing agile development, defensive programming, and database unit testing every day. In his leisure time Alex prepares for and runs ultramarathons.

Search for other articles by Alex Kuznetsov

Rate this article:   Avg rating: from a total of 9 votes.


Poor

OK

Good

Great

Must read
 
Have Your Say
Do you have an opinion on this article? Then add your comment below:
You must be logged in to post to this forum

Click here to log in.


Subject: Possible Solution
Posted by: Chris Howarth (view profile)
Posted on: Tuesday, March 10, 2009 at 4:13 AM
Message:

I get 355 / 113 using the following method:

SET NOCOUNT ON
DECLARE
@numbers TABLE (ID NUMERIC(18, 14) PRIMARY KEY)

DECLARE @i INT
SET
@i = 1
  
WHILE @i < 1000
BEGIN
    INSERT INTO
@numbers
    
VALUES(@i)
    
SET @i = @i + 1
END

;WITH CTE
AS
(
SELECT  ROW_NUMBER() OVER (ORDER BY ABS(PI() - n1.ID / n2.ID)) AS RowNumber,
        
n1.ID / n2.ID AS Ratio,
        
CAST(n1.ID AS INT) AS N1ID,
        
CAST(n2.ID AS INT) AS N2ID
FROM @numbers n1
    
CROSS JOIN @numbers n2
)
SELECT  *,
        
PI() AS PI
FROM CTE
WHERE RowNumber = 1


Subject: Possible Solution - Updated
Posted by: Chris Howarth (view profile)
Posted on: Tuesday, March 10, 2009 at 4:17 AM
Message:

...and here's a slightly tweaked version that will return a pair of values that cannot be reduced:

SET NOCOUNT ON
DECLARE
@numbers TABLE (ID NUMERIC(18, 14) PRIMARY KEY)
DECLARE @i INT
    SET
@i = 1
WHILE @i < 1000
    
BEGIN
    INSERT INTO
@numbers
            
VALUES(@i)
    
SET @i = @i + 1
    
END
            
;WITH CTE
            
AS
    
(
    
SELECT ROW_NUMBER() OVER (
            
ORDER BY ABS(PI() - n1.ID / n2.ID), n1.ID) AS RowNumber,
                
n1.ID / n2.ID AS Ratio,
                
CAST(n1.ID AS INT) AS N1ID,
                
CAST(n2.ID AS INT) AS N2ID
        
FROM @numbers n1
                
CROSS JOIN @numbers n2
    
)
SELECT *,
            
PI() AS PI
    
FROM CTE
    
WHERE RowNumber = 1


Subject: You actually have to calculate pi!
Posted by: Phil Factor (view profile)
Posted on: Tuesday, March 10, 2009 at 5:14 AM
Message:

As I understand Alex's puzzle. you have to actually calculate PI. If you already know PI, then it is easy to calculate the best-fit numerator and denominator below a particular limit.

DECLARE @numbers TABLE
   (
n INT NOT NULL IDENTITY PRIMARY KEY)
INSERT @numbers DEFAULT
        VALUES
;
WHILE SCOPE_IDENTITY() < 1000
    
INSERT @numbers DEFAULT
        VALUES
;
SELECT  TOP 1
         n
AS numerator,
         ROUND
(n/PI(),0) AS denominator,
        
n/ROUND(n/PI(),0) AS Decimal_Fraction  
    
FROM @numbers
    
WHERE n>1
    
ORDER BY ABS(PI()-n/ ROUND(n/PI(),0)) ASC,
            
n ASC
            


Subject: The rules are fuzzy
Posted by: mjswart (view profile)
Posted on: Tuesday, March 10, 2009 at 9:13 AM
Message: My initial thought was that the work Phil Phactor did in the last post was the gist of the puzzle. The results that are expected are a ratio of two integers.

For the purposes of this puzzle, I don't think pi has to be calculated, for example, if PI() can't be used, then neither should 2.0 * ACOS(0.0).
What about POWER(2143.0/22.0, 0.25)? Or the constant 3.14159265?

That's why my guess is that the work done by Phil Phactor is the work asked of the puzzle.

Subject: Re: The Rules are fuzzy
Posted by: Andrew Clarke (view profile)
Posted on: Tuesday, March 10, 2009 at 9:28 AM
Message: Alex sends his apologies. Yes, he hadn't been quite explicit enough, and has amended the rules in the article to ban the use of PI(). Actually, I think that we need to ban the use of 2.0 * ACOS(0.0) and any other expressions that resolve to the value as well (thanks mjswart). The panel of distinguished judges will look most favourably on a TSQL Solution that uses a variation of Archimedes' proof, or an ingenious twist on it.

Subject: ..breaking the rules
Posted by: Phil Factor (view profile)
Posted on: Tuesday, March 10, 2009 at 10:18 AM
Message: A slight modification of my technique, using the method of the Gregory-Leibniz series. Hang on guys, we're calculating an irrational number here!

DECLARE @numbers TABLE
  
(n INT NOT NULL IDENTITY PRIMARY KEY,
   approximation numeric
(19,18) DEFAULT 0)
INSERT @numbers DEFAULT VALUES ;
WHILE SCOPE_IDENTITY() < 1000
  
INSERT @numbers DEFAULT VALUES ;

DECLARE @PI numeric(19,18),
  
@Approximation numeric(19,18),
  
@operator CHAR(1)
SELECT  @operator='+', @approximation=0

UPDATE @numbers
  
SET @Approximation=approximation=@Approximation +
  
CASE WHEN @operator='+' THEN +(4.00/n)
                   
ELSE -(4.00/n) END,
  
@operator = CASE WHEN @operator='+' THEN '-'
                   
ELSE '+' END
  WHERE
n % 2=1
SELECT @PI=AVG(approximation)
  
FROM @numbers WHERE n % 2=1 AND n>991

SELECT  TOP 1
      n
AS numerator,
      
ROUND(n/@PI,0) AS denominator,
      
n/ROUND(n/@PI,0) AS Decimal_Fraction
  
FROM @numbers  WHERE n>1
  
ORDER BY ABS(@PI-n/ ROUND(n/@PI,0)) ASC,
      
n ASC
      


Subject: Pi Maker
Posted by: Joe Celko (not signed in)
Posted on: Thursday, March 12, 2009 at 3:09 PM
Message:

>> Consider the following brainteaser: using only commands, features and functions described in Books Online except for PI(), find the best approximation of Pi number as a ratio of two integer numbers, both less than 1000. The ideal solution is a ratio that cannot be reduced. You can use a helper table populated with integer numbers. <<

A little research tells us that 355/113 is good to six decimals and meets the criteria. But 103993/33102 is good to nine decimals, so we can get a better approximation of pi without any fancy math at all.

The fastest way is to just use constants in a simple query:

SELECT X.dividend, X.divisor, X.pi
FROM (VALUES (355, 113, (CAST 355 AS DECIMAL(8,7))/ (CAST 113 AS DECIMAL(8,7))
AS X(dividend, divisor, pi);

I did it as decimal and not float to keep this at the level of a pocket calculator. If I can do more math than just a simple ratio or use floats, there are better formulas.

I suppose we could do a brute force query like:

WITH Digits (i)
AS
(SELECT X.i
  
FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9))
        
AS X(i)),
Thousands (i)
AS
(SELECT ((D1.i * D2.i * D3.i * D4.i) + 1) AS i
  
FROM Digits AS D1, Digits AS D2, Digits AS D3, Digits AS D4),

PiList (dividend, divisor, dif_pi, candiate_rank)
AS
(SELECT dividend, divisor,
        
ABS ((CAST (103993 AS DECIMAL(8,7))/ CAST (33102 AS DECIMAL(8,7)))
     - (
CAST (dividend AS DECIMAL(8,7))/ CAST (divisor AS DECIMAL(8,7))))
        
AS dif_pi    
  
FROM Thousands AS Dividends
      
CROSS JOIN
      
Thousands AS Divisors
WHERE (dividend / divisor) BETWEEN 3 AND 4)  --known integer range

SELECT P1.dividend, P1.divisor
  
FROM PiList AS P1
WHERE dif_pi
    
= (SELECT MIN(dif_pi)
          
FROM PiList AS P2);

Digits builds the table of 1 to 1000 integers. PiList is a table of candidate approximations. The base query is the (dividend, divisor) pair closet to the better aproximation. We get (355, 113) and (710, 226) as candidates, so we could do one more CTE of Candidates and add a (ROW_NUMBER() OVER (dividend)) AS candidate_size to it and keep only (candidate_size = 1).


Subject: Little known facts about the value of PI
Posted by: Andrew Clarke (view profile)
Posted on: Friday, March 13, 2009 at 8:37 AM
Message: Three years prior to the turn of the nineteenth century, one Edwin J. Goodman, M.D. introduced into the Indiana House of Representatives a bill that included the passage "disclosing the fourth important fact that the ratio of the diameter and circumference is as five-fourths to four"
Thus one of Goodman's new mathematical "truths" is that pi = 16/5 = 3.2 In spite of this
and numerous other absurd statements, the Indiana House passed the bill unanimously. On Feb. 5, 1897. The bill then passed a Senate committee, and would have been enacted into law had it not been for the last-minute intervention of Prof. C. A. Waldo of Purdue University, who happened to hear some of the deliberation while on other business.

The Quest for PI (1996) Bailey, Borwain, Borwain and Plouffe.

Subject: Calculate pi using Euler's Formula - not very accurate!
Posted by: PeterG (view profile)
Posted on: Friday, March 13, 2009 at 12:46 PM
Message: CREATE TABLE [dbo].[#Square](
[n] [int] IDENTITY(1,1) NOT NULL,
[ReciprocalSquare] AS ((1.0)/square([n]))
) ON [PRIMARY]

INSERT #Square DEFAULT VALUES ;
WHILE SCOPE_IDENTITY() < 1000
INSERT #Square DEFAULT VALUES ;
Select sqrt(6*sum(Reciprocalsquare))as "pi" from #square

Subject: Neat solution
Posted by: Robyn Page (view profile)
Posted on: Monday, March 16, 2009 at 5:58 AM
Message: I'm in awe of this solution
http://omnibuzz-sql.blogspot.com/2006/10/calculating-value-of-pi.html

Subject: Notice: no use of Pi() or trigonometric functions like Cos()
Posted by: Emtucifor (view profile)
Posted on: Thursday, March 19, 2009 at 8:30 PM
Message: -- Requires a numbers table, if you don't have one, us this code:
CREATE TABLE Numbers (Num int identity(1,1))
INSERT Numbers DEFAULT VALUES
SET IDENTITY_INSERT Numbers ON
GO
INSERT Numbers (Num) SELECT Num + (SELECT Max(Num) FROM Numbers) FROM Numbers
GO 10
SET IDENTITY_INSERT Numbers OFF
--Now for the solution
;WITH Iter AS (
SELECT i = 1, a = Convert(float, 1), b = 1 / Sqrt(2), t = Convert(float, 1) / 4, p = 1
UNION ALL SELECT i + 1, (a + b) / 2, Sqrt(a * b), t - p * (a - (a + b) / 2) * (a - (a + b) / 2), 2 * p FROM Iter
WHERE i < 4
)
SELECT TOP 1 N1.Num, N2.Num
FROM
Iter
CROSS JOIN Numbers N1
INNER JOIN Numbers N2 ON N1.Num BETWEEN N2.Num * 3 AND N2.Num * 4
WHERE
Iter.i = 4
AND N1.Num < 1000
AND N2.Num < 1000
ORDER BY Abs((a + b) * (a + b) / 4 / t - Convert(float, N1.Num) / N2.Num), N1.Num

-- With special functions that accept and return strings but in fact perform add, subtract, multiply, divide, and square root on arbitrary-length decimal values, this could be extended greatly.

Subject: Winner?
Posted by: Emtucifor (view profile)
Posted on: Thursday, April 16, 2009 at 1:36 PM
Message: So, who's the winner? It's been almost a month.

 










Phil Factor
Automated Script-generation with Powershell and SMO
 In the first of a series of articles on automating the process of building, modifying and copying SQL Server... Read more...



 View the blog
Using SQL Test Database Unit Testing with TeamCity Continuous Integration
 With database applications, the process of test and integration can be frustratingly slow because so... Read more...

SQL Source Control: The Development Story
 Often, there is a huge difference between software being easy to use, and easy to develop. When your... Read more...

How to Import Data from HTML pages
 It turns out that there are plenty of ways to get data into SQL Server from websites, whether the data... Read more...

SQL Scripts Manager: An Appreciation
 SQL Scripts Manager is Simple-Talk's present to its readers. William Brewer was an enthusiastic... Read more...

Hosted Team Foundation Server 2010 Review
 Team Foundation Server (TFS) has expanded its remit to support the whole software development process,... Read more...

Beginning SQL Server 2005 Reporting Services Part 1
 Steve Joubert begins an in-depth tour of SQL Server 2005 Reporting Services with a step-by-step guide... Read more...

Ten Common Database Design Mistakes
 Database design and implementation is the cornerstone of any data centric project (read 99.9% of... Read more...

Reading and Writing Files in SQL Server using T-SQL
 SQL Server provides several "standard" techniques by which to read and write to files but, just... Read more...

Beginning SQL Server 2005 Reporting Services Part 2
 Continuing his in-depth tour of SQL Server 2005 Reporting Services, Steve Joubert demonstrates the most... Read more...

Creating CSV Files Using BCP and Stored Procedures
 Nigel Rivett demonstrates some core techniques for extracting SQL Server data into CSV files, focussing... Read more...

Over 400,000 Microsoft professionals subscribe to the Simple-Talk technical journal. Join today, it's fast, simple, free and secure.

Join Simple Talk