Results 1 to 13 of 13
Thread: Prime factors using TSQL

061610, 01:37 #1Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
Provided Answers: 54Unanswered: Prime factors using TSQL
I had to work out a prime factors routine to solve another problem, and used TSQL because it is what I had handy at the moment. I was surprised at how efficient it was and thought I'd throw the code sample out for others to play with and improve.
Code:DECLARE @d1 DATETIME  Dummy var used to compute ms of runtime , @i BIGINT  Working accumulator , @v BIGINT  Working divisor SET @d1 = GETDATE()  Store begin of run DECLARE @t TABLE (v BIGINT)  Table to hold factors SET @i = 1234567890  Set initial value WHILE 0 = @i % 2  Factor out twos first BEGIN INSERT @t VALUES (2)  Store factor SET @i = @i / 2  Reduce accumulator END SET @v = 3  Check all odd numbers WHILE @v * @v < @i  While divisor less than sqr of accumulator BEGIN WHILE 0 = @i % @v  Test for even divisibility BEGIN INSERT @t VALUES (@v) SET @i = @i / @v  Reduce accumulator END SET @v = 2 + @v  Skip to next divisor END INSERT @t VALUES (@i)  Remainder is last prime factor SELECT DATEDIFF(ms, @d1, GetDate())  Computations are done SELECT v, COUNT(*) FROM @t GROUP BY v SET @i = 1  Prove our work SELECT @i = @i * v FROM @t SELECT @i  Must be initial value
In theory, theory and practice are identical. In practice, theory and practice are unrelated.

061610, 10:43 #2Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
Provided Answers: 54I'm kind of bummed, I'd hoped for some discussion.... This was an interesting issue for me because I normally solve this kind of problem in middleware instead of at the database, but for this particular problem that would have made the overall code execution take too long.
FWIW, I left more than one "discussion starter" in the code. I figured if nothing else that would have attracted the Flump.
PatPIn theory, theory and practice are identical. In practice, theory and practice are unrelated.

061610, 10:54 #3King of Understatement
 Join Date
 Feb 2004
 Location
 One Flump in One Place
 Posts
 14,912
To catch a fish such code is fitting. To catch a flump  why you only need call his name.

061610, 10:58 #4King of Understatement
 Join Date
 Feb 2004
 Location
 One Flump in One Place
 Posts
 14,912
Ok  the one thing that struck me when I first read it was why you insert 2 (a constant) many times in a loop. I don't understand why you insert a hard coded value, nor why in a loop instead of a set. Don't tell me know  I am indulging you by studying your code in more depth

061610, 10:58 #5World Class Flame Warrior
 Join Date
 Jun 2003
 Location
 Ohio
 Posts
 12,592
Provided Answers: 1Sorry. I have no time for mssqlbation today....
If it's not practically useful, then it's practically useless.
blindman
www.chess.com: "sqlblindman"
www.LobsterShot.blogspot.com

061610, 11:02 #6Registered User
 Join Date
 Dec 2007
 Location
 Richmond, VA
 Posts
 1,328
Provided Answers: 5Hey Pat,
I did some advertising for you on the DB2 side of the forum. As there is a guy over there who loves this kind of stuff. He has a sudoku solver over there that he posts about.
Dave

061610, 11:03 #7King of Understatement
 Join Date
 Feb 2004
 Location
 One Flump in One Place
 Posts
 14,912
Oh for Chrissake. You've included code just for the mischievousness of it.
Very unprofessional  I would never dream of such a thing.
Well, apart from yesterday in a QAD archiving scriptCode:SELECT * INTO tabby FROM tabbyWabby WHERE 1^21=17

061610, 13:05 #8Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
How it's simple in DB2
Code:with number (number) as (select int(2010) from sysibm.sysdummy1 ) , factors(fact) as (select 2 from sysibm.sysdummy1 union all select fact + 1 from factors, number where fact + 1 <= number ) , Prime_Factorization (in_number, remd, Prime_Factorization) as (select number, number, varchar('1', 1000) from number union all select in_number, int(remd / fact), Prime_Factorization  ' * '  varchar(fact) from Prime_Factorization, factors where mod(remd, fact) = 0 and remd > 1 and fact = (select min(fact) from factors where mod(remd, fact) = 0 ) ) select in_number "Number", Prime_Factorization "Prime Factorization of number" from Prime_Factorization where remd = 1
Number.... Prime Factorization of number
2010....... 1 * 2 * 3 * 5 * 67
P.S. Thanks for dav1mo for his remembering

