Post date: Apr 12, 2014 2:23:36 PM
"What is the 1000th number in the Fibonacci sequence?"
The main thing that makes this tricky in SQL Server is that the answer is larger than the largest number supported. As far as I have been able to find in my research, the largest number we can represent accurately, as a numeric data type, is numeric(38,0). Floating point numbers can get bigger, but they are approximate. Everything after the 12th significant digit AFAIR is useless. That is no good for us.
But we do have a data type that allows us to represent numbers as large as we want, limited only by memory and time. That is varchar(max). It takes extra work to add two strings together, and it's definitely not remotely efficient, but it can be done. And so I present a few functions that will allow you to, theoretically, calculate Fibonacci numbers as large as you want, limited only by time and memory. Mostly by time, because it's very inefficient.
CREATE FUNCTION dbo.ShiftStringRight
(
@String varchar(max), @Places int
)
RETURNS TABLE
AS RETURN (
SELECT Shift = RIGHT(@String,@Places),
String = REVERSE(STUFF(REVERSE(@String),1,@Places,''))
)
GO
CREATE FUNCTION dbo.AddBigNumbers
(
@Number1 varchar(max), @Number2 varchar(max)
)
RETURNS varchar(max)
AS
BEGIN
/* Add two numbers of arbitrary length that are encoded as strings. */
DECLARE @Right1 varchar(35), @Right2 varchar(35), @Temp numeric(38,0)
DECLARE @CarryOver tinyint = 0, @Result varchar(max) = ''
-- Break the string into segments of 35 digits each and add them.
-- A 35 digit string is small enough to fit into a numeric.
WHILE 1 = 1
BEGIN
-- Shift 35 characters off the numbers into the working segment.
SELECT @Number1 = String, @Right1 = Shift
FROM dbo.ShiftStringRight(RTRIM(LTRIM(@Number1)), 35)
SELECT @Number2 = String, @Right2 = Shift
FROM dbo.ShiftStringRight(RTRIM(LTRIM(@Number2)), 35)
IF ISNULL(@Right1,'') = '' AND ISNULL(@Right2,'') = ''
BREAK
-- Do the math on this segment.
SET @Temp = ISNULL(CONVERT(numeric(38,0),NULLIF(@Right1,'')),0)
+ ISNULL(CONVERT(numeric(38,0),NULLIF(@Right2,'')),0)
+ @CarryOver
-- Get the right 35 characters from the result and add it to the working result.
-- Anything to the left of that is the carryover digit to be added to the next loop.
-- You need to pad the result with zeroes so you don't lose digits if the sum is less than 35 digits.
SELECT @CarryOver = ISNULL(CONVERT(int,NULLIF(String,'')),0), @Result = Shift + @Result
FROM dbo.ShiftStringRight(
RIGHT(REPLICATE('0',36) + CONVERT(varchar(36),@Temp),36)
,35)
END -- While
-- If we have a carry-over digit at the end, then add it to the left.
IF @CarryOver > 0
SET @Result = RTRIM(@CarryOver) + @Result
-- Get rid of the zero padding.
SET @Result = STUFF(@Result, 1, PATINDEX('%[^0]%', @Result) - 1, '')
RETURN @Result
END
GO
CREATE FUNCTION dbo.GetFibonacci
(
@find bigint
)
RETURNS varchar(max)
AS
BEGIN
/* This is a simple non-recursive Fibonacci sequence calculator, except that it uses strings. */
DECLARE @nm2 varchar(max) = 0, @nm1 varchar(max) = 1, @n varchar(max), @c int
IF @find = 0
return 0
IF @find = 1
return 1
SET @c = 2
WHILE 1 = 1
BEGIN
SET @n = dbo.AddBigNumbers(@nm2, @nm1)
SET @c = @c + 1
if @c > @find
BREAK
SET @nm2 = @nm1
SET @nm1 = @n
END -- While
RETURN @n
END
GO
SELECT dbo.GetFibonacci(1000)
This takes between 3 and 4 seconds to return 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875, which matches the result I get in Python.