Results 1 to 13 of 13
  1. #1
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54

    Unanswered: Prime factors using T-SQL

    I had to work out a prime factors routine to solve another problem, and used T-SQL 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
    -PatP
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  2. #2
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    I'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.

    -PatP
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  3. #3
    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.

  4. #4
    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

  5. #5
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    Sorry. 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

  6. #6
    Join Date
    Dec 2007
    Location
    Richmond, VA
    Posts
    1,328
    Provided Answers: 5
    Hey 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

  7. #7
    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 script
    Code:
    SELECT * INTO tabby FROM tabbyWabby WHERE 1^21=17

  8. #8
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Lightbulb 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
    Result:

    Number.... Prime Factorization of number
    2010....... 1 * 2 * 3 * 5 * 67
    Lenny

    P.S. Thanks for dav1mo for his remembering

  9. #9
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    I'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)
    -PatP
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  10. #10
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Thumbs up DB2 made EASY

    Quote Originally Posted by Pat Phelan View Post
    I'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)
    -PatP
    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
    Result:

    Number.............................. Prime Factorization of number
    277945762500....... 1 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5 * 5 * 5 * 7 * 7 * 7 * 7 * 7 * 7 * 7
    The next query I changed in your way:

    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
    And we got the result:

    Number......... Prime Factor......... Factor Power
    277945762500
    .......................... 2........................... 2
    .......................... 3........................... 3
    .......................... 5........................... 5
    .......................... 7........................... 7
    With respect, Lenny
    Last edited by Lenny77; 06-16-10 at 18:21.

  11. #11
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    I 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 10-17 digit numbers being factored on both tables using a 4 Gb laptop, and the performance shocked me.

    -PatP
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  12. #12
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Arrow

    Quote Originally Posted by Pat Phelan View Post
    I 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 10-17 digit numbers being factored on both tables using a 4 Gb laptop, and the performance shocked me.

    -PatP
    I'm agree with you:
    "In theory, theory and practice are identical. In practice, theory and practice are unrelated"....

    Lenny

  13. #13
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Thumbs up 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
    And we got the same result:

    Number......... Prime Factor......... Factor Power
    277945762500
    .......................... 2........................... 2
    .......................... 3........................... 3
    .......................... 5........................... 5
    .......................... 7........................... 7
    With respect, Lenny
    Last edited by Lenny77; 06-17-10 at 19:02.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •