Post date: Jun 07, 2014 1:13:11 AM
"Find 100! Then sum up the digits because there are too many to type in."
100 factorial is a lot larger than any SQL Server datatypes, so now it has become time to implement string multiplication. I knew this was coming but I didn't want to do it.
This is implemented like multiplication by hand. So you multiply each "digit," keep track of them, and then, later, add up the results.
234
x21
---
234
468
----
4914
CREATE FUNCTION dbo.MultiplyBigNumbers (@Number1 varchar(max), @Number2 varchar(max))
RETURNS varchar(max)
AS BEGIN
-- We need a lot of working tables for this process.
DECLARE @Reg1 TABLE (id int PRIMARY KEY NOT NULL IDENTITY(1,1), value numeric(18,0) NOT NULL)
DECLARE @Reg2 TABLE (id int PRIMARY KEY NOT NULL IDENTITY(1,1), value numeric(18,0) NOT NULL)
DECLARE @Work TABLE (id int NOT NULL, value numeric(18,0) NOT NULL)
DECLARE @Temp TABLE (id int PRIMARY KEY NOT NULL, value numeric(18,0) NOT NULL)
DECLARE @Result TABLE (id int PRIMARY KEY NOT NULL, value numeric(18,0) NOT NULL)
DECLARE @id int, @value numeric(18,0), @carryover varchar(18), @sum numeric(38,0), @return varchar(max)
-- Anything times 0, blank, or null is 0
IF ISNULL(@Number1,'') = '' OR ISNULL(@Number2,'') = '' OR @Number1 = '0' OR @Number2 = '0'
RETURN '0'
-- Load Reg1 with input 1, broken into 18 digit pieces
WHILE 1 = 1
BEGIN
IF @Number1 = '' BREAK
INSERT INTO @Reg1 (value)
SELECT RIGHT(@Number1,18)
SET @Number1 = REVERSE(STUFF(REVERSE(@Number1),1,18,''))
END
-- Load Reg2 with input 2, broken into 18 digit pieces
WHILE 1 = 1
BEGIN
IF @Number2 = '' BREAK
INSERT INTO @Reg2 (value)
SELECT RIGHT(@Number2,18)
SET @Number2 = REVERSE(STUFF(REVERSE(@Number2),1,18,''))
END
-- Multiply each number in reg 1 by each number in reg 2, adding the right 18 digits of any result to the work table.
-- id in the work place tells us if we are in the first "digit," second, etc.
INSERT INTO @Work (id, value)
SELECT r1.id + r2.id - 1, RIGHT(r1.value * r2.value,18)
FROM @Reg1 r1
CROSS JOIN @Reg2 r2
-- Multiply each number by each number, adding the next 18 digits to work table
; WITH Work (id, value) AS
(
SELECT r1.id + r2.id - 1, RIGHT(REVERSE(STUFF(REVERSE(r1.value * r2.value),1,18,'')),18)
FROM @Reg1 r1
CROSS JOIN @Reg2 r2
)
INSERT INTO @Work (id, value)
SELECT id + 1, value
FROM Work
WHERE value <> ''
-- Multiply each number by each number, adding the carryover digit, if it should exist, to work table
; WITH Work (id, value) AS
(
SELECT r1.id + r2.id - 1, REVERSE(STUFF(REVERSE(r1.value * r2.value),1,36,''))
FROM @Reg1 r1
CROSS JOIN @Reg2 r2
)
INSERT INTO @Work (id, value)
SELECT id + 2, value
FROM Work
WHERE value <> ''
-- Add up the partial results in the work table to get a final result (stored in the result table).
WHILE 1 = 1
BEGIN
-- Pop the first row off.
; WITH Temp AS (SELECT TOP (1) * FROM @Work ORDER BY id)
DELETE FROM Temp
OUTPUT deleted.id, deleted.value
INTO @Temp (id, value)
IF @@ROWCOUNT = 0 BREAK
-- Get the values from that one row, and discard the row. We don't care any more.
SELECT @id = id, @value = value
FROM @Temp
DELETE FROM @Temp
-- Add the value to the current result at that point.
SET @sum = @value
SELECT @sum = value + @sum
FROM @Result
WHERE id = @id
-- Update the result table
-- Insert the record if it doesn't exist yet.
-- This would be a good place for MERGE, but that has known issues with variable tables, which this is.
UPDATE @Result
SET value = RIGHT(@sum,18)
WHERE id = @id
IF @@ROWCOUNT = 0
INSERT INTO @Result (id, value)
SELECT @id, RIGHT(@sum,18)
-- Check to see if there are any carryover digits
-- If there is a carryover, then add it to the work table one level up.
SET @carryover = REVERSE(STUFF(REVERSE(@sum),1,18,''))
IF @carryover <> ''
INSERT INTO @Work (id, value)
SELECT @id + 1, @carryover
END -- While records in work table
-- Join all the numbers in the result table together in a single string.
SET @return = (SELECT RIGHT('000000000000000000' + CONVERT(varchar(18),value),18) FROM @Result ORDER BY id DESC FOR XML PATH(''),TYPE).value('text()[1]','nvarchar(max)')
-- Drop leading zeros
RETURN STUFF(@return,1,PATINDEX('%[^0]%',@return) - 1,'')
END
GO
-- Calculate the factorial
DECLARE @i int = 2
DECLARE @Result varchar(max) = '1'
WHILE 1 = 1
BEGIN
SET @Result = dbo.MultiplyBigNumbers(@Result, @i)
SET @i = @i + 1
IF @i > 100 BREAK
END -- While
-- Add up the digits in the answer
CREATE TABLE #Temp(i INT NOT NULL)
WHILE 1 = 1
BEGIN
INSERT INTO #Temp
SELECT LEFT(@Result,1)
WHERE LEN(@Result) > 0
SET @Result = STUFF(@Result,1,1,'')
IF @Result = '' BREAK
END -- While
SELECT SUM(i)
FROM #Temp
GO
DROP FUNCTION dbo.MultiplyBigNumbers
GO