Project Euler problem 2 T-SQL

May 26

Euler problem 2: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
This is a sort of running sum problem that used to be hard (before T-SQL in SQL server 2012) I solved it with known math formula and recursion with common table expression. Tomas as usual solved with single-statement magic.

Fibonacci can formula can be calculated by using golden ratio with Binets formula. (cool) .

The drawing of a man's body in a pentagram suggests relationships to the golden ratio

Human body relationship to golden ratio

I define a function to calculate Fibonacci for the term n as: golden ratio raised to n divided with sqr of 5 and the get the closest integer.
Or in T-SQL is:

Create FUNCTION dbo.FiboN (@n int)
RETURNS int
AS
Begin
	DECLARE @phi float; --golden ratio
	SET @phi=(1+ SQRT(5))/2
	DECLARE @f AS float
	SET @f = FLOOR(POWER(@phi,@n)*SQRT(5)/5+0.5	)
	return (@f)
END;

I then use a common table expression in T-SQL to recursively find the sum unfortunately i had to limit to k<45 otherwize it ends with an overflow.

DECLARE	 @int_tbl TABLE  ( k INTEGER) ;
With int_CTE( i ) as
(
Select 1 as j
union all
Select i +1
from int_CTE
where <1000
)
INSERT  INTO @int_tbl
Select i
From int_CTE N
Option (MaxRecursion 0);
WITH fib_serie (n,fibb) AS
(select
 k AS n, dbo.FiboN(k)AS fibb
from @int_tbl d
WHERE   k < 45
AND dbo.FiboN(k)%2=0
AND dbo.FiboN(k) <= 4000000
)
SELECT SUM(fibb)AS ProjectEuler_problem_2 FROM fib_serie;

My colleague Tomas solution do not use any fancy algorithms more the power of sets and SQL Server. I still do not understand how it can work. He starts by using all the columns in the sys tables to get a table with integers and then the magic happens where he can refer to the previous tuple with @current += @previous. I thought that was impossible with sets and T-SQL in 2008 version.

USE master;
GO
DECLARE @current    bigint = 1
      ,@previous   bigint = 0
      ,@temp       bigint = 0
      ,@sum        bigint = 0
      ,@limit      bigint = 4000000;
SELECT TOP 50 @temp     = @current
            ,@current += @previous
            ,@previous = @temp
            ,@sum     += CASE WHEN @current % 2 = 0
                         AND @current < @limit
                         THEN @current ELSE 0 END
FROM sys.all_columns;
SELECT @current AS [current]
       , @previous AS previous
       , @temp AS temp
       , @sum  AS [sum of all even fibonacci numbers below 4M];

5 comments

  1. Jane /

    Jag vill se resultat från Euler 3 + 4 NU!!!
    Gärna med syntax från SQL 2012

  2. Japp jag ska börja med det nästa helg. Lösning kommer. Tomas har redan löst problem 3.

  3. Euler 2

    Lösning och förklaring

    Timing[
    Total[Select[Fibonacci /@
    Range[1, NestWhile[(# + 1) &, 1, Fibonacci[#] <= 4*10^6 &] – 1],
    EvenQ]
    ]]

    {0., 4613732}

    Fibonacci är en färdig funktion i Mathematica. Vilket är lite fuskigt jämfört m Patriks lösning. Några förklaringar- inifrån & ut:
    Fibonacci[n] returnerar det n:te Fibonaccinumret.
    Range[..] skapar en lista med heltal från 1 till det Fibonaccinummer som är mindre än vår gräns, .t.ex. 4 millioner. Övre gränsen för Range bestäms av funktionen NestWhile hjälper till med att hitta övre gränsen på listan med heltal.
    Fibonacci /@ gör om lista av Fibonaccinummer n till tal genom att "mappa" funktionen Fibonacci på listan.
    Select [lista, kriterier], väljer de element ur listan som uppfyller kriterier, ex. att elementen är jämna (görs med inbyggda funktinen EvenQ)
    Total är en inbyggd funktion som summerar alla element i en lista.
    Timing returnerar hur lång tid som datorn behövde på sig. Jag behövde öka till 10^200 för att det skulle ta någon nämnvärd tid, se nedan

    Mathematicakoden blir svår att förstå i detalj om man är obekant med Mathematicas syntax för funktionell programmering (/@, &, etc.). Intuitivt så mappar det dock bra vis a vis problembeskrivningen.

    Timing[
    Total[Select[Fibonacci /@
    Range[1, NestWhile[(# + 1) &, 1, Fibonacci[#] <= 4*10^200 &] – 1],
    EvenQ]
    ]]

    {0.031, 2486536980944494035657517433235891279450308298864884827272294875847635\
    086470138534314038827005946268556581842513530802320498944542073091826135225017\
    39061101416995758180656703597023916782383168918383040}

    • Kul med Mathematica koden ska visa den för annan projektkollega Andreas Broström som är vän av Mathematica. Ja dess kod är intuitivt lätt att förstå. Vad betyder /@ och & ?
      Jag hittade den här Mathematica Tips, Tricks, and Techniques

      Där stod det:
      5 Bells and Whistles. (Advanced)
      5.1 How can I easily apply a function to a whole bunch of argument values?
      To map a function onto a list, you can give the list to the function as its argument (enclosed
      in square brackets).
      Alternatively, you can use the mapping symbol @.

      5.2 What’s a handy, powerful shorthand way to define functions? 8
      Tip Most built-in Mathematica functions act on lists element-by-element. That is, Mathematica typically
      maps functions across lists. Such functions have the Attribute Listable. Ify ou want to give this attribute
      to your own function f, type SetAttributes[f,Listable].
      5.2 What’s a handy, powerful shorthand way to define functions?
      Use anonymous functions.
      To write an anonymous pure function, we use two symbols. Immediately after the function definition,
      use the symbol & to tell Mathematica that whatever preceded this symbol is a pure function. In the body of
      the function, we represent the argument by the symbol #.

      I T-SQL finns inte anonyma funktioner (mig veterligen). Men jag undrar om kan se @ operatorn ungefär som apply och cross apply funktionen i T-SQL. Ska fundera på det.

      • Ja, att sätta sin funktion till “Listable” är en smart möjlighet. Man kan iterera sig fram till något som fungerar för ett element och sedan slippa använda Map[..] .
        /@ är kortformen för Map[f, {..}]:
        Map[f, {a, b, c, d, e}]
        {f[a], f[b], f[c], f[d], f[e]}

        & är korformen för anonyma funktioner som du skriver. Praktiskt att ibland slippa behöva ge funktioner ett namn om man inte känner att de egentligen tillför något.

Leave a Reply

Your email address will not be published.