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

1. King of Understatement
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

, @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. Registered User
Join Date
Jan 2003
Location
Massachusetts
Posts
5,862
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. King of Understatement
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. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
Sorry MCrowley - started writing then got drawn to something else.
Originally Posted by MCrowley
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

Originally Posted by MCrowley
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. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
Shame we only have natural log and log base 10, otherwise I think this would become a trifle easier...

6. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
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

7. King of Understatement
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

, @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. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
Originally Posted by gvee
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. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
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.

10. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
Originally Posted by gvee
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

11. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
Originally Posted by Pat Phelan
Poots' just needed the integer portion of the log in order to find her limit.
Hehe, burn

12. Registered User
Join Date
Jan 2003
Location
Massachusetts
Posts
5,862