Post date: Mar 12, 2015 11:56:5 PM
"Find the solutions for the equation x**2 - Dy**2 = 1, where D is a positive integer less than or equal to 1000. Of all these, find the largest value of x."
When I saw this, I thought, 'Yay, a one-query solution after those continued fraction problems I am sick of.' Well, optimization can instantly return half the results, but the other half, NO WAY. Some of the solutions for x for big numbers are 38 digits long. No query is going to quickly hit a table with every number available to SQL Server. So this question ended up beating me up.
Luckily there is a known formula to Pell's equation, which is what this problem is. But then I hit a roadblock: poor documentation and a difficult Google search. Almost all pages on the web say you can start with a continued fraction, *handwave*, and now you have a solution, *mumble.* But there was one page with the algorithm, and the steps involved are simple. I wrote it down. Then I lost the URL of the page, so I couldn't go back and read more about it. But it works so ...
Next problem: Even though the largest answer is only 38 digits, which is just barely enough for SQL Server, this problem involves division. Division requires at least 5 free digits.You cannot divide a 37 or 38 digit number by *1* in SQL Server. In addition, there are a total of two multiplication instances that temporarily require 40 digits within a set of parentheses (which are then divided out). To solve the problem correctly, it's necessary to implement string division (decimal multiplication). GAH!
To do the math with highest speed and cleanliness, only using string division on big numbers, I need to use TRY/CATCH, which means I can't run a UDF on a list of numbers. Zathras has much sadness. It has to be a kind of ugly loop.
CREATE FUNCTION dbo.MultiplyBigNumbers
...
GO
CREATE FUNCTION dbo.ShiftStringRight
...
GO
CREATE FUNCTION dbo.AddBigNumbers
...
GO
-- Here's the first new function.
CREATE FUNCTION dbo.MultiplyBigDecimals(@n1 varchar(max), @n2 varchar(max))
RETURNS varchar(max)
AS
BEGIN
DECLARE @decimal INT = 0, @result varchar(max)
-- Only do something special if n1 has a dot
IF @n1 LIKE '%.%'
BEGIN
--Trim trailing zeros
SET @n1 = REVERSE(@n1)
SET @n1 = STUFF(@n1, 1, PATINDEX('%[^0]%',@n1) - 1, '')
-- If we end in dot, it means the number ended in .0
IF LEFT(@n1,1) = '.'
SET @n1 = REVERSE(STUFF(@n1,1,1,''))
ELSE -- Not .0
BEGIN
-- Count number of decimal places and shift the dot off the end
SET @decimal = CHARINDEX('.',@n1) - 1
SET @n1 = REVERSE(REPLACE(@n1,'.',''))
END -- Not .0
END -- n1 had a dot
-- Only do something special if n2 has a dot
IF @n2 LIKE '%.%'
BEGIN
--Trim trailing zeros
SET @n2 = REVERSE(@n2)
SET @n2 = STUFF(@n2, 1, PATINDEX('%[^0]%',@n2) - 1, '')
-- If we end in dot, it means the number ended in .0
IF LEFT(@n2,1) = '.'
SET @n2 = REVERSE(STUFF(@n2,1,1,''))
ELSE -- Not .0
BEGIN
-- Count number of decimal places and shift the dot off the end
SET @decimal = @decimal + CHARINDEX('.',@n2) - 1
SET @n2 = REVERSE(REPLACE(@n2,'.',''))
END -- Not .0
END -- n2 had a dot
-- Get rid of leading zeroes (from numbers starting with '0.')
SET @n1 = STUFF(@n1, 1, PATINDEX('%[^0]%',@n1) - 1, '')
SET @n2 = STUFF(@n2, 1, PATINDEX('%[^0]%',@n2) - 1, '')
-- Multiply the two numbers, with the decimal place shifted all the way to the right, making them both integers
SET @result = dbo.MultiplyBigNumbers(@n1, @n2)
-- Exit if they weren't decimals.
IF @decimal = 0
RETURN @result
-- If there were decimals, we need to put them back into the result. 0.003 * 0.05 = 0.00015, 5 decimal places.
-- This does mean left padding may be necessary.
IF LEN(@result) <= @decimal
SET @result = RIGHT(REPLICATE('0',@decimal + 1) + @result, @decimal + 1)
SET @result = REVERSE(STUFF(REVERSE(@result),@decimal + 1,0,'.'))
RETURN @result
END
GO
-- These are the possible values. Need to skip perfect squares.
CREATE TABLE #D (d bigint primary key not null)
; WITH Integers(i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 1000
)
INSERT INTO #D
SELECT i
FROM Integers
WHERE i >= 2
AND i <= 1000
AND SQRT(i) <> FLOOR(SQRT(i))
OPTION (MAXRECURSION 1000)
DECLARE @s int = 0
DECLARE @p numeric(38,0), @q numeric(38,0), @x numeric(38,0), @y numeric(38,0), @root float, @result NUMERIC(38,0), @temp VARCHAR(MAX)
CREATE TABLE #Results (d INT primary key not null, x numeric(38,0))
WHILE 1 = 1 BEGIN
-- This could be a cursor. Not in the mood today.
SELECT @s = MIN(d)
FROM #D
WHERE d > @s
-- Solve Pell's equation in the inner loop. Keep going until q is 1. When it is, x is the answer.
SELECT @p = 1, @q = 1, @x = 1, @y = 0, @root = SQRT(@s)
WHILE 1 = 1
BEGIN
-- Find p. Note that step 2 depends on the changes to p in step 1
SET @p = @q * FLOOR(1 + 1.0 * @p/@q) - @p
SET @p = @p - ROUND((@p - @root)/@q,0,1) * @q
-- Find X. This is the biggest number.
BEGIN TRY
SET @result = (@p * @x + @s * @y)/ABS(@q)
END TRY
BEGIN CATCH
-- Multiply/divide with strings if we can't multiply with numeric types
SET @temp =
dbo.MultiplyBigDecimals(
dbo.AddBigNumbers(
dbo.MultiplyBigNumbers(@p, @x),
dbo.MultiplyBigNumbers(@s, @y) ),
1.0/ABS(@q) )
IF @temp LIKE '%.%'
SET @temp = LEFT(@temp,CHARINDEX('.', @temp) -1)
SET @result = @temp
END CATCH
-- Find Y. This is also fairly big.
BEGIN TRY
SET @y = (@p * @y + @x)/ABS(@q)
END TRY
BEGIN CATCH
SET @temp = dbo.MultiplyBigDecimals(
dbo.AddBigNumbers(dbo.MultiplyBigNumbers(@p, @y), @x ),
1.0/ABS(@q) )
IF @temp LIKE '%.%'
SET @temp = LEFT(@temp,CHARINDEX('.', @temp) -1)
SET @y = @temp
END CATCH
-- Find q
SET @q = (@p*@p - @s)/@q
-- Store the current calculated result
SET @x = @result
IF @q = 1 BREAK
END -- inner loop (this would be the end of the UDF, if a UDF could be used.
INSERT INTO #Results VALUES (@s, @result)
DELETE FROM #d WHERE d = @s
IF NOT EXISTS (SELECT 1 FROM #d) BREAK
END -- outer loop (each value in #D)
-- Return the value of d with the highest result.
SELECT TOP 1 d FROM #Results ORDER BY x DESC
DROP TABLE #D
DROP TABLE #Results
GO
DROP FUNCTION dbo.MultiplyBigDecimals
GO
DROP FUNCTION dbo.MultiplyBigNumbers
GO
DROP FUNCTION dbo.AddBigNumbers
GO
DROP FUNCTION dbo.ShiftStringRight
GO