061610, 15:03 #9Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
Provided Answers: 54I'm pretty sure that Lenny's DB2 solution will determine which prime numbers are factors of the argument, but not how many times they are factors of it. Consdier the following output as an example:
Code: 0 (1 row(s) affected) v   2 2 3 3 5 5 7 7 (4 row(s) affected)  277945762500 (1 row(s) affected)
In theory, theory and practice are identical. In practice, theory and practice are unrelated.

061610, 17:16 #10Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
DB2 made EASY
This one is much easier than you are thinking about:
1. Original, which I changed from INTEGER to DECIMAL:
Code:with number (number) as (select decimal(277945762500, 15, 0) from sysibm.sysdummy1 ) , factors(fact) as (select decimal(2, 15, 0) from sysibm.sysdummy1 union all select fact + 1 from factors, number where fact + 1 <= sqrt(2 * number) union all select number from number ) , Prime_Factorization (in_number, remd, Prime_Factorization) as (select number, number, varchar('1', 1000) from number union all select in_number, decimal(remd / fact, 15, 0), Prime_Factorization  ' * '  strip(varchar(fact), t, '.') from Prime_Factorization, factors where mod(remd, fact) = 0 and remd > 1 and fact = (select min(fact) from factors where mod(remd, fact) = 0 ) ) select in_number "Number", Prime_Factorization "Prime Factorization of number" from Prime_Factorization where remd = 1
Number.............................. Prime Factorization of number
277945762500....... 1 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5 * 5 * 5 * 7 * 7 * 7 * 7 * 7 * 7 * 7
Code:with number (number) as (select decimal(277945762500, 15, 0) from sysibm.sysdummy1 ) , factors(fact) as (select decimal(2, 15, 0) from sysibm.sysdummy1 union all select fact + 1 from factors, number where fact + 1 <= sqrt(2 * number) union all select number from number ) , Prime_Factorization (in_number, remd, fact) as (select number, number, 1 from number union all select in_number, decimal(pf.remd / f1.fact, 15, 0), f1.fact from Prime_Factorization pf, factors f1 where mod(pf.remd, f1.fact) = 0 and pf.remd > 1 and f1.fact = (select min(f2.fact) from factors f2 where mod(pf.remd, fact) = 0 ) ) select distinct in_number "Number", nullif(0, 0) "Prime Factor", nullif(0, 0) "Factor Power" from Prime_Factorization union all select nullif(0, 0) "Number", fact "Prime Factor", count(*) "Factor Power" from Prime_Factorization where fact > 1 group by fact
Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7Last edited by Lenny77; 061610 at 17:21.

061610, 17:55 #11Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
Provided Answers: 54I was concerned the the original solution would simply determine that the argument was divisible by a prime (such as 2), but not the power of 2. I was mistaken.
Unfortunately I don't have a current version of DB2 to test code and concepts... I'm supporting zOS DB2 v7.1 and that is all that I've got access to at the moment. I'm accustomed to later versions of DB2, and the client now has an upgrade project in place so hopefully I'll be able to play with my old toys (DB2 8.x and possibly 9.x) again soon!
I'm just curious, but what kind of run times are you getting and what kind of hardware are you using to get those runtimes? I'm processing JOINS that rely on the results of a revised version of my code that are handling over 2500 rows per second with 1017 digit numbers being factored on both tables using a 4 Gb laptop, and the performance shocked me.
PatPIn theory, theory and practice are identical. In practice, theory and practice are unrelated.

061610, 18:08 #12Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963

061710, 16:16 #13Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
From Theory to Practice
Yesterday my query worked for more than 45 second...
It was the theory of programming  Idea.
Today I modified the query to get result in 1 second.
This is a practice of programming  Optimization.
Optimized query:
Code:with number (number) as (select decimal(277945762500, 15, 0) from sysibm.sysdummy1 ) , fact1(fact) as ( select decimal(3, 15, 0) from sysibm.sysdummy1 union all select fact + 2 from fact1, number where fact + 2 <= sqrt(number) + 1 ) , factors(fact) as ( select 2 from sysibm.sysdummy1 union all select * from fact1 ) , Prime_Factorization (in_number, remd, fact) as (select number, number, 1 from number union all select in_number, decimal(pf.remd / coalesce(f1.fact, pf.remd) , 15, 0), coalesce(f1.fact, pf.remd) from Prime_Factorization pf, table (select min(f2.fact) fact from factors f2 where mod(pf.remd, f2.fact) = 0 and f2.fact <= sqrt(pf.remd) + 1 ) f1 where pf.remd > 1 ) select distinct in_number "Number", nullif(0, 0) "Prime Factor", nullif(0, 0) "Factor Power" from Prime_Factorization union all select nullif(0, 0) "Number", fact "Prime Factor", count(*) "Factor Power" from Prime_Factorization where fact > 1 group by fact
Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7Last edited by Lenny77; 061710 at 18:02.