Post date: Sep 04, 2016 1:10:51 PM
Long time no see
"Sum the first 100 decimal digits of all the integers from 1 to 100 that have irrational square roots."
A simple but annoying problem for T-SQL code. This is one that would have been loads easier using the Python service I made a while ago. A square root to 100 digits (not decimal places, and not rounded) is beyond what SQL Server can do easily.
In researching this and trying to find a way to solve it without doing big decimal division, I stumbled upon a method by Frazer Jarvis using only repeated addition and subtraction. In Wikipedia, this looks similar the floating point approximation method, with the operations multiplied by 10, which makes it much nicer for my purposes. Aside from that, it's simpler than the other methods I looked at. It's definitely not fast but it's straightforward. I do have to make a SubtractBigNumbers function, though.
This method gives you only the digits, not the position of the decimal place, but in this case we don't care.
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.SubtractBigNumbers
(
@Number1 varchar(max), @Number2 varchar(max)
)
RETURNS varchar(max)
AS
BEGIN
/* Subtract two positive integers of arbitrary length that are encoded as strings. */
-- If the second number is bigger, the answer is negative.
-- The value of the number is the same as the subtraction of the reverse (multiply -1 times both sides)
-- This is a bit tricky, because these are strings, and alpha order isn't the same as numeric. The length affects the result.
IF LEN(@Number1) < LEN(@Number2)
RETURN '-' + dbo.SubtractBigNumbers(@Number2, @Number1)
IF LEN(@Number1) = LEN(@Number2) AND @Number1 < @Number2
RETURN '-' + dbo.SubtractBigNumbers(@Number2, @Number1)
DECLARE @Right1 varchar(35), @Right2 varchar(35), @Temp numeric(38,0)
DECLARE @Carry numeric(38,0) = 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)
- @Carry
SET @Carry = 0
IF @Temp < 0
BEGIN
SET @Carry = 1
SET @Temp = @Temp + CONVERT(numeric(38,0),'1' + REPLICATE('0',35)) -- (Save myself some typing)
END
-- Append it to the the working result. Pad it with zeros to keep it a static length.
SELECT @Result = RIGHT(REPLICATE('0',35) + RTRIM(@Temp),35) + @Result
END -- While
-- If we have a carry digit at the end, the result is negative
-- This shouldn't happen. It should have been caught at the beginning. It is an error.
IF @Carry > 0
RETURN NULL
-- Get rid of the zero padding.
SET @Result = STUFF(@Result, 1, PATINDEX('%[^0]%', @Result) - 1, '')
IF @Result IS NULL
RETURN 0
RETURN @Result
END
GO
/* Finally we get to actually solve the problem. This takes less code than the bits before, which just cover for SQL Server's lack of handling for gigantic numbers. */
CREATE FUNCTION dbo.GetIrrationalSquareRootDigits
(
@Number int, @Digits int
)
RETURNS varchar(max)
AS
BEGIN
/* This returns the square root of a number to a certain number of digits.
Only use it for irrationals, because it is an approximation. If you give it 9, for example, it will get closer and closer to 3 over time. But never exactly. */
DECLARE @temp varchar(max) = 5 * @Number
DECLARE @result varchar(max) = 5
WHILE LEN(@result) <= @Digits
BEGIN
-- This is a bit tricky, because these are strings, and alpha order isnt the same as numeric.
IF LEN(@temp) > LEN(@result)
OR (LEN(@temp) = LEN(@result) AND @temp > @result)
SELECT @temp = dbo.SubtractBigNumbers(@temp, @result),
@result = dbo.AddBigNumbers(@result, '10')
ELSE
SELECT @temp = @temp + '00',
@result = REVERSE(STUFF(REVERSE(@result),1,1,'50'))
END -- Loop
RETURN @result
END
GO
CREATE FUNCTION dbo.SumDigits (@Number varchar(max))
RETURNS bigint
AS
BEGIN
IF @Number IS NULL RETURN NULL
DECLARE @answer bigint
DECLARE @SumDigits TABLE (i INT NOT NULL)
WHILE @Number <> ''
BEGIN
INSERT INTO @SumDigits
SELECT LEFT(@Number,1)
SET @Number = STUFF(@Number,1,1,'')
END
SELECT @answer = SUM(i)
FROM @SumDigits
RETURN @answer
END
GO
-- This answer depends on the nice easy float approximation of a square root that SQL Server gives us to determine if the root is irrational.
-- They didn't say we couldn't use it.
WITH Hundred (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Hundred
WHERE i < 99
),
Irrational (i) AS
(
SELECT i
FROM Hundred
WHERE SQRT(i) <> FLOOR(SQRT(i))
)
SELECT SUM(dbo.SumDigits(LEFT(dbo.GetIrrationalSquareRootDigits(i,110),100)))
FROM Irrational
GO
DROP FUNCTION dbo.SubtractBigNumbers
GO
DROP FUNCTION dbo.AddBigNumbers
GO
DROP FUNCTION dbo.ShiftStringRight
GO
DROP FUNCTION dbo.GetIrrationalSquareRootDigits
GO
DROP FUNCTION dbo.SumDigits
GO