Results 1 to 12 of 12
  1. #1
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912

    Unanswered: Mathematics - algorithm to find greatest exponent for a base

    Hi

    A rather humbling experience for your favourite flump. I have a task that requires finding the greatest exponent a base can be raised by without the result passing a threshold (in this case the maximum BIGINT). I have ended up writing the below simple SQL to generate a table that I can use to look up the exponents.

    However I am sure there must be a better way, ideally one that fits in with the below criteria:

    • The value will be calculated at run time
    • The @base will be a fixed and known BIGINT with a value between 2 and 36
    • The algorithm will not rely on errors to work
    • Ideally it would make use of a numbers table (since this would then integrate nicely in to an inline function I have written)

    Code:
    /*
        Find the greatest exponent of a base that can exist in an 8 byte integer
    */
    SET NOCOUNT ON
    
    DECLARE    @base       AS BIGINT    = 2    --Start with binary
          , @exponent   AS TINYINT   = 62   --We know 62 is the greatest exponent for binary so start with this
          , @pow        AS BIGINT           --Scratch variable
    
    --Table for results
    DECLARE    @powers TABLE 
        (
            base            TINYINT     NULL
          , max_exponent    TINYINT     NULL
        )
    
    --Work through to base 36
    WHILE @base <= 36
    BEGIN
        
        --Use TRY...CATCH as a fudge to identify greatest exponent
        BEGIN TRY
            
            --Attempt to raise base to the exponent
            --Error caught if arithmetic overflow
            SELECT  @pow    = POWER(@base, @exponent)
            
            --If we get here then this is the max exponent - log it
            INSERT INTO @powers
            VALUES  (@base, @exponent)
            
            --Move to next base
            SELECT  @base   += 1
            
        END TRY
        BEGIN CATCH
            
            --Exponent is too high - deduct one and try again
            SELECT  @exponent -= 1
        
        END CATCH
        
    END
    
    SELECT  *
    FROM    @powers

  2. #2
    Join Date
    Jan 2003
    Location
    Massachusetts
    Posts
    5,800
    Provided Answers: 11
    Suppose you take the threshold value (2^64 - 1, but you can reconfigure if you like), and divide by the base. This would become your 'lower threshold", because if you multiply any number above that threshold by the base, you will get an overflow. So all you need is to increase the exponent, until you break the lower threshold. Saves you the catch. As for doing this outside of a while loop, I am not sure.

    Also, POWER seems to return the datatype of the base. You will want to declare that as a bigint.

  3. #3
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Ok, so this works:
    Code:
    DECLARE @base       AS BIGINT    = 36
    
    SELECT  max_exponent        = MAX(number)
    FROM    dbo.numbers
    WHERE   number  <= 62
        AND POWER(CAST(@base AS FLOAT), number) <= CAST(0x7FFFFFFFFFFFFFFF AS BIGINT)
    but isn't really what I had in mind. If the limit changes instead to FLOAT instead of BIGINT then I am back to square one. It is better than the loop though.

  4. #4
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Sorry MCrowley - started writing then got drawn to something else.
    Quote Originally Posted by MCrowley View Post
    Also, POWER seems to return the datatype of the base. You will want to declare that as a bigint.
    Check out the datatype of @base

    Quote Originally Posted by MCrowley View Post
    Suppose you take the threshold value (2^64 - 1, but you can reconfigure if you like), and divide by the base. This would become your 'lower threshold", because if you multiply any number above that threshold by the base, you will get an overflow. So all you need is to increase the exponent, until you break the lower threshold. Saves you the catch. As for doing this outside of a while loop, I am not sure.
    K - I'll play around.

  5. #5
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Shame we only have natural log and log base 10, otherwise I think this would become a trifle easier...
    George
    Home | Blog

  6. #6
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    I'd cheat and use basic mathematics for this one.
    Code:
    --  ptp  20100701  Show maximum exponent for a given base that does not exceed specified limit
    
    DECLARE
       @limit		BIGINT
    ,  @base		BIGINT
    
    SET @limit = 100
    SET @base = 2
    
    SELECT LOG(@limit) / LOG(@base)
    -PatP
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  7. #7
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Yay Pat!

    Code:
    /*
        Find the greatest exponent of a base that can exist in an 8 byte integer
    */
    SET NOCOUNT ON
    
    DECLARE @base       AS BIGINT    = 2    --Start with binary
          , @exponent   AS TINYINT   = 62   --We know 62 is the greatest exponent for binary so start with this
          , @pow        AS BIGINT           --Scratch variable
    
    --Table for results
    DECLARE    @powers TABLE 
        (
            base            TINYINT     NULL
          , max_exponent    TINYINT     NULL
        )
    
    --Work through to base 36
    WHILE @base <= 36
    BEGIN
        
        --Use TRY...CATCH as a fudge to identify greatest exponent
        BEGIN TRY
            
            --Attempt to raise base to the exponent
            --Error caught if arithmetic overflow
            SELECT  @pow    = POWER(@base, @exponent)
            
            --If we get here then this is the max exponent - log it
            INSERT INTO @powers
            VALUES  (@base, @exponent)
            
            --Move to next base
            SELECT  @base   += 1
            
        END TRY
        BEGIN CATCH
            
            --Exponent is too high - deduct one and try again
            SELECT  @exponent -= 1
        
        END CATCH
        
    END
    
    DECLARE
       @limit        BIGINT
    
    SET @limit = CAST(0x7FFFFFFFFFFFFFFF AS BIGINT)
    
    SELECT  *
          , FLOOR(CAST(LOG(@limit) AS DECIMAL(38, 36)) / CAST(LOG(base) AS DECIMAL(38, 36)))
    FROM    @powers
    I had to account for rounding errors on SQL's part (Naughty SQL Server!) but otherwise that got the bugger.

    Many thanks

  8. #8
    Join Date
    Feb 2004
    Location
    One Flump in One Place
    Posts
    14,912
    Quote Originally Posted by gvee View Post
    Shame we only have natural log and log base 10, otherwise I think this would become a trifle easier...
    Yes. A basic grasp of maths helps too it appears.

  9. #9
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Yep, logarithms are very basic
    I wish I could remember half the maths I learnt back in the day -- I should really have know Pat's solution, ah well.
    George
    Home | Blog

  10. #10
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    Quote Originally Posted by gvee View Post
    Shame we only have natural log and log base 10, otherwise I think this would become a trifle easier...
    FWIW, my solution actually computes the log for whatever base is specified. Poots' just needed the integer portion of the log in order to find her limit.

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

  11. #11
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Quote Originally Posted by Pat Phelan View Post
    Poots' just needed the integer portion of the log in order to find her limit.
    Hehe, burn
    George
    Home | Blog

  12. #12
    Join Date
    Jan 2003
    Location
    Massachusetts
    Posts
    5,800
    Provided Answers: 11
    What? Is she that hot?

Posting Permissions

